On October 28, 2025, Jakob Greilhuber from the CISPA Helmholtz Center for Information Security gave a talk at the Discrete Math Seminar on the parameterized complexity of the problem of deleting k vertices to make every component small. The title of his talk was “A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth“.
Vertex Cover is perhaps the most-studied problem in parameterized complexity that frequently serves as a testing ground for new concepts and techniques. In this talk, I will focus on a generalization of Vertex Cover called Component Order Connectivity (COC). Given a graph G, an integer k and a positive integer d, the task is to decide whether there is a vertex set S of size at most k such that each connected component of G – S has size at most d. If d = 1, then COC is the same as Vertex Cover.
While almost all techniques to obtain polynomial kernels for Vertex Cover extend well to COC parameterized by k + d, the same cannot be said for structural parameters. Vertex Cover admits a polynomial kernel parameterized by the vertex deletion distance to treewidth 1 graphs, but not when parameterized by the deletion distance to treewidth 2 graphs. The picture changes when considering COC: It was recently shown that COC does not admit a polynomial kernel parameterized by the vertex deletion distance to treewidth 1 graphs with pathwidth 2, even if d ≥ 2 is a fixed constant.
Complementing this, we show that COC does admit a polynomial kernel parameterized by the distance to graphs with pathwidth at most 1 (plus d). Hence, the deletion distance to pathwidth 1 vs. pathwidth 2 forms a similar line of tractability for COC as the distance to treewidth 1 vs. treewidth 2 does for Vertex Cover. In this talk, I will highlight the ideas and techniques that make this kernelization result possible.
