Document Open Access Logo

Planar Matching in Streams Revisited

Authors Andrew McGregor, Sofya Vorotnikova

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2016.17.pdf
  • Filesize: 0.54 MB
  • 12 pages

Document Identifiers

Author Details

Andrew McGregor
Sofya Vorotnikova

Cite As Get BibTex

Andrew McGregor and Sofya Vorotnikova. Planar Matching in Streams Revisited. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.17

Abstract

We present data stream algorithms for estimating the size or weight of the maximum matching in low arboricity graphs. A large body of work has focused on improving the constant approximation factor for general graphs when the data stream algorithm is permitted O(n polylog n) space where n is the number of nodes. This space is necessary if the algorithm must return the matching. Recently, Esfandiari et al. (SODA 2015) showed that it was possible to estimate the maximum cardinality of a matching in a planar graph up to a factor of 24+epsilon using O(epsilon^{-2} n^{2/3} polylog n) space. We first present an algorithm (with a simple analysis) that improves this to a factor 5+epsilon using the same space. We also improve upon the previous results for other graphs with bounded arboricity. We then present a factor 12.5 approximation for matching in planar graphs that can be implemented using O(log n) space in the adjacency list data stream model where the stream is a concatenation of the adjacency lists of the graph. The main idea behind our results is finding "local" fractional matchings, i.e., fractional matchings where the value of any edge e is solely determined by the edges sharing an endpoint with e. Our work also improves upon the results for the dynamic data stream model where the stream consists of a sequence of edges being inserted and deleted from the graph. We  also extend our results to weighted graphs, improving over the bounds given by Bury and Schwiegelshohn (ESA 2015), via a reduction to the unweighted problem that increases the approximation by at most a factor of two.

Subject Classification

Keywords
  • data streams
  • planar graphs
  • arboricity
  • matchings

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, 2013. URL: http://dx.doi.org/10.1016/j.ic.2012.10.006.
  2. Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA., pages 623-632, 2002. URL: http://dl.acm.org/citation.cfm?id=545381.545464.
  3. Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Christian Sohler. Counting triangles in data streams. In Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 26-28, 2006, Chicago, Illinois, USA, pages 253-262, 2006. URL: http://dx.doi.org/10.1145/1142351.1142388.
  4. Marc Bury and Chris Schwiegelshohn. Sublinear estimation of weighted matchings in dynamic data streams. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 263-274, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_23.
  5. 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 2016, Arlington, VA, USA, January 10-12, 2016, pages 1326-1344, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch92.
  6. Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 205-214, 2009. URL: http://dx.doi.org/10.1145/1536414.1536445.
  7. Michael Crouch and Daniel S. Stubbs. Improved streaming algorithms for weighted matching, via unweighted matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain, pages 96-104, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.96.
  8. Michael S. Crouch, Andrew McGregor, and Daniel Stubbs. Dynamic graphs in the sliding-window model. In Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, pages 337-348, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40450-4_29.
  9. Andrzej Czygrinow, Michal Hanckowiak, and Edyta Szymanska. Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs. In Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, pages 668-678, 2009. URL: http://dx.doi.org/10.1007/978-3-642-10631-6_68.
  10. Jack Edmonds. Maximum matching and a polyhedron with 0,1-vertices. Journal of Research of the National Bureau of Standards, 69:125-130, 1965. Google Scholar
  11. 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.
  12. Hossein Esfandiari, Mohammad Taghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, and Krzysztof Onak. Streaming algorithms for estimating the matching size in planar graphs and beyond. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1217-1233, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.81.
  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, 2005. URL: http://dx.doi.org/10.1016/j.tcs.2005.09.013.
  14. Mina Ghashami, Edo Liberty, Jeff M. Phillips, and David P. Woodruff. Frequent directions: Simple and deterministic matrix sketching. CoRR, abs/1501.01711, 2015. URL: http://arxiv.org/abs/1501.01711.
  15. 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 2012, Kyoto, Japan, January 17-19, 2012, pages 468-485, 2012. URL: http://portal.acm.org/citation.cfm?id=2095157&CFID=63838676&CFTOKEN=79617016.
  16. Elena Grigorescu, Morteza Monemizadeh, and Samson Zhou. Estimating weighted matchings in o(n) space. CoRR, abs/1604.07467, 2016. URL: http://arxiv.org/abs/1604.07467.
  17. Venkatesan Guruswami and Krzysztof Onak. Superlinear lower bounds for multipass graph processing. In Proc. of the 28th Conference on Computational Complexity, CCC 2013, Palo Alto, California, USA, 5-7 June, 2013, pages 287-298, 2013. URL: http://dx.doi.org/10.1109/CCC.2013.37.
  18. Michael Kapralov. Better bounds for matchings in the streaming model. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1679-1697, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.121.
  19. 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 2014, Portland, Oregon, USA, January 5-7, 2014, pages 734-751, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.55.
  20. Christian Konrad. Maximum matching in turnstile streams. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 840-852, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_70.
  21. 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, pages 231-242, 2012. URL: http://dx.doi.org/10.1007/978-3-642-32512-0_20.
  22. Christian Konrad and Adi Rosén. Approximating semi-matchings in streaming and in two-party communication. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, pages 637-649, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39206-1_54.
  23. Madhusudan Manjunath, Kurt Mehlhorn, Konstantinos Panagiotou, and He Sun. Approximate counting of cycles in streams. In Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings, pages 677-688, 2011. URL: http://dx.doi.org/10.1007/978-3-642-23719-5_57.
  24. Andrew McGregor. Finding graph matchings in data streams. APPROX-RANDOM, pages 170-181, 2005. Google Scholar
  25. Andrew McGregor. Graph stream algorithms: a survey. SIGMOD Record, 43(1):9-20, 2014. URL: http://dx.doi.org/10.1145/2627692.2627694.
  26. Mariano Zelke. Weighted matching in the semi-streaming model. Algorithmica, 62(1-2):1-20, 2012. URL: http://dx.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