Document Open Access Logo

Improved Hardness of Approximation of Diameter in the CONGEST Model

Authors Ofer Grossman, Seri Khoury, Ami Paz

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.19.pdf
  • Filesize: 1.04 MB
  • 16 pages

Document Identifiers

Author Details

Ofer Grossman
  • MIT, Cambridge, MA, USA
Seri Khoury
  • University of California, Berkeley, CA, USA
Ami Paz
  • Faculty of Computer Science, Universität Wien, Austria

Funding

  • Grossman, Ofer: Supported by a Fannie and John Hertz Foundation Fellowship.
  • Paz, Ami: Supported by the Austrian Science Fund (FWF): P 33775-N, Fast Algorithms for a Reactive Network Layer.

Acknowledgements

We thank Noga Alon for useful pointers regarding generalized polygons. This work was done while the fist two authors were visiting the Simon’s Institute for the Theory of Computing.

Cite As Get BibTex

Ofer Grossman, Seri Khoury, and Ami Paz. Improved Hardness of Approximation of Diameter in the CONGEST Model. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.DISC.2020.19

Abstract

We study the problem of approximating the diameter D of an unweighted and undirected n-node graph in the congest model. Through a connection to extremal combinatorics, we show that a (6/11 + ε)-approximation requires Ω(n^{1/6}/log n) rounds, a (4/7 + ε)-approximation requires Ω(n^{1/4}/log n) rounds, and a (3/5 + ε)-approximation requires Ω(n^{1/3}/log n) rounds. These lower bounds are robust in the sense that they hold even against algorithms that are allowed to return an additional small additive error. Prior to our work, only lower bounds for (2/3 + ε)-approximation were known [Frischknecht et al. SODA 2012, Abboud et al. DISC 2016]. 
Furthermore, we prove that distinguishing graphs of diameter 3 from graphs of diameter 5 requires Ω(n/log n) rounds. This stands in sharp contrast to previous work: while there is an algorithm that returns an estimate ⌊ 2/3D ⌋ ≤ D̃ ≤ D in Õ(√n+D) rounds [Holzer et al. DISC 2014], our lower bound implies that any algorithm for returning an estimate 2/3D ≤ D̃ ≤ D requires ̃Ω(n) rounds.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Approximation algorithms
  • Theory of computation → Distributed computing models
Keywords
  • Distributed graph algorithms
  • Approximation algorithms
  • Lower bounds

Metrics

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

References

  1. Amir Abboud, Keren Censor-Hillel, and Seri Khoury. Near-linear lower bounds for distributed distance computations, even in sparse networks. In Distributed Computing - 30th International Symposium, DISC, volume 9888 of Lecture Notes in Computer Science, pages 29-42. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-53426-7_3.
  2. Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Christoph Lenzen. Fooling views: A new lower bound technique for distributed computations under congestion. Distributed Computing, pages 1-15, 2020. Google Scholar
  3. Bertie Ancona, Keren Censor-Hillel, Yuval Efron, Mina Dalirrooyfard, and Virginia Vassilevska Williams. Distributed distance approximation. In submission, 2020. Google Scholar
  4. Clark T. Benson. Minimal regular graphs of girths eight and twelve. Canadian Journal of Mathematics, 18:1091–1094, 1966. URL: https://doi.org/10.4153/CJM-1966-109-8.
  5. Karl Bringmann and Sebastian Krinninger. Brief announcement: A note on hardness of diameter approximation. In 31st International Symposium on Distributed Computing, DISC, volume 91 of LIPIcs, pages 44:1-44:3. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.44.
  6. Keren Censor-Hillel, Michal Dory, Janne H. Korhonen, and Dean Leitersdorf. Fast approximate shortest paths in the congested clique. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC, pages 74-83. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331633.
  7. Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC, pages 143-152. ACM, 2015. URL: https://doi.org/10.1145/2767386.2767414.
  8. Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz, and Amir Yehudayoff. Distributed construction of purely additive spanners. In Proceedings of the 30th International Symposium on Distributed Computing, DISC, pages 129-142, 2016. Google Scholar
  9. Keren Censor-Hillel, Seri Khoury, and Ami Paz. Quadratic and near-quadratic lower bounds for the CONGEST model. In 31st International Symposium on Distributed Computing, DISC, pages 10:1-10:16, 2017. Google Scholar
  10. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proceedings of the 33rd ACM Symposium on Principles of Distributed Computing, PODC, pages 367-376, 2014. Google Scholar
  11. Yuval Efron, Ofer Grossman, and Seri Khoury. Beyond alice and bob: Improved inapproximability for maximum independent set in CONGEST. In Yuval Emek and Christian Cachin, editors, PODC '20: ACM Symposium on Principles of Distributed Computing, Virtual Event, pages 511-520. ACM, 2020. URL: https://doi.org/10.1145/3382734.3405702.
  12. Orr Fischer, Tzlil Gonen, Fabian Kuhn, and Rotem Oshman. Possibilities and impossibilities for distributed subgraph detection. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA, pages 153-162. ACM, 2018. Google Scholar
  13. 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. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00071.
  14. Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks cannot compute their diameter in sublinear time. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1150-1162, 2012. Google Scholar
  15. Zoltán Füredi and Miklós Simonovits. The History of Degenerate (Bipartite) Extremal Graph Problems, pages 169-264. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. URL: https://doi.org/10.1007/978-3-642-39286-3_7.
  16. Stephan Holzer, David Peleg, Liam Roditty, and Roger Wattenhofer. Distributed 3/2-approximation of the diameter. In Proceedings of the 28th International Symposium on Distributed Computing, DISC, pages 562-564, 2014. Google Scholar
  17. Stephan Holzer and Nathan Pinsker. Approximation of distances and shortest paths in the broadcast congest clique. In 19th International Conference on Principles of Distributed Systems, OPODIS, volume 46 of LIPIcs, pages 6:1-6:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2015.6.
  18. Stephan Holzer and Roger Wattenhofer. Optimal distributed all pairs shortest paths and applications. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC, pages 355-364, 2012. Google Scholar
  19. Qiang-Sheng Hua, Haoqiang Fan, Lixiang Qian, Ming Ai, Yangyang Li, Xuanhua Shi, and Hai Jin. Brief announcement: A tight distributed algorithm for all pairs shortest paths and applications. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, pages 439-441, 2016. Google Scholar
  20. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, New York, NY, USA, 1997. Google Scholar
  21. Christoph Lenzen and David Peleg. Efficient distributed source detection with limited bandwidth. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC, pages 375-382, 2013. Google Scholar
  22. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. Google Scholar
  23. David Peleg, Liam Roditty, and Elad Tal. Distributed algorithms for network diameter and girth. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming, ICALP, pages 660-672, 2012. Google Scholar
  24. Alexander A. Razborov. On the distributional complexity of disjointness. Theor. Comput. Sci., 106(2):385-390, 1992. Google Scholar
  25. R. Singleton. On minimal graphs of maximum even girth. Journal of Combinatorial Theory, 1:306-332, December 1966. URL: https://doi.org/10.1016/S0021-9800(66)80054-6.
  26. 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, STOC, 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 About DROPS Imprint Privacy Contact