Source author record

Eva-Maria C. Hols

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms

Catalog footprint

Research overview

2works

2topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Approximate Turing Kernelization for Problems Parameterized by Treewidth

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 optimization problem is a polynomial-time algorithm that, when given access to an oracle that outputs $c$ -approximate solutions in $O(1)$ time, obtains an $(α\cdot c)$ -approximate solution to the considered problem, using calls to the oracle of size at most $f(k)$ for some function $f$ that only depends on the parameter. Using this definition, we show that Independent Set parameterized by treewidth $\ell$ has a $(1+\varepsilon)$ -approximate Turing kernel with $O(\frac{\ell^2}{\varepsilon})$ vertices, answering an open question posed by Lokshtanov et al. [STOC 2017]. Furthermore, we give $(1+\varepsilon)$ -approximate Turing kernels for the following graph problems parameterized by treewidth: Vertex Cover, Edge Clique Cover, Edge-Disjoint Triangle Packing and Connected Vertex Cover. We generalize the result for Independent Set and Vertex Cover, by showing that all graph problems that we will call "friendly" admit $(1+\varepsilon)$ -approximate Turing kernels of polynomial size when parameterized by treewidth. We use this to obtain approximate Turing kernels for Vertex-Disjoint $H$ -packing for connected graphs $H$ , Clique Cover, Feedback Vertex Set and Edge Dominating Set.

preprint2015arXiv

A randomized polynomial kernel for Subset Feedback Vertex Set

The Subset Feedback Vertex Set problem generalizes the classical Feedback Vertex Set problem and asks, for a given undirected graph $G=(V,E)$ , a set $S \subseteq V$ , and an integer $k$ , whether there exists a set $X$ of at most $k$ vertices such that no cycle in $G-X$ contains a vertex of $S$ . It was independently shown by Cygan et al. (ICALP '11, SIDMA '13) and Kawarabayashi and Kobayashi (JCTB '12) that Subset Feedback Vertex Set is fixed-parameter tractable for parameter $k$ . Cygan et al. asked whether the problem also admits a polynomial kernelization. We answer the question of Cygan et al. positively by giving a randomized polynomial kernelization for the equivalent version where $S$ is a set of edges. In a first step we show that Edge Subset Feedback Vertex Set has a randomized polynomial kernel parameterized by $|S|+k$ with $O(|S|^2k)$ vertices. For this we use the matroid-based tools of Kratsch and Wahlström (FOCS '12) that for example were used to obtain a polynomial kernel for $s$ -Multiway Cut. Next we present a preprocessing that reduces the given instance $(G,S,k)$ to an equivalent instance $(G',S',k')$ where the size of $S'$ is bounded by $O(k^4)$ . These two results lead to a polynomial kernel for Subset Feedback Vertex Set with $O(k^9)$ vertices.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.