Document Open Access Logo

Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model

Authors Moran Feldman , Ariel Szarf

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.33.pdf
  • Filesize: 0.89 MB
  • 24 pages

Document Identifiers

Author Details

Moran Feldman
  • Department of Computer Science, University of Haifa, Israel
Ariel Szarf
  • Department of Mathematics and Computer Science, Open University of Israel, Ra'anana, Israel

Funding

  • Feldman, Moran: Research supported in part by Israel Science Foundation (ISF) grant number 459/20.

Cite As Get BibTex

Moran Feldman and Ariel Szarf. Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 33:1-33:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.33

Abstract

The problem of finding a maximum size matching in a graph (known as the maximum matching problem) is one of the most classical problems in computer science. Despite a significant body of work dedicated to the study of this problem in the data stream model, the state-of-the-art single-pass semi-streaming algorithm for it is still a simple greedy algorithm that computes a maximal matching, and this way obtains 1/2-approximation. Some previous works described two/three-pass algorithms that improve over this approximation ratio by using their second and third passes to improve the above mentioned maximal matching. One contribution of this paper continues this line of work by presenting new three-pass semi-streaming algorithms that work along these lines and obtain improved approximation ratios of 0.6111 and 0.5694 for triangle-free and general graphs, respectively.
Unfortunately, a recent work [Christian Konrad and Kheeran K. Naidu, 2021] shows that the strategy of constructing a maximal matching in the first pass and then improving it in further passes has limitations. Additionally, this technique is unlikely to get us closer to single-pass semi-streaming algorithms obtaining a better than 1/2-approximation. Therefore, it is interesting to come up with algorithms that do something else with their first pass (we term such algorithms non-maximal-matching-first algorithms). No such algorithms are currently known (to the best of our knowledge), and the main contribution of this paper is describing such algorithms that obtain approximation ratios of 0.5384 and 0.5555 in two and three passes, respectively, for general graphs (the result for three passes improves over the previous state-of-the-art, but is worse than the result of this paper mentioned in the previous paragraph for general graphs). The improvements obtained by these results are, unfortunately, numerically not very impressive, but the main importance (in our opinion) of these results is in demonstrating the potential of non-maximal-matching-first algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Maximum matching
  • semi-streaming algorithms
  • multi-pass algorithms

Metrics

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

Related Versions

References

  1. Kook Jin Ahn and Sudipto Guha. Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. ACM Trans. Parallel Comput., 4(4):17:1-17:40, 2018. URL: https://doi.org/10.1145/3154855.
  2. Sepehr Assadi. A two-pass (conditional) lower bound for semi-streaming maximum matching. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 708-742. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.32.
  3. 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. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.19.
  4. Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. Semi-streaming bipartite matching in fewer passes and optimal space. arXiv e-prints, pages arXiv-2011, 2020. Google Scholar
  5. Sepehr Assadi, Sanjeev Khanna, and Yang Li. On estimating maximum matching size in graph streams. 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 1723-1742. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.113.
  6. Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, and Huacheng Yu. Multi-pass graph streaming lower bounds for cycle counting, max-cut, matching size, and other problems. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 354-364. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00041.
  7. Sepehr Assadi, S. Cliff Liu, and Robert E. Tarjan. An auction algorithm for bipartite matching in streaming and massively parallel computation models. In 4th Symposium on Simplicity in Algorithms (SOSA), pages 165-171, 2021. URL: https://doi.org/10.1137/1.9781611976496.18.
  8. Sepehr Assadi and Vishvajeet N. Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 612-625. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451110.
  9. Michel L. Balinski and Jaime Gonzalez. Maximum matchings in bipartite graphs via strong spanning trees. Networks, 21(2):165-179, 1991. URL: https://doi.org/10.1002/net.3230210203.
  10. Aaron Bernstein. Improved bounds for matching in random-order streams. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 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. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.12.
  11. Aaron Bernstein, Aditi Dudeja, and Zachary Langley. A framework for dynamic matching in weighted graphs. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 668-681. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451113.
  12. 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 (SODA), pages 1326-1344, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch92.
  13. Graham Cormode, Hossein Jowhari, Morteza Monemizadeh, and S. Muthukrishnan. The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs. In 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, volume 87 of LIPIcs, pages 29:1-29:15, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.29.
  14. Michael S. Crouch and Daniel M. Stubbs. Improved streaming algorithms for weighted matching, via unweighted matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), volume 28 of LIPIcs, pages 96-104, 2014. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.96.
  15. Jack Edmonds. Maximum matching and a polyhedron with 0, 1-vertices. Journal of research of the National Bureau of Standards B, 69(125-130):55-56, 1965. Google Scholar
  16. Leah Epstein, Asaf Levin, Julián Mestre, and Danny Segev. Improved approximation guarantees for weighted matching in the semi-streaming model. SIAM J. Discret. Math., 25(3):1251-1265, 2011. URL: https://doi.org/10.1137/100801901.
  17. Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, and Krzysztof Onak. Streaming algorithms for estimating the matching size in planar graphs and beyond. ACM Trans. Algorithms, 14(4):48:1-48:23, 2018. URL: https://doi.org/10.1145/3230819.
  18. Hossein Esfandiari, MohammadTaghi Hajiaghayi, and Morteza Monemizadeh. Finding large matchings in semi-streaming. In Carlotta Domeniconi, Francesco Gullo, Francesco Bonchi, Josep Domingo-Ferrer, Ricardo Baeza-Yates, Zhi-Hua Zhou, and Xindong Wu, editors, IEEE International Conference on Data Mining Workshops, ICDM Workshops 2016, December 12-15, 2016, Barcelona, Spain, pages 608-614. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/ICDMW.2016.0092.
  19. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. Theor. Comput. Sci., 348(2-3):207-216, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.013.
  20. Moran Feldman and Ariel Szarf. Maximum matching sans maximal matching: A new approach for finding maximum matchings in the data stream model. CoRR, abs/2109.05946, 2021. URL: http://arxiv.org/abs/2109.05946.
  21. Manuela Fischer, Slobodan Mitrovic, and Jara Uitto. Deterministic (1+ε)-approximate maximum matching with poly(1/ε) passes in the semi-streaming model and beyond. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 248-260. ACM, 2022. URL: https://doi.org/10.1145/3519935.3520039.
  22. Ashish Goel, Michael Kapralov, and Sanjeev Khanna. On the communication and streaming complexity of maximum bipartite matching. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 468-485, 2012. URL: https://doi.org/10.1137/1.9781611973099.41.
  23. 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.
  24. Sagar Kale and Sumedh Tirodkar. Maximum matching in two, three, and a few more passes over graph streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA, volume 81 of LIPIcs, pages 15:1-15:21, 2017. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.15.
  25. Michael Kapralov. Better bounds for matchings in the streaming model. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1679-1697, 2013. URL: https://doi.org/10.1137/1.9781611973105.121.
  26. Michael Kapralov. Space lower bounds for approximating maximum matching in the edge arrival model. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1874-1893, 2021. URL: https://doi.org/10.1137/1.9781611976465.112.
  27. Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Approximating matching size from random streams. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 734-751, 2014. URL: https://doi.org/10.1137/1.9781611973402.55.
  28. Christian Konrad. A simple augmentation method for matchings with applications to streaming algorithms. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 117 of LIPIcs, pages 74:1-74:16, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.74.
  29. Christian Konrad, Frédéric Magniez, and Claire Mathieu. Maximum matching in semi-streaming with few passes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings, volume 7408 of Lecture Notes in Computer Science, pages 231-242, 2012. URL: https://doi.org/10.1007/978-3-642-32512-0_20.
  30. Christian Konrad and Kheeran K. Naidu. On two-pass streaming algorithms for maximum bipartite matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, August 16-18, 2021, University of Washington, Seattle, Washington, USA (Virtual Conference), volume 207 of LIPIcs, pages 19:1-19:18, 2021. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.19.
  31. Andrew McGregor. Finding graph matchings in data streams. In Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) and 9th International Workshop on Randomization and Computation (RANDOM), pages 170-181, 2005. URL: https://doi.org/10.1007/11538462_15.
  32. Andrew McGregor and Sofya Vorotnikova. Planar matching in streams revisited. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 17:1-17:12, 2016. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.17.
  33. Andrew McGregor and Sofya Vorotnikova. A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs. In 1st Symposium on Simplicity in Algorithms (SOSA), volume 61 of OASICS, pages 14:1-14:4, 2018. URL: https://doi.org/10.4230/OASIcs.SOSA.2018.14.
  34. Ami Paz and Gregory Schwartzman. A (2 + ε)-approximation for maximum weight matching in the semi-streaming model. ACM Trans. Algorithms, 15(2):18:1-18:15, 2019. URL: https://doi.org/10.1145/3274668.
  35. Mariano Zelke. Weighted matching in the semi-streaming model. Algorithmica, 62(1-2):1-20, 2012. URL: https://doi.org/10.1007/s00453-010-9438-5.
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