Timeline for Complexity difference of Vertex cover and Vertex coloring regarding parametrized algorithms
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 11, 2021 at 10:08 | vote | accept | Felix | ||
| Nov 8, 2021 at 11:53 | comment | added | Juho | @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). | |
| Nov 8, 2021 at 11:50 | comment | added | Felix | So for a fixed $k$ ($k$ not part of the input) vertex coloring is $NP$-complete, but vertex cover isn't? | |
| Nov 8, 2021 at 11:43 | history | answered | Juho | CC BY-SA 4.0 |