Alladi Ramakrishnan Hall

Difference Determines the Degree: Structural Kernelizations of Component Order Connectivity

Satyabrata Jana

IMSc

In the c-Component Order Connectivity problem (c-COC) we are given an undirected graph G and a non-negative integer t, the objective is to test whether there exists a set S of size at most t such that every component of G − S has size at most c. Such a set S is called a c-coc set. Observe that for c = 1, this corresponds to the Vertex Cover problem.

We study the c-Component Order Connectivity problem parameterized by the size of a d-coc set (c-COC/d-COC), where c, d are natural numbers with c ≤ d. In particular, the input is an undirected graph G, a positive integer t, and a set M of at most k vertices of G, such that the size of each connected component in G − M is at most d. The question is to find a set S of vertices of size at most t, such that the size of each connected component in G − S is at most c.

In this talk, we present an algorithm to obtain a kernel for c-COC/d-COC with O(k^{d−c+1}) vertices and O(k^{d−c+2}) edges. Our result exhibits that the difference in d and c, and not their absolute values, determines the exact degree of the polynomial in the kernel size. We also show that the dependence of d − c in the exponent of the kernel size cannot be avoided under reasonable complexity assumptions