Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach

Authors Sepehr Assadi, Shay Solomon



PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.8.pdf
  • Filesize: 0.74 MB
  • 18 pages

Document Identifiers

Author Details

Sepehr Assadi
  • Rutgers University, New Brunswick, NJ, USA
Shay Solomon
  • Tel Aviv University, Israel

Cite AsGet BibTex

Sepehr Assadi and Shay Solomon. Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.8

Abstract

In the (fully) dynamic set cover problem, we have a collection of m sets from a universe of size n that undergo element insertions and deletions; the goal is to maintain an approximate set cover of the universe after each update. We give an O(f²) update time algorithm for this problem that achieves an f-approximation, where f is the maximum number of sets that an element belongs to; under the unique games conjecture, this approximation is best possible for any fixed f. This is the first algorithm for dynamic set cover with approximation ratio that exactly matches f (as opposed to almost f in prior work), as well as the first one with runtime independent of n,m (for any approximation factor of o(f³)). Prior to our work, the state-of-the-art algorithms for this problem were O(f²) update time algorithms of Gupta et al. [STOC'17] and Bhattacharya et al. [IPCO'17] with O(f³) approximation, and the recent algorithm of Bhattacharya {et al. } [FOCS'19] with O(f⋅log{n}/ε²) update time and (1+ε)⋅f approximation, improving the O(f²⋅log{n}/ε⁵) bound of Abboud et al. [STOC'19]. The key technical ingredient of our work is an algorithm for maintaining a maximal matching in a dynamic hypergraph of rank r - where each hyperedge has at most r vertices - that undergoes hyperedge insertions and deletions in O(r²) amortized update time; our algorithm is randomized, and the bound on the update time holds in expectation and with high probability. This result generalizes the maximal matching algorithm of Solomon [FOCS'16] with constant update time in ordinary graphs to hypergraphs, and is of independent merit; the previous state-of-the-art algorithms for set cover do not translate to (integral) matchings for hypergraphs, let alone a maximal one. Our quantitative result for the set cover problem is translated directly from this qualitative result for maximal matching using standard reductions. An important advantage of our approach over the previous ones for approximation (1+ε)⋅f (by Abboud et al. [STOC'19] and Bhattacharya et al. [FOCS'19]) is that it is inherently local and can thus be distributed efficiently to achieve low amortized round and message complexities.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Approximation algorithms
Keywords
  • dynamic graph algorithms
  • hypergraph
  • maximal matching
  • matching
  • set cover

Metrics

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

References

  1. Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, and Barna Saha. Dynamic set cover: improved algorithms and lower bounds. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 114-125, 2019. Google Scholar
  2. Shiri Antaki, Quanquan C. Liu, and Shay Solomon. Dynamic distributed MIS with improved bounds. CoRR, abs/2010.16177, 2020. URL: http://arxiv.org/abs/2010.16177.
  3. Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear update time. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 815-826, 2018. Google Scholar
  4. Sepehr Assadi and Shay Solomon. Fully dynamic set cover via hypergraph maximal matching: An optimal approximation through a local approach. arXiv preprint arXiv:2105.06889, 2021. Google Scholar
  5. S. Baswana, M. Gupta, and S. Sen. Fully dynamic maximal matching in O(log n) update time. In Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, October 23-25, 2011, pages 383-392, 2011 (see also SICOMP'15 version, and subsequent erratum). Google Scholar
  6. S. Bhattacharya, M. Henzinger, and G. F. Italiano. Deterministic fully dynamic data structures for vertex cover and matching. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 785-804, 2015. Google Scholar
  7. S. Bhattacharya, M. Henzinger, and D. Nanongkai. New deterministic approximation algorithms for fully dynamic matching. In STOC, 2016. Google Scholar
  8. S. Bhattacharya, M. Henzinger, and D. Nanongkai. Fully dynamic maximum matching and vertex cover in O(log³ n) worst case update time. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, January 16-19, 2017, pages 470-489, 2017. Google Scholar
  9. Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger. Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time. In Proceedings of the 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, pages 86-98, 2017. Google Scholar
  10. Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. Deterministic fully dynamic data structures for vertex cover and matching. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, January 4-6, 2015, pages 785-804, 2015. Google Scholar
  11. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. A new deterministic algorithm for dynamic set cover. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 406-423. IEEE, 2019. Google Scholar
  12. Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Xiaowei Wu. An improved algorithm for dynamic set cover. CoRR, abs/2002.11171, 2020. Google Scholar
  13. Sayan Bhattacharya and Janardhan Kulkarni. Deterministically maintaining a (2 + ε)-approximate minimum vertex cover in o(1/ε²) amortized update time. In SODA, 2019. Google Scholar
  14. Matthias Bonne and Keren Censor-Hillel. Distributed detection of cliques in dynamic networks. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, Proc. 46th ICALP, volume 132 of LIPIcs, pages 132:1-132:15, 2019. Google Scholar
  15. Keren Censor-Hillel, Elad Haramaty, and Zohar S. Karnin. Optimal dynamic distributed MIS. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 217-226, 2016. Google Scholar
  16. Moses Charikar and Shay Solomon. Fully dynamic almost-maximal matching: Breaking the polynomial worst-case time barrier. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, Proc. 45th ICALP, volume 107 of LIPIcs, pages 33:1-33:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  17. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 624-633, 2014. Google Scholar
  18. Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi. Online and dynamic algorithms for set cover. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 537-550, 2017. Google Scholar
  19. Haim Kaplan and Shay Solomon. Dynamic representations of sparse distributed networks: A locality-sensitive approach. In Christian Scheideler and Jeremy T. Fineman, editors, Proc. of 30th SPAA 2018, pages 33-42, 2018. Google Scholar
  20. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci., 74(3):335-349, 2008. Google Scholar
  21. Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. In Proceedings of the 45th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2013, Palo Alto, CA, USA, June 1-4, 2013, pages 745-754, 2013. Google Scholar
  22. Merav Parter, David Peleg, and Shay Solomon. Local-on-average distributed tasks. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 220-239, 2016. Google Scholar
  23. D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. Google Scholar
  24. D. Peleg and S. Solomon. Dynamic (1 + ε)-approximate matchings: A density-sensitive approach. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, 2016. Google Scholar
  25. S. Solomon. Fully dynamic maximal matching in constant update time. In Proceedings of the 57th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2016, New Brunswick, NJ, USA, October 9-11, 2016, pages 325-334, 2016. Google Scholar
  26. David P Williamson and David B Shmoys. The design of approximation algorithms. Cambridge university press, 2011. 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