VRTXCOVR - Editorial

2-sat
acm17chn
chn17rol
graphs
medium

#1

PROBLEM LINK:

Practice

Contest

Author: Triveni Maratha

Tester: Misha Chorniy

Editorialist: Animesh Fatehpuria

PROBLEM

Given an undirected graph, compute a vertex cover such that nodes 2i and 2i - 1 are on different sides of the vertex cover.

QUICK EXPLANATION

Formulate the constraints as 2-SAT clauses and run the 2-SAT algorithm.

EXPLANATION

It is a prerequisite for this problem to be familiar with the linear time 2-SAT algorithm. In fact, even if you don’t know the details about how it works, being familiar with its applications (and having book-code) is sufficient to solve this problem.

We interpret each node in the graph as a variable. Let x_i denote the variable for node number i. We’ll let A comprise the set of nodes that have x_i = 1 in any assignment. We encode the constraints as follows:

  • An edge (u, v) corresponds to the simple clause x_u \lor x_v. This means at least one of x_u and x_v will exist in A and thus every edge will be covered.
  • Nodes 2i and 2i - 1 should be in different sets. Here, we note that the structure of 2-SAT is rich enough to support XOR clauses, i.e. ensure that two variables x_i and x_j have different values in an assignment. What we want to do here is add the clause x_{2i} \oplus x_{2i - 1} which is equivalent to (x_{2i} \lor x_{2i - 1}) \land ( eg x_{2i} \lor eg x_{2i - 1}).

That’s all we need to reduce the problem to 2-SAT. Clearly, we’ll have O(n + m) clauses and since 2-SAT runs in linear time our whole algorithm is O(n + m).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.