Parameterized exact and approximation algorithms for maximum $k$-set cover and related satisfiability problems

Bonnet, Édouard; Paschos, Vangelis Th.; Sikora, Florian

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 3, pp. 227-240.

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$.

Classification : 68Q17, 68W25
Mots clés : Parameterized complexity, parameterized approximation, max k-set cover

A.A. Ageev and M. Sviridenko, Approximation algorithms for maximum coverage and max cut with given sizes of parts. In Proc. of Conference on Integer Programming and Combinatorial Optimization, IPCO’99, edited by G. Cornuéjols, R.E. Burkard and G.J. Woeginger. Vol. 1610 of Lecture Notes in Computer Science. Springer-Verlag (1999) 17–30. | MR | Zbl

A. Badanidiyuru, R. Kleinberg and H. Lee, Approximating low-dimensional coverage problems. In Proc. of Symposuim on Computational Geometry, SoCG’12, Chapel Hill, NC, edited by T.K. Dey and S. Whitesides. ACM (2012) 161–170. | MR | Zbl

A. Björklund, T. Husfeldt and M. Koivisto, Set partitioning via inclusion-exclusion. SIAM J. Comput. 39 (2009) 546–563. | DOI | MR | Zbl

M. Bläser, Computing small partial coverings. Inform. Process. Lett. 85 (2003) 327–331. | DOI | MR | Zbl

E. Bonnet, B. Escoffier, V.Th. Paschos and E. Tourniaire, Multi-parameter complexity analysis for constrained size graph problems: using greediness for parameterization. Algorithmica 71 (2015) 566–580. | DOI | MR | Zbl

E. Bonnet, V.Th. Paschos and F. Sikora, Multiparameterizations for max $k$-set cover and related satisfiability problems. Preprint (2013). | arXiv

L. Cai, Parameter complexity of cardinality constrained optimization problems. Comput. J. 51 (2008) 102–121. | DOI

L. Cai and X. Huang, Fixed-parameter approximation: conceptual framework and approximability results. In Proc. of International Workshop on Parameterized and Exact Computation, IWPEC’06, edited by H.L. Bodlaender and M.A. Langston. Vol. 4169 of Lect. Notes Comput. Sci. Springer-Verlag (2006) 96–108. | MR | Zbl

M. Cesati, The turing way to parameterized complexity. J. Comput. System Sci. 67 (2003) 654–685. | DOI | MR | Zbl

J. Chen, D.K. Friesen, W. Jia and I.A. Kanj, Using nondeterminism to design deterministic algorithms. In Proc. of Foundations of Software Technology and Theoretical Computer Science, FSTTCS’01, edited by R. Hariharan, M. Mukund and V. Vinay. Vol. 2245 of Lect. Notes Comput. Sci. Springer-Verlag (2001) 120–131. | MR | Zbl

Y. Chen, M. Grohe and M. Grüber, On parameterized approximability. In Proc. of the International Workshop on Parameterized and Exact Computation, IWPEC’06, edited by H.L. Bodlaender and M.A. Langston. Vol. 4169 of Lect. Notes Comput. Sci. Springer-Verlag (2006) 109–120. | MR | Zbl

Y. Chen and B. Lin, The constant inapproximability of the parameterized dominating set problem. Preprint (2015). | arXiv | MR

G. Cornuejols, M.L. Fisher and G.L. Nemhauser, Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Management Sci. 23 (1977) 789–810. | DOI | MR | Zbl

F. Della Croce and V.Th. Paschos, Efficient algorithms for the max $k$-vertex cover problem. J. Comb. Optim. 28 (2014) 674–691. | DOI | MR | Zbl

F. Dehne, M.R. Fellows, F.A. Rosamond and P. Shaw, Greedy localization, iterative compression, modeled crown reductions: new FPT techniques, an improved algorithm for set splitting, and a novel $2k$ kernelization for vertex cover. In Proc. of the International Workshop on Parameterized and Exact Computation, IWPEC’04, edited by R.G. Downey, M.R. Fellows and F. Dehne. Vol. 3162 of Lect. Notes Comput. Sci. Springer-Verlag (2004) 271–280. | Zbl

R.G. Downey and M.R. Fellows, Parameterized complexity. Monographs in Computer Science. Springer, New York (1999). | MR

R.G. Downey, M.R. Fellows and C. McCartin, Parameterized approximation problems. In Proc. of the International Workshop on Parameterized and Exact Computation, IWPEC’06, edited by H.L. Bodlaender and M.A. Langston. Vol. 4169 of Lect. Notes Comput. Sci. Springer-Verlag (2006) 121–129. | MR | Zbl

R.G. Downey, M.R. Fellows, C. Mccartin and F.A. Rosamond, Parameterized approximation of dominating set problems. Inform. Process. Lett. 109 (2008) 68–70. | DOI | MR | Zbl

U. Feige, A threshold of $lnn$ for approximating set cover. J. Assoc. Comput. Mach. 45 (1998) 634–652. | DOI | MR | Zbl

M.R. Fellows, J. Flum, D. Hermelin, M. Müller and F.A. Rosamond, W-hierarchies defined by symmetric gates. Theory Comput. Sys. 46 (2010) 311–339. | DOI | MR | Zbl

M.R. Garey and D.S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, edited by W. H. Freeman, San Francisco (1979). | MR | Zbl

J. Guo, R. Niedermeier and S. Wernicke, Parameterized complexity of vertex cover variants. Theory Comput. Syst. 41 (2007) 501–520. | DOI | MR | Zbl

Y. Liu, S. Lu, J. Chen and S.-H. Sze, Greedy localization and color-coding: improved matching and packing algorithms. In Proc. of the International Workshop on Parameterized and Exact Computation, IWPEC’06, edited by H.L. Bodlaender and M.A. Langston. Vol. 4169 of Lecture Notes in Computer Science. Springer-Verlag (2006) 84–95. | MR | Zbl

D. Marx, Parameterized complexity and approximation algorithms. Comput. J. 51 (2008) 60–78. | DOI

D. Moshkovitz, The projection games conjecture and the NP-hardness of $lnn$-approximating set-cover. In Proc. of Workshop on Approximation Algorithms for Combinatorial Optimization Problems and Workshop on Randomization and Computation, APPROX-RANDOM’12, edited by A. Gupta, K. Jansen, J.D.P. Rolim and R.A. Servedio. Vol. 7408 of Lecture Notes in Computer Science. Springer-Verlag (2012) 276–287. | MR

R. Niedermeier, Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford (2006). | MR | Zbl

C.H. Papadimitriou, Computational complexity. Addison-Wesley (1994). | MR | Zbl

C.H. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and complexity. Prentice Hall, New Jersey (1981). | MR | Zbl

P. Skowron and P. Faliszewski, In Fully proportional representation with approval ballots: approximating the maxcover problem with bounded frequencies in FPT time. AAAI Conference on Artificial Intelligence (2015). | MR