2026-08-21T17:31:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27389 2026-08-21T14:42:37Z ddc:004 open_access

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth Greilhuber, Jakob Sharma, Roohani Kernelization Component Order Connectivity Caterpillars Pathwidth Structural Parameterization In this work we study a classic generalization of the ubiquitous Vertex Cover (VC) problem, called the Component Order Connectivity (COC) problem. In COC, given an undirected graph G, integers d ≥ 1 and k, the goal is to determine if there is a set of at most k vertices whose deletion results in a graph where each connected component has at most d vertices. When d = 1, this is exactly VC. This work is inspired by polynomial kernelization results with respect to structural parameters for VC. On one hand, Jansen & Bodlaender [TOCS 2013] show that VC admits a polynomial kernel when the parameter is the distance to treewidth-1 graphs, on the other hand Cygan, Lokshtanov, Pilipczuk, Pilipczuk & Saurabh [TOCS 2014] showed that VC does not admit a polynomial kernel when the parameter is distance to treewidth-2 graphs. Greilhuber & Sharma [IPEC 2024] showed that, for any d ≥ 2, d-COC cannot admit a polynomial kernel when the parameter is distance to a forest of pathwidth 2. Here, d-COC is the variant of COC where d is a fixed constant rather than part of the input. We complement this result and show that, analogously to the VC setting, where distance to treewidth-1 graphs versus distance to treewidth-2 graphs is the dividing line between structural parameterizations that admit and respectively do not admit polynomial kernelization, for COC this dividing line lies between distance to pathwidth-1 graphs and distance to pathwidth-2 graphs. The main technical result of this work is that COC admits a polynomial kernel parameterized by distance to pathwidth-1 graphs plus d. The problem d-COC can also be expressed as an ℱ-MinorDeletion problem for an appropriate graph family ℱ. One of the central questions around ℱ-MinorDeletion is for which families ℱ and minor-closed graph classes 𝒢 the problem admits a polynomial kernel when parameterized by the distance to 𝒢. For some families ℱ complete dichotomies answering this question are known [Bougeret et al., SIDMA 2022][Bougeret et al., STACS 2026][Bougeret et al., arXiv 2026]. But, these results do not capture the 2-COC problem. We show that, when d ≥ 2, the line of tractability for polynomial kernelization of d-COC parameterized by the distance to 𝒢 is different from the tractability line of the ℱ-MinorDeletion problems for which the currently known dichotomies apply. Thus, with our result, d-COC serves as an outlier in the class of ℱ-MinorDeletion problems when it comes to understanding the dichotomies for polynomial kernelization when parameterizing by the distance to some minor-closed graph class. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jakob Greilhuber and Roohani Sharma 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.8 urn:nbn:de:0030-drops-273890 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.8 eng https://creativecommons.org/licenses/by/4.0/legalcode