The answer...

Here's the answer to yesterday's question:

It becomes clear fairly quickly once you start playing with examples that the thing to do is create some kind of bipartite graph, where the left side is the "bad answer" and the right side is the "good answer". Since picking all the vertices on a side is a valid cover, and you have to pick all of at least one side, it is clear that the smaller side is the optimal solution. So the goal is to make an example with more nodes on the left than on the right, and force the algorithm to pick something from the left each time (if you could direct the edges, to force picking from one side, then it would be easier, but then you've just created a SET COVER instance).

The catch is that just by averaging, if the left side has more nodes than the right, then it seems that the nodes on the right should have higher degree and should be picked first. How does one avoid this ? This is where the "trick" is used. Gronwall's theorem bounds the sum of the number of divisors of n. Roughly, the sum of the divisors of n behaves like n ln ln n as n goes to infinity. So here's the construction:

Let 1 = d₁ < d₂ < ... < d_k = n be the divisors of n. Create n nodes on the right side. For each i, create d_i nodes on the left side. Of these d_i nodes, connect the first to the first n/d_i nodes on the right, and the second to the next n/d_i, and so on. There are (asymptotically) n ln ln n nodes on the left side. The maximum degree on the left side is n/d₁ (= d_k!), and the maximum degree on the right side is k, since each node on the right connects to only one node in each group on the left. It is easy to check that d_k is always greater than k, so the algorithm always picks the first node from the left side. Repeat, use induction, clean your hands, and voila! you end up picking n ln ln n nodes instead of n: a ln ln n approximation gap.

This is not the best solution possible. With a bit more work based on this solution alone you can go up to c ln n. I'll leave that as an exercise ;).

Tags: VertexCover, algorithms, numbertheory