Fine-grained parameterized complexity analysis of graph coloring problems
Journal article, Peer reviewed
Published version
![Thumbnail](/bora-xmlui/bitstream/handle/11250/3119635/1-s2.0-S0166218X22004346-main.pdf.jpg?sequence=6&isAllowed=y)
Åpne
Permanent lenke
https://hdl.handle.net/11250/3119635Utgivelsesdato
2023Metadata
Vis full innførselSamlinger
- Department of Informatics [978]
- Registrations from Cristin [10237]
Sammendrag
The q-Coloring problem asks whether the vertices of a graph can be properly colored with q colors. In this paper we perform a fine-grained analysis of the complexity of q- Coloring with respect to a hierarchy of structural parameters. We show that unless the Exponential Time Hypothesis fails, there is no constant θ such that q-Coloring parameterized by the size k of a vertex cover can be solved in O∗(θk) time for all fixed q. We prove that there are O∗((q − ε)k) time algorithms where k is the vertex deletion distance to several graph classes for which q-Coloring is known to be solvable in polynomial time, including all graph classes F whose (q + 1)-colorable members have bounded treedepth. In contrast, we prove that if F is the class of paths – some of the simplest graphs of unbounded treedepth – then no such algorithm can exist unless the Strong Exponential Time Hypothesis fails.