TY - GEN

T1 - Fine-grained parameterized complexity analysis of graph coloring problems

AU - Jaffke , L.

AU - Jansen, B.M.P.

PY - 2017

Y1 - 2017

N2 - The q-Coloring problem asks whether the vertices of a graph can be properly colored with q colors. Lokshtanov et al. [SODA 2011] showed that q-Coloring on graphs with a feedback vertex set of size k cannot be solved in time O ∗ ((q−ε) k )
O∗((q−ε)k)
, for any ε>0
ε>0
, unless the Strong Exponential-Time Hypothesis (SETH
SETH
) fails. In this paper we perform a fine-grained analysis of the complexity of q-Coloring with respect to a hierarchy of parameters. We show that unless ETH
ETH
fails, there is no universal constant θ
θ
such that q-Coloring parameterized by vertex cover can be solved in time O ∗ (θ k )
O∗(θk)
for all fixed q. We prove that there are O ∗ ((q−ε) k )
O∗((q−ε)k)
time algorithms where k is the vertex deletion distance to several graph classes F
F
for which q-Coloring is known to be solvable in polynomial time, including all graph classes whose (q+1)
(q+1)
-colorable members have bounded treedepth. In contrast, we prove that if F
F
is the class of paths – some of the simplest graphs of unbounded treedepth – then no such algorithm can exist unless SETH
SETH
fails.
This research was partially funded by the Networks programme via the Dutch Ministry of Education, Culture and Science through the Netherlands Organisation for Scientific Research. The research was done while the first author was at CWI, Amsterdam. The second author was supported by NWO Veni grant “Frontiers in Parameterized Preprocessing”.

AB - The q-Coloring problem asks whether the vertices of a graph can be properly colored with q colors. Lokshtanov et al. [SODA 2011] showed that q-Coloring on graphs with a feedback vertex set of size k cannot be solved in time O ∗ ((q−ε) k )
O∗((q−ε)k)
, for any ε>0
ε>0
, unless the Strong Exponential-Time Hypothesis (SETH
SETH
) fails. In this paper we perform a fine-grained analysis of the complexity of q-Coloring with respect to a hierarchy of parameters. We show that unless ETH
ETH
fails, there is no universal constant θ
θ
such that q-Coloring parameterized by vertex cover can be solved in time O ∗ (θ k )
O∗(θk)
for all fixed q. We prove that there are O ∗ ((q−ε) k )
O∗((q−ε)k)
time algorithms where k is the vertex deletion distance to several graph classes F
F
for which q-Coloring is known to be solvable in polynomial time, including all graph classes whose (q+1)
(q+1)
-colorable members have bounded treedepth. In contrast, we prove that if F
F
is the class of paths – some of the simplest graphs of unbounded treedepth – then no such algorithm can exist unless SETH
SETH
fails.
This research was partially funded by the Networks programme via the Dutch Ministry of Education, Culture and Science through the Netherlands Organisation for Scientific Research. The research was done while the first author was at CWI, Amsterdam. The second author was supported by NWO Veni grant “Frontiers in Parameterized Preprocessing”.

UR - http://www.scopus.com/inward/record.url?scp=85018418260&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-57586-5_29

DO - 10.1007/978-3-319-57586-5_29

M3 - Conference contribution

SN - 978-3-319-57585-8

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 345

EP - 356

BT - Algorithms and Complexity

A2 - Fotakis, D.

A2 - Pagourtzis, A.

A2 - Paschos, V.T.

PB - Springer

CY - Dordrecht

T2 - 10th International Conference on Algorithms and Complexity, CIAC 2017

Y2 - 24 May 2017 through 26 May 2017

ER -