Document Open Access Logo

Distributed Planar Reachability in Nearly Optimal Time

Author Merav Parter

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.38.pdf
  • Filesize: 0.76 MB
  • 17 pages

Document Identifiers

Author Details

Merav Parter
  • Weizmann Institute of Science, Rehovot, Israel

Funding

Partially funded by the ISF, grant no. 713130

Cite As Get BibTex

Merav Parter. Distributed Planar Reachability in Nearly Optimal Time. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.DISC.2020.38

Abstract

We present nearly optimal distributed algorithms for fundamental reachability problems in planar graphs. In the single-source reachability problem given is an n-vertex directed graph G = (V,E) and a source node s, it is required to determine the subset of nodes that are reachable from s in G. We present the first distributed reachability algorithm for planar graphs that runs in nearly optimal time of Õ(D) rounds, where D is the undirected diameter of the graph. This improves the complexity of Õ(D²) rounds implied by the recent work of [Li and Parter, STOC'19]. 

We also consider the more general reachability problem of identifying the strongly connected components (SCCs) of the graph. We present an Õ(D)-round algorithm that computes for each node in the graph an identifier of its strongly connected component in G. No non-trivial upper bound for this problem (even in general graphs) has been known before. 

Our algorithms are based on characterizing the structural interactions between balanced cycle separators. We show that the reachability relations between separator nodes can be compressed due to a Monge-like property of their directed shortest paths. The algorithmic results are obtained by combining this structural characterization with the recursive graph partitioning machinery of [Li and Parter, STOC'19].

Subject Classification

ACM Subject Classification
  • Networks → Network algorithms
Keywords
  • Distributed Graph Algorithms
  • Planar Graphs
  • Reachability

Metrics

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

References

  1. Amir Abboud, Vincent Cohen-Addad, and Philip N Klein. New hardness results for planar graph problems in p and an algorithm for sparsest cut. In Proc. of the Symp. on Theory of Comp. (STOC), 2020. URL: http://www.wisdom.weizmann.ac.il/~robi/Bertinoro2019_FineGrained/program/program-bertinoro19.html#Cohen-Addad.
  2. Amir Abboud, Pawel Gawrychowski, Shay Mozes, and Oren Weimann. Near-optimal compression for the planar graph metric. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 530-549. SIAM, 2018. Google Scholar
  3. Glencora Borradaile, Philip N Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen. Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time. SIAM Journal on Computing, 46(4):1280-1303, 2017. Google Scholar
  4. Sergio Cabello. Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. ACM Transactions on Algorithms (TALG), 15(2):1-38, 2018. Google Scholar
  5. Shiri Chechik and Doron Mukhtar. Reachability and shortest paths in the broadcast CONGEST model. In 33rd International Symposium on Distributed Computing, DISC 2019, October 14-18, 2019, Budapest, Hungary, pages 11:1-11:13, 2019. Google Scholar
  6. 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. In Proc. of the Symp. on Theory of Comp. (STOC), pages 363-372, 2011. Google Scholar
  7. Michael Elkin. Distributed exact shortest paths in sublinear time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 757-770, 2017. Google Scholar
  8. Jittat Fakcharoenphol and Satish Rao. Planar graphs, negative weight edges, shortest paths, and near linear time. Journal of Computer and System Sciences, 72(5):868-889, 2006. Google Scholar
  9. Orr Fischer and Rotem Oshman. A distributed algorithm for directed minimum-weight spanning tree. In 33rd International Symposium on Distributed Computing, DISC 2019, October 14-18, 2019, Budapest, Hungary, pages 16:1-16:16, 2019. Google Scholar
  10. Sebastian Forster and Danupon Nanongkai. A faster distributed single-source shortest paths algorithm. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 686-697. IEEE, 2018. Google Scholar
  11. Harold N Gabow. Scaling algorithms for network problems. In 24th Annual Symposium on Foundations of Computer Science (sfcs 1983), pages 248-258. IEEE, 1983. Google Scholar
  12. Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz. Distance labeling in graphs. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 210-219. Society for Industrial and Applied Mathematics, 2001. Google Scholar
  13. Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks i: Planar embedding. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC), pages 29-38, 2016. Google Scholar
  14. Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks ii: Low-congestion shortcuts, mst, and min-cut. In Proc. of ACM-SIAM Symp. on Disc. Alg. (SODA), pages 202-219, 2016. Google Scholar
  15. Mohsen Ghaffari and Jason Li. Improved distributed algorithms for exact shortest paths. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 431-444, 2018. Google Scholar
  16. Mohsen Ghaffari and Merav Parter. Near-optimal distributed DFS in planar graphs. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, pages 21:1-21:16, 2017. URL: http://www.weizmann.ac.il/math/parter/sites/math.parter/files/uploads/planarDFS_DISC17.pdf.
  17. Mohsen Ghaffari and Rajan Udwani. Brief announcement: Distributed single-source reachability. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015, pages 163-165, 2015. Google Scholar
  18. Bernhard Haeupler, D. Ellis Hershkowitz, and David Wajc. Round- and message-optimal distributed graph algorithms. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 119-128, 2018. Google Scholar
  19. Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Low-congestion shortcuts without embedding. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 451-460. ACM, 2016. Google Scholar
  20. Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Near-optimal low-congestion shortcuts on bounded parameter graphs. In International Symposium on Distributed Computing, pages 158-172. Springer, 2016. Google Scholar
  21. Bernhard Haeupler, Jason Li, and Goran Zuzic. Minor excluded network families admit fast distributed algorithms. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 465-474, 2018. Google Scholar
  22. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In Proc. of the Symp. on Theory of Comp. (STOC), pages 489-498, 2016. Google Scholar
  23. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM Journal on Computing, STOC16:98-137, 2019. URL: https://doi.org/10.1137/16M1097808.
  24. Giuseppe F Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. Improved algorithms for min cut and max flow in undirected planar graphs. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 313-322, 2011. Google Scholar
  25. Arun Jambulapati, Yang P Liu, and Aaron Sidford. Parallel reachability in almost linear work and square root depth. arXiv preprint arXiv:1905.08841, 2019. Google Scholar
  26. Philip N Klein and Sairam Subramanian. A randomized parallel algorithm for single-source shortest paths. Journal of Algorithms, 25(2):205-220, 1997. Google Scholar
  27. Christoph Lenzen and Boaz Patt-Shamir. Fast partial distance estimation and applications. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 153-162, 2015. Google Scholar
  28. Jason Li. Distributed treewidth computation. arXiv preprint arXiv:1805.10708, 2018. Google Scholar
  29. Jason Li and Merav Parter. Planar diameter via metric compression. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019., pages 152-163, 2019. Google Scholar
  30. Richard J Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979. Google Scholar
  31. Shay Mozes and Christian Sommer. Exact distance oracles for planar graphs. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms, pages 209-222. SIAM, 2012. Google Scholar
  32. Shay Mozes and Christian Wulff-Nilsen. Shortest paths in planar graphs with real lengths in o (nlog 2 n/loglogn) time. In European Symposium on Algorithms, pages 206-217. Springer, 2010. Google Scholar
  33. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In Proc. of the Symp. on Theory of Comp. (STOC), 2014. Google Scholar
  34. David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. Google Scholar
  35. 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 Journal on Computing, 41(5):1235-1265, 2012. Google Scholar
  36. Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. Journal of the ACM (JACM), 51(6):993-1024, 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 About DROPS Imprint Privacy Contact