Multiparameterizations for max k-set cover and related satisfiability problems
Édouard Bonnet, Vangélis Th. Paschos, Florian Sikora · arXiv (Cornell University) · 2013
We study the complexity of several parameterizations for max k-set cover as well as for some related satisfiability problems. Given a family of subsets S = {S1,...,Sm} over a set of elements X = {x1,...,xn} and an integer p, max k-set cover consists of finding a set T of at most k subsets covering at least p elements. This problem, when parameterized by k, can be easily shown to be W[2]-hard. Here, we settle the multiparameterized complexity of max k-set cover under pairs of parameters as max{k,�}, where � = maxi{|Si|} and max{k,f}, where f = maxi |{j|xi 2 Sj}|. We also study parameterized approximability of the problem with respect to parameters k and p. Then, we investigate some similar parameterizations of a satisfiability problem that is linked to max k-set cover in a sense explained in the paper. Finally, we sketch an enhancement of the classes of the W[·] hierarchy that seems more appropriate for showing completeness of cardinality constrained W[·]-hard problems.