Linear Kernels for $l$-Exact Component Order Connectivity

The \textsc{$l$-Exact Component Order Connectivity} problem asks whether, given an input graph $G$ and an integer $k$, there exists a vertex subset $S\subseteq V(G)$ of size at most $k$ such that every connected component in $G-S$ has exactly $l$ vertices. In this paper, we present an $O(kl)$-vertex kernel for this problem, computable in $\mathrm{\mid }V(G){\mathrm{\mid }}^{O(l)}$ time. This is the first known linear kernel for each fixed $l\ge 3$. For $l=1$, this problem reduces to the classical $\text{textsc}VertexCover$, and our result matches the best-known $2k$-vertex kernel. For $l=2$ (known as $\text{textsc}DeletiontoInducedMatching$), we can get a $(3k+1)$-vertex kernel, improving the previously known result of $6k$ vertices. Our kernelization algorithm is built upon on an extended crown decomposition combined with linear programming and other techniques.