We extend the notion of lossy kernelization, introduced by Lokshtanov et al. (2017) [19] , to approximate Turing kernelization. An α -approximate Turing kernelization 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, computes an α ⋅ 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 ℓ has a ( 1 + ε ) -approximate Turing kernelization with O ( ℓ 2 ε ) vertices, answering an open question posed by Lokshtanov et al. (2017) [19] . Furthermore, we give ( 1 + ε ) -approximate Turing kernelizations 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 + ε ) -approximate Turing kernelizations of polynomial size when parameterized by treewidth. We use this to establish approximate Turing kernelizations for Vertex-Disjoint H -packing for connected graphs H , Clique Cover , Feedback Vertex Set , and Edge Dominating Set .

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 ${\mathsf{NP}}$-hard problems. Motivated by the great variety of positive and negative results for kernelization for Vertex Cover subject to different parameters and graph classes, we seek to unify and generalize them using so-called blocking sets. A blocking set is a set of vertices such that no optimal vertex cover contains all vertices in the blocking set, and the study of minimal blocking sets played implicit and explicit roles in many existing results. We show that in the most-studied setting, parameterized by the size of a deletion set to a specified graph class ${\mathcal{C}}$, bounded minimal blocking set size is necessary but not sufficient to get a polynomial kernelization. Under mild technical assumptions, bounded minimal blocking set size is shown to allow an essentially tight polynomial-time reduction in the number of connected components. We then determine the exact maximum size of minimal blocking sets for graphs of bounded elimination distance to any hereditary class $\mathcal{C}$, including the case of graphs of bounded treedepth. We get similar but not tight bounds for certain nonhereditary classes $\mathcal{C}$, including the class ${\mathcal{C}}_{{\mathrm{LP}}}$ of graphs where integral and fractional vertex cover size coincide. These bounds allow us to derive polynomial kernels for Vertex Cover parameterized by the size of a deletion set to graphs of bounded elimination distance to, e.g., forest, bipartite, or ${\mathcal{C}}_{\mathrm{LP}}$ graphs.

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.

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 NP-hard problems. Motivated by the great variety of positive and negative results for kernelization for Vertex Cover subject to different parameters and graph classes, we seek to unify and generalize them using so-called blocking sets. A blocking set is a set of vertices such that no optimal vertex cover contains all vertices in the blocking set, and the study of minimal blocking sets played implicit and explicit roles in many existing results. We show that in the most-studied setting, parameterized by the size of a deletion set to a specified graph class ?, bounded minimal blocking set size is necessary but not sufficient to get a polynomial kernelization. Under mild technical assumptions, bounded minimal blocking set size is showed to allow an essentially tight efficient reduction in the number of connected components. We then determine the exact maximum size of minimal blocking sets for graphs of bounded elimination distance to any hereditary class ?, including the case of graphs of bounded treedepth. We get similar but not tight bounds for certain non-hereditary classes ?, including the class ?_{LP} of graphs where integral and fractional vertex cover size coincide. These bounds allow us to derive polynomial kernels for Vertex Cover parameterized by the size of a deletion set to graphs of bounded elimination distance to, e.g., forest, bipartite, or ?_{LP} graphs.

In the NP-hard Edge Dominating Set problem (EDS) we are given a graph $G=(V,E)$ and an integer $k$, and need to determine whether there is a set $F\subseteq E$ of at most $k$ edges that are incident with all (other) edges of $G$. It is known that this problem is fixed-parameter tractable and admits a polynomial kernel when parameterized by $k$. A caveat for this parameter is that it needs to be large, i.e., at least equal to half the size of a maximum matching of $G$, for instances not to be trivially negative. Motivated by this, we study the existence of polynomial kernels for EDS when parameterized by structural parameters that may be much smaller than $k$. Unfortunately, at first glance this looks rather hopeless: Even when parameterized by the deletion distance to a disjoint union of paths $P_3$ of length two there is no polynomial kernelization (under standard assumptions), ruling out polynomial kernels for many smaller parameters like the feedback vertex set size. In contrast, somewhat surprisingly, there is a polynomial kernelization for deletion distance to a disjoint union of paths $P_5$ of length four. As our main result, we fully classify for all finite sets $\mathcal{H}$ of graphs, whether a kernel size polynomial in $|X|$ is possible when given $X$ such that each connected component of $G-X$ is isomorphic to a graph in $\mathcal{H}$.

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 ⊆ 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 $\mathcal {O}(|S|^{2}k)$ 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 $\mathcal {O}(k^{4})$ . These two results lead to a randomized polynomial kernel for subset feedback vertex set with $\mathcal {O}(k^{9})$ vertices.

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 kernel with O(|X|^{12}) vertices when X is a vertex set such that each connected component of G-X contains at most one cycle, i.e., X is a modulator to a pseudoforest. We strongly generalize this result by using modulators to d-quasi-forests, i.e., graphs where each connected component has a feedback vertex set of size at most d, and obtain kernels with O(|X|^{3d+9}) vertices. Our result relies on proving that minimal blocking sets in a d-quasi-forest have size at most d+2. This bound is tight and there is a related lower bound of O(|X|^{d+2-epsilon}) on the bit size of kernels. In fact, we also get bounds for minimal blocking sets of more general graph classes: For d-quasi-bipartite graphs, where each connected component can be made bipartite by deleting at most d vertices, we get the same tight bound of d+2 vertices. For graphs whose connected components each have a vertex cover of cost at most d more than the best fractional vertex cover, which we call d-quasi-integral, we show that minimal blocking sets have size at most 2d+2, which is also tight. Combined with existing randomized polynomial kernelizations this leads to randomized polynomial kernelizations for modulators to d-quasi-bipartite and d-quasi-integral graphs. There are lower bounds of O(|X|^{d+2-epsilon}) and O(|X|^{2d+2-epsilon}) for the bit size of such kernels.

We continue the study of preprocessing under uncertainty that was initiated independently by Assadi et al. (FSTTCS 2015) and Fafianie et al. (STACS 2016). Here, we are given an instance of a tractable problem with a large static/known part and a small part that is dynamic/uncertain, and ask if there is an efficient algorithm that computes an instance of size polynomial in the uncertain part of the input, from which we can extract an optimal solution to the original instance for all (usually exponentially many) instantiations of the uncertain part. In the present work, we focus on the Matroid Intersection problem. Amongst others we present a positive preprocessing result for the important case of finding a largest common independent set in two linear matroids. Motivated by an application for intersecting two gammoids we also revisit Maximum Flow. There we tighten a lower bound of Assadi et al. and give an alternative positive result for the case of low uncertain capacity that yields a Maximum Flow instance as output rather than a matrix.