Component Order Connectivity admits no polynomial kernel parameterized by the distance to subdivided comb graphs

Summary

In this paper we show that the {\sc $d$-Component Order Connectivity ($d$-COC)} problem parameterized by the \distToSubCombFull{} (\distToSubCombShort{}) does not admit a polynomial kernel, unless \conditionone. The {\sc $d$-COC} problem is a generalization of the classical {\sc Vertex Cover} problem. An instance of the {\sc $d$-COC} problem consists of an undirected graph $G$ and a positive integer $k$, and the question is whether there exists a set $S \subseteq V(G)$ of size at most $k$, such that each connected component of $G-S$ contains at most $d$ vertices. When $d=1$, {\sc $d$-COC} is the {\sc Vertex Cover} problem. \textsc{Vertex Cover} is a ubiquitous problem in parameterized complexity, and it admits a kernel with $O(k^2)$ edges and $O(k)$ vertices, which is tight [Dell \& van Melkebeek, JACM 2014]. Our result is inspired by the work of Jansen \& Bodlaender~[TOCS 2013], who gave the first polynomial kernel for \textsc{Vertex Cover} where the parameter is provably smaller or equal to the standard parameter, solution size $k$. They used \texttt{fvs}, the feedback vertex set number, as the parameter. In this work, we show that unlike most other existing results or techniques for kernelization of \textsc{Vertex Cover} that generalize to {\sc $d$-COC}, this is not the case when \distToSubCombShort{}, which is at least as large as \texttt{fvs}, is the parameter. Our lower bound is achieved in two stages. In the first stage we extend the result of Hols, Kratsch \& Pieterse [SIDMA 2022] where they show that if a graph family $\mathcal{C}$, which is closed under taking disjoint unions, has unbounded ``blocking set'' size, then {\sc Vertex Cover} does not admit a polynomial kernel parameterized by the size of a vertex modulator to $\mathcal{C}$, unless \conditionone{}. We show that a similar sufficient condition for proving the non-existence of polynomial kernels also holds for {\sc $d$-COC}. In the second stage, we show that when $\mathcal{C}$ is the family of subdivided comb graphs, contrary to {\sc Vertex Cover}, where the size of minimal blocking sets of graphs in $\mathcal{C}$ is at most two [Jansen \& Bodlaender, STACS 2011], the size of minimal blocking sets of graphs in $\mathcal{C}$ for the {\sc $d$-COC} problem can be arbitrarily large. This yields the desired lower bound. In addition to this we also show that when $\mathcal{C}$ is a class of paths, then it still has blocking sets of size at most two for {\sc $d$-COC}, indicating that polynomial kernels might be achievable when the parameter is the size of a vertex modulator to the class of disjoint unions of paths (linear forests).