A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth

Jakob Greilhuber, Roohani Sharma · 2026

Read A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth by Jakob Greilhuber, Roohani Sharma (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-22240.txt.

Description

Greilhuber and Sharma draw a sharp line for when a graph problem admits a polynomial kernel. The problem is Component Order Connectivity, a generalization of Vertex Cover. Deleting at most k vertices should leave only components of at most d vertices. For Vertex Cover, the line runs between treewidth 1 and 2. For this problem, the authors locate the line elsewhere. A polynomial kernel exists when the parameter is distance to pathwidth-1 graphs, plus d. Past work rules one out for distance to pathwidth-2 forests.

Catalog record

CREATORJakob Greilhuber, Roohani Sharma
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE226977
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.22240

Browse the full library · About the Tower of Babel