Partially polynomial kernels for set cover and test cover

Abstract

An instance of the (n-k)-Set Cover or the (n-k)-Test Cover problems is of the form (U, S, k), where U is a set with n elements, S ? 2U with |S| = m, and k is the parameter. The instance is a Yes-instance of (n - k)-Set Cover if and only if there exists S' ? S with |S'| ? n - k such that every element of U is contained in some set in S'. Similarly, it is a Yes-instance of (n - k)-Test Cover if and only if there exists S' ? S with |S'| ? n - k such that for any pair of elements from U, there exists a set in S' that contains one of them but not the other. 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": we give polynomial time algorithms that take as input an instance (U, S, k) of (n - k)-Set Cover (respectively, (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 |?| = O(k2) (respectively, |?| = 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 partial kernelization algorithm for (n - k)-Set Cover, we also get an improved fixed-parameter tractable algorithm for this problem which runs in time O(4kkO(1)(m + n) + mn) 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 gives an algorithm with running time O(2O(k2)(m + n)O(1)). We believe such an approach could also be useful for other covering problems. Copyright by SIAM.