1
$\begingroup$

Found this from graphclasses.org.

Two papers give conflicting results for coloring $P_5$-free graphs which appear to imply $P=NP$.

From Polynomial-time algorithm for vertex k-colorability of P_5-free graphs

Abstract. We give the first polynomial-time algorithm for coloring vertices of P5 -free graphs with k colors. This settles an open problem and generalizes several previously known results.

From Some new hereditary classes where graph coloring remains NP-hard, p 5

... Coloring is NP-hard in $2K_2$-free ... and $\{C_5,P_5\} \cup \ldots$-free

$2K_2-free \subset P_5-free$ and the other class contains $P_5$.

According to graphclasses, another reason for hardness is clique cover on the complement (another paper), click +Details for references.

Question:

What is wrong with this seeming contradiction?

$\endgroup$
  • 5
    $\begingroup$ The first paper shows that there exists a function $f$ such that it can be decided if a $P_5$-free graph can be $k$-colored in time $O(n^{f(k)})$. This means that for each fixed $k$, the problem can be solved in polynomial time in $n$. This is an interesting result since the trivial algorithm would use $O(k^n)$ time. However, the result does not give a polynomial time algorithm for CHROMATIC NUMBER of $P_5$-free graphs, since $\sum_{k=1..n} n^{f(k)}$ is not polynomial in $n$. That CHROMATIC NUMBER is NP-hard for $P_5$-free graphs is even mentioned in (the conference version of) the paper. $\endgroup$ – JWM Jul 10 '15 at 11:24
3
$\begingroup$

One of those papers is about k-colorability and the other of
those papers does not specify a constant number of colors.

(For a similar example, consider k-variable-SAT versus SAT.)

$\endgroup$
  • $\begingroup$ Thank you, but I don't understand. The second paper defines on p.1 "MCP: Find in G = (V , E) a minimum number k of stable sets S1 , . . . , Sk , which cover V (i.e. S1 ∪ · · · ∪ Sk = V ). This minimum number is the chromatic number chi(G) of G.. The quoted result hardness of MCP. In the first paper $k$ is given, so binary search will find minimum $k$. What is wrong with this? According to graphclasses $k$-colorability is NP-hard. $\endgroup$ – joro Jul 10 '15 at 8:04
  • $\begingroup$ "In the first paper $k$" determines which of [3-coloring,4-coloring,5-coloring,6-coloring,7-coloring,...] is the current problem. $\;$ $\endgroup$ – user6973 Jul 10 '15 at 8:24
  • $\begingroup$ Yes, but this is enough. We know $k \le n$. Try $k=2,3,4,...n$ and stop if you find coloring. Each call is polynomial in $n$ and there are at most $n$ calls, which is polynomial in $n$. $\endgroup$ – joro Jul 10 '15 at 8:26
  • $\begingroup$ Each call being polynomial in $n$ is not enough for their sum to be polynomial in $n$. $\:$ (Consider (n^2)+(n^3)+(n^4)+...+(n^(n-1)).) $\;\;\;\;$ $\endgroup$ – user6973 Jul 10 '15 at 8:30
  • 4
    $\begingroup$ Max clique is Np-complete. But 2-clique is polynomial time solvable (in $n^2$ time). And we can do 3-clique in $n^3$ time. In fact, for ever fixed k we can solve k-clique in $n^k$ time. But this still doesnt imply P=NP $\endgroup$ – daniello Jul 10 '15 at 20:00

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.