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
| CREATOR | Jakob Greilhuber, Roohani Sharma |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 226977 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.22240