6 papers · 1 filter
Sparsification Lower Bounds for List -Coloring
Hubie Chen, Bart M. P. Jansen, Karolina Okrasa +2
We investigate the List -Coloring problem, the generalization of graph coloring that asks whether an input graph admits a homomorphism to the undirected graph (possibly…
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
The Vertex Cover problem plays an essential role in the study of polynomial kernelization in parameterized complexity, i.e., the study of provable and efficient preprocessing for N…
Parameterized Complexity of Conflict-free Graph Coloring
Hans L. Bodlaender, Sudeshna Kolay, Astrid Pieterse
Given a graph G, a q-open neighborhood conflict-free coloring or q-ONCF-coloring is a vertex coloring such that for each vertex t…
Best-case and Worst-case Sparsifiability of Boolean CSPs
Hubie Chen, Bart M. P. Jansen, Astrid Pieterse
We continue the investigation of polynomial-time sparsification for NP-complete Boolean Constraint Satisfaction Problems (CSPs). The goal in sparsification is to reduce the number…
Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations
Bart M. P. Jansen, Astrid Pieterse
We investigate polynomial-time preprocessing for the problem of hitting forbidden minors in a graph, using the framework of kernelization. For a fixed finite set of connected graph…
Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials
Bart M. P. Jansen, Astrid Pieterse
The theory of kernelization can be used to rigorously analyze data reduction for graph coloring problems. Here, the aim is to reduce a q-Coloring input to an equivalent but smaller…