PROBLEM LINK:
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 (\neg x_{2i} \lor \neg 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.