Document Open Access Logo

Incremental (1-ε)-Approximate Dynamic Matching in O(poly(1/ε)) Update Time

Authors Joakim Blikstad , Peter Kiss

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.22.pdf
  • Filesize: 0.91 MB
  • 19 pages

Document Identifiers

Author Details

Joakim Blikstad
  • KTH Royal Institute of Technology, Stockholm, Sweden
Peter Kiss
  • Max-Planck-Institut für Informatik, Saarbrücken, Germany
  • University of Warwick, Coventry, UK

Funding

  • Blikstad, Joakim: Partially supported by the Swedish Research Council (Reg. No. 2019-05622).
  • Kiss, Peter: Partially supported by Engineering and Physical Sciences Research Council, UK (EPSRC) Grant EP/S03353X/1.

Acknowledgements

We thank Danupon Nanongkai for insightful discussions and valuable comments throughout the development of this work. Part of this work was done while the authors visited the Max Planck Institute of Informatics, Saarbrücken.

Cite As Get BibTex

Joakim Blikstad and Peter Kiss. Incremental (1-ε)-Approximate Dynamic Matching in O(poly(1/ε)) Update Time. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.22

Abstract

In the dynamic approximate maximum bipartite matching problem we are given bipartite graph G undergoing updates and our goal is to maintain a matching of G which is large compared the maximum matching size μ(G). We define a dynamic matching algorithm to be α (respectively (α, β))-approximate if it maintains matching M such that at all times |M | ≥ μ(G) ⋅ α (respectively |M| ≥ μ(G) ⋅ α - β). 
We present the first deterministic (1-ε)-approximate dynamic matching algorithm with O(poly(ε^{-1})) amortized update time for graphs undergoing edge insertions. Previous solutions either required super-constant [Gupta FSTTCS'14, Bhattacharya-Kiss-Saranurak SODA'23] or exponential in 1/ε [Grandoni-Leonardi-Sankowski-Schwiegelshohn-Solomon SODA'19] update time. Our implementation is arguably simpler than the mentioned algorithms and its description is self contained. Moreover, we show that if we allow for additive (1, ε⋅n)-approximation our algorithm seamlessly extends to also handle vertex deletions, on top of edge insertions. This makes our algorithm one of the few small update time algorithms for (1-ε)-approximate dynamic matching allowing for updates both increasing and decreasing the maximum matching size of G in a fully dynamic manner. 
Our algorithm relies on the weighted variant of the celebrated Edge-Degree-Constrained-Subgraph (EDCS) datastructure introduced by [Bernstein-Stein ICALP'15]. As far as we are aware we introduce the first application of the weighted-EDCS for arbitrarily dense graphs. We also present a significantly simplified proof for the approximation ratio of weighed-EDCS as a matching sparsifier compared to [Bernstein-Stein], as well as simple descriptions of a fractional matching and fractional vertex cover defined on top of the EDCS. Considering the wide range of applications EDCS has found in settings such as streaming, sub-linear, stochastic and more we hope our techniques will be of independent research interest outside of the dynamic setting.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Bipartite Matching
  • Incremental Matching
  • Dynamic Algorithms
  • Approximation Algorithms
  • EDCS

Metrics

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

Related Versions

References

  1. Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, and Barna Saha. Dynamic set cover: improved algorithms and lower bounds. In STOC, pages 114-125. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316376.
  2. Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, and David Wajc. Dynamic matching: Reducing integral algorithms to approximately-maximal fractional algorithms. In ICALP, volume 107 of LIPIcs, pages 7:1-7:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPICS.ICALP.2018.7.
  3. Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, and Cliff Stein. Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In SODA, pages 1616-1635. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.98.
  4. Sepehr Assadi and Soheil Behnezhad. Beating two-thirds for random-order streaming matching. In ICALP, volume 198 of LIPIcs, pages 19:1-19:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPICS.ICALP.2021.19.
  5. Sepehr Assadi and Aaron Bernstein. Towards a unified theory of sparsification for matching problems. In SOSA, volume 69 of OASIcs, pages 11:1-11:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/OASICS.SOSA.2019.11.
  6. Surender Baswana, Manoj Gupta, and Sandeep Sen. Fully dynamic maximal matching in O(log n) update time (corrected version). SIAM J. Comput., 47(3):617-650, 2018. Announced at FOCS'11. URL: https://doi.org/10.1137/16M1106158.
  7. Soheil Behnezhad. Improved analysis of EDCS via gallai-edmonds decomposition. CoRR, abs/2110.05746, 2021. Google Scholar
  8. Soheil Behnezhad. Dynamic algorithms for maximum matching size. In SODA, pages 129-162. SIAM, 2023. URL: https://doi.org/10.1137/1.9781611977554.CH6.
  9. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. Fully dynamic maximal independent set with polylogarithmic update time. In FOCS, pages 382-405. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00032.
  10. Soheil Behnezhad and Sanjeev Khanna. New trade-offs for fully dynamic matching via hierarchical EDCS. In SODA, pages 3529-3566. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.140.
  11. Soheil Behnezhad, Jakub Lacki, and Vahab S. Mirrokni. Fully dynamic matching: Beating 2-approximation in Δ^ε update time. In SODA, pages 2492-2508. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.152.
  12. Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein. Sublinear time algorithms and complexity of approximate maximum matching. In STOC, pages 267-280. ACM, 2023. URL: https://doi.org/10.1145/3564246.3585231.
  13. Aaron Bernstein. Improved bounds for matching in random-order streams. In ICALP, volume 168 of LIPIcs, pages 12:1-12:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPICS.ICALP.2020.12.
  14. Aaron Bernstein, Sebastian Forster, and Monika Henzinger. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Trans. Algorithms, 17(4):29:1-29:51, 2021. Announced at SODA'19. URL: https://doi.org/10.1145/3469833.
  15. Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing. In FOCS, pages 1123-1134. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00108.
  16. Aaron Bernstein and Cliff Stein. Fully dynamic matching in bipartite graphs. In ICALP (1), volume 9134 of Lecture Notes in Computer Science, pages 167-179. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-47672-7_14.
  17. Aaron Bernstein and Cliff Stein. Faster fully dynamic matchings with small approximation ratios. In SODA, pages 692-711. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.CH50.
  18. Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger. Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time. In IPCO, volume 10328 of Lecture Notes in Computer Science, pages 86-98. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-59250-3_8.
  19. Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. Deterministic fully dynamic data structures for vertex cover and matching. SIAM J. Comput., 47(3):859-887, 2018. Announced at SODA'15. URL: https://doi.org/10.1137/140998925.
  20. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. New deterministic approximation algorithms for fully dynamic matching. In STOC, pages 398-411. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897568.
  21. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. Fully dynamic approximate maximum matching and minimum vertex cover in O(log^3 n) worst case update time. In SODA, pages 470-489. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.30.
  22. Sayan Bhattacharya and Peter Kiss. Deterministic rounding of dynamic fractional matchings. In ICALP, volume 198 of LIPIcs, pages 27:1-27:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPICS.ICALP.2021.27.
  23. Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak. Dynamic algorithms for packing-covering lps via multiplicative weight updates. In SODA, pages 1-47. SIAM, 2023. URL: https://doi.org/10.1137/1.9781611977554.CH1.
  24. Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak. Sublinear algorithms for (1.5+ε)-approximate matching. In STOC, pages 254-266. ACM, 2023. URL: https://doi.org/10.1145/3564246.3585252.
  25. Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, and David Wajc. Dynamic matching with better-than-2 approximation in polylogarithmic update time. In SODA, pages 100-128. SIAM, 2023. URL: https://doi.org/10.1137/1.9781611977554.CH5.
  26. Sayan Bhattacharya and Janardhan Kulkarni. Deterministically maintaining a (2 + ε)-approximate minimum vertex cover in O(1/ε²) amortized update time. In SODA, pages 1872-1885. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.113.
  27. Joakim Blikstad and Peter Kiss. Incremental (1-(epsilon))-approximate dynamic matching in O(poly(1/(epsilon))) update time. CoRR, abs/2302.08432, 2023. URL: https://doi.org/10.48550/arXiv.2302.08432.
  28. Moses Charikar and Shay Solomon. Fully dynamic almost-maximal matching: Breaking the polynomial worst-case time barrier. In ICALP, volume 107 of LIPIcs, pages 33:1-33:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPICS.ICALP.2018.33.
  29. Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In FOCS, pages 612-623. IEEE, 2022. URL: https://doi.org/10.1109/FOCS54457.2022.00064.
  30. Jack Edmonds and Richard M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM, 19(2):248-264, 1972. URL: https://doi.org/10.1145/321694.321699.
  31. Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski, Chris Schwiegelshohn, and Shay Solomon. (1 + ε)-approximate incremental matching in constant deterministic amortized time. In SODA, pages 1886-1898. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.114.
  32. Fabrizio Grandoni, Chris Schwiegelshohn, Shay Solomon, and Amitai Uzrad. Maintaining an EDCS in general graphs: Simpler, density-sensitive and with worst-case time bounds. In SOSA, pages 12-23. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977066.2.
  33. Manoj Gupta. Maintaining approximate maximum matching in an incremental bipartite graph in polylogarithmic update time. In FSTTCS, volume 29 of LIPIcs, pages 227-239. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. URL: https://doi.org/10.4230/LIPICS.FSTTCS.2014.227.
  34. Manoj Gupta and Richard Peng. Fully dynamic (1+ e)-approximate matchings. In FOCS, pages 548-557. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/FOCS.2013.65.
  35. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In STOC, pages 21-30. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746609.
  36. John E. Hopcroft and Richard M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2(4):225-231, 1973. URL: https://doi.org/10.1137/0202019.
  37. Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. Regularized box-simplex games and dynamic decremental bipartite matching. In ICALP, volume 229 of LIPIcs, pages 77:1-77:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPICS.ICALP.2022.77.
  38. Peter Kiss. Deterministic dynamic matching in worst-case update time. In ITCS, volume 215 of LIPIcs, pages 94:1-94:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPICS.ITCS.2022.94.
  39. Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 1955. Google Scholar
  40. Marcin Mucha and Piotr Sankowski. Maximum matchings via gaussian elimination. In FOCS, pages 248-255. IEEE Computer Society, 2004. URL: https://doi.org/10.1109/FOCS.2004.40.
  41. Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. ACM Trans. Algorithms, 12(1):7:1-7:15, 2016. Announced at STOC'13. URL: https://doi.org/10.1145/2700206.
  42. Krzysztof Onak and Ronitt Rubinfeld. Maintaining a large matching and a small vertex cover. In STOC, pages 457-464. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806753.
  43. David Peleg and Shay Solomon. Dynamic (1 + ε)-approximate matchings: A density-sensitive approach. In SODA, pages 712-729. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.CH51.
  44. Mohammad Roghani, Amin Saberi, and David Wajc. Beating the folklore algorithm for dynamic matching. In ITCS, volume 215 of LIPIcs, pages 111:1-111:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPICS.ITCS.2022.111.
  45. Piotr Sankowski. Faster dynamic matchings and vertex connectivity. In SODA, pages 118-126. SIAM, 2007. Google Scholar
  46. Shay Solomon. Fully dynamic maximal matching in constant update time. In FOCS, pages 325-334. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/FOCS.2016.43.
  47. David Wajc. Rounding dynamic matchings against an adaptive adversary. In STOC, pages 194-207. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384258.
  48. Da Wei Zheng and Monika Henzinger. Multiplicative auction algorithm for approximate maximum weight bipartite matching. In IPCO, volume 13904 of Lecture Notes in Computer Science, pages 453-465. Springer, 2023. URL: https://doi.org/10.1007/978-3-031-32726-1_32.
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