Hiya!

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.

A more natural thing is to do the following. Clearly, 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 and , 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.

An interesting application of this idea is a way to find all vertices that must lie in the optimal vertex cover. In terms of 2-SAT, we just want to find out for every variable whether its value is the same for any valid assignment. Clearly, if x is reachable from not-x, then x has to be 1. One can also show that in case when neither x nor not-x is reachable from one another, the value of x can be set arbitrarily.

A downside of this method is that in works in O(n²), where n is the number of variables, since we need to run n independent DFS's. One can optimize this to O(n² / 32) by compressing strongly connected components and run DFS on DAG with bitsets. However, if the maximum matching is not given beforehand, we don't lose in terms of time complexity, as we first need to find M itself.

Hope this idea will be helpful one day (it was for me).

Bonus: can this idea be applied for determining for every vertex whether is can belong to some optimal vertex cover?