1
$\begingroup$

I stumbled upon some problem in my understanding of the complexity classes FPT and XP. According to Wikipedia (and the Book "Parameterized Algorithms") we know the following about the Vertex Cover and Vertex Coloring problem:

A vertex cover of size $k$ in a graph of order $n$ can be found in time $O(2^{k}n)$, so this problem is in FPT.

An example of a problem that is thought not to be in FPT is graph coloring parameterized by the number of colors. It is known that 3-coloring is NP-hard, and an algorithm for graph $k$-coloring in time $O(f(k)n^{O(1)})$ for $k=3$ would run in polynomial time in the size of the input. Thus, if graph coloring parameterized by the number of colors were in FPT, then $P = NP$.

According to this answer from a different question it is also true that Vertex coloring isn't even contained in $XP$ (unless $P = NP$).

since $3$-coloring (which is NP-complete) would be solvable in $O(n^{f(3)})=O(n^c)$ time, thus rendering it polynomially solvable.

While each statement above makes perfect sense on its own the combination of all three seems odd to me, as we know that Vertex Cover is considered NP-complete just like Vertex Coloring is.

What I don't get is: As far as my understanding goes I could argue as above that for a fixed $k$ (say $k=3$) in a vertex cover instance we could achieve a linear runtime, namely $O(2^3n)=O(n)$. Which would show $P=NP$, just as it is argued in Vertex Coloring.

And again since $O(n^{f(3)})=O(n^c)$ it wouldn't even be in $XP$. Thus Vertex Cover should not be contained in $FPT$ or $XP$.

Since Vertex Cover clearly is in FPT: What am I getting wrong here?

$\endgroup$
4
  • $\begingroup$ An algorithm for vertex cover running in time $O(2^kn)$ isn't a polynomial time algorithm, since the input size is $O(n^2 + \log k)$; in fact, it is not even exponential time! $\endgroup$ Nov 8 at 11:24
  • $\begingroup$ I don't understand what you don't get. Can you give a statement which you think you can prove, but contradicts another statement which you think you can prove? Also supply the proofs. $\endgroup$ Nov 8 at 11:25
  • $\begingroup$ According to this book on page 6 we get a $O(2^knk)$ algorithm for vertex cover (which is great since its an FPT algorithm). On page 7 the "negative example" vertex coloring is mentioned. As stated on page 8 we get: Given a graph $G$, we can decide whether G has proper $5$-coloring in time $f(5)n$ [if we assumed for that vertex coloring admits an FPT algorithm]. But then we have a polynomial time algorithm for an NP-hard problem, implying $P = NP$. Looking back to V. cover couldn't I argue with the same argument that the $O(2^knk)$ algorithm would imply $P=NP$ for some fixed $k$ $\endgroup$
    – Felix
    Nov 8 at 11:34
  • $\begingroup$ This is the book i mentioned above: mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf $\endgroup$
    – Felix
    Nov 8 at 11:34
2
$\begingroup$

What you are probably missing is that vertex coloring is hard already when $k=3$, i.e., the number of colors is not part of the input but fixed. In contrast, for vertex cover, the size of the cover $k$ is part of the input.

$\endgroup$
2
  • $\begingroup$ So for a fixed $k$ ($k$ not part of the input) vertex coloring is $NP$-complete, but vertex cover isn't? $\endgroup$
    – Felix
    Nov 8 at 11:50
  • $\begingroup$ @Felix That seems to be the case. When $k$ is fixed, you can use the $2^k$-algorithm for VC to solve it efficiently. No such algorithm is known for 3-COL (and the existence of such an algorithm would give us P=NP). $\endgroup$
    – Juho
    Nov 8 at 11:53

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.