Document Open Access Logo

Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms

Authors Chien-Chung Huang, François Sellier

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2022.27.pdf
  • Filesize: 0.69 MB
  • 15 pages

Document Identifiers

Author Details

Chien-Chung Huang
  • CNRS, DI ENS, École normale supérieure, Université PSL, Paris, France
François Sellier
  • Université Paris Cité, CNRS, IRIF, F-75013, Paris, France, MINES ParisTech, Université PSL, F-75006, Paris, France

Funding

This work was funded by the grants ANR-19-CE48-0016 and ANR-18-CE40-0025-01 from the French National Research Agency (ANR).

Acknowledgements

The authors thank the anonymous reviewers for their helpful comments. One of them especially pointed out a mistake on a counter-example for gammoids in the submitted version.

Cite As Get BibTex

Chien-Chung Huang and François Sellier. Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SWAT.2022.27

Abstract

Given a graph with weights on the edges and a matroid imposed on the vertices, our problem is to choose a subset of vertices that is independent in the matroid, with the objective of maximizing the total weight of covered edges. This problem is a generalization of the much studied max k-vertex cover problem, where the matroid is the simple uniform matroid, and it is also a special case of maximizing a monotone submodular function under a matroid constraint.
In this work, we give a Fixed Parameter Tractable Approximation Scheme (FPT-AS) when the given matroid is a partition matroid, a laminar matroid, or a transversal matroid. Precisely, if k is the rank of the matroid, we obtain (1 - ε) approximation using (1/(ε))^{O(k)}n^{O(1)} time for partition and laminar matroids and using (1/(ε)+k)^{O(k)}n^{O(1)} time for transversal matroids. This extends a result of Manurangsi for uniform matroids [Pasin Manurangsi, 2018]. We also show that these ideas can be applied in the context of (single-pass) streaming algorithms.
Our FPT-AS introduces a new technique based on matroid union, which may be of independent interest in extremal combinatorics.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Maximum vertex cover
  • matroid
  • approximate kernel
  • streaming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alexander A. Ageev and Maxim I. Sviridenko. Approximation algorithms for maximum coverage and max cut with given sizes of parts. In IPCO 1999, 1999. Google Scholar
  2. Per Austrin and Aleksa Stankovic. Global cardinality constraints make approximating some max-2-csps harder. In APPROX/RANDOM 2019, pages 24:1-24:17, 2019. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.24.
  3. M. Babaioff, N. Immorlica, and R. Kleinberg. Matroids, secretary problems, and online mechanisms. In SODA, pages 434-443, 2007. Google Scholar
  4. Édouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, and Georgios Stamoulis. Purely combinatorial approximation algorithms for maximum k-vertex cover in bipartite graphs. Discrete Optimization, 27:26-56, 2018. Google Scholar
  5. Vladimir Braverman, Zaoxing Liu, Tejasvam Singh, N. V. Vinodchandran, and Lin F. Yang. New bounds for the CLIQUE-GAP problem using graph decomposition theory. Algorithmica, 80(2):652-667, 2018. URL: https://doi.org/10.1007/s00453-017-0277-5.
  6. Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a submodular set function subject to a matroid constraint (extended abstract). In Proc . 12th IPCO, pages 182-196, 2007. URL: https://doi.org/10.1007/978-3-540-72792-7_15.
  7. Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a submodular set function subject to a matroid constraint. SIAM J . Comput ., 40(6):1740-1766, 2011. Google Scholar
  8. Amit Chakrabarti and Sagar Kale. Submodular maximization meets streaming: Matchings, matroids and more. In Proc . 17th IPCO, pages 210-221, 2014. Google Scholar
  9. S. Chakraborty and O. Lachish. Improved competitive ratio for the matroid secretary prob- lem. In SODA, pages 1702-1712, 2012. Google Scholar
  10. Chandra Chekuri, Shalmoli Gupta, and Kent Quanrud. Streaming algorithms for submodular function maximization. In Proc . 42nd ICALP, pages 318-330, 2015. Google Scholar
  11. Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, and Sofya Vorotnikova. Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. In SODA 2016, pages 1326-1344, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch92.
  12. William H Cunningham. Testing membership in matroid polyhedra. Journal of Combinatorial Theory, Series B, 36(2):161-188, 1984. Google Scholar
  13. J. Edmonds and D.R. Fulkerson. Transversals and matroid partition. Journal of Research National Bureau of Standards Section B, 69:147-153, 1965. Google Scholar
  14. Uriel Feige and Michael Langberg. Approximation algorithms for maximization problems arising in graph partitioning. Journal of Algorithms, 41(2):174-211, 2001. Google Scholar
  15. M. Feldman, O. Svensson, and R. Zenklusen. A simple olog log(rank))-competitive al- gorithm for the matroid secretary problem. In SODA, pages 1189-1201, 2015. Google Scholar
  16. Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. Streaming submodular maximization with matroid and matching constraints. CoRR, abs/2107.07183, 2021. URL: http://arxiv.org/abs/2107.07183.
  17. Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, and Pasin Manurangsi. A survey on approximation in parameterized complexity: Hardness and algorithms. Algorithms, 13(6):146, 2020. URL: https://doi.org/10.3390/a13060146.
  18. Yuval Filmus and Justin Ward. A tight combinatorial algorithm for submodular maximization subject to a matroid constraint. In Proc . 53nd FOCS, 2012. Google Scholar
  19. Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke. Parameterized complexity of generalized vertex cover problems. In Algorithms and Data Structures, pages 36-48, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. Google Scholar
  20. Anupam Gupta, Euiwoong Lee, and Jason Li. Faster exact and approximate algorithms for k-cut. In FOCS 2018, pages 113-123. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00020.
  21. Qiaoming Han, Yinyu Ye, Hantao Zhang, and Jiawei Zhang. On approximation of max-vertex-cover. Eur. J. Oper. Res., 143(2):342-355, 2002. URL: https://doi.org/10.1016/S0377-2217(02)00330-2.
  22. Qiaoming Han, Yinyu Ye, and Jiawei Zhang. An improved rounding method and semidefinite programming relaxation for graph partition. Math. Program., 92(3):509-535, 2002. URL: https://doi.org/10.1007/s101070100288.
  23. Dorit S Hochbaum and Anu Pathria. Analysis of the greedy approach in covering problems. Naval Research Quarterly, 45:615-627, 1998. Google Scholar
  24. S. Im and Y. Wang. Secretary problems: laminar matroids and interval scheduling. In SODA, pages 1265-1274, 2011. Google Scholar
  25. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In STOC 2017, pages 224-237. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055456.
  26. Pasin Manurangsi. A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation. In SOSA 2019, pages 15:1-15:21, 2018. Google Scholar
  27. Pasin Manurangsi. Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In SODA, pages 62-81, 2020. Google Scholar
  28. Dániel Marx. Parameterized Complexity and Approximation Algorithms. The Computer Journal, 51(1):60-78, July 2008. Google Scholar
  29. Andrew McGregor, David Tench, and Hoa T. Vu. Maximum coverage in the data stream model: Parameterized and generalized. In ICDT 2021, volume 186, pages 12:1-12:20, 2021. URL: https://doi.org/10.4230/LIPIcs.ICDT.2021.12.
  30. L. Mirsky and H. Perfect. Applications of the notion of independence to problems of combinatorial analysis. Journal of Combinatorial Theory, 2:327-357, 1965. Google Scholar
  31. S. Muthukrishnan. Data Streams: Algorithms and Applications. Now Publishers Inc, January 2005. Google Scholar
  32. András Recski. Matroid Theory and its Applications in Electric Network Theory and in Statics. Springer-Verlag, 1989. Google Scholar
  33. Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency. Springer, 2003. Google Scholar
  34. J. Soto. Matroid secretary problem in the random assignment model. SIAM Journal on Computing, 42:178-211, 2013. Google Scholar
  35. D.J.A Welsh. Transversal theory and matroids. Canadian Journal of Mathematics, 21:1323-1302, 1969. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact