AI summaryⓘ
The authors study the Component Order Connectivity (COC) problem, which generalizes the Vertex Cover problem by asking whether we can remove a small set of vertices to break a graph into small pieces of size at most d. They explore when it is possible to reduce the problem efficiently (called polynomial kernelization) based on how close the graph is to simpler structures measured by pathwidth. Building on past results for Vertex Cover, the authors show that COC can be efficiently simplified if the graph is close to graphs with pathwidth 1, but not if the graph is close to pathwidth 2. Their main result is a polynomial kernel for COC parameterized by both the size of the deletion set to reach pathwidth-1 graphs and the constant d.
Component Order ConnectivityVertex CoverPolynomial KernelizationPathwidthTreewidthParameterizationGraph DeletionStructural ParameterFixed-Parameter Tractability
Abstract
In this work we study a classic generalization of the Vertex Cover (VC) problem, called the Component Order Connectivity (COC) problem. In COC, given an undirected graph $G$, integers $d \geq 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 \geq 2$, $d$-COC cannot admit a polynomial kernel when the parameter is distance to a forest of pathwidth $2$. Here, $d$-COC is the same as COC only that $d$ is a fixed constant not part of the input. We complement this result and show that like for the VC problem where distance to treewidth-$1$ graphs versus distance to treewidth-$2$ graphs is the dividing line between structural parameterizations that allow and respectively disallow polynomial kernelization, for COC this dividing line happens 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$.