Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems
Édouard Bonnet, Vangélis Th. Paschos, Florian Sikora · RAIRO - Theoretical Informatics and Applications · 2016
Given a family of subsets 𝒮 over a set of elements X and two integers p and k, max k-set cover consists of finding a subfamily 𝒯 ⊆ 𝒮 of cardinality at most k, covering at least p elements of X. This problem is W[2]-hard when parameterized by k, and FPT when parameterized by p. We investigate the parameterized approximability of the problem with respect to parameters k and p. Then, we show that max sat-k, a satisfiability problem generalizing max k-set cover, is also FPT with respect to parameter p.