Data reduction for graph coloring problems
From MaRDI portal
Publication:3088272
DOI10.1007/978-3-642-22953-4_8zbMATH Open1342.68167arXiv1104.4229OpenAlexW2962964261MaRDI QIDQ3088272FDOQ3088272
Authors: Bart M. P. Jansen, Stefan Kratsch 
Publication date: 19 August 2011
Published in: Fundamentals of Computation Theory (Search for Journal in Brave)
Abstract: This paper studies the kernelization complexity of graph coloring problems with respect to certain structural parameterizations of the input instances. We are interested in how well polynomial-time data reduction can provably shrink instances of coloring problems, in terms of the chosen parameter. It is well known that deciding 3-colorability is already NP-complete, hence parameterizing by the requested number of colors is not fruitful. Instead, we pick up on a research thread initiated by Cai (DAM, 2003) who studied coloring problems parameterized by the modification distance of the input graph to a graph class on which coloring is polynomial-time solvable; for example parameterizing by the number k of vertex-deletions needed to make the graph chordal. We obtain various upper and lower bounds for kernels of such parameterizations of q-Coloring, complementing Cai's study of the time complexity with respect to these parameters. Our results show that the existence of polynomial kernels for q-Coloring parameterized by the vertex-deletion distance to a graph class F is strongly related to the existence of a function f(q) which bounds the number of vertices which are needed to preserve the NO-answer to an instance of q-List-Coloring on F.
Full work available at URL: https://arxiv.org/abs/1104.4229
Recommendations
Cites Work
- Graph Classes: A Survey
- On problems without polynomial kernels
- Graph colorings with local constraints -- a survey
- Parameterized complexity of vertex colouring
- Intractability of clique-width parameterizations
- Some consequences of non-uniform conditions on uniform classes
- Parameterized coloring problems on chordal graphs
- Cross-composition: a new technique for kernelization lower bounds
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover
- Graph-Theoretic Concepts in Computer Science
- On the complexity of some colorful problems parameterized by treewidth
- The complexity ecology of parameters: An illustration using bounded max leaf number
- Axioms and hulls
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Scheduling with incompatible jobs
- Edge dominating set and colorings on graphs with fixed clique-width
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (17)
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- Optimal data reduction for graph coloring using low-degree polynomials
- Data Reduction for Maximum Matching on Real-World Graphs
- On the hardness of losing width
- Graph-Theoretic Concepts in Computer Science
- Optimal data reduction for graph coloring using low-degree polynomials
- On the hardness of losing width
- On the pseudo-achromatic number problem
- Kernelization -- preprocessing with a guarantee
- Open problems on graph coloring for special graph classes
- Reducing graph coloring to clique search
- Data reduction for graph coloring problems
- Parameterized complexity of vertex colouring
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- On cutwidth parameterized by vertex cover
- On cutwidth parameterized by vertex cover
- On the Pseudo-achromatic Number Problem
This page was built for publication: Data reduction for graph coloring problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088272)
