Vertex cover of bipartite graph

Question

A vertex cover is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. A minimum vertex cover is a vertex cover with minimal cardinality.

From codeforces,

The minimum vertex cover should contain exactly one vertex for every edge in the maximum matching $M$. So let's assign a boolean variable for every edge in $M$, say, $x_i = 0$ if the $i$-th edge adds its left end to the vertex cover. One can build all the dependencies over these variables. For example, if there exist edges $(u,v) \in M$ and $(u,w) \notin M$, while $w$ is not saturated by $M$, we have to set $x_i$ equal to 0, because there is no other way to cover the edge $(u, w)$. All the other cases are handled trivially.

As a result, we obtain a full system of restrictions for the set of variables. Finding an arbitrary valid assignment is a classical 2-SAT problem. So we have basically reduced the minimum vertex cover problem to 2-SAT without thinking too much.

I don't understand the variables. I have an edge from maximum matching then I might have both the endpoints of that edge in the vertex cover. But this scheme does not allow this.

This is the graph I have ($2K_2$) two edges in the maximum matching:

For the first edge I took left vertex in the cover $x_1=0$ (according to the blog in the link) for the second edge I took right vertex in the cover $x_2=1$.

Questions:

1. How final 2-sat will be true?
2. Can anyone explain what will be the relation between $x_1$ and $x_2$?

Answer 1

As that link explains, you have one variable per edge in the maximum matching, call it $x_i$ for the $i$th edge. If $x_i=0$, we'll choose the left endpoint of that edge to be in the vertex cover; if $x_i=1$, we'll add the right endpoint of that edge to the vertex cover.

Now, we need to make sure that all of the vertices are covered. Iterate over each edge $(u,w)$ that's not in the matching:

• If $u$ is touched by the matching but $w$ is not touched by the matching, then the only way to achieve a valid vertex cover from this matching is to include $u$ in the vertex cover. So, we need to find the edge $(u,v)$ in the matching, then set the corresponding variable $x_i$ to 0 (to ensure $u$ is selected, not $v$).

• If $u$ is not touched by the matching but $w$ is touched, then do the reverse of the above.

• If neither of $u$ nor $w$ is touched by the matching -- this can't happen in a maximum matching (because you could add the edge $(u,w)$ and get a larger matching). So, you can ignore this case.

• If both $u$ and $w$ are touched by the matching, then we need to ensure that either $u$ or $w$ is selected. This can be enforced with a 2-CNF clause. In particular, let $x_i$ be the variable for the edge that touches $u$, and let $x_j$ be the variable for the edge that touches $w$. If $u$ is the left endpoint for $x_i$ and $w$ is the right endpoint for $x_j$, we add the 2-CNF clause $\neg x_i \lor x_j$; this ensures that either $u$ or $w$ are selected (or possibly both).

So, combine all the 2-CNF clauses you get in this way, and you get a 2-CNF formula, i.e., a 2-SAT instance. Solving the 2-SAT instance tells you how to pick a set of vertices that will be a vertex cover. Once you have an assignment that satisfies the 2-SAT instance, that corresponds to a consistent way to choose vertices; and you can verify that this set of vertices forms a vertex cover.

Answer 2

I don't understand the variables. I have an edge from maximum matching then I might have both the endpoints of that edge in the vertex cover. But this scheme does not allow this.

In bipartite graphs, the size of a maximum matching is also the size of the minimum vertex cover. Since every vertex cover must contain at least one vertex from each edge in the matching, it follows that it has to contain exactly one vertex from each edge in the matching.