Optimal data reduction for graph coloring using low-degree polynomials

DOI10.4230/LIPICS.IPEC.2017.22MaRDI QIDQ5111881zbMATH OpenOpenAlexFDO

Authors 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Optimal data reduction for graph coloring using low-degree polynomials
• Data reduction for graph coloring problems
• Data reduction for graph coloring problems
• A (2 + ) k-vertex kernel for the dual coloring problem
• Graph-Theoretic Concepts in Computer Science

Cites work

• Data reduction for graph coloring problems
• Fine-grained parameterized complexity analysis of graph coloring problems
• Fundamentals of parameterized complexity
• Kernelization of packing problems
• Optimal sparsification for some binary CSPs using low-degree polynomials
• Parameterized algorithms
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Sparsification upper and lower bounds for graph problems and not-all-equal SAT

Cited in

(8)

• Constraint and satisfiability reasoning for graph coloring
• Optimal data reduction for graph coloring using low-degree polynomials
• Sparsification lower bounds for list \(H\)-coloring
• Data reduction for graph coloring problems
• Data reduction for graph coloring problems
• Best-case and worst-case sparsifiability of Boolean CSPs
• Polynomial-time data reduction for weighted problems beyond additive goal functions
• Best-case and worst-case sparsifiability of Boolean CSPs

This page was built for publication: Optimal data reduction for graph coloring using low-degree polynomials

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