Fine-grained parameterized complexity analysis of graph coloring problems

L. Jaffke , B.M.P. Jansen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

13 Citations (Scopus)

Abstract

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”.
Original languageEnglish
Title of host publicationAlgorithms and Complexity
Subtitle of host publication10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings
EditorsD. Fotakis, A. Pagourtzis, V.T. Paschos
Place of PublicationDordrecht
PublisherSpringer
Chapter29
Pages345-356
Number of pages12
ISBN (Electronic)978-3-319-57586-5
ISBN (Print)978-3-319-57585-8
DOIs
Publication statusPublished - 2017
Event10th International Conference on Algorithms and Complexity, CIAC 2017 - Athens, Greece
Duration: 24 May 201726 May 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10236 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Conference on Algorithms and Complexity, CIAC 2017
Abbreviated titleCIAC 2017
CountryGreece
CityAthens
Period24/05/1726/05/17

Fingerprint Dive into the research topics of 'Fine-grained parameterized complexity analysis of graph coloring problems'. Together they form a unique fingerprint.

Cite this