Please use this identifier to cite or link to this item:
https://idr.l2.nitk.ac.in/jspui/handle/123456789/12635
Title: | Partially polynomial kernels for set cover and test cover |
Authors: | Basavaraju, M. Francis, M.C. Ramanujan, M.S. Saurabh, S. |
Issue Date: | 2016 |
Citation: | SIAM Journal on Discrete Mathematics, 2016, Vol.30, 3, pp.1401-1423 |
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. |
URI: | http://idr.nitk.ac.in/jspui/handle/123456789/12635 |
Appears in Collections: | 1. Journal Articles |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.