Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials

DOI10.4230/LIPIcs.IPEC.2017.22zbMath1443.68132OpenAlexW2963300845MaRDI QIDQ5111881

Bart M. P. Jansen, Astrid Pieterse

Publication date: 27 May 2020

Full work available at URL: https://doi.org/10.4230/LIPIcs.IPEC.2017.22

zbMATH Keywords

graph coloringsparsificationkernelization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (4)

Unnamed Item ⋮ Unnamed Item ⋮ Constraint and Satisfiability Reasoning for Graph Coloring ⋮ Best-case and worst-case sparsifiability of Boolean CSPs

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• Data reduction for graph coloring problems
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• Sparsification upper and lower bounds for graph problems and not-all-equal SAT
• Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials
• Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• Parameterized Algorithms

This page was built for publication: Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials