Document Open Access Logo

On the Robust Communication Complexity of Bipartite Matching

Authors Sepehr Assadi, Soheil Behnezhad

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.48.pdf
  • Filesize: 0.74 MB
  • 17 pages

Document Identifiers

Author Details

Sepehr Assadi
  • Rutgers University, Piscataway, NJ, USA
Soheil Behnezhad
  • University of Maryland, College Park, MD, USA

Funding

  • Assadi, Sepehr: Research supported in part by the NSF CAREER award CCF-2047061 and a gift from Google Research.
  • Behnezhad, Soheil: Research supported by Google PhD Fellowship.

Cite AsGet BibTex

Sepehr Assadi and Soheil Behnezhad. On the Robust Communication Complexity of Bipartite Matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 48:1-48:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.48

Abstract

We study the robust - à la Chakrabarti, Cormode, and McGregor [STOC'08] - communication complexity of the maximum bipartite matching problem. The edges of an adversarially chosen n-vertex bipartite graph G are partitioned randomly between Alice and Bob. Alice has to send a single message to Bob, using which Bob has to output an approximate maximum matching of G. We are particularly interested in understanding the best approximation ratio possible by protocols that use a near-optimal message size of n ⋅ polylog(n). The communication complexity of bipartite matching in this setting under an adversarial partitioning is well-understood. In their beautiful paper, Goel, Kapralov, and Khanna [SODA'12] gave a rac{2} {3}-approximate protocol with O(n) communication and showed that this approximation is tight unless we allow more than a near-linear communication. The complexity of the robust version, i.e., with a random partitioning of the edges, however remains wide open. The best known protocol, implied by a very recent random-order streaming algorithm of the authors [ICALP'21], uses O(n log n) communication to obtain a (rac{2} {3} + ε₀)-approximation for a constant ε₀ ∼ 10^{-14}. The best known lower bound, on the other hand, leaves open the possibility of all the way up to even a (1-ε)-approximation using near-linear communication for constant ε > 0. In this work, we give a new protocol with a significantly better approximation. Particularly, our protocol achieves a 0.716 expected approximation using O(n) communication. This protocol is based on a new notion of distribution-dependent sparsifiers which give a natural way of sparsifying graphs sampled from a known distribution. We then show how to lift the assumption on knowing the graph’s distribution via minimax theorems. We believe this is a particularly powerful method of designing communication protocols and might find further applications.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Maximum Matching
  • Communication Complexity
  • Random-Order Streaming

Metrics

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

References

  1. Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, and Cliff Stein. Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1616-1635, 2019. Google Scholar
  2. Sepehr Assadi and Soheil Behnezhad. Beating two-thirds for random-order streaming matching. CoRR, abs/2102.07011. To appear in ICALP 2021, 2021. Google Scholar
  3. Sepehr Assadi and Aaron Bernstein. Towards a unified theory of sparsification for matching problems. In 2nd Symposium on Simplicity in Algorithms, SOSA@SODA 2019, January 8-9, 2019 - San Diego, CA, USA, pages 11:1-11:20, 2019. Google Scholar
  4. Sepehr Assadi, Sanjeev Khanna, and Yang Li. The stochastic matching problem with (very) few queries. In Proceedings of the 2016 ACM Conference on Economics and Computation, EC '16, Maastricht, The Netherlands, July 24-28, 2016, pages 43-60, 2016. Google Scholar
  5. 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, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1723-1742, 2017. Google Scholar
  6. 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, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1345-1364, 2016. Google Scholar
  7. Sepehr Assadi, Gillat Kol, and Rotem Oshman. Lower bounds for distributed sketching of maximal matchings and maximal independent sets. In Yuval Emek and Christian Cachin, editors, PODC '20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020, pages 79-88. ACM, 2020. Google Scholar
  8. Sepehr Assadi and Ran Raz. Near-quadratic lower bounds for two-pass graph streaming algorithms. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 342-353. IEEE, 2020. Google Scholar
  9. Maria-Florina Balcan, Yi Li, David P. Woodruff, and Hongyang Zhang. Testing matrix rank, optimally. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 727-746, 2019. Google Scholar
  10. Soheil Behnezhad and Mahsa Derakhshan. Stochastic weighted matching: (1-ε) approximation. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1392-1403, 2020. Google Scholar
  11. Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. Stochastic matching with few queries: (1-ε) approximation. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1111-1124, 2020. Google Scholar
  12. Soheil Behnezhad, Alireza Farhadi, MohammadTaghi Hajiaghayi, and Nima Reyhani. Stochastic matching with few queries: New algorithms and tools. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2855-2874, 2019. Google Scholar
  13. András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in Õ(n^2) time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 47-55, 1996. Google Scholar
  14. András A. Benczúr and David R. Karger. Randomized approximation schemes for cuts and flows in capacitated graphs. SIAM J. Comput., 44(2):290-319, 2015. Google Scholar
  15. Aaron Bernstein. Improved bounds for matching in random-order streams. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), pages 12:1-12:13, 2020. Google Scholar
  16. Aaron Bernstein and Cliff Stein. Fully dynamic matching in bipartite graphs. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, July 6-10, 2015, Proceedings, Part I, pages 167-179, 2015. Google Scholar
  17. Aaron Bernstein and Cliff Stein. Faster fully dynamic matchings with small approximation ratios. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, January 10-12, 2016, pages 692-711, 2016. Google Scholar
  18. Amit Chakrabarti, Graham Cormode, and Andrew McGregor. Robust lower bounds for communication and stream computation. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, May 17-20, 2008, pages 641-650, 2008. Google Scholar
  19. Graham Cormode, Jacques Dark, and Christian Konrad. Independent sets in vertex-arrival streams. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, pages 45:1-45:14, 2019. Google Scholar
  20. Jacques Dark and Christian Konrad. Optimal lower bounds for matching and vertex cover in dynamic graph streams. In Shubhangi Saraf, editor, 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference), volume 169 of LIPIcs, pages 30:1-30:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  21. Shahar Dobzinski, Noam Nisan, and Sigal Oren. Economic efficiency requires interaction. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 233-242, 2014. Google Scholar
  22. Alireza Farhadi, Mohammad Taghi Hajiaghayi, Tung Mai, Anup Rao, and Ryan A. Rossi. Approximate maximum matching in random streams. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1773-1785, 2020. Google Scholar
  23. 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. Google Scholar
  24. Buddhima Gamlath, Sagar Kale, Slobodan Mitrovic, and Ola Svensson. Weighted matchings via unweighted augmentations. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 491-500, 2019. Google Scholar
  25. 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 '12, pages 468-485. SIAM, 2012. URL: http://dl.acm.org/citation.cfm?id=2095116.2095157.
  26. Venkatesan Guruswami and Krzysztof Onak. Superlinear lower bounds for multipass graph processing. In Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013, pages 287-298, 2013. Google Scholar
  27. András Hajnal, Wolfgang Maass, and György Turán. On the communication complexity of graph properties. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 186-191, 1988. Google Scholar
  28. 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. Google Scholar
  29. Zengfeng Huang, Bozidar Radunovic, Milan Vojnovic, and Qin Zhang. Communication complexity of approximate matching in distributed graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, pages 460-473, 2015. Google Scholar
  30. Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, and Ronald de Wolf. New bounds on the classical and quantum communication complexity of some graph properties. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India, pages 148-159, 2012. Google Scholar
  31. 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: https://doi.org/10.1137/1.9781611973105.121.
  32. Michael Kapralov. Space lower bounds for approximating maximum matching in the edge arrival model. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1874-1893. SIAM, 2021. Google Scholar
  33. Michael Kapralov, Gilbert Maystre, and Jakab Tardos. Communication efficient coresets for maximum matching. In Hung Viet Le and Valerie King, editors, 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, pages 156-164. SIAM, 2021. Google Scholar
  34. Christian Konrad. A simple augmentation method for matchings with applications to streaming algorithms. In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, pages 74:1-74:16, 2018. Google Scholar
  35. 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. Google Scholar
  36. Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997. Google Scholar
  37. Euiwoong Lee and Sahil Singla. Maximum matching in the online batch-arrival model. In Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, pages 355-367, 2017. Google Scholar
  38. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995. Google Scholar
  39. Ilan Newman. Private vs. common random bits in communication complexity. Inf. Process. Lett., 39(2):67-71, 1991. Google Scholar
  40. Ran Raz and Boris Spieker. On the "log rank"-conjecture in communication complexity. In 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, pages 168-176, 1993. Google Scholar
  41. Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity (extended abstract). In 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977, pages 222-227, 1977. Google Scholar
  42. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 209-213, 1979. 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