2026-07-22T10:50:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19424 2024-03-06T11:04:01Z ddc:004 open_access

Difference Determines the Degree: Structural Kernelizations of Component Order Connectivity Bhyravarapu, Sriram Jana, Satyabrata Saurabh, Saket Sharma, Roohani Kernelization Component Order Connectivity Vertex Cover Structural Parameterizations We consider the question of polynomial kernelization of a generalization of the classical Vertex Cover problem parameterized by a parameter that is provably smaller than the solution size. In particular, we focus on the c-Component Order Connectivity problem (c-COC) where given an undirected graph G and a non-negative integer t, the objective is to test whether there exists a set S of size at most t such that every component of G-S contains at most c vertices. Such a set S is called a c-coc set. It is known that c-COC admits a kernel with {O}(ct) vertices. Observe that for c = 1, this corresponds to the Vertex Cover problem. We study the c-Component Order Connectivity problem parameterized by the size of a d-coc set (c-COC/d-COC), where c,d ∈ ℕ with c ≤ d. In particular, the input is an undirected graph G, a positive integer t and a set M of at most k vertices of G, such that the size of each connected component in G - M is at most d. The question is to find a set S of vertices of size at most t, such that the size of each connected component in G - S is at most c. In this paper, we give a kernel for c-COC/d-COC with O(k^{d-c+1}) vertices and O(k^{d-c+2}) edges. Our result exhibits that the difference in d and c, and not their absolute values, determines the exact degree of the polynomial in the kernel size. When c = d = 1, the c-COC/d-COC problem is exactly the Vertex Cover problem parameterized by the solution size, which has a kernel with O(k) vertices and O(k²) edges, and this is asymptotically tight [Dell & Melkebeek, JACM 2014]. We also show that the dependence of d-c in the exponent of the kernel size cannot be avoided under reasonable complexity assumptions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sriram Bhyravarapu and Satyabrata Jana and Saket Saurabh and Roohani Sharma 2023 Is Part Of LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2023.5 urn:nbn:de:0030-drops-194241 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.5 eng https://creativecommons.org/licenses/by/4.0/legalcode