Fine-grained parameterized complexity analysis of graph coloring problems

DOI10.1007/978-3-319-57586-5_29MaRDI QIDQ5283380zbMATH OpenOpenAlexFDO

Authors Lars Jaffke, Bart M. P. Jansen

Publication date 21 July 2017

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

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

Mathematics Subject Classification ID

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

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}^{\ast }((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}^{\ast }(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}^{\ast }((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}^{\ast }((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.

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

Cites work

• scientific article; zbMATH DE number 6783432 (Why is no real title available?)
• Data reduction for graph coloring problems
• Fine-grained parameterized complexity analysis of graph coloring problems
• Fundamentals of parameterized complexity
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• On the complexity of k-SAT
• Parameterized algorithms
• Parameterized complexity of vertex colouring
• Set partitioning via inclusion-exclusion
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Which problems have strongly exponential complexity?

Cited in

(27)

• Fine-grained parameterized complexity analysis of graph coloring problems
• Towards exact structural thresholds for parameterized complexity
• Optimal data reduction for graph coloring using low-degree polynomials
• Finer tight bounds for coloring on clique-width
• Finer tight bounds for coloring on clique-width
• On the tractability of \((k,i)\)-coloring
• Optimal data reduction for graph coloring using low-degree polynomials
• Digraph coloring and distance to acyclicity
• Sparsification lower bounds for list H-coloring
• Computing the chromatic number using graph decompositions via matrix rank
• Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
• Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover
• Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
• Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
• Fine-grained parameterized complexity analysis of graph coloring problems
• Sparsification lower bounds for list \(H\)-coloring
• Worst case analysis of a graph coloring algorithm
• scientific article; zbMATH DE number 7764100 (Why is no real title available?)
• Parameterized (approximate) defective coloring
• Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth
• Digraph coloring and distance to acyclicity
• Breaking the 2ⁿ barrier for 5-coloring and 6-coloring
• List-coloring -- parameterizing from triviality
• Fundamental problems on bounded-treewidth graphs: the real source of hardness
• scientific article; zbMATH DE number 7559420 (Why is no real title available?)
• Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
• Structural parameterizations of clique coloring

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)