Jakob Greilhuber, 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.