We know that graph coloring is NP-complete even in some special graph classes. On the other hand if someone tells you the exact value of the chromatic number of the input graph, is this problem remains NP-complete. In other words I am wondering if there are any result for the search version of the coloring problem (possibly on different graph classes).
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
Knowing the exact value of the chromatic number $\chi$ cannot help by more than a factor of $n$. Since there are only $n$ possible values of $\chi$, you can 'guess' its value, i.e., run processes $P_1,\dots,P_n$, where $P_i$ runs an algorithm assuming $\chi=i$. This whole scheme can find an optimum colouring in time at most $n$ times the time that it takes $P_\chi$ to find an optimum colouring.
On the other hand, if you're talking about parameterizing the running time by $\chi$, then it's a much more interesting question. It's in FPT if you parameterize by $n-\chi$ S. Khot and V. Raman, ‘Parameterized Complexity of Finding Subgraphs with Hereditary properties’. If you parameterize by $\chi$ I would assume it's W[1]-hard.
-
1$\begingroup$ Similar argument: if there exists a polynomial-time (deterministic) algorithm, then it can detect in polynomial time if it has been fooled, that is if the input graph really admits a $k$-coloration. Then we can solve the decision problem in polynomial time, and in particular decides if a graph admits a $3$-coloration (which is NP-complete). $\endgroup$ Commented Jan 19, 2011 at 19:29
-
$\begingroup$ And by similar arguments, I think that when parameterized by $\chi$, the problem is paraNP-complete (above the parameterized W hierarchy), as it is already NP-complete for $\chi = 3$. $\endgroup$ Commented Jan 19, 2011 at 19:33
$\begingroup$
$\endgroup$
2
Actually, Guruswami et al. proved in [1] that it is NP-complete to find a 4-coloring of a 3-colorable graph, even on bounded-degree graphs.
This result, initially proven in [2] (but without the bounded-degree condition), implies that it is NP-hard to color a $k$-colorable graph with at most $k + 2\lfloor k/3 \rfloor - 1$ colors.
[1] V. Guruswami, S. Khanna. On the hardness of 4-coloring a 3-colorable graph. In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity (2000). http://dx.doi.org/10.1109/CCC.2000.856749
[2] S. Khanna, N. Linial, S. Safra. On the hardness of approximating the chromatic number. Combinatorica 20(3) (2000). http://dx.doi.org/10.1007/s004930070013
-
$\begingroup$ Could you point me to (or explain briefly) the $k + 2 \left \lfloor k/3 \right \rfloor -1$ implication? $\endgroup$ Commented May 18, 2013 at 21:00
-
$\begingroup$ I found it in the second paper, section 4.4 corollary 1, proof omitted. Is it that obvious and I'm just not seeing it? $\endgroup$ Commented May 18, 2013 at 23:11
$\begingroup$
$\endgroup$
The result of Khuller and Vazirani shows that finding the lexicographically first four-coloring for planar graphs is $NP$-hard.
answered Jan 19, 2011 at 18:00