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.
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$.
- How final 2-sat will be true?
- Can anyone explain what will be the relation between $x_1$ and $x_2$?