7 papers
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…
Approximate Turing Kernelization for Problems Parameterized by Treewidth
Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
We extend the notion of lossy kernelization, introduced by Lokshtanov et al. [STOC 2017], to approximate Turing kernelization. An -approximate Turing kernel for a parameterized…
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…