Document Open Access Logo

Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams

Authors Sagar Kale, Sumedh Tirodkar

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.15.pdf
  • Filesize: 0.56 MB
  • 21 pages

Document Identifiers

Author Details

Sagar Kale
Sumedh Tirodkar

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 15:1-15:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.15

Abstract

We consider the maximum matching problem in the semi-streaming model formalized by Feigenbaum, Kannan, McGregor, Suri, and Zhang that is inspired by giant graphs of today.  As our main result, we give a two-pass (1/2 + 1/16)-approximation algorithm for triangle-free graphs and a two-pass (1/2 + 1/32)-approximation algorithm for general graphs; these improve the approximation ratios of 1/2 + 1/52 for bipartite graphs and 1/2 + 1/140 for general graphs by Konrad, Magniez, and Mathieu. In three passes, we achieve approximation ratios of 1/2 + 1/10 for triangle-free graphs and 1/2 + 1/19.753 for general graphs.  We also give a multi-pass algorithm where we bound the number of passes precisely - we give a (2/3 - epsilon)-approximation algorithm that uses 2/(3 epsilon) passes for triangle-free graphs and 4/(3 epsilon) passes for general graphs. Our algorithms are simple and combinatorial, use O(n log(n)) space, and have O(1) update time per edge.

For general graphs, our multi-pass algorithm improves the best known deterministic algorithms in terms of the number of passes:

* Ahn and Guha give a (2/3 - epsilon)-approximation algorithm that uses O(log(1/epsilon)/epsilon^2) passes, whereas our (2/3 - epsilon)-approximation algorithm uses 4/(epsilon) passes;

* they also give a (1 - epsilon)-approximation algorithm that uses O(log(n) poly(1/epsilon)) passes, where n is the number of vertices of the input graph; although our algorithm is (2/3 - epsilon)-approximation, our number of passes do not depend on n.

Earlier multi-pass algorithms either have a large constant inside big-O notation for the number of passes or the constant cannot be determined due to the involved analysis, so our multi-pass algorithm should use much fewer passes for approximation ratios bounded slightly below 2/3.

Subject Classification

Keywords
  • Semi Streaming
  • Maximum Matching

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. Inf. Comput., 222:59-79, January 2013. URL: http://dx.doi.org/10.1016/j.ic.2012.10.006.
  2. Sepehr Assadi, Sanjeev Khanna, and Yang Li. On estimating maximum matching size in graph streams. In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1723-1742, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.113.
  3. Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev. Maximum matchings in dynamic graph streams and the simultaneous communication model. In Proc. 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1345-1364, 2016. URL: http://dl.acm.org/citation.cfm?id=2884435.2884528.
  4. Marc Bury and Chris Schwiegelshohn. Sublinear estimation of weighted matchings in dynamic data streams. In Proc. 23rd Annual European Symposium on Algorithms, pages 263-274, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_23.
  5. Amit Chakrabarti and Sagar Kale. Submodular maximization meets streaming: matchings, matroids, and more. Mathematical Programming, 154(1):225-247, 2015. URL: http://dx.doi.org/10.1007/s10107-015-0900-7.
  6. Chandra Chekuri, Shalmoli Gupta, and Kent Quanrud. Streaming algorithms for submodular function maximization. In Proc. 42nd International Colloquium on Automata, Languages and Programming, pages 318-330, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_26.
  7. 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 Proc. 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1326-1344, 2016. URL: http://dl.acm.org/citation.cfm?id=2884435.2884527.
  8. Michael 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 2014), volume 28 of Leibniz International Proceedings in Informatics (LIPIcs), pages 96-104. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.96.
  9. Sebastian Eggert, Lasse Kliemann, Peter Munstermann, and Anand Srivastav. Bipartite matching in the semi-streaming model. Algorithmica, 63(1):490-508, 2012. URL: http://dx.doi.org/10.1007/s00453-011-9556-8.
  10. Leah Epstein, Asaf Levin, Julian Mestre, and Danny Segev. Improved approximation guarantees for weighted matching in the semi-streaming model. SIAM Journal on Discrete Mathematics, 25(3):1251-1265, 2011. URL: http://dx.doi.org/10.1137/100801901.
  11. H. Esfandiari, M. Hajiaghayi, and M. Monemizadeh. Finding large matchings in semi-streaming. In 2016 IEEE 16th International Conference on Data Mining Workshops (ICDMW), pages 608-614, Dec 2016. URL: http://dx.doi.org/10.1109/ICDMW.2016.0092.
  12. Hossein Esfandiari, Mohammad T. Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, and Krzysztof Onak. Streaming algorithms for estimating the matching size in planar graphs and beyond. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1217-1233, 2015. URL: http://dl.acm.org/citation.cfm?id=2722129.2722210.
  13. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. Theor. Comput. Sci., 348(2):207-216, December 2005. URL: http://dx.doi.org/10.1016/j.tcs.2005.09.013.
  14. Ashish Goel, Michael Kapralov, and Sanjeev Khanna. On the communication and streaming complexity of maximum bipartite matching. In Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 468-485, 2012. URL: http://dl.acm.org/citation.cfm?id=2095116.2095157.
  15. Elena Grigorescu, Morteza Monemizadeh, and Samson Zhou. Streaming weighted matchings: Optimal meets greedy. CoRR, abs/1608.01487, 2016. URL: http://arxiv.org/abs/1608.01487.
  16. Michael Kapralov. Better bounds for matchings in the streaming model. In Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2013. Google Scholar
  17. Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Approximating matching size from random streams. In Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 734-751, 2014. URL: http://dl.acm.org/citation.cfm?id=2634074.2634129.
  18. Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proc. 22nd Annual ACM Symposium on the Theory of Computing, pages 352-358, 1990. URL: http://dx.doi.org/10.1145/100216.100262.
  19. Christian Konrad. Maximum matching in turnstile streams. In Proc. 23rd Annual European Symposium on Algorithms, pages 840-852, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_70.
  20. Christian Konrad, Frédéric Magniez, and Claire Mathieu. Maximum matching in semi-streaming with few passes. In Proc. 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 231-242, 2012 and CoRR, abs/1112.0184, 2014. URL: http://arxiv.org/abs/1112.0184.
  21. Andrew McGregor. Problem 60: Single-pass unweighted matchings. http://sublinear.info/index.php?title=Open_Problems:60. Accessed: 2017-02-16.
  22. Andrew McGregor. Finding graph matchings in data streams. In Proc. 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 170-181, 2005. URL: http://dx.doi.org/10.1007/11538462_15.
  23. Ami Paz and Gregory Schwartzman. A (2 + ε)-approximation for maximum weight matching in the semi-streaming model. In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2153-2161, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.140.
  24. Mariano Zelke. Weighted matching in the semi-streaming model. In Proc. 25th International Symposium on Theoretical Aspects of Computer Science, pages 669-680, 2008. 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