Document Open Access Logo

Decremental Matching in General Graphs

Authors Sepehr Assadi, Aaron Bernstein, Aditi Dudeja

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.11.pdf
  • Filesize: 1.02 MB
  • 19 pages

Document Identifiers

Author Details

Sepehr Assadi
  • Department of Computer Science, Rutgers University, Piscataway, NJ, USA
Aaron Bernstein
  • Department of Computer Science, Rutgers University, Piscataway, NJ, USA
Aditi Dudeja
  • Department of Computer Science, Rutgers University, Piscataway, NJ, USA

Funding

  • Assadi, Sepehr: Supported in part by an NSF CAREER Grant CCF-2047061, and a gift from Google Research.
  • Bernstein, Aaron: Funded by NSF CAREER Grant 1942010.

Cite AsGet BibTex

Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja. Decremental Matching in General Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.11

Abstract

We consider the problem of maintaining an approximate maximum integral matching in a dynamic graph G, while the adversary makes changes to the edges of the graph. The goal is to maintain a (1+ε)-approximate maximum matching for constant ε > 0, while minimizing the update time. In the fully dynamic setting, where both edge insertion and deletions are allowed, Gupta and Peng (see [Manoj Gupta and Richard Peng, 2013]) gave an algorithm for this problem with an update time of O(√m/ε²). Motivated by the fact that the O_ε(√m) barrier is hard to overcome (see Henzinger, Krinninger, Nanongkai, and Saranurak [Henzinger et al., 2015]; Kopelowitz, Pettie, and Porat [Kopelowitz et al., 2016]), we study this problem in the decremental model, where the adversary is only allowed to delete edges. Recently, Bernstein, Probst-Gutenberg, and Saranurak (see [Bernstein et al., 2020]) gave an O(poly({log n}/ε)) update time decremental algorithm for this problem in bipartite graphs. However, beating O(√m) update time remained an open problem for general graphs. In this paper, we bridge the gap between bipartite and general graphs, by giving an O_ε(poly(log n)) update time algorithm that maintains a (1+ε)-approximate maximum integral matching under adversarial deletions. Our algorithm is randomized, but works against an adaptive adversary. Together with the work of Grandoni, Leonardi, Sankowski, Schwiegelshohn, and Solomon [Fabrizio Grandoni et al., 2019] who give an O_ε(1) update time algorithm for general graphs in the incremental (insertion-only) model, our result essentially completes the picture for partially dynamic matching.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
Keywords
  • Dynamic algorithms
  • matching
  • primal-dual algorithms

Metrics

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

References

  1. Kook Jin Ahn and Sudipto Guha. Linear programming in the semi-streaming model with application to the maximum matching problem. In Proceedings of the 38th International Conference on Automata, Languages and Programming - Volume Part II, ICALP'11, pages 526-538, Berlin, Heidelberg, 2011. Springer-Verlag. Google Scholar
  2. Nima Anari and Vijay V. Vazirani. Matching is as easy as the decision problem, in the nc model. In ITCS, 2020. Google Scholar
  3. Nima Anari and Vijay V. Vazirani. Planar graph perfect matching is in nc. J. ACM, 67(4), May 2020. URL: https://doi.org/10.1145/3397504.
  4. Sepehr Assadi, Sanjeev Khanna, and Yang Li. The stochastic matching problem with (very) few queries. ACM Transactions on Economics and Computation (TEAC), 7(3):1-19, 2019. Google Scholar
  5. 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. URL: https://doi.org/10.1137/16M1106158.
  6. Soheil Behnezhad and Sanjeev Khanna. New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS, pages 3529-3566. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.140.
  7. Soheil Behnezhad, Jakub Łącki, and Vahab Mirrokni. Fully dynamic matching: Beating 2-approximation in δ^ε update time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2492-2508. SIAM, 2020. Google Scholar
  8. 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. URL: https://doi.org/10.1145/3469833.
  9. Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1123-1134. IEEE, 2020. Google Scholar
  10. Aaron Bernstein and Cliff Stein. Fully dynamic matching in bipartite graphs. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, 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.
  11. Aaron Bernstein and Cliff Stein. Faster fully dynamic matchings with small approximation ratios. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 692-711. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch50.
  12. Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger. Deterministic dynamic matching in O(1) update time. Algorithmica, 82(4):1057-1080, 2020. URL: https://doi.org/10.1007/s00453-019-00630-4.
  13. 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 '15, pages 785-804, USA, 2015. Society for Industrial and Applied Mathematics. Google Scholar
  14. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. New deterministic approximation algorithms for fully dynamic matching. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 398-411, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2897518.2897568.
  15. 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 Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 470-489. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.30.
  16. Sayan Bhattacharya and Peter Kiss. Deterministic rounding of dynamic fractional matchings. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), 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.
  17. Bartlomiej Bosek, Dariusz Leniowski, Piotr Sankowski, and Anna Zych. Online bipartite matching in offline time. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 384-393, 2014. URL: https://doi.org/10.1109/FOCS.2014.48.
  18. 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 Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 1326-1344. SIAM, 2016. Google Scholar
  19. Søren Dahlgaard. On the hardness of partially dynamic graph problems and connections to diameter. CoRR, abs/1602.06705, 2016. URL: http://arxiv.org/abs/1602.06705.
  20. Ran Duan and Seth Pettie. Linear-time approximation for maximum weight matching. Journal of the ACM (JACM), 61(1):1-23, 2014. Google Scholar
  21. Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009. URL: http://www.cambridge.org/gb/knowledge/isbn/item2327542/.
  22. Sebastian Eggert, Lasse Kliemann, Peter Munstermann, and Anand Srivastav. Bipartite matching in the semi-streaming model. Algorithmica, 63:490-508, 2011. Google Scholar
  23. Stephen Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-nc. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 754-763, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2897518.2897564.
  24. Manuela Fischer, Slobodan Mitrovic, and Jara Uitto. Deterministic (1+ε)-approximate maximum matching with poly(1/ε) passes in the semi-streaming model. CoRR, abs/2106.04179, 2021. URL: http://arxiv.org/abs/2106.04179.
  25. Harold N. Gabow and Robert E. Tarjan. Faster scaling algorithms for general graph matching problems. J. ACM, 38(4):815-853, October 1991. URL: https://doi.org/10.1145/115234.115366.
  26. Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski, Chris Schwiegelshohn, and Shay Solomon. (1 + ε)-approximate incremental matching in constant deterministic amortized time. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1886-1898. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.114.
  27. Fabrizio Grandoni, Chris Schwiegelshohn, Shay Solomon, and Amitai Uzrad. Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds, pages 12-23. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977066.2.
  28. Manoj Gupta. Maintaining approximate maximum matching in an incremental bipartite graph in polylogarithmic update time. In FSTTCS, 2014. Google Scholar
  29. Manoj Gupta and Richard Peng. Fully dynamic (1+ e)-approximate matchings. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 548-557, 2013. Google Scholar
  30. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 21-30, 2015. Google Scholar
  31. John E. Hopcroft and Richard M. Karp. An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2:225-231, 1973. Google Scholar
  32. A. Karzanov. On finding a maximum flow in a network with special structure and some applications. Matematicheskie Voprosy Upravleniya Proizvodstvom (L.A. Lyusternik, ed.), Moscow State Univ. Press, Moscow, 1973, Issue 5, pp. 81–94, in Russian., 1973. Google Scholar
  33. Peter Kiss. Deterministic dynamic matching in worst-case update time. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, 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.
  34. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3sum conjecture. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 1272-1287. SIAM, 2016. Google Scholar
  35. Meena Mahajan and Kasturi R. Varadarajan. A new nc-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract). In STOC '00, 2000. Google Scholar
  36. Silvio Micali and Vijay V. Vazirani. An o(sqrt(|v|) |e|) algorithm for finding maximum matching in general graphs. In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980, pages 17-27. IEEE Computer Society, 1980. URL: https://doi.org/10.1109/SFCS.1980.12.
  37. Mohammad Roghani, Amin Saberi, and David Wajc. Beating the Folklore Algorithm for Dynamic Matching. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 111:1-111:23, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.111.
  38. Alexander Schrijver et al. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003. Google Scholar
  39. Shay Solomon. Fully dynamic maximal matching in constant update time. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 325-334. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/FOCS.2016.43.
  40. Ola Svensson and Jakub Tarnawski. The matching problem in general graphs is in quasi-nc. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 696-707, 2017. Google Scholar
  41. David Wajc. Rounding dynamic matchings against an adaptive adversary. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 194-207, 2020. 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 Imprint Privacy Contact