Is there an example of a class of graphs for which the vertex coloring problem is in P but the independent set is problem is NP complete?
1
-
1$\begingroup$ there is a sense in which computation of either one is apparently tightly coupled, see the lovasz sandwich thm etc $\endgroup$– vznCommented Apr 3, 2012 at 23:46
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
A perhaps more general statement (with an easy proof) is that the following problem is already NP-complete:
Input: A graph G, a 3-coloring of G, an integer k.
Question: Does G have an independent set of size k?
This can be proven by a reduction from Independent Set. Observe that if we take a graph G, pick some edge, and subdivide it twice (i.e. replace edge {u,v} by a path u,x,y,v where x and y have degree two) then the independence number of G increases by exactly one. (You can add exactly one of x or y to any set which was independent in G, and the reverse is not difficult either.) So the question if graph G with m edges has an independent set of size k, is equivalent to the question whether G', which is the result of subdividing all edges in G twice, has an independent set of size k + m. But note that it is easy to get a 3-coloring of G', by partitioning G' into three independent sets as follows: one contains the vertices which were also in G, and the other two classes each contain exactly one of the two "subdivider" vertices for each edge. Hence this procedure constructs a graph G' with a 3-coloring of it, such that computing its independence number gives you the independence number of the original graph G.
-
4$\begingroup$ This reduction also immediately proves the hardness of independent set in triangle-free planar graphs, from my answer, without reference to difficult-to-obtain papers. $\endgroup$ Commented Apr 4, 2012 at 21:22
$\begingroup$
$\endgroup$
3
Supposedly the reference "NP-complete problems on a 3-connected cubic planar graph and their applications" by Uehara (a paper I haven't actually seen) proves that independent set is NP-complete even for triangle-free planar graphs. But by Grötzsch's theorem they are always 3-colorable, and testing for smaller numbers of colors than 3 is easy in any graph, so they can be optimally colored in P.
Circle graphs have the opposite property: for them, coloring is NP complete but the independent set problem is easy.
answered Apr 3, 2012 at 21:04
-
2
-
$\begingroup$ Oops, got it backwards. Will fix. $\endgroup$ Commented Apr 4, 2012 at 1:01
-
$\begingroup$ Thanks. It would be great to get other examples. The paper by Uehara seems somewhat isolated; there are not too many other papers citing it. I am not even sure if it has been peer reviewed and published. $\endgroup$– AnkurCommented Apr 4, 2012 at 15:31
$\begingroup$
$\endgroup$
1
This is not a new answer but rather a clarification the first and easy-to-obtain reference for hardness of INDEPENDENT SET in triangle-free cubic planar graphs: The note by Owen Murphy, Computing independent sets in graphs with large girth, Discrete Applied Mathematics 35 (1992) 167-170 proves that
INDEPENDENT SET is NP-complete for cubic planar $n$-vertex graphs of girth at least $cn^k$ for any given constants $c>0$ and $k, 0\le k < 1$.
(In particular, INDEPENDEN SET is NP-complete for cubic planar graphs without cycles of length less than $c$ for any constant $c>0$)
The reduction indicated by @BartJansen is a special case in Murphy's proof of his theorem.
For the opposite property, line graphs seem to be more natural than circle graphs as addressed by @DavidEppstein. For line graphs, COLOURING is NP-complete but INDEPENDENT SET is easy.
-
6