2015/11/24 by Pradeesha Ashok, Ashok, Pradeesha, Sudeshna Kolay +3
Computer Science · Engineering · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #cs.DS #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1511.07642
openalex publication_date 2015/11/24 · arxiv created 2015/11/25 · arxiv updated 2015/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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_ℓ and kr, and a family \F of ℓ sets over U, the \srbsc problem is to decide whether there is a subfamily \F'⊆ \F of size at most k_ℓ that covers all blue elements, but at most kr of the red elements. This generalizes SET COVER and thus in full generality it is intractable in the parameterized setting. In this paper, we study a geometric version of this problem, called Gen-RBSC-lines, where the elements are points in the plane and sets are defined by lines. We study this problem for an array of parameters, namely, k_ℓ, kr, r, b, and ℓ, and all possible combinations of them. For all these cases, we either prove that the problem is W-hard or show that the problem is fixed parameter tractable (FPT). In particular, on the algorithmic side, our study shows that a combination of k_ℓ and kr gives rise to a nontrivial algorithm for Gen-RBSC-lines. On the hardness side, we show that the problem is para-NP-hard when parameterized by kr, and W[1]-hard when parameterized by k_ℓ. Finally, for the combination of parameters for which Gen-RBSC-lines admits FPT algorithms, we ask for the existence of polynomial kernels. We are able to provide a complete kernelization dichotomy by either showing that the problem admits a polynomial kernel or that it does not contain a polynomial kernel unless \CoNP ⊆ \NP/poly.