Lesson 4

The bipartiteness condition in Kőnig–Egerváry theorem is essential: in general, the problem of finding a minimum vertex cover is NP-hard, while the problem of finding a maximum matching is solvable in polynomial time. At the same time, the weak duality \(\alpha'(G) \le \beta(G)\) allows a very simple 2-approximation algorithm for the vertex cover problem.

The algorithm is very simple. Start with an empty set \(C\). While the graph still has edges, repeat the following: take any edge \(\{u,v\}\), remove vertices \(u,v\) from the graph (along with all their edges, of course) and add \(u,v\) to \(C\).

It's easy to see that the constructed set \(C\) is a cover. It turns out it always exceeds the optimal vertex cover \(C'\) by at most a factor of two. Indeed, the edges \(\{u,v\}\) selected by our algorithm form a matching \(M\). Then \[|C|=2|M| \le 2|C'|\ ,\] since the size of any vertex cover is at least the size of any matching.

Let's note an important detail of this simple proof. Suppose we are given a graph \(G\) of huge size. As we discussed above, finding a minimum vertex cover in such a graph quickly is unlikely. So, we don't know the value of \(\beta(G)\). But how then were we able to prove above that the size of the vertex cover given by our simple algorithm is at most \(2\beta(G)\)? If we look closely at the proof, it becomes clear that we were able to do this because we have a lower bound on \(\beta(G)\) (\(\beta(G) \ge |M|\)), which we can easily compute.