An old question, a new approach

In a graph, say that a vertex v covers an edge e if v is adjacent to e. VERTEX COVER, one of the original 6 NP-Complete problems, asks if you can find a set of vertices of minimum size that cover all edges in the graph (for purists, the decision problem is to check, for a given G, and value B, if there is a vertex cover of size at most B).

One of the most obvious attacks on this problem is to use a greedy approach. Pick the vertex of highest degree, and remove all the adjacent edges. Repeat this till all edges have been removed. Clearly the set of vertices picked form a cover. But how good is this ?

The answer is, 'not very good', and one of the first homework problems in a graduate class on algorithms is to show why, by coming up with a counter-example. There are some standard (but not trivial) constructions that can be used, and you can amuse yourself with thinking about this.

However, this is not the point of this post. Amit Chakrabarti is teaching an graduate algorithms class up in Dartmouth, and Khanh Do Ba, a junior taking the class, came up with an ingenious solution that I at least had not heard of before. I will not tell you the solution just yet, but I will give you the hint that Amit gave me when he told me about it: the student used Gronwall's Theorem.

Happy pondering. Tune in tomorrow for the answer.

Tags: VertexCover, algorithms, numbertheory