A $2\ell k$ Kernel for $\ell$-Component Order Connectivity

Abstract

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|\le 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.

14 pages, 1 figure, accepted in IPEC 2016, (New: provided separation oracle for the LP, 1st appeared in the PhD thesis of Mithilesh Kumar)