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?

Improve this question
$\endgroup$
1
  • 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, 2015 at 11:24

1 Answer 1

Reset to default
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.)

Improve this answer
$\endgroup$
14
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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