Options
Hitting and covering partially
ISSN
03029743
Date Issued
2018-01-01
Author(s)
Agrawal, Akanksha
Choudhary, Pratibha
Jain, Pallavi
Kanesh, Lawqueen
Sahlot, Vibha
Saurabh, Saket
DOI
10.1007/978-3-319-94776-1_62
Abstract
d-Hitting Set and d-Set Cover are among the classical NP-hard problems. In this paper, we study variants of d-Hitting Set and d-Set Cover, which are called Partial d -Hitting Set (Partial d -HS) and Partial d -Exact Set Cover (Partial d -Exact SC), respectively. In Partial d -HS, given a universe U, a family F, of sets of size at most d over U, and integers k and t, the objective is to decide if there exists a (Formula Presented) of size at most k such that S intersects with at least t sets in F. We obtain a kernel for Partial d -HS in which the size of the universe is bounded by O(dt) and the size of the family is bounded by O(dt2). Using this result, we obtain a kernel for Partial Vertex Cover (PVC) with O(t) vertices, where t is the number of edges to be covered. Next, we study the Partial d -Exact SC problem, where, given a universe U, a family F, of sets of size exactly d over U, and integers k and t, the objective is to decide if there is (Formula Presented) of size at most k, such that S covers at least t elements in U. We design a kernel for Partial d -Exact SC in which sizes of the universe and the family are bounded by (Formula Presented). Finally, we study a special case of Partial d -HS, when d=2, and design an exact exponential time algorithm with running time (Formula Presented).