PARTIALLY POLYNOMIAL KERNELS FOR SET COVER AND TEST COVER

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 subset of 2(U) with vertical bar S vertical bar = m, and k is the parameter. The instance is a YES-instance of (n - k)-SET COVER if and only if there exists S' subset of S with vertical bar S'vertical bar <= 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' subset of S with vertical bar S'vertical bar <= 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) over tilde, (S) over tilde, (k) over tilde) of (n - k)-SET COVER (respectively, (n - k)-TEST COVER) with (k) over tilde <= k and vertical bar(U) over tilde vertical bar = O (k(2)) (respectively, vertical bar(U) over tilde vertical bar = O (k(7))). 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 (4(k) k(O(1)) (m + n) + mn) improving over the previous best of O (8(k+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 (2(O(k2)) (m + n)(O(1))). We believe such an approach could also be useful for other covering problems.