Fine-grained parameterized complexity analysis of graph coloring problems

DOI10.1007/978-3-319-57586-5_29zbMATH Open1486.68083arXiv1701.06985OpenAlexW2580171847MaRDI QIDQ5283380FDOQ5283380

Bart M. P. Jansen, Lars Jaffke

Publication date: 21 July 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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 $mathcal{O}^{*}((q-varepsilon{)}^k)$, for any $varepsilon>0$, unless the Strong Exponential-Time Hypothesis (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 even when parameterized by the vertex cover number, $q$ must appear in the base of the exponent: Unless ETH fails, there is no universal constant $heta$ such that $q$-Coloring parameterized by vertex cover can be solved in time $mathcal{O}^{*}(het{a}^k)$ for all fixed $q$. We apply a method due to Jansen and Kratsch [Inform. & Comput. 2013] to prove that there are $mathcal{O}^{*}((q-varepsilon{)}^k)$ time algorithms where $k$ is the vertex deletion distance to several graph classes $mathcalF$ for which $q$-Coloring is known to be solvable in polynomial time. We generalize earlier ad-hoc results by showing that if $mathcalF$ is a class of graphs whose $(q+1)$-colorable members have bounded treedepth, then there exists some $varepsilon>0$ such that $q$-Coloring can be solved in time $mathcal{O}^{*}((q-varepsilon{)}^k)$ when parameterized by the size of a given modulator to $mathcalF$. In contrast, we prove that if $mathcalF$ is the class of paths - some of the simplest graphs of unbounded treedepth - then no such algorithm can exist unless SETH fails.

Full work available at URL: https://arxiv.org/abs/1701.06985

Recommendations

• Finer tight bounds for coloring on clique-width
• Finer tight bounds for coloring on clique-width
• Data reduction for graph coloring problems
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Fundamentals of parameterized complexity
• Which problems have strongly exponential complexity?
• Parameterized Algorithms
• On the complexity of \(k\)-SAT
• Set Partitioning via Inclusion-Exclusion
• Parameterized complexity of vertex colouring
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Data reduction for graph coloring problems
• Title not available (Why is that?)
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems

Cited In (19)

• Parameterized (Approximate) Defective Coloring
• Optimal data reduction for graph coloring using low-degree polynomials
• Computing the chromatic number using graph decompositions via matrix rank
• Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
• Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
• Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover
• Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
• Worst case analysis of a graph coloring algorithm
• Title not available (Why is that?)
• Digraph coloring and distance to acyclicity
• Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials
• List-coloring -- parameterizing from triviality
• Title not available (Why is that?)
• Finer Tight Bounds for Coloring on Clique-Width
• Title not available (Why is that?)
• Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
• Structural parameterizations of clique coloring
• Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
• Title not available (Why is that?)

This page was built for publication: Fine-grained parameterized complexity analysis of graph coloring problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283380)