Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2605.19853 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911698493898752 |
|---|---|
| author | Liu, Yuxi Xiao, Mingyu |
| author_facet | Liu, Yuxi Xiao, Mingyu |
| contents | 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 $|V(G)|^{O(l)}$ time. This is the first known linear kernel for each fixed $l\geq 3$. For $l=1$, this problem reduces to the classical \textsc{Vertex Cover}, and our result matches the best-known $2k$-vertex kernel. For $l=2$ (known as \textsc{Deletion to Induced Matching}), 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_19853 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Linear Kernels for $l$-Exact Component Order Connectivity Liu, Yuxi Xiao, Mingyu Data Structures and Algorithms 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 $|V(G)|^{O(l)}$ time. This is the first known linear kernel for each fixed $l\geq 3$. For $l=1$, this problem reduces to the classical \textsc{Vertex Cover}, and our result matches the best-known $2k$-vertex kernel. For $l=2$ (known as \textsc{Deletion to Induced Matching}), 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. |
| title | Linear Kernels for $l$-Exact Component Order Connectivity |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.19853 |