Document Open Access Logo

Graph Spanners in the Message-Passing Model

Authors Manuel Fernández V, David P. Woodruff, Taisuke Yasuda

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.77.pdf
  • Filesize: 0.5 MB
  • 18 pages

Document Identifiers

Author Details

Manuel Fernández V
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA
David P. Woodruff
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA
Taisuke Yasuda
  • Akuna Capital, Chicago, Illinois, USA

Funding

  • Woodruff, David P.: D. Woodruff would like to acknowledge support from the Office of Naval Research (ONR) grant N00014-18-1-2562.

Acknowledgements

We would like to thank Gregory Kehne, Roie Levin, Chen Shao and Srikanta Tirthapura for helpful discussions, as well as the anonymous reviewers for their useful feedback.

Cite As Get BibTex

Manuel Fernández V, David P. Woodruff, and Taisuke Yasuda. Graph Spanners in the Message-Passing Model. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 77:1-77:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ITCS.2020.77

Abstract

Graph spanners are sparse subgraphs which approximately preserve all pairwise shortest-path distances in an input graph. The notion of approximation can be additive, multiplicative, or both, and many variants of this problem have been extensively studied. We study the problem of computing a graph spanner when the edges of the input graph are distributed across two or more sites in an arbitrary, possibly worst-case partition, and the goal is for the sites to minimize the communication used to output a spanner. We assume the message-passing model of communication, for which there is a point-to-point link between all pairs of sites as well as a coordinator who is responsible for producing the output. We stress that the subset of edges that each site has is not related to the network topology, which is fixed to be point-to-point. While this model has been extensively studied for related problems such as graph connectivity, it has not been systematically studied for graph spanners. We present the first tradeoffs for total communication versus the quality of the spanners computed, for two or more sites, as well as for additive and multiplicative notions of distortion. We show separations in the communication complexity when edges are allowed to occur on multiple sites, versus when each edge occurs on at most one site. We obtain nearly tight bounds (up to polylog factors) for the communication of additive 2-spanners in both the with and without duplication models, multiplicative (2k-1)-spanners in the with duplication model, and multiplicative 3 and 5-spanners in the without duplication model. Our lower bound for multiplicative 3-spanners employs biregular bipartite graphs rather than the usual Erdős girth conjecture graphs and may be of wider interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
  • Mathematics of computing → Graph algorithms
Keywords
  • Graph spanners
  • Message-passing model
  • Communication complexity

Metrics

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

Related Versions

References

  1. Amir Abboud and Greg Bodwin. The 4/3 Additive Spanner Exponent Is Tight. J. ACM, 64(4):28:1-28:20, September 2017. Google Scholar
  2. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 459-467. SIAM, 2012. URL: https://doi.org/10.1137/1.9781611973099.40.
  3. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Michael Benedikt, Markus Krötzsch, and Maurizio Lenzerini, editors, Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012, pages 5-14. ACM, 2012. URL: https://doi.org/10.1145/2213556.2213560.
  4. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Spectral Sparsification in Dynamic Graph Streams. In Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, volume 8096 of Lecture Notes in Computer Science, pages 1-10. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40328-6_1.
  5. Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing, 28(4):1167-1181, 1999. Google Scholar
  6. Gabriela Araujo-Pardo, Alejandra Ramos-Rivera, and Robert Jajcay. Bipartite Biregular Cages and Block Designs. arXiv preprint, 2019. URL: http://arxiv.org/abs/1907.11568.
  7. Baruch Awerbuch. Complexity of Network Synchronization. J. ACM, 32(4):804-823, 1985. URL: https://doi.org/10.1145/4221.4227.
  8. Baruch Awerbuch. Distributed Shortest Paths Algorithms (Extended Abstract). In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washigton, USA, pages 490-500, 1989. Google Scholar
  9. László Babai, Anna Gál, Peter G. Kimmel, and Satyanarayana V. Lokam. Communication Complexity of Simultaneous Messages. SIAM J. Comput., 33(1):137-166, 2003. URL: https://doi.org/10.1137/S0097539700375944.
  10. Surender Baswana. Streaming algorithm for graph spanners - single pass and constant processing time per edge. Inf. Process. Lett., 106(3):110-114, 2008. URL: https://doi.org/10.1016/j.ipl.2007.11.001.
  11. Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. New constructions of (alpha, beta)-spanners and purely additive spanners. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 672-681, 2005. Google Scholar
  12. Surender Baswana and Sandeep Sen. Approximate distance oracles for unweighted graphs in Õ(n^2) time. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004, pages 271-280, 2004. Google Scholar
  13. Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms, 30(4):532-563, 2007. URL: https://doi.org/10.1002/rsa.20130.
  14. Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, and Vinod Vaikuntanathan. A Tight Bound for Set Disjointness in the Message-Passing Model. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 668-677, 2013. Google Scholar
  15. Keren Censor-Hillel and Michal Dory. Distributed Spanner Approximation. In Calvin Newport and Idit Keidar, editors, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 139-148. ACM, 2018. URL: https://doi.org/10.1145/3212734.3212758.
  16. Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz, and Amir Yehudayoff. Distributed construction of purely additive spanners. In International Symposium on Distributed Computing, pages 129-142. Springer, 2016. Google Scholar
  17. Arkadev Chattopadhyay and Toniann Pitassi. The story of set disjointness. ACM SIGACT News, 41(3):59-85, 2010. Google Scholar
  18. Shiri Chechik. New Additive Spanners. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 498-512, 2013. Google Scholar
  19. Edith Cohen. Fast Algorithms for Constructing t-Spanners and Paths with Stretch t. SIAM J. Comput., 28(1):210-236, 1998. URL: https://doi.org/10.1137/S0097539794261295.
  20. Edith Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. J. ACM, 47(1):132-166, 2000. URL: https://doi.org/10.1145/331605.331610.
  21. Don Coppersmith and Michael Elkin. Sparse sourcewise and pairwise distance preservers. SIAM Journal on Discrete Mathematics, 20(2):463-501, 2006. Google Scholar
  22. Lenore Cowen. Compact Routing with Minimum Stretch. J. Algorithms, 38(1):170-183, 2001. URL: https://doi.org/10.1006/jagm.2000.1134.
  23. Lenore Cowen and Christopher G. Wagner. Compact roundtrip routing in directed networks. J. Algorithms, 50(1):79-95, 2004. URL: https://doi.org/10.1016/j.jalgor.2003.08.001.
  24. D De Caen and László A Székely. On dense bipartite graphs of girth eight and upper bounds for certain configurations in planar point-line systems. Journal of Combinatorial Theory, Series A, 77(2):268-278, 1997. Google Scholar
  25. Michael Dinitz and Yasamin Nazari. Approximating k-spanners in the LOCAL model. CoRR, abs/1703.07417, 2017. URL: http://arxiv.org/abs/1703.07417.
  26. Dorit Dor, Shay Halperin, and Uri Zwick. All-pairs almost shortest paths. SIAM Journal on Computing, 29(5):1740-1759, 2000. Google Scholar
  27. Michael Elkin. Computing almost shortest paths. ACM Trans. Algorithms, 1(2):283-323, 2005. URL: https://doi.org/10.1145/1103963.1103968.
  28. Michael Elkin and Ofer Neiman. Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 652-669, 2017. Google Scholar
  29. Michael Elkin and David Peleg. (1+epsilon, beta)-Spanner Constructions for General Graphs. SIAM J. Comput., 33(3):608-631, 2004. Google Scholar
  30. P Erdős. On extremal problems of graphs and generalized graphs. Israel Journal of Mathematics, 2(3):183-190, 1964. Google Scholar
  31. P Erdős. On some extremal problems in graph theory. Israel Journal of Mathematics, 3(2):113-116, 1965. Google Scholar
  32. Slobodan Filipovski, Alejandra Ramos Rivera, and Robert Jajcay. On biregular bipartite graphs of small excess. Discrete Mathematics, 342(7):2066-2076, 2019. URL: https://doi.org/10.1016/j.disc.2019.04.004.
  33. Zoltán Füredi. Quadrilateral-free graphs with maximum number of edges. preprint, 1994. Google Scholar
  34. Ofer Grossman and Merav Parter. Improved Deterministic Distributed Construction of Spanners. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, pages 24:1-24:16, 2017. Google Scholar
  35. Shlomo Hoory. The Size of Bipartite Graphs with a Given Girth. J. Comb. Theory, Ser. B, 86(2):215-220, 2002. URL: https://doi.org/10.1006/jctb.2002.2123.
  36. Zengfeng Huang, Bozidar Radunovic, Milan Vojnovic, and Qin Zhang. Communication Complexity of Approximate Matching in Distributed Graphs. In Ernst W. Mayr and Nicolas Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, volume 30 of LIPIcs, pages 460-473. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.STACS.2015.460.
  37. Bala Kalyanasundaram and Georg Schnitger. The Probabilistic Communication Complexity of Set Intersection. SIAM J. Discrete Math., 5(4):545-557, 1992. Google Scholar
  38. Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford. Single Pass Spectral Sparsification in Dynamic Streams. SIAM J. Comput., 46(1):456-477, 2017. URL: https://doi.org/10.1137/141002281.
  39. Michael Kapralov, Navid Nouri, Aaron Sidford, and Jakab Tardos. Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space. CoRR, abs/1903.12150, 2019. URL: http://arxiv.org/abs/1903.12150.
  40. Michael Kapralov and David P. Woodruff. Spanners and sparsifiers in dynamic streams. In Magnús M. Halldórsson and Shlomi Dolev, editors, ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15-18, 2014, pages 272-281. ACM, 2014. URL: https://doi.org/10.1145/2611462.2611497.
  41. Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, and Peter Robinson. Distributed Computation of Large-scale Graph Problems. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 391-410, 2015. Google Scholar
  42. Felix Lazebnik, Vasiliy A Ustimenko, and Andrew J Woldar. A new series of dense graphs of high girth. Bulletin of the American mathematical society, 32(1):73-79, 1995. Google Scholar
  43. Felix Lazebnik, Vasiliy A. Ustimenko, and Andrew J. Woldar. A characterization of the components of the graphs D(k, q). Discrete Mathematics, 157(1-3):271-283, 1996. URL: https://doi.org/10.1016/S0012-365X(96)83019-6.
  44. Merav Parter, Ronitt Rubinfeld, Ali Vakilian, and Anak Yodpinyanee. Local Computation Algorithms for Spanners. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 58:1-58:21. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.58.
  45. Merav Parter and Eylon Yogev. Congested Clique Algorithms for Graph Spanners. In Ulrich Schmid and Josef Widder, editors, 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, volume 121 of LIPIcs, pages 40:1-40:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.40.
  46. David Peleg and Jeffrey D. Ullman. An Optimal Synchronizer for the Hypercube. SIAM J. Comput., 18(4):740-747, 1989. Google Scholar
  47. David Peleg and Eli Upfal. A Tradeoff between Space and Efficiency for Routing Tables (Extended Abstract). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 43-52, 1988. Google Scholar
  48. Jeff M. Phillips, Elad Verbin, and Qin Zhang. Lower bounds for number-in-hand multiparty communication complexity, made easy. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 486-501, 2012. Google Scholar
  49. Mikkel Thorup and Uri Zwick. Compact routing schemes. In SPAA, pages 1-10, 2001. URL: https://doi.org/10.1145/378580.378581.
  50. Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1-24, 2005. URL: https://doi.org/10.1145/1044731.1044732.
  51. Jacques Tits. Sur la trialité et certains groupes qui s' en déduisent. Publications Mathématiques de l'IHÉS, 2:13-60, 1959. Google Scholar
  52. Omri Weinstein and David P. Woodruff. The Simultaneous Communication of Disjointness with Applications to Data Streams. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 1082-1093. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-47672-7_88.
  53. Rephael Wenger. Extremal graphs with no C^4’s, C^6’s, or C^10’s. J. Comb. Theory, Ser. B, 52(1):113-116, 1991. URL: https://doi.org/10.1016/0095-8956(91)90097-4.
  54. David P Woodruff. Additive spanners in nearly quadratic time. In International Colloquium on Automata, Languages, and Programming, pages 463-474. Springer, 2010. Google Scholar
  55. David P. Woodruff and Qin Zhang. Tight bounds for distributed functional monitoring. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 941-960, 2012. Google Scholar
  56. David P. Woodruff and Qin Zhang. When Distributed Computation Is Communication Expensive. In Distributed Computing - 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14-18, 2013. Proceedings, pages 16-30, 2013. Google Scholar
  57. Yuansheng Yang and Weifa Liang. The minimum number of vertices with girth 6 and degree set D=r, m. Discrete Mathematics, 269(1-3):249-258, 2003. URL: https://doi.org/10.1016/S0012-365X(02)00758-6.
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