Behdad Esfahbod's daily notes on GNOME, Pango, Fedora, Persian Computing, Bob Dylan, and Dan Bern!

My Photo
Location: Toronto, Ontario, Canada

Ask Google.

Contact info
Hacker Emblem Become a Friend of GNOME I Power Blogger
follow me on Twitter
July 2003
August 2003
October 2003
November 2003
December 2003
March 2004
April 2004
May 2004
July 2004
August 2004
September 2004
November 2004
March 2005
April 2005
May 2005
June 2005
July 2005
August 2005
September 2005
October 2005
November 2005
December 2005
January 2006
February 2006
March 2006
April 2006
May 2006
June 2006
July 2006
August 2006
September 2006
October 2006
November 2006
December 2006
January 2007
February 2007
March 2007
April 2007
May 2007
June 2007
July 2007
August 2007
September 2007
October 2007
November 2007
December 2007
January 2008
February 2008
March 2008
April 2008
May 2008
June 2008
July 2008
August 2008
October 2008
November 2008
December 2008
January 2009
March 2009
April 2009
May 2009
June 2009
July 2009
August 2009
November 2009
December 2009
March 2010
April 2010
May 2010
June 2010
July 2010
October 2010
November 2010
April 2011
May 2011
August 2011
September 2011
October 2011
November 2011
November 2012
June 2013
January 2014
May 2015
Current Posts
McEs, A Hacker Life
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.
Post a Comment

<< Archive
<< Home