Document Open Access Logo

Towards a Unified Theory of Sparsification for Matching Problems

Authors Sepehr Assadi, Aaron Bernstein

PDF
Thumbnail PDF

File

OASIcs.SOSA.2019.11.pdf
  • Filesize: 0.5 MB
  • 20 pages

Document Identifiers

Author Details

Sepehr Assadi
Aaron Bernstein

Cite As Get BibTex

Sepehr Assadi and Aaron Bernstein. Towards a Unified Theory of Sparsification for Matching Problems. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/OASIcs.SOSA.2019.11

Abstract

In this paper, we present a construction of a "matching sparsifier", that is, a sparse subgraph of the given graph that preserves large matchings approximately and is robust to modifications of the graph. We use this matching sparsifier to obtain several new algorithmic results for the maximum matching problem: 
- An almost (3/2)-approximation one-way communication protocol for the maximum matching problem, significantly simplifying the (3/2)-approximation protocol of Goel, Kapralov, and Khanna (SODA 2012) and extending it from bipartite graphs to general graphs. 
- An almost (3/2)-approximation algorithm for the stochastic matching problem, improving upon and significantly simplifying the previous 1.999-approximation algorithm of Assadi, Khanna, and Li (EC 2017). 
- An almost (3/2)-approximation algorithm for the fault-tolerant matching problem, which, to our knowledge, is the first non-trivial algorithm for this problem. 
 Our matching sparsifier is obtained by proving new properties of the edge-degree constrained subgraph (EDCS) of Bernstein and Stein (ICALP 2015; SODA 2016) - designed in the context of maintaining matchings in dynamic graphs - that identifies EDCS as an excellent choice for a matching sparsifier. This leads to surprisingly simple and non-technical proofs of the above results in a unified way. Along the way, we also provide a much simpler proof of the fact that an EDCS is guaranteed to contain a large matching, which may be of independent interest.

Subject Classification

Keywords
  • Maximum matching
  • matching sparsifiers
  • one-way communication complexity
  • stochastic matching
  • fault-tolerant matching

Metrics

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

References

  1. Noga Alon and Joel H Spencer. The probabilistic method. John Wiley &Sons, 2004. Google Scholar
  2. Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, and Cliff Stein. Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. CoRR, abs/1711.03076. To appear in SODA 2019, 2017. Google Scholar
  3. 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
  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, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1723-1742, 2017. Google Scholar
  5. Sepehr Assadi, Sanjeev Khanna, and Yang Li. The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm. In Proceedings of the 2017 ACM Conference on Economics and Computation, EC '17, Cambridge, MA, USA, June 26-30, 2017, pages 99-116, 2017. Google Scholar
  6. Baruch Awerbuch. Complexity of Network Synchronization. J. ACM, 32(4):804-823, 1985. Google Scholar
  7. Surender Baswana, Keerti Choudhary, and Liam Roditty. Fault tolerant subgraph for single source reachability: generic and optimal. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 509-518, 2016. Google Scholar
  8. Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice-ramanujan sparsifiers. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 255-262, 2009. Google Scholar
  9. Soheil Behnezhad, Alireza Farhadi, MohammadTaghi Hajiaghayi, and Nima Reyhani. Stochastic Matching with Few Queries: New Algorithms and Tools. In Manuscript. To appear in SODA 2019., 2018. Google Scholar
  10. Soheil Behnezhad and Nima Reyhani. Almost Optimal Stochastic Weighted Matching with Few Queries. In Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, pages 235-249, 2018. Google Scholar
  11. 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
  12. Claude Berge. The theory of graphs. Courier Corporation, 1962. Google Scholar
  13. Aaron Bernstein and Cliff Stein. Fully Dynamic Matching in Bipartite Graphs. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 167-179, 2015. Google Scholar
  14. 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, Arlington, VA, USA, January 10-12, 2016, pages 692-711, 2016. Google Scholar
  15. Avrim Blum, John P. Dickerson, Nika Haghtalab, Ariel D. Procaccia, Tuomas Sandholm, and Ankit Sharma. Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, Portland, OR, USA, June 15-19, 2015, pages 325-342, 2015. Google Scholar
  16. Greg Bodwin, Michael Dinitz, Merav Parter, and Virginia Vassilevska Williams. Optimal Vertex Fault Tolerant Spanners (for fixed stretch). In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1884-1900, 2018. Google Scholar
  17. Greg Bodwin, Fabrizio Grandoni, Merav Parter, and Virginia Vassilevska Williams. Preserving Distances in Very Faulty Graphs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 73:1-73:14, 2017. Google Scholar
  18. Béla Bollobás, Don Coppersmith, and Michael Elkin. Sparse distance preservers and additive spanners. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA., pages 414-423, 2003. Google Scholar
  19. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. Fault-tolerant spanners for general graphs. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 435-444, 2009. Google Scholar
  20. Don Coppersmith and Michael Elkin. Sparse Sourcewise and Pairwise Distance Preservers. SIAM J. Discrete Math., 20(2):463-501, 2006. Google Scholar
  21. Paul Erdős and László Lovász. Problems and results on 3-chromatic hypergraphs and some related questions. In COLLOQUIA MATHEMATICA SOCIETATIS JANOS BOLYAI 10. INFINITE AND FINITE SETS, KESZTHELY (HUNGARY). Citeseer, 1973. Google Scholar
  22. Wai Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, and Debmalya Panigrahi. A general framework for graph sparsification. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 71-80, 2011. Google Scholar
  23. 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.
  24. Philip Hall. On representatives of subsets. Journal of the London Mathematical Society, 1(1):26-30, 1935. Google Scholar
  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 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1679-1697, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.121.
  26. David R. Karger. Random sampling in cut, flow, and network design problems. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 648-657, 1994. Google Scholar
  27. 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
  28. David Peleg. As Good as It Gets: Competitive Fault Tolerance in Network Structures. In Stabilization, Safety, and Security of Distributed Systems, 11th International Symposium, SSS 2009, Lyon, France, November 3-6, 2009. Proceedings, pages 35-46, 2009. Google Scholar
  29. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. Google Scholar
  30. Imre Z Ruzsa and Endre Szemerédi. Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai, 18:939-945, 1978. Google Scholar
  31. Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-Hoeffding Bounds for Applications with Limited Independence. SIAM J. Discrete Math., 8(2):223-250, 1995. Google Scholar
  32. Daniel A. Spielman and Shang-Hua Teng. Spectral Sparsification of Graphs. SIAM J. Comput., 40(4):981-1025, 2011. Google Scholar
  33. William T Tutte. The factorization of linear graphs. Journal of the London Mathematical Society, 1(2):107-111, 1947. Google Scholar
  34. Yutaro Yamaguchi and Takanori Maehara. Stochastic Packing Integer Programs with Few Queries. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 293-310, 2018. 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