irkstepanov's blog

By irkstepanov, history, 5 years ago, In English

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, 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.

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(n2), where n is the number of variables, since we need to run n independent DFS's. One can optimize this to O(n2 / 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?

  • Vote: I like it
  • +84
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

With the original idea it's easy to find both vertices that have to be in vertex cover and can be in vertex cover:

You start with vertices not in matching. They have to be in matching. Ones that are connected to them can't be in matching, their pairs in matching have to be in matching. continue dfs this way. Not visited vertices are all in matching and all can be in vertex cover (you may choose any of two in each pair)

»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

bonus solution: vertex can be in vertex cover iff it has to be in vertex cover or if it's pair in matching doesn't have to be in vertex cover

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it
  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +28 Vote: I do not like it

    There was task which contains your task as subtask on this Moscow workshop. I guess Ilya used this idea in his solution. And solution which was on analysis is different from this. So, post is interesting :)