|
2025-06-25 / 16:30 ~ 17:30
|
| IBS-KAIST 세미나 - 이산수학: Uniform and Constructive Polynomial Kernel for Deletion to $K_{2,p}$ Minor-Free Graphs |
|
|
by Roohani Sharma(IBS 이산수학 그룹)
|
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 -\epsilon)}$, for any $\epsilon >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.
|
|
|
