I've been recently dealing with the classical problem of finding the minimum vertex cover in a bipartite graph. The common approach is to set direction to all edges and run DFS from all vertices of the left part outside of the matching. However, this solution seems too clever for me.
I read this in this link. Can any body explain it to me with simple example. https://codeforces.com/blog/entry/63164
" 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, xi = 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 and , while w is not saturated by M, we have to set xi 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. "
what I dont understand is this
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 two edges in the maximum matching.
For the first edge I took left vertex in the cover
x1=0(according to the blog in the link)
for the second edge I took right vertex in the cover x2=1
How final 2-sat will be true?
Can anyone explain what will be the relation between x1 and x2 ?
