Tag: RoohaniSharma

Let $\mathcal{F}$ be a fixed, finite family of graphs. In the $\mathcal{F}$-Deletion problem, the input is a graph G and a positive integer k, and the goal is to determine if there exists a set of at most k vertices whose deletion results in a graph that does not contain any graph of $\mathcal{F}$ as a minor. The $\mathcal{F}$-Deletion problem encapsulates a large class of natural and interesting graph problems like Vertex Cover, Feedback Vertex Set, Treewidth-$\eta$ Deletion, Treedepth-$\eta$ Deletion, Pathwidth-$\eta$ Deletion, Outerplanar Deletion, Vertex Planarization and many more. We study the $\mathcal{F}$-Deletion problem from the kernelization perspective.

In a seminal work, Fomin, Lokshtanov, Misra & Saurabh [FOCS 2012] gave a polynomial kernel for this problem when the family F contains at least one planar graph. The asymptotic growth of the size of the kernel is not uniform with respect to the family $\mathcal{F}$: that is, the size of the kernel is $k^{f(\mathcal{F})}$, for some function f that depends only on $\mathcal{F}$. Also the size of the kernel depends on non-constructive constants.

Later Giannopoulou, Jansen, Lokshtanov & Saurabh [TALG 2017] showed that the non-uniformity in the kernel size bound of Fomin et al. is unavoidable as Treewidth-$\eta$ Deletion, cannot admit a kernel of size $O(k^{(\eta +1)/2-ϵ)}$, for any $ϵ>0$, unless NP $\subseteq$ coNP/poly. On the other hand it was also shown that Treedepth-$\eta$ Deletion, admits a uniform kernel of size $f(\mathcal{F})k^6$, showcasing that there are subclasses of $\mathcal{F}$ where the asymptotic kernel sizes do not grow as a function of the family $\mathcal{F}$. This work leads to the natural question of determining classes of $\mathcal{F}$ where the problem admits uniform polynomial kernels.

In this work, we show that if all the graphs in $\mathcal{F}$ are connected and $\mathcal{F}$ contains $K_{2,p}$ (a bipartite graph with 2 vertices on one side and p vertices on the other), then the problem admits a uniform kernel of size $f(\mathcal{F})k^{10}$ where the constants in the size bound are also constructive. The graph $K_{2,p}$ is one natural extension of the graph ${\theta }_p$, where ${\theta }_p$ is a graph on two vertices and p parallel edges. The case when $\mathcal{F}$ contains ${\theta }_p$ has been studied earlier and serves as (the only) other example where the problem admits a uniform polynomial kernel.

This is joint work with William Lochet.