Timeline for Complexity difference of Vertex cover and Vertex coloring regarding parametrized algorithms
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 11, 2021 at 10:08 | vote | accept | Felix | ||
| Nov 8, 2021 at 19:17 | history | became hot network question | |||
| Nov 8, 2021 at 11:43 | answer | added | Juho | timeline score: 2 | |
| Nov 8, 2021 at 11:34 | comment | added | Felix | This is the book i mentioned above: mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf | |
| Nov 8, 2021 at 11:34 | comment | added | Felix | 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$ | |
| Nov 8, 2021 at 11:25 | comment | added | Yuval Filmus | 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. | |
| Nov 8, 2021 at 11:24 | comment | added | Yuval Filmus | 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! | |
| Nov 8, 2021 at 11:15 | history | asked | Felix | CC BY-SA 4.0 |