Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2016
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1610.04711 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915163581448192 |
|---|---|
| author | Kumar, Mithilesh Lokshtanov, Daniel |
| author_facet | Kumar, Mithilesh Lokshtanov, Daniel |
| contents | In the $\ell$-Component Order Connectivity problem ($\ell \in \mathbb{N}$), we are given a graph $G$ on $n$ vertices, $m$ edges and a non-negative integer $k$ and asks whether there exists a set of vertices $S\subseteq V(G)$ such that $|S|\leq k$ and the size of the largest connected component in $G-S$ is at most $\ell$. In this paper, we give a linear programming based kernel for $\ell$-Component Order Connectivity with at most $2\ell k$ vertices that takes $n^{\mathcal{O}(\ell)}$ time for every constant $\ell$. Thereafter, we provide a separation oracle for the LP of $\ell$-COC implying that the kernel only takes $(3e)^{\ell}\cdot n^{O(1)}$ time. On the way to obtaining our kernel, we prove a generalization of the $q$-Expansion Lemma to weighted graphs. This generalization may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1610_04711 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | A $2\ell k$ Kernel for $\ell$-Component Order Connectivity Kumar, Mithilesh Lokshtanov, Daniel Data Structures and Algorithms In the $\ell$-Component Order Connectivity problem ($\ell \in \mathbb{N}$), we are given a graph $G$ on $n$ vertices, $m$ edges and a non-negative integer $k$ and asks whether there exists a set of vertices $S\subseteq V(G)$ such that $|S|\leq k$ and the size of the largest connected component in $G-S$ is at most $\ell$. In this paper, we give a linear programming based kernel for $\ell$-Component Order Connectivity with at most $2\ell k$ vertices that takes $n^{\mathcal{O}(\ell)}$ time for every constant $\ell$. Thereafter, we provide a separation oracle for the LP of $\ell$-COC implying that the kernel only takes $(3e)^{\ell}\cdot n^{O(1)}$ time. On the way to obtaining our kernel, we prove a generalization of the $q$-Expansion Lemma to weighted graphs. This generalization may be of independent interest. |
| title | A $2\ell k$ Kernel for $\ell$-Component Order Connectivity |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/1610.04711 |