Optimal data reduction for graph coloring using low-degree polynomials
From MaRDI portal
Publication:2272594
DOI10.1007/s00453-019-00578-5zbMath1430.68128arXiv1802.02050OpenAlexW2942681663MaRDI QIDQ2272594
Bart M. P. Jansen, Astrid Pieterse
Publication date: 10 September 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1802.02050
Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies, Computing L(p,1)-Labeling with Combined Parameters, Unnamed Item, Computing \(L(p, 1)\)-labeling with combined parameters, Parameterized Complexity of Conflict-Free Graph Coloring
Cites Work
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Data reduction for graph coloring problems
- List H-coloring a graph by removing few vertices
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- On the complexity of H-coloring
- Efficient graph representations
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials
- Point Line Cover
- Kernelization Lower Bounds by Cross-Composition
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs
- Smaller Parameters for Vertex Cover Kernelization
- Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
