Document Open Access Logo

Deterministic Dynamic Matching in Worst-Case Update Time

Author Peter Kiss

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.94.pdf
  • Filesize: 0.82 MB
  • 21 pages

Document Identifiers

Author Details

Peter Kiss
  • Department of Computer Science, University of Warwick, Coventry, UK

Funding

  • Kiss, Peter: This work is supported by Engineering and Physical Sciences Research Council, UK (EPSRC) GrantEP/S03353X/1.

Acknowledgements

We would like to thank Sayan Bhattacharya and Thatchaphol Saranurak for helpful discussions. Further we would like to thank Thatchaphol Saranurak for suggesting to use lossless expanders to deterministically generate ε-matching preserving partitionings.

Cite AsGet BibTex

Peter Kiss. Deterministic Dynamic Matching in Worst-Case Update Time. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 94:1-94:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.94

Abstract

We present deterministic algorithms for maintaining a (3/2 + ε) and (2 + ε)-approximate maximum matching in a fully dynamic graph with worst-case update times Ô(√n) and Õ(1) respectively. The fastest known deterministic worst-case update time algorithms for achieving approximation ratio (2 - δ) (for any δ > 0) and (2 + ε) were both shown by Roghani et al. [arXiv'2021] with update times O(n^{3/4}) and O_ε(√n) respectively. We close the gap between worst-case and amortized algorithms for the two approximation ratios as the best deterministic amortized update times for the problem are O_ε(√n) and Õ(1) which were shown in Bernstein and Stein [SODA'2021] and Bhattacharya and Kiss [ICALP'2021] respectively. The algorithm achieving (3/2 + ε) approximation builds on the EDCS concept introduced by the influential paper of Bernstein and Stein [ICALP'2015]. Say that H is a (α, δ)-approximate matching sparsifier if at all times H satisfies that μ(H) ⋅ α + δ ⋅ n ≥ μ(G) (define (α, δ)-approximation similarly for matchings). We show how to maintain a locally damaged version of the EDCS which is a (3/2 + ε, δ)-approximate matching sparsifier. We further show how to reduce the maintenance of an α-approximate maximum matching to the maintenance of an (α, δ)-approximate maximum matching building based on an observation of Assadi et al. [EC'2016]. Our reduction requires an update time blow-up of Ô(1) or Õ(1) and is deterministic or randomized against an adaptive adversary respectively. To achieve (2 + ε)-approximation we improve on the update time guarantee of an algorithm of Bhattacharya and Kiss [ICALP'2021]. In order to achieve both results we explicitly state a method implicitly used in Nanongkai and Saranurak [STOC'2017] and Bernstein et al. [arXiv'2020] which allows to transform dynamic algorithms capable of processing the input in batches to a dynamic algorithms with worst-case update time. Independent Work: Independently and concurrently to our work Grandoni et al. [arXiv'2021] has presented a fully dynamic algorithm for maintaining a (3/2 + ε)-approximate maximum matching with deterministic worst-case update time O_ε(√n).

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • Dynamic Algorithms
  • Matching
  • Approximate Matching
  • 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 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 114-125, 2019. Google Scholar
  2. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 434-443. IEEE, 2014. Google Scholar
  3. Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, and David Wajc. Dynamic matching: Reducing integral algorithms to approximately-maximal fractional algorithms. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 7:1-7:16, 2018. Google Scholar
  4. Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein. Coresets meet edcs: algorithms for matching and vertex cover on massive graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1616-1635. SIAM, 2019. Google Scholar
  5. Sepehr Assadi and Soheil Behnezhad. Beating two-thirds for random-order streaming matching. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 19:1-19:13, 2021. Google Scholar
  6. Sepehr Assadi and Aaron Bernstein. Towards a unified theory of sparsification for matching problems. In 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8-9, 2019, San Diego, CA, USA, volume 69 of OASICS, 2019. Google Scholar
  7. 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
  8. Surender Baswana, Manoj Gupta, and Sandeep Sen. Fully dynamic maximal matching in o(log (n)) update time. SIAM Journal on Computing, 44(1):88-113, 2015. Google Scholar
  9. Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. Stochastic matching with few queries:(1 - ε) approximation. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 1111-1124, 2020. Google Scholar
  10. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. Fully dynamic maximal independent set with polylogarithmic update time. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 382-405. IEEE, 2019. Google Scholar
  11. Soheil Behnezhad, Jakub Lacki, 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
  12. Radu Berinde, Anna C Gilbert, Piotr Indyk, Howard Karloff, and Martin J Strauss. Combining geometry and combinatorics: A unified approach to sparse signal recovery. In 2008 46th Annual Allerton Conference on Communication, Control, and Computing, pages 798-805. IEEE, 2008. Google Scholar
  13. Aaron Bernstein. Improved bounds for matching in random-order streams. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 12:1-12:13, 2020. Google Scholar
  14. Aaron Bernstein, Aditi Dudeja, and Zachary Langley. A framework for dynamic matching in weighted graphs. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 668-681. ACM, 2021. Google Scholar
  15. Aaron Bernstein, Sebastian Forster, and Monika Henzinger. A deamortization approach for dynamic spanner and dynamic maximal matching. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1899-1918. SIAM, 2019. Google Scholar
  16. 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
  17. Aaron Bernstein and Cliff Stein. Fully dynamic matching in bipartite graphs. In International Colloquium on Automata, Languages, and Programming, pages 167-179. Springer, 2015. Google Scholar
  18. Aaron Bernstein and Cliff Stein. Faster fully dynamic matchings with small approximation ratios. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 692-711. SIAM, 2016. Google Scholar
  19. Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger. Deterministic fully dynamic approximate vertex cover and fractional matching in o(1) amortized update time. In International Conference on Integer Programming and Combinatorial Optimization, pages 86-98. Springer, 2017. Google Scholar
  20. Sayan Bhattacharya, Monika Henzinger, and Giuseppe F Italiano. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing, 47(3):859-887, 2018. Google Scholar
  21. 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, pages 398-411, 2016. Google Scholar
  22. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. Fully dynamic approximate maximum matching and minimum vertex cover in o(log³ (n)) worst case update time. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 470-489. SIAM, 2017. Google Scholar
  23. Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson. Randomness conductors and constant-degree lossless expanders. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 659-668, 2002. Google Scholar
  24. Moses Charikar and Shay Solomon. Fully dynamic almost-maximal matching: Breaking the polynomial barrier for worst-case time bounds. ICALP, 2017. Google Scholar
  25. Devdatt P Dubhashi and Desh Ranjan. Balls and bins: A study in negative dependence. BRICS Report Series, 3(25), 1996. Google Scholar
  26. Devdatt P Dubhashi and Desh Ranjan. Balls and bins: A study in negative dependence. BRICS Report Series, 3(25), 1996. Google Scholar
  27. M Gerasimov, V Kruglov, and A Volodin. On negatively associated random variables. Lobachevskii Journal of Mathematics, 33(1):47-55, 2012. Google Scholar
  28. Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski, Chris Schwiegelshohn, and Shay Solomon. (1+ε)-approximate incremental matching in constant deterministic amortized time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1886-1898. SIAM, 2019. Google Scholar
  29. Fabrizio Grandoni, Chris Schwiegelshohn, Shay Solomon, and Amitai Uzrad. Maintaining an edcs in general graphs: Simpler, density-sensitive and with worst-case time bounds, 2021. URL: http://arxiv.org/abs/2108.08825.
  30. 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, pages 537-550, 2017. Google Scholar
  31. Manoj Gupta. Maintaining approximate maximum matching in an incremental bipartite graph in polylogarithmic update time. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014. Google Scholar
  32. Manoj Gupta and Richard Peng. Fully dynamic 1 + ε-approximate matchings. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 548-557. IEEE, 2013. Google Scholar
  33. 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
  34. Monika Rauch Henzinger and Valerie King. Randomized dynamic graph algorithms with polylogarithmic time per operation. In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, pages 519-527, 1995. Google Scholar
  35. Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM (JACM), 48(4):723-760, 2001. Google Scholar
  36. Bruce M Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1131-1142. SIAM, 2013. Google Scholar
  37. 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
  38. Kasper Green Larsen. The cell probe complexity of dynamic range counting. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 85-94, 2012. Google Scholar
  39. Danupon Nanongkai and Thatchaphol Saranurak. Dynamic spanning forest with worst-case update time: adaptive, las vegas, and o(n^1/2 - ε)-time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1122-1129, 2017. Google Scholar
  40. Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. ACM Transactions on Algorithms (TALG), 12(1):1-15, 2015. Google Scholar
  41. Krzysztof Onak and Ronitt Rubinfeld. Maintaining a large matching and a small vertex cover. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 457-464, 2010. Google Scholar
  42. Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 603-610, 2010. Google Scholar
  43. Mohammad Roghani, Amin Saberi, and David Wajc. Beating the folklore algorithm for dynamic matching. arXiv preprint arXiv:2106.10321, 2021. Google Scholar
  44. Piotr Sankowski. Faster dynamic matchings and vertex connectivity. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 118-126, 2007. Google Scholar
  45. Peter Kiss Sayan Bhattacharya. Deterministic rounding of dynamic fractional matchings. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, volume 198 of LIPIcs, 2021. Google Scholar
  46. Noam Solomon and Shay Solomon. A generalized matching reconfiguration problem. In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, LIPIcs, 2021. Google Scholar
  47. Shay Solomon. Fully dynamic maximal matching in constant update time. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 325-334. IEEE, 2016. Google Scholar
  48. Aaron Bernstein Jan van den Brand Maximilian Probst Gutenberg Danupon Nanongkai Thatchaphol Saranurak Aaron Sidford He Sun. Fully-dynamic graph sparsifiers against an adaptive adversary. CoRR, abs/2004.08432, 2020. Google Scholar
  49. David Wajc. Rounding dynamic matchings against an adaptive adversary. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 194-207. ACM, 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