Paper Info
Title
Parameterized Complexity of Red Blue Set Cover for Lines.
Abstract
We investigate the parameterized complexity of Generalized Red Blue Set Cover (Gen-RBSC), a generalization of the classic Set Cover problem and the more recently studied Red Blue Set Cover problem. Given a universe U containing b blue elements and r red elements, positive integers (k_ell ) and (k_r), and a family (mathcal F ) of (ell ) sets over U, the Gen-RBSC problem is to decide whether there is a subfamily (mathcal F u0027subseteq mathcal F ) of size at most (k_ell ) that covers all blue elements, but at most (k_r) of the red elements. This generalizes Set Cover and thus in full generality it is intractable in the parameterized setting, when parameterized by (k_ell +k_r). In this paper, we study Gen-RBSC-lines, where the elements are points in the plane and sets are defined by lines. We study this problem for the parameters (k_ell , k_r), and (k_ell +k_r). For all these cases, we either prove that the problem is W-hard or show that the problem is fixed parameter tractable (FPT). Finally, for the parameter (k_ell +k_r), for which Gen-RBSC-lines admits FPT algorithms, we show that the problem does not have a polynomial kernel unless (text { co-NP}subseteq text { NP}/mathrm{poly}). Further, we show that the FPT algorithm does not generalize to higher dimensions.
Year
Venue
Field
2016
LATIN
Integer,Discrete mathematics,Set cover problem,Parameterized complexity,Combinatorics,Computer science,Polynomial kernel
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
7
3
Name
Order
Citations
PageRank
Pradeesha Ashok1116.11
Sudeshna Kolay22512.77
Saket Saurabh32023179.50