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

Archives

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

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

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.)

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.)

Comments:

Links to this post:

<< Archive

<< Home

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
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.

Links to this post:

<< Archive

<< Home