Tuesday, March 08, 2005

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


  1. Is the vertex cover problem equivalent to the Traveling Salesman Problem with the vertices replaced by edges?

    What is the difference between a vertex cover V and a minimum vertex cover M? Can one find subsets M of V? 

    Posted by Rafael

  2. Am not sure what you mean by that. If you replace vertices by edges, what are "vertices" in this new graph. Also, I am not sure what you mean by equivalent. These ar e both NP-hard, so there is a reduction from one to the other; apart from that they are quite different.

    A minimum vertex cover is a vertex cover of smallest cardinality.  

    Posted by Suresh

  3. Sorry about that Suresh. I was thinking of something like a dual or inverse but it isn't. 

    Posted by Rafael


Disqus for The Geomblog