3 citations · 3 across the 6 of their papers we have counts for
10 papers
Kernelization for list -coloring for graphs with small vertex cover
Marta Piecyk, Astrid Pieterse, Paweł Rzążewski +1
For a fixed graph , in the List -Coloring problem, we are given a graph along with list for every , and we have to determine if there ex…
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…