Document Open Access Logo

Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model

Authors Keren Censor-Hillel, Seri Khoury, Ami Paz

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.10.pdf
  • Filesize: 0.61 MB
  • 16 pages

Document Identifiers

Author Details

Keren Censor-Hillel
Seri Khoury
Ami Paz

Cite As Get BibTex

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 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.10

Abstract

We present the first super-linear lower bounds for natural graph problems in the CONGEST model, answering a long-standing open question.

Specifically, we show that any exact computation of a minimum vertex cover or a maximum independent set requires a near-quadratic number of rounds in the CONGEST model, as well as any algorithm for computing the chromatic number of the graph. We further show that such strong lower bounds are not limited to NP-hard problems, by showing two simple graph problems in P which require a quadratic and near-quadratic number of rounds.

Finally, we address the problem of computing an exact solution to weighted all-pairs-shortest-paths (APSP), which arguably may be considered as a candidate for having a super-linear lower bound. We show a simple linear lower bound for this problem, which implies a separation between the weighted and unweighted cases, since the latter is known to have a sub-linear complexity. We also formally prove that the standard Alice-Bob framework is incapable of providing a super-linear lower bound for exact weighted APSP, whose complexity remains an intriguing open question.

Subject Classification

Keywords
  • CONGEST
  • Lower Bounds
  • Minimum Vertex Cover
  • Chromatic Number
  • Weighted APSP

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 30th International Symposium on Distributed Computing, DISC, pages 29-42, 2016. Google Scholar
  2. Amir Abboud and Kevin Lewi. Exact weight subgraphs and the k-sum conjecture. In 40th International Colloquium on Automata, Languages, and Programming, ICALP, pages 1-12, 2013. Google Scholar
  3. Amir Abboud, Kevin Lewi, and Ryan Williams. Losing weight by gaining edges. In 22th Annual European Symposium on Algorithms, ESA, pages 1-12, 2014. Google Scholar
  4. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997. Google Scholar
  5. Matti Åstrand, Patrik Floréen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto. A local 2-approximation algorithm for the vertex cover problem. In 23rd International Symposium on Distributed Computing, DISC, pages 191-205, 2009. Google Scholar
  6. Matti Åstrand and Jukka Suomela. Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, pages 294-302, 2010. Google Scholar
  7. Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari, and Gregory Schwartzman. Distributed approximation of maximum independent set and maximum matching. In ACM Symposium on Principles of Distributed Computing, PODC, 2017. Google Scholar
  8. Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. A distributed (2+ε)-approximation for vertex cover in o(logδ/ε log log δ) rounds. In 2016 ACM Symposium on Principles of Distributed Computing, PODC, pages 3-8, 2016. Google Scholar
  9. Leonid Barenboim. On the locality of some NP-complete problems. In 39th International Colloquium on Automata, Languages, and Programming, ICALP, pages 403-415, 2012. Google Scholar
  10. Leonid Barenboim. Deterministic (Δ + 1)-coloring in sublinear (in Δ) time in static, dynamic, and faulty networks. J. ACM, 63(5):47:1-47:22, 2016. Google Scholar
  11. Leonid Barenboim and Michael Elkin. Deterministic distributed vertex coloring in polylogarithmic time. J. ACM, 58(5):23:1-23:25, 2011. Google Scholar
  12. Leonid Barenboim and Michael Elkin. Combinatorial algorithms for distributed graph coloring. Distributed Computing, 27(2):79-93, 2014. Google Scholar
  13. Leonid Barenboim, Michael Elkin, and Fabian Kuhn. Distributed (delta+1)-coloring in linear (in delta) time. SIAM J. Comput., 43(1):72-95, 2014. Google Scholar
  14. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. J. ACM, 63(3):20:1-20:45, 2016. Google Scholar
  15. Marijke H. L. Bodlaender, Magnús M. Halldórsson, Christian Konrad, and Fabian Kuhn. Brief announcement: Local independent set approximation. In ACM Symposium on Principles of Distributed Computing, PODC, pages 93-95, 2016. Google Scholar
  16. Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. In 2015 ACM Symposium on Principles of Distributed Computing, PODC, 2015. Google Scholar
  17. Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz, and Amir Yehudayoff. Distributed construction of purely additive spanners. Distributed Computing, 2017. Google Scholar
  18. Keren Censor-Hillel, Seri Khoury, and Ami Paz. Quadratic and near-quadratic lower bounds for the CONGEST model. CoRR, abs/1705.05646, 2017. URL: https://arxiv.org/abs/1705.05646.
  19. Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS, pages 615-624, 2016. Google Scholar
  20. Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the LOCAL model. CoRR, abs/1704.06297, 2017. Google Scholar
  21. Kai-Min Chung, Seth Pettie, and Hsin-Hao Su. Distributed algorithms for the lovász local lemma and graph coloring. In ACM Symposium on Principles of Distributed Computing, PODC, pages 134-143, 2014. Google Scholar
  22. Richard Cole and Uzi Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70(1):32-53, 1986. Google Scholar
  23. Andrzej Czygrinow, Michal Hanckowiak, and Wojciech Wawrzyniak. Fast distributed approximations in planar graphs. In 22nd International Symposium on Distributed Computing, DISC, pages 78-92, 2008. Google Scholar
  24. Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Morten Stöckel. Finding even cycles faster via capped k-walks. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 112-120, 2017. Google Scholar
  25. Danny Dolev, Christoph Lenzen, and Shir Peled. Tri, Tri Again: Finding triangles and small subgraphs in a distributed setting. In 26th International Symposium on Distributed Computing, DISC, pages 195-209, 2012. Google Scholar
  26. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In 33rd ACM Symposium on Principles of Distributed Computing, PODC, pages 367-376, 2014. Google Scholar
  27. Michael Elkin. Distributed approximation: a survey. SIGACT News, 35(4):40-57, 2004. Google Scholar
  28. Michael Elkin. An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM J. Comput., 36(2):433-456, 2006. Google Scholar
  29. Michael Elkin. Distributed exact shortest paths in sublinear time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 757-770, 2017. Google Scholar
  30. Yuval Emek, Christoph Pfister, Jochen Seidel, and Roger Wattenhofer. Anonymous networks: randomization = 2-hop coloring. In ACM Symposium on Principles of Distributed Computing, PODC, pages 96-105, 2014. Google Scholar
  31. Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas, and Andrzej Pelc. Distributed computing with advice: information sensitivity of graph coloring. Distributed Computing, 21(6):395-403, 2009. Google Scholar
  32. Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. Local conflict coloring. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS, pages 625-634, 2016. Google Scholar
  33. Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks cannot compute their diameter in sublinear time. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1150-1162, 2012. Google Scholar
  34. Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing. Theory of Computing, 12(1):1-33, 2016. Google Scholar
  35. Fabrizio Grandoni, Jochen Könemann, and Alessandro Panconesi. Distributed weighted vertex cover via maximal matchings. ACM Trans. Algorithms, 5(1):6:1-6:12, 2008. Google Scholar
  36. Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi, and Mauro Sozio. A primal-dual bicriteria distributed algorithm for capacitated vertex cover. SIAM J. Comput., 38(3):825-840, 2008. Google Scholar
  37. Michal Hanckowiak, Michal Karonski, and Alessandro Panconesi. On the distributed complexity of computing maximal matchings. SIAM J. Discrete Math., 15(1):41-57, 2001. Google Scholar
  38. David G. Harris, Johannes Schneider, and Hsin-Hao Su. Distributed (Δ+1)-coloring in sublogarithmic rounds. In 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 465-478, 2016. Google Scholar
  39. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 489-498, 2016. Google Scholar
  40. Stephan Holzer, David Peleg, Liam Roditty, and Roger Wattenhofer. Distributed 3/2-approximation of the diameter. In 28th International Symposium on Distributed Computing, DISC, pages 562-564, 2014. Google Scholar
  41. 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, pages 6:1-6:16, 2015. Google Scholar
  42. Stephan Holzer and Roger Wattenhofer. Optimal distributed all pairs shortest paths and applications. In ACM Symposium on Principles of Distributed Computing, PODC, pages 355-364, 2012. Google Scholar
  43. 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 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, pages 439-441, 2016. Google Scholar
  44. Allan Grønlund Jørgensen and Seth Pettie. Threesomes, degenerates, and love triangles. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 621-630, 2014. Google Scholar
  45. Samir Khuller, Uzi Vishkin, and Neal E. Young. A primal-dual parallel approximation technique applied to weighted set and vertex covers. J. Algorithms, 17(2):280-289, 1994. Google Scholar
  46. Liah Kor, Amos Korman, and David Peleg. Tight bounds for distributed MST verification. In 28th International Symposium on Theoretical Aspects of Computer Science, STACS, pages 69-80, 2011. Google Scholar
  47. Christos Koufogiannakis and Neal E. Young. Distributed and parallel algorithms for weighted vertex cover and other covering problems. In 28th Annual ACM Symposium on Principles of Distributed Computing, PODC, pages 171-179, 2009. Google Scholar
  48. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. The price of being near-sighted. In 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 980-989, 2006. Google Scholar
  49. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. J. ACM, 63(2):17:1-17:44, 2016. Google Scholar
  50. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, New York, 1997. Google Scholar
  51. Christoph Lenzen and Boaz Patt-Shamir. Fast partial distance estimation and applications. In 2015 ACM Symposium on Principles of Distributed Computing, PODC, 2015. Google Scholar
  52. Christoph Lenzen and David Peleg. Efficient distributed source detection with limited bandwidth. In ACM Symposium on Principles of Distributed Computing, PODC, pages 375-382, 2013. Google Scholar
  53. Christoph Lenzen and Roger Wattenhofer. Leveraging linial’s locality limit. In 22nd International Symposium on Distributed Computing, DISC, pages 394-407, 2008. Google Scholar
  54. Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193-201, 1992. Google Scholar
  55. Dániel Marx and Michal Pilipczuk. Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask). In 31st International Symposium on Theoretical Aspects of Computer Science, STACS, pages 542-553, 2014. Google Scholar
  56. Thomas Moscibroda and Roger Wattenhofer. Coloring unstructured radio networks. Distributed Computing, 21(4):271-284, 2008. Google Scholar
  57. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In Symposium on Theory of Computing, STOC,, pages 565-573, 2014. Google Scholar
  58. Danupon Nanongkai, Atish Das Sarma, and Gopal Pandurangan. A tight unconditional lower bound on distributed randomwalk computation. In 30th Annual ACM Symposium on Principles of Distributed Computing, PODC, pages 257-266, 2011. Google Scholar
  59. Alessandro Panconesi and Romeo Rizzi. Some simple distributed algorithms for sparse networks. Distributed Computing, 14(2):97-100, 2001. Google Scholar
  60. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. Google Scholar
  61. David Peleg, Liam Roditty, and Elad Tal. Distributed algorithms for network diameter and girth. In 39th International Colloquium on Automata, Languages, and Programming, ICALP, pages 660-672, 2012. Google Scholar
  62. David Peleg and Vitaly Rubinovich. A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput., 30(5):1427-1442, 2000. Google Scholar
  63. Seth Pettie and Hsin-Hao Su. Distributed coloring algorithms for triangle-free graphs. Inf. Comput., 243:263-280, 2015. Google Scholar
  64. Valentin Polishchuk and Jukka Suomela. A simple local 3-approximation algorithm for vertex cover. Inf. Process. Lett., 109(12):642-645, 2009. Google Scholar
  65. 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
  66. Johannes Schneider and Roger Wattenhofer. Distributed coloring depending on the chromatic number or the neighborhood growth. In 18th International Colloquium on Structural Information and Communication Complexity, SIROCCO, pages 246-257, 2011. Google Scholar
  67. Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput., 42(3):831-854, 2013. 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