The Parameterized Complexity of Unique Coverage and Its Variants
In this paper we study the parameterized complexity of the Unique Coverage problem, a variant of the classic Set Cover problem. This problem admits several parameterizations and we show that all, except the standard parameterization and a generalization of it, are unlikely to be fixed-parameter tractable. We use results from extremal combinatorics to obtain the best-known kernel for Unique Coverage and the well-known color-coding technique of Alon et al. (J.ACM 42(4), 844856, 1995) to show that a weighted version of this problem is fixed-parameter tractable.
unique coverage parameterized algorithms budgeted unique coverage color coding hash functions