Document Open Access Logo

Deterministic Rounding of Dynamic Fractional Matchings

Authors Sayan Bhattacharya, Peter Kiss

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.27.pdf
  • Filesize: 0.69 MB
  • 14 pages

Document Identifiers

Author Details

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

Funding

  • Bhattacharya, Sayan: Supported by EPSRC Grant EP/S03353X/1.

Cite As Get BibTex

Sayan Bhattacharya and Peter Kiss. Deterministic Rounding of Dynamic Fractional Matchings. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.27

Abstract

We present a framework for deterministically rounding a dynamic fractional matching. Applying our framework in a black-box manner on top of existing fractional matching algorithms, we derive the following new results: (1) The first deterministic algorithm for maintaining a (2-δ)-approximate maximum matching in a fully dynamic bipartite graph, in arbitrarily small polynomial update time. (2) The first deterministic algorithm for maintaining a (1+δ)-approximate maximum matching in a decremental bipartite graph, in polylogarithmic update time. (3) The first deterministic algorithm for maintaining a (2+δ)-approximate maximum matching in a fully dynamic general graph, in small polylogarithmic (specifically, O(log⁴ n)) update time. These results are respectively obtained by applying our framework on top of the fractional matching algorithms of Bhattacharya et al. [STOC'16], Bernstein et al. [FOCS'20], and Bhattacharya and Kulkarni [SODA'19]. 
Previously, there were two known general-purpose rounding schemes for dynamic fractional matchings. Both these schemes, by Arar et al. [ICALP'18] and Wajc [STOC'20], were randomized. 
Our rounding scheme works by maintaining a good matching-sparsifier with bounded arboricity, and then applying the algorithm of Peleg and Solomon [SODA'16] to maintain a near-optimal matching in this low arboricity graph. To the best of our knowledge, this is the first dynamic matching algorithm that works on general graphs by using an algorithm for low-arboricity graphs as a black-box subroutine. This feature of our rounding scheme might be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Matching
  • Dynamic Algorithms
  • Data Structures

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, 2019. Google Scholar
  2. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In FOCS, 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 ICALP, 2018. Google Scholar
  4. Sepehr Assadi and Aaron Bernstein. Towards a unified theory of sparsification for matching problems. In SOSA, 2019. Google Scholar
  5. S. Baswana, M. Gupta, and S. Sen. Fully dynamic maximal matching in O(log n) update time. In FOCS, 2011. Google Scholar
  6. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. Fully dynamic maximal independent set with polylogarithmic update time. In FOCS, 2019. Google Scholar
  7. Soheil Behnezhad, Jakub Lacki, and Vahab S. Mirrokni. Fully dynamic matching: Beating 2-approximation in O(Δ^ε) update time. In SODA, 2020. Google Scholar
  8. Aaron Bernstein, Sebastian Forster, and Monika Henzinger. A deamortization approach for dynamic spanner and dynamic maximal matching. In SODA, 2019. Google Scholar
  9. Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing. In FOCS, 2020. Google Scholar
  10. Aaron Bernstein and Cliff Stein. Fully dynamic matching in bipartite graphs. In ICALP, 2015. Google Scholar
  11. Aaron Bernstein and Cliff Stein. Faster fully dynamic matchings with small approximation ratios. In SODA, 2016. Google Scholar
  12. Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger. Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time. In IPCO, 2017. Google Scholar
  13. Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. Deterministic fully dynamic data structures for vertex cover and matching. In SODA, 2015. Google Scholar
  14. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. New deterministic approximation algorithms for fully dynamic matching. In STOC, 2016. Google Scholar
  15. 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 SODA, 2017. Google Scholar
  16. Sayan Bhattacharya and Janardhan Kulkarni. Deterministically maintaining a (2+ε)-approximate minimum vertex cover in O(1/ε²) amortized update time. In SODA, 2019. Google Scholar
  17. Moses Charikar and Shay Solomon. Fully dynamic almost-maximal matching: Breaking the polynomial barrier for worst-case time bounds. In ICALP, 2018. Google Scholar
  18. Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. In FOCS, 2020. Google Scholar
  19. Ran Duan, Haoqing He, and Tianyi Zhang. Dynamic edge coloring with improved approximation. In Timothy M. Chan, editor, SODA, 2019. Google Scholar
  20. Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, and Christian Wulff-Nilsen. Decremental APSP in directed graphs versus an adaptive adversary. CoRR, abs/2010.00937, 2020. URL: http://arxiv.org/abs/2010.00937.
  21. Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, and Zihan Tan. The expander hierarchy and its applications to dynamic graph algorithms. In SODA, 2021. Google Scholar
  22. Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski, Chris Schwiegelshohn, and Shay Solomon. (1 + ε)-approximate incremental matching in constant deterministic amortized time. In SODA, 2019. Google Scholar
  23. Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi. Online and dynamic algorithms for set cover. In STOC, 2017. Google Scholar
  24. Manoj Gupta. Maintaining approximate maximum matching in an incremental bipartite graph in polylogarithmic update time. In FSTTCS, 2014. Google Scholar
  25. Manoj Gupta and Richard Peng. Fully dynamic (1+ε)-approximate matchings. In FOCS, 2013. Google Scholar
  26. Monika Henzinger and Valerie King. Randomized dynamic graph algorithms with polylogarithmic time per operation. In STOC, 1995. Google Scholar
  27. 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, 2015. Google Scholar
  28. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723-760, 2001. Google Scholar
  29. Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, and Shay Solomon. Orienting fully dynamic graphs with worst-case time bounds. In ICALP, 2014. Google Scholar
  30. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3sum conjecture. In SODA, 2016. Google Scholar
  31. Kasper Green Larsen. The cell probe complexity of dynamic range counting. In Howard J. Karloff and Toniann Pitassi, editors, STOC, 2012. Google Scholar
  32. Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. Dynamic minimum spanning forest with subpolynomial worst-case update time. In FOCS, 2017. Google Scholar
  33. C St JA Nash-Williams. Edge-disjoint spanning trees of finite graphs. Journal of the London Mathematical Society, 1(1):445-450, 1961. Google Scholar
  34. Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. In STOC, 2013. Google Scholar
  35. Krzysztof Onak and Ronitt Rubinfeld. Maintaining a large matching and a small vertex cover. In STOC, 2010. Google Scholar
  36. Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In STOC, 2010. Google Scholar
  37. David Peleg and Shay Solomon. Dynamic (1+ε)-approximate matchings: A density-sensitive approach. In SODA, 2016. Google Scholar
  38. Piotr Sankowski. Faster dynamic matchings and vertex connectivity. In SODA, 2007. Google Scholar
  39. Shay Solomon. Fully dynamic maximal matching in constant update time. In FOCS, 2016. Google Scholar
  40. David Wajc. Rounding dynamic matchings against an adaptive adversary. In STOC, 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 About DROPS Imprint Privacy Contact