Partially Polynomial Kernels for Set Cover and Test Cover

Abstract

In a typical covering problem we are given a universe U of size n, a family S (S could be given implicitly) of size m and an integer k and the objective is to check whether there exists a subfamily S 0 ⊆ S of size at most k satisfying some desired properties. If S 0 is required to contain all the elements of U then it corresponds to the classical Set Cover problem. On the other hand if we require S 0 to satisfy the property that for every pair of elements x, y ∈ U there exists a set S ∈ S0 such that |S ∩ {x, y}| = 1 then it corresponds to the Test Cover problem. In this paper we consider a natural parameterization of Set Cover and Test Cover. More precisely, we study the (n − k)-Set Cover and (n − k)-Test Cover problems, where the objective is to find a subfamily S 0 of size at most n − k satisfying the respective properties, from the kernelization perspective. It is known in the literature that both (n−k)-Set Cover and (n−k)- Test Cover do not admit polynomial kernels (under some well known complexity theoretic assumptions). However, in this paper we show that they do admit “partially polynomial kernels”. More precisely, we give polynomial time algorithms that take as input an instance (U, S, k) of (n−k)-Set Cover ((n−k)-Test Cover) and return an equivalent instance (U˜, S˜, ˜k) of (n−k)- Set Cover (respectively (n − k)-Test Cover) with ˜k ≤ k and |U| ˜ = O(k 2) (|U| ˜ = O(k7)). These results allow us to generalize, improve and unify several results known in the literature. For example, these immediately imply traditional kernels when input instances satisfy certain “sparsity properties”. Using a part of our kernelization algorithm for (n − k)-Set Cover, we also get an improved FPT algorithm for this problem which runs in time O(4kk O(1)(m+n)) improving over the previous best of O(8k+o(k) (m+n) O(1)). On the other hand the partially polynomial kernel for (n − k)-Test Cover implies the first single exponential FPT algorithm, an algorithm with running time O(2O(k2) (m+n) O(1)). We believe such an approach will also be useful for other covering problems as well.