3 citations · 3 across the 2 of their papers we have counts for
4 papers · 1 filter
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…
On Kernelization for Edge Dominating Set under Structural Parameters
Eva-Maria C. Hols, Stefan Kratsch
In the NP-hard Edge Dominating Set problem (EDS) we are given a graph and an integer , and need to determine whether there is a set of at most edges…
Smaller parameters for vertex cover kernelization
Eva-Maria C. Hols, Stefan Kratsch
We revisit the topic of polynomial kernels for Vertex Cover relative to structural parameters. Our starting point is a recent paper due to Fomin and Strømme [WG 2016] who gave a ke…
A randomized polynomial kernel for Subset Feedback Vertex Set
Eva-Maria C. Hols, Stefan Kratsch
The Subset Feedback Vertex Set problem generalizes the classical Feedback Vertex Set problem and asks, for a given undirected graph , a set , and an integer…