Document Open Access Logo

Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms

Authors Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, David Wajc

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.7.pdf
  • Filesize: 0.51 MB
  • 16 pages

Document Identifiers

Author Details

Moab Arar
  • Tel Aviv University, Tel Aviv, Israel
Shiri Chechik
  • Tel Aviv University, Tel Aviv, Israel
Sarel Cohen
  • Tel Aviv University, Tel Aviv, Israel
Cliff Stein
  • Columbia University, New York, USA
David Wajc
  • Carnegie Mellon University, Pittsburgh, USA

Funding

  • Stein, Cliff: Supported in part by NSF grant CCF-1421161.
  • Wajc, David: Supported in part by NSF grants CCF-1527110, CCF-1618280 and NSF CAREER award CCF-1750808.

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.7

Abstract

We present a simple randomized reduction from fully-dynamic integral matching algorithms to fully-dynamic "approximately-maximal" fractional matching algorithms. Applying this reduction to the recent fractional matching algorithm of Bhattacharya, Henzinger, and Nanongkai (SODA 2017), we obtain a novel result for the integral problem. Specifically, our main result is a randomized fully-dynamic (2+epsilon)-approximate integral matching algorithm with small polylog worst-case update time. For the (2+epsilon)-approximation regime only a fractional fully-dynamic (2+epsilon)-matching algorithm with worst-case polylog update time was previously known, due to Bhattacharya et al. (SODA 2017). Our algorithm is the first algorithm that maintains approximate matchings with worst-case update time better than polynomial, for any constant approximation ratio. As a consequence, we also obtain the first constant-approximate worst-case polylogarithmic update time maximum weight matching algorithm.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
Keywords
  • Dynamic
  • Worst-case
  • Maximum Matching
  • Maximum Weight Matching

Metrics

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

Related Versions

References

  1. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Proceedings of the 55th Symposium on Foundations of Computer Science (FOCS), pages 434-443, 2014. Google Scholar
  2. Ittai Abraham and Shiri Chechik. Dynamic decremental approximate distance oracles with (1+ε,2) stretch. CoRR, abs/1307.1516, 2013. Google Scholar
  3. Ittai Abraham, Shiri Chechik, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. On dynamic approximate shortest paths for planar graphs with worst-case costs. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 740-753, 2016. Google Scholar
  4. Ittai Abraham, Shiri Chechik, and Sebastian Krinninger. Fully dynamic all-pairs shortest paths with worst-case update-time revisited. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 440-452, 2017. Google Scholar
  5. Ravindra K Ahuja, Thomas L Magnanti, and James B Orlin. Network flows - theory, algorithms, and applications. Prentice hall, 1993. Google Scholar
  6. Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, and David Wajc. Dynamic matching: Reducing integral algorithms to approximately-maximal fractional algorithms. CoRR, abs/1711.06625, 2017. URL: http://arxiv.org/abs/1711.06625.
  7. Giorgio Ausiello, Giuseppe F. Italiano, Alberto Marchetti-Spaccamela, and Umberto Nanni. Incremental algorithms for minimal length paths. Journal of Algorithms, 12(4):615-638, 1991. Google Scholar
  8. Surender Baswana, Manoj Gupta, and Sandeep Sen. Fully dynamic maximal matching in O (log n) update time. In Proceedings of the 52nd Symposium on Foundations of Computer Science (FOCS), pages 383-392, 2011. Google Scholar
  9. Surender Baswana, Manoj Gupta, and Sandeep Sen. Fully dynamic maximal matching in O(log n) update time. SIAM Journal on Computing (SICOMP), 44(1):88-113, 2015. Google Scholar
  10. Surender Baswana, Ramesh Hariharan, and Sandeep Sen. Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths. Journal of Algorithms, 62(2):74-92, 2007. Google Scholar
  11. Aaron Bernstein and Cliff Stein. Fully dynamic matching in bipartite graphs. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP), pages 167-179, 2015. Google Scholar
  12. Aaron Bernstein and Cliff Stein. Faster fully dynamic matchings with small approximation ratios. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 692-711, 2016. Google Scholar
  13. Sayan Bhattacharya, Monika Henzinger, and Giuseppe 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), pages 785-804, 2015. Google Scholar
  14. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. New deterministic approximation algorithms for fully dynamic matching. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 398-411, 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 Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 470-489, 2017. Google Scholar
  16. Moses Charikar and Shay Solomon. Fully dynamic almost-maximal matching: Breaking the polynomial barrier for worst-case time bounds. In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP), 2018. Google Scholar
  17. Michael B Cohen, Aleksander Mądry, Piotr Sankowski, and Adrian Vladu. Negative-weight shortest paths and unit capacity minimum cost flow in Õ (m^10/7 log W) time. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 752-771, 2017. Google Scholar
  18. Michael Crouch and Daniel M Stubbs. Improved streaming algorithms for weighted matching, via unweighted matching. In Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), page 96, 2014. Google Scholar
  19. Camil Demetrescu and Giuseppe F. Italiano. A new approach to dynamic all pairs shortest paths. Journal of the ACM (JACM), 51(6):968-992, 2004. Google Scholar
  20. Camil Demetrescu and Giuseppe F. Italiano. Fully dynamic all pairs shortest paths with real edge weights. Journal of Computer and System Sciences, 72(5):813-837, 2006. Google Scholar
  21. Ran Duan and Seth Pettie. Linear-time approximation for maximum weight matching. Journal of the ACM (JACM), 61(1):1, 2014. Google Scholar
  22. Jack Edmonds and Richard M Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM), 19(2):248-264, 1972. Google Scholar
  23. Michael L Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM), 34(3):596-615, 1987. Google Scholar
  24. Harold N Gabow. Data structures for weighted matching and nearest common ancestors with linking. In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 434-443, 1990. Google Scholar
  25. Harold N Gabow and Robert E Tarjan. Faster scaling algorithms for network problems. SIAM Journal on Computing (SICOMP), 18(5):1013-1036, 1989. Google Scholar
  26. Fabrizio Grandoni and Virginia Vassilevska Williams. Improved distance sensitivity oracles via fast single-source replacement paths. In Proceedings of the 53rd Symposium on Foundations of Computer Science (FOCS), pages 748-757, 2012. Google Scholar
  27. Manoj Gupta and Richard Peng. Fully dynamic (1+ε)-approximate matchings. In Proceedings of the 54th Symposium on Foundations of Computer Science (FOCS), pages 548-557, 2013. Google Scholar
  28. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Dynamic approximate all-pairs shortest paths: Breaking the o(mn) barrier and derandomization. In Proceedings of the 54th Symposium on Foundations of Computer Science (FOCS), pages 538-547, 2013. Google Scholar
  29. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Decremental single-source shortest paths on undirected graphs in near-linear total update time. In Proceedings of the 55th Symposium on Foundations of Computer Science (FOCS), pages 146-155, 2014. Google Scholar
  30. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pages 674-683, 2014. Google Scholar
  31. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A subquadratic-time algorithm for decremental single-source shortest paths. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1053-1072, 2014. Google Scholar
  32. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Improved algorithms for decremental single-source reachability on directed graphs. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP), pages 725-736, 2015. Google Scholar
  33. Monika Rauch Henzinger and Valerie King. Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing (SICOMP), 31(2):364-374, 2001. Google Scholar
  34. John E Hopcroft and Richard M Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. In Proceedings of the 12th Annual Symposium on Switching and Automata Theory (SWAT), pages 122-125, 1971. Google Scholar
  35. Zoran Ivkovic and Errol L Lloyd. Fully dynamic maintenance of vertex cover. In Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science, pages 99-111, 1993. Google Scholar
  36. Valerie King. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In Proceedings of the 40th Symposium on Foundations of Computer Science (FOCS), pages 81-91, 1999. Google Scholar
  37. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3sum conjecture. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1272-1287, 2016. Google Scholar
  38. László Lovász and Michael D Plummer. Matching theory, volume 367. American Mathematical Society, 2009. Google Scholar
  39. Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In Proceedings of the 54th Symposium on Foundations of Computer Science (FOCS), pages 253-262, 2013. Google Scholar
  40. Silvio Micali and Vijay V Vazirani. An O(√|V| |E|) algoithm for finding maximum matching in general graphs. In Proceedings of the 21st Symposium on Foundations of Computer Science (FOCS), pages 17-27, 1980. Google Scholar
  41. Marcin Mucha and Piotr Sankowski. Maximum matchings via gaussian elimination. In Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS), pages 248-255, 2004. Google Scholar
  42. Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), pages 745-754, 2013. Google Scholar
  43. Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. ACM Transactions on Algorithms (TALG), 12(1):7, 2016. Google Scholar
  44. Krzysztof Onak and Ronitt Rubinfeld. Maintaining a large matching and a small vertex cover. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), pages 457-464, 2010. Google Scholar
  45. David Peleg and Shay Solomon. Dynamic (1+ ε)-approximate matchings: a density-sensitive approach. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 712-729, 2016. Google Scholar
  46. Seth Pettie. A simple reduction from maximum weight matching to maximum cardinality matching. Information Processing Letters (IPL), 112(23):893-898, 2012. Google Scholar
  47. Piotr Sankowski. Faster dynamic matchings and vertex connectivity. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 118-126, 2007. Google Scholar
  48. Piotr Sankowski. Maximum weight bipartite matching in matrix multiplication time. Theoretical Computer Science (TCS), 410(44):4480-4488, 2009. Google Scholar
  49. Shay Solomon. Fully dynamic maximal matching in constant update time. In Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS), pages 325-334, 2016. Google Scholar
  50. Daniel Stubbs and Virginia Vassilevska Williams. Metatheorems for dynamic weighted matching. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS), 2017. Google Scholar
  51. Mikkel Thorup. Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. In Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT), pages 384-396, 2004. Google Scholar
  52. Mikkel Thorup. Worst-case update times for fully-dynamic all-pairs shortest paths. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 112-119, 2005. Google Scholar
  53. Vadim G Vizing. On an estimate of the chromatic class of a p-graph. Diskret analiz, 3:25-30, 1964. Google Scholar
  54. Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pages 887-898, 2012. 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