Finer Tight Bounds for Coloring on Clique-Width

DOI10.1137/19M1280326zbMath1462.68143arXiv1804.07975MaRDI QIDQ5130905

Michael Lampis

Publication date: 29 October 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

coloringclique-widthSETH

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Between treewidth and clique-width
• Model counting for CNF formulas of bounded modular treewidth
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Zero knowledge and the chromatic number
• Which problems have strongly exponential complexity?
• Algorithmic meta-theorems for restrictions of treewidth
• Edge dominating set and colorings on graphs with fixed clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Parametrized complexity theory.
• Approximating clique-width and branch-width
• Parameterized Compilation Lower Bounds for Restricted CNF-Formulas
• Parameterized Algorithms for Modular-Width
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• Intractability of Clique-Width Parameterizations
• Clique-Width is NP-Complete
• Faster Algorithms on Branch and Clique Decompositions
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
• Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth
• Optimal dynamic program for r-domination problems over tree decompositions
• On Problems as Hard as CNF-SAT
• Tight Lower Bounds for the Complexity of Multicoloring
• Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms
• On the complexity of \(k\)-SAT

This page was built for publication: Finer Tight Bounds for Coloring on Clique-Width