Hitting and Covering Partially

摘要

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 S ⊆ U 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(dt~2). 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 S ⊆ F 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 O(k~(d+1)). Finally, we study a special case of Partial d-HS, when d = 2, and design an exact exponential time algorithm with running time O(1.73l~nn~(O(1))).