19
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ there is a sense in which computation of either one is apparently tightly coupled, see the lovasz sandwich thm etc $\endgroup$ – vzn Apr 3 '12 at 23:46
21
$\begingroup$

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.

$\endgroup$
  • 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$ – David Eppstein Apr 4 '12 at 21:22
22
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Are you sure about circle graphs? The wiki page says "the chromatic number of a circle graph may be arbitrarily large, and determining the chromatic number of a circle graph is NP-complete." $\endgroup$ – Ankur Apr 4 '12 at 0:12
  • $\begingroup$ Oops, got it backwards. Will fix. $\endgroup$ – David Eppstein Apr 4 '12 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$ – Ankur Apr 4 '12 at 15:31
11
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ Another interesting example for the opposite property is the class of well-covered graphs (see here and here). For them, Coloring is hard but Independent Set is trivially easy. $\endgroup$ – vb le Mar 15 '13 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.