Behdad Esfahbod's daily notes on GNOME, Pango, Fedora, Persian Computing, Bob Dylan, and Dan Bern! Name:
Contact info Saturday, February 18, 2006
Chinese Feast

Yesterday, it was the grad visit day in the CS department where candidates for next year grad students where visiting. I was part of the theory group team of it, chatting with them over snacks, and we (the theory group) went out for dinner in a Chinese restaurant in China town when the Database and Graphics groups were partying in Karan Singh's place.

The food was a real treat though. We tried more than ten dishes, every single one of them could make a delicious dinner in itself.

A cute (and easy) problem somebody dropped on the table: Find a polynomial-time algorithm to find a subset of the nodes in a simple graph, that is both a minimum vertex cover, and a maximum independent set, or determine that no such set exists. (Yes, it's maximum/minimum, not maximal/minimal. Yes, both min-vertex-cover and max-independent-set problems are NP-hard.)

Ok, only Ryan wrote to me about the solution. Anyway, here is the solution:

Let n be the number of vertices in the graph, and let S be the solution set, if one exists.

First, note that for each edge, at least one of the ends should be in S (cause S is a vertex cover), and not two of them are in S (cause S is an independent set). So, if S exists, the graph should be two-colorable. i.e., it's bipartite.

Second, for every graph, |max-independent-set| = n - |min-vertex-cover|. So, if S exists, |S| = n - |S| or |S| = n / 2.

Third, for every bipartite graph, |min-vertex-cover| = |max-matching|. This is a widely known result, or you can work it out yourself, but it's a bit nontrivial at first (unless you think about incremental paths.) So, if S exists, |S| = |max-matching|.

From the three paragraphs above, we deduce that if S exists, the graph should be bipartite and have a matching of size n / 2. In other words: the problem has a solution only for bipartite graphs with perfect matching. If we have such a graph on the other hand, any of the two parts is indeed both a max-independent-set and min-vertex-cover, and so a solution.