Document Open Access Logo

The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs

Authors Graham Cormode, Hossein Jowhari, Morteza Monemizadeh, S. Muthukrishnan

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.29.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Graham Cormode
Hossein Jowhari
Morteza Monemizadeh
S. Muthukrishnan

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 29:1-29:15, Schloss Dagstuhl ā€“ Leibniz-Zentrum fĆ¼r Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.29

Abstract

Estimating the size of the maximum matching is a canonical problem in graph analysis, and one that has attracted extensive study over a range of different computational models. We present improved streaming algorithms for approximating the size of maximum matching with sparse (bounded arboricity) graphs. 

* (Insert-Only Streams) We present a one-pass algorithm that takes  O(alpha log n) space and approximates the size of the maximum matching in graphs with arboricity alpha within a factor of O(alpha). This improves significantly upon the state-of-the-art tilde{O}(alpha n^{2/3})-space streaming algorithms, and is the first poly-logarithmic space algorithm for this problem. 

* (Dynamic Streams) Given a dynamic graph stream (i.e., inserts and deletes) of edges of an underlying alpha-bounded arboricity graph, we present an one-pass algorithm that uses  space tilde{O}(alpha^{10/3}n^{2/3}) and returns an O(alpha)-estimator for the size of the maximum matching on the condition that the number edge deletions in the stream is bounded by O(alpha n). For this class of inputs, our algorithm improves the state-of-the-art tilde{O}(\alpha n^{4/5})-space algorithms, where the \tilde{O}(.) notation hides logarithmic in n dependencies.

In contrast to prior work, our results take more advantage of the streaming access to the input and characterize the matching size based on the ordering of the edges in the stream in addition to the degree distributions and structural properties of the sparse graphs.

Subject Classification

Keywords
  • streaming algorithms
  • matching size

Metrics

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

References

  1. K. J. Ahn, S. Guha, and A. McGregor. Analyzing graph structure via linear measurements. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 459-467, 2012. Google Scholar
  2. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In ACM Principles of Database Systems, pages 5-14, 2012. URL: http://dx.doi.org/10.1145/2213556.2213560.
  3. Sepehr Assadi, Sanjeev Khanna, and Yang Li. On estimating maximum matching size in graph streams. In Proceedings of the Twenty-Eigth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, January 2017, 2017. URL: http://www.seas.upenn.edu/~sassadi/pages/streaming_matching-size_2017.html.
  4. Sepehr Assadi, Sanjeev Khanna, and Yang Li. On estimating maximum matching size in graph streams. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1723-1742, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.113.
  5. Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev. Maximum matchings in dynamic graph streams and the simultaneous communication model. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1345-1364, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch93.
  6. M. Bury and C. Schwiegelshohn. Sublinear estimation of weighted matchings in dynamic data streams. In Proceedings of the 23rd Annual European Symposium on Algorithms (ESA), pages 263-274, 2015. Google Scholar
  7. R. Chitnis, G. Cormode, H. Esfandiari, M.T. Hajiaghayi, A. McGregor, M. Monemizadeh, and S. Vorotnikova. Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1326-1344, 2016. Google Scholar
  8. Edith Cohen. All-distances sketches, revisited: HIP estimators for massive graphs analysis. In ACM Principles of Database Systems, pages 88-99, 2014. URL: http://dx.doi.org/10.1145/2594538.2594546.
  9. Graham Cormode and Donatella Firmani. On unifying the space of š“ā‚€-sampling algorithms. In Algorithm Engineering and Experiments, 2013. Google Scholar
  10. Graham Cormode, Hossein Jowhari, Morteza Monemizadeh, and S. Muthukrishnan. The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs. Technical Report 1608.03118, ArXiv, 2016. URL: http://arxiv.org/abs/1608.03118.
  11. M. Crouch and D. S. Stubbs. Improved streaming algorithms for weighted matching, via unweighted matching. In Proceedings of the 17th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages 96-104, 2014. Google Scholar
  12. R. Duan and S. Pettie. Linear-time approximation for maximum weight matchings. Journal of the ACM, 61(1):1-23, 2014. Google Scholar
  13. S. Eggert, L. Kliemann, P. Munstermann, and A. Srivastav. Bipartite graph matchings in the semi-streaming model. Algorithmica, 63(1-2):490-508, 2012. Google Scholar
  14. Leah Epstein, Asaf Levin, JuliƔn Mestre, and Danny Segev. Improved approximation guarantees for weighted matching in the semi-streaming model. SIAM J. Discrete Math., 25(3):1251-1265, 2011. URL: http://dx.doi.org/10.1137/100801901.
  15. H. Esfandiari, M.T. Hajiaghyi, V. Liaghat, M. Monemizadeh, and K. Onak. Streaming algorithms for estimating the matching size in planar graphs and beyond. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015. Google Scholar
  16. J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang. On graph problems in a semi-streaming model. Theoretical Computer Science, 348(2):207-216, 2005. Google Scholar
  17. Ashish Goel, Michael Kapralov, and Sanjeev Khanna. On the communication and streaming complexity of maximum bipartite matching. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 468-485, 2012. Google Scholar
  18. Yijie Han. Matching for graphs of bounded degree. In Frontiers in Algorithmics, Second Annual International Workshop, FAW 2008, Changsha, China, June 19-21, 2008, Proceeedings, pages 171-173, 2008. URL: http://dx.doi.org/10.1007/978-3-540-69311-6_19.
  19. 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: http://dx.doi.org/10.1137/0202019.
  20. M. Kapralov. Better bounds for matchings in the streaming model. Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1679-1697, 2013. Google Scholar
  21. M. Kapralov, S. Khanna, and M. Sudan. Approximating matching size from random streams. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 734-751, 2014. Google Scholar
  22. R. M. Karp, U. V. Vazirani, and V. V. Vazirani. An optimal algorithm for on-line bipartite matching. Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 352-358, 1990. Google Scholar
  23. C. Konrad, F. Magniez, and C. Mathieu. Maximum matching in semi-streaming with few passes. In Proceedings of the 11th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages 231-242, 2012. Google Scholar
  24. Alexandr V. Kostochka. Lower bound of the hadwiger number of graphs by their average degree. Combinatorica, 4(4):307-316, 1984. Google Scholar
  25. Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: A method for solving graph problems in mapreduce. In Proceedings of the Twenty-third Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'11, pages 85-94. ACM, 2011. URL: http://dx.doi.org/10.1145/1989493.1989505.
  26. L. Lovasz and M.D. Plummer. Matching theory. In North-Holland, Amsterdam-New York, 1986. Google Scholar
  27. Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 253-262, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.35.
  28. A. McGregor. Finding graph matchings in data streams. In Proceedings of the 8th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages 170-181, 2005. Google Scholar
  29. A. McGregor. Graph mining on streams. In Encyclopedia of Database Systems, pages 1271-1275. Springer, 2009. Google Scholar
  30. A. McGregor and S. Vorotnikova. Planar matching in streams revisited. In Proceedings of the 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2016. Google Scholar
  31. Andrew McGregor. Graph stream algorithms: a survey. SIGMOD Record, 43(1):9-20, 2014. URL: http://dx.doi.org/10.1145/2627692.2627694.
  32. Andrew McGregor and Sofya Vorotnikova. A note on logarithmic space stream algorithms for matchings in low arboricity graphs. Technical Report 1612.02531, ArXiv, 2016. Google Scholar
  33. Andrew McGregor, Sofya Vorotnikova, and Hoa T. Vu. Better algorithms for counting triangles in data streams. In ACM Principles of Database Systems, pages 401-411, 2016. URL: http://dx.doi.org/10.1145/2902251.2902283.
  34. Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, and Vijay V. Vazirani. Adwords and generalized online matching. J. ACM, 54(5), 2007. Google Scholar
  35. S. Micali and V. V. Vazirani. An o(āˆš|V| |e|) algorithm for finding maximum matching in general graphs. Proceedings of the 21st IEEE Symposium on Foundations of Computer Science (FOCS), pages 17-27, 1980. Google Scholar
  36. C. St. J. A. Nash-Williams. Edge-disjoint spanning trees of finite graphs. Journal of the London Mathematical Society, 36(1):445-450, 1961. Google Scholar
  37. C. St. J. A. Nash-Williams. Decomposition of finite graphs into forests. Journal of the London Mathematical Society, 39(1):12, 1964. Google Scholar
  38. Huy Nguyen and Krzysztof Onak. Constant-time approximation algorithms via local improvements. In IEEE Conference on Foundations of Computer Science, 2008. Google Scholar
  39. List of open problems in sublinear algorithms: Problem 60. URL: http://sublinear.info/60.
  40. Ami Paz and Gregory Schwartzman. A (2 + Īµ)-approximation for maximum weight matching in the semi-streaming model. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2153-2161, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.140.
  41. A. E. Roth and M. A. O. Sotomayor. Two-sided matching: A study in game-theoretic modeling and analysis. Cambridge University Press, 1990. Google Scholar
  42. Nenad Trinajstic, Douglas J. Klein, and Milan Randic. On some solved and unsolved problems of chemical graph theory. International Journal of Quantum Chemistry, 30(S20):699-742, 1986. Google Scholar
  43. Mariano Zelke. Weighted matching in the semi-streaming model. Algorithmica, 62(1-2):1-20, 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 About DROPS Imprint Privacy Contact