Document Open Access Logo

Low Diameter Graph Decompositions by Approximate Distance Computation

Authors Ruben Becker, Yuval Emek, Christoph Lenzen

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.50.pdf
  • Filesize: 0.69 MB
  • 29 pages

Document Identifiers

Author Details

Ruben Becker
  • Gran Sasso Science Institute, L'Aquila, Italy
Yuval Emek
  • Technion - Israel Institute of Technology, Haifa, Israel
Christoph Lenzen
  • MPI for Informatics, Saarland Informatics Campus, Saarbrücken, Germany

Funding

  • Emek, Yuval: This work has been supported in part by an Israeli Science Foundation grant number 1016/17.

Cite AsGet BibTex

Ruben Becker, Yuval Emek, and Christoph Lenzen. Low Diameter Graph Decompositions by Approximate Distance Computation. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 50:1-50:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.50

Abstract

In many models for large-scale computation, decomposition of the problem is key to efficient algorithms. For distance-related graph problems, it is often crucial that such a decomposition results in clusters of small diameter, while the probability that an edge is cut by the decomposition scales linearly with the length of the edge. There is a large body of literature on low diameter graph decomposition with small edge cutting probabilities, with all existing techniques heavily building on single source shortest paths (SSSP) computations. Unfortunately, in many theoretical models for large-scale computations, the SSSP task constitutes a complexity bottleneck. Therefore, it is desirable to replace exact SSSP computations with approximate ones. However this imposes a fundamental challenge since the existing constructions of low diameter graph decomposition with small edge cutting probabilities inherently rely on the subtractive form of the triangle inequality, which fails to hold under distance approximation. The current paper overcomes this obstacle by developing a technique termed blurry ball growing. By combining this technique with a clever algorithmic idea of Miller et al. (SPAA 2013), we obtain a construction of low diameter decompositions with small edge cutting probabilities which replaces exact SSSP computations by (a small number of) approximate ones. The utility of our approach is showcased by deriving efficient algorithms that work in the CONGEST, PRAM, and semi-streaming models of computation. As an application, we obtain metric tree embedding algorithms in the vein of Bartal (FOCS 1996) whose computational complexities in these models are optimal up to polylogarithmic factors. Our embeddings have the additional useful property that the tree can be mapped back to the original graph such that each edge is "used" only logaritmically many times, which is of interest for capacitated problems and simulating CONGEST algorithms on the tree into which the graph is embedded.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parallel algorithms
  • Theory of computation → Distributed algorithms
Keywords
  • graph decompositions
  • metric tree embeddings
  • distributed graph algorithms
  • parallel graph algorithms
  • (semi-)streaming graph algorithms

Metrics

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

References

  1. Amir Abboud, Greg Bodwin, and Seth Pettie. A Hierarchy of Lower Bounds for Sublinear Additive Spanners. SIAM J. Comput., 47(6):2203-2236, 2018. Google Scholar
  2. Ittai Abraham, Yair Bartal, and Ofer Neiman. Nearly Tight Low Stretch Spanning Trees. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 781-790, 2008. Google Scholar
  3. Ittai Abraham and Ofer Neiman. Using petal-decompositions to build a low stretch spanning tree. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC, pages 395-406, 2012. Google Scholar
  4. Noga Alon, Richard M. Karp, David Peleg, and Douglas B. West. A Graph-Theoretic Game and Its Application to the k-Server Problem. SIAM J. Comput., 24(1):78-100, 1995. Google Scholar
  5. Baruch Awerbuch. Complexity of Network Synchronization. J. ACM, 32(4):804-823, 1985. Google Scholar
  6. Baruch Awerbuch and David Peleg. Sparse Partitions (Extended Abstract). In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume II, pages 503-513, 1990. Google Scholar
  7. Yair Bartal. Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications. In 37th Annual Symposium on Foundations of Computer Science, FOCS, pages 184-193, 1996. Google Scholar
  8. Yair Bartal. On Approximating Arbitrary Metrices by Tree Metrics. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, STOC, pages 161-168, 1998. Google Scholar
  9. Yair Bartal. Graph Decomposition Lemmas and Their Role in Metric Embedding Methods. In Algorithms - ESA 2004, 12th Annual European Symposium, pages 89-97, 2004. Google Scholar
  10. Surender Baswana. Streaming algorithm for graph spanners - single pass and constant processing time per edge. Inf. Process. Lett., 106(3):110-114, 2008. Google Scholar
  11. Ruben Becker, Yuval Emek, Mohsen Ghaffari, and Christoph Lenzen. Distributed Algorithms for Low Stretch Spanning Trees. In 33rd International Symposium on Distributed Computing, DISC, 2019. To appear. Google Scholar
  12. Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, pages 7:1-7:16, 2017. Google Scholar
  13. Guy E. Blelloch, Anupam Gupta, Ioannis Koutis, Gary L. Miller, Richard Peng, and Kanat Tangwongsan. Nearly-Linear Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs. Theory of Computing Systems, 55(3):521-554, 2014. Google Scholar
  14. Edith Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. J. ACM, 47(1):132-166, 2000. Google Scholar
  15. Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu. Solving SDD linear systems in nearly mlog^1/2n time. In Symposium on Theory of Computing, STOC, pages 343-352, 2014. Google Scholar
  16. Michael B. Cohen, Gary L. Miller, Jakub W. Pachocki, Richard Peng, and Shen Chen Xu. Stretching Stretch. CoRR, abs/1401.2454, 2014. URL: http://arxiv.org/abs/1401.2454.
  17. Michael Elkin. Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Trans. Algorithms, 7(2):20:1-20:17, 2011. Google Scholar
  18. Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng. Lower-Stretch Spanning Trees. SIAM J. Comput., 38(2):608-628, 2008. Google Scholar
  19. Michael Elkin and Ofer Neiman. Distributed Strong Diameter Network Decomposition: Extended Abstract. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 211-216, 2016. Google Scholar
  20. Michael Elkin and Ofer Neiman. Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 128-137, 2016. Google Scholar
  21. Michael Elkin and Jian Zhang. Efficient algorithms for constructing (1+epsilon, beta)-spanners in the distributed and streaming models. Distributed Computing, 18(5):375-385, 2006. Google Scholar
  22. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485-497, 2004. 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. Sebastian Forster and Gramoz Goranci. Dynamic low-stretch trees via dynamic low-diameter decompositions. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019., pages 377-388, 2019. Google Scholar
  25. Sebastian Forster and Danupon Nanongkai. A Faster Distributed Single-Source Shortest Paths Algorithm. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 686-697, 2018. Google Scholar
  26. Stephan Friedrichs and Christoph Lenzen. Parallel Metric Tree Embedding Based on an Algebraic View on Moore-Bellman-Ford. J. ACM, 65(6):43:1-43:55, 2018. Google Scholar
  27. Juan A Garay, Shay Kutten, and David Peleg. A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM Journal on Computing, 27(1):302-316, 1998. Google Scholar
  28. Mohsen Ghaffari and Bernhard Haeupler. Distributed Algorithms for Planar Networks II: Low-congestion Shortcuts, MST, and Min-Cut. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 202-219, 2016. Google Scholar
  29. Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, and Boaz Patt-Shamir. Near-Optimal Distributed Maximum Flow. SIAM Journal on Computing, 47(6):2078-2117, 2018. Google Scholar
  30. Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the Complexity of Local Distributed Graph Problems. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 784-797, 2017. Google Scholar
  31. Mohsen Ghaffari and Christoph Lenzen. Near-Optimal Distributed Tree Embedding. In Distributed Computing - 28th International Symposium, DISC, pages 197-211, 2014. Google Scholar
  32. Monika Rauch Henzinger, Prabhakar Raghavan, and Sridhar Rajagopalan. Computing on data streams. In External Memory Algorithms, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, May 20-22, 1998, pages 107-118, 1998. Google Scholar
  33. Michael Kapralov and Rina Panigrahy. Spectral sparsification via random spanners. In Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012, pages 393-398, 2012. Google Scholar
  34. Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan, and Kunal Talwar. Efficient distributed approximation algorithms via probabilistic tree embeddings. Distributed Computing, 25(3):189-205, 2012. Google Scholar
  35. Ioannis Koutis. Simple parallel and distributed algorithms for spectral graph sparsification. In 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '14, Prague, Czech Republic - June 23 - 25, 2014, pages 61-66, 2014. Google Scholar
  36. Ioannis Koutis, Gary L. Miller, and Richard Peng. A Nearly-m log n Time Solver for SDD Linear Systems. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 590-598, 2011. Google Scholar
  37. Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching Optimality for Solving SDD Linear Systems. SIAM J. Comput., 43(1):337-354, 2014. Google Scholar
  38. Shay Kutten and David Peleg. Fast Distributed Construction of Smallk-Dominating Sets and Applications. Journal of Algorithms, 28(1):40-66, 1998. Google Scholar
  39. Christoph Lenzen, Boaz Patt-Shamir, and David Peleg. Distributed distance computation and routing with small messages. Distributed Computing, 2018. Google Scholar
  40. Nathan Linial and Michael Saks. Low diameter graph decompositions. Combinatorica, 13(4):441-454, 1993. Google Scholar
  41. Andrew McGregor. Graph stream algorithms: a survey. SIGMOD Record, 43(1):9-20, 2014. Google Scholar
  42. Gary L. Miller, Richard Peng, Adrian Vladu, and Shen Chen Xu. Improved Parallel Algorithms for Spanners and Hopsets. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13-15, 2015, pages 192-201, 2015. Google Scholar
  43. Gary L. Miller, Richard Peng, and Shen Chen Xu. Parallel graph decompositions using random shifts. In 25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '13, Montreal, QC, Canada - July 23 - 25, 2013, pages 196-203, 2013. Google Scholar
  44. D. Peleg. Distributed Computing: A Locality-Sensitive Approach. Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, 2000. Google Scholar
  45. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. Google Scholar
  46. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed Verification and Hardness of Distributed Approximation. SIAM J. Comput., 41(5):1235-1265, 2012. Google Scholar
  47. Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 81-90, 2004. 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