Search Results

In this paper we show that the d-Component Order Connectivity (d-COC) problem parameterized by the distance to subdivided comb graphs (dist-to-subdivided-combs) does not admit a polynomial kernel, unless NP ⊆ coNP/poly. The d-COC problem is a generalization of the classical Vertex Cover problem. An instance of the d-COC problem consists of an undirected graph G and a positive integer k, and the question is whether there exists a set S ⊆ V(G) of size at most k, such that each connected component of G-S contains at most d vertices. When d = 1, d-COC is the Vertex Cover problem. Vertex Cover is a ubiquitous problem in parameterized complexity, and it admits a kernel with O(k²) 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 Vertex Cover where the parameter is provably smaller or equal to the standard parameter, solution size k. They used 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 Vertex Cover that generalize to d-COC, this is not the case when dist-to-subdivided-combs, which is at least as large as 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 𝒞, which is closed under taking disjoint unions, has unbounded "blocking set" size, then Vertex Cover does not admit a polynomial kernel parameterized by the size of a vertex modulator to 𝒞, unless NP ⊆ coNP/poly. We show that a similar sufficient condition for proving the non-existence of polynomial kernels also holds for d-COC. In the second stage, we show that when 𝒞 is the family of subdivided comb graphs, contrary to Vertex Cover, where the size of minimal blocking sets of graphs in 𝒞 is at most two [Jansen & Bodlaender, STACS 2011], the size of minimal blocking sets of graphs in 𝒞 for the d-COC problem can be arbitrarily large. This yields the desired lower bound. In addition to this we also show that when 𝒞 is a class of paths, then it still has blocking sets of size at most two for 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).