publication . Preprint . Article . 2021

Smaller Cuts, Higher Lower Bounds

Amir Abboud; Keren Censor-Hillel; Seri Khoury; Ami Paz;
Open Access
  • Published: 31 Oct 2021 Journal: ACM Transactions on Algorithms, volume 17, pages 1-40 (issn: 1549-6325, eissn: 1549-6333, Copyright policy)
  • Publisher: Association for Computing Machinery (ACM)
Abstract
This paper proves strong lower bounds for distributed computing in the CONGEST model, by presenting the bit-gadget: a new technique for constructing graphs with small cuts. The contribution of bit-gadgets is twofold. First, developing careful sparse graph constructions with small cuts extends known techniques to show a near-linear lower bound for computing the diameter, a result previously known only for dense graphs. Moreover, the sparseness of the construction plays a crucial role in applying it to approximations of various distance computation problems, drastically improving over what can be obtained when using dense graphs. Second, small cuts are essential for proving super-linear lower bounds, none of which were known prior to this work. In fact, they allow us to show near-quadratic lower bounds for several problems, such as exact minimum vertex cover or maximum independent set, as well as for coloring a graph with its chromatic number. Such strong lower bounds are not limited to NP-hard problems, as given by two simple graph problems in P which are shown to require a quadratic and near-quadratic number of rounds. All of the above are optimal up to logarithmic factors. In addition, in this context, the complexity of the all-pairs-shortest-paths problem is discussed. Finally, it is shown that graph constructions for CONGEST lower bounds translate to lower bounds for the semi-streaming model, despite being very different in its nature.
Comment: This is work is a merger of arXiv:1605.05109 and arXiv:1705.05646
Persistent Identifiers

doi: 10.1145/3469834

Subjects
free text keywords: Mathematics (miscellaneous), Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Data Structures and Algorithms, Mathematics, Independent set, Quadratic equation, Logarithm, Dense graph, Context (language use), Vertex cover, Discrete mathematics, Distributed algorithm, Upper and lower bounds
Related Organizations
View more
Funded by
EC| BANDWIDTH
Project
BANDWIDTH
The cost of limited communication bandwidth in distributed computing
  • Funder: European Commission (EC)
  • Project Code: 755839
  • Funding stream: H2020 | ERC | ERC-STG
Download fromView all 2 versions
Open Access
arXiv.org e-Print Archive
Preprint . 2019
Providers: arXiv.org e-Print Archive
null
ACM Transactions on Algorithms
Article . 2021
Providers: Crossref

[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.

[2] Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1681{1697, 2015.

[3] Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and xed parameter subquadratic algorithms for radius and diameter in sparse graphs. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 377{391, 2016.

[4] Pierre Aboulker, Marthe Bonamy, Nicolas Bousquet, and Louis Esperet. Distributed coloring in sparse graphs with fewer colors. In ACM Symposium on Principles of Distributed Computing, PODC, pages 419{425, 2018.

[5] Udit Agarwal and Vijaya Ramachandran. A faster deterministic distributed algorithm for weighted apsp through pipelining. CoRR, abs/1804.05441, 2018.

[6] Udit Agarwal, Vijaya Ramachandran, Valerie King, and Matteo Pontecorvi. A deterministic distributed algorithm for exact weighted all-pairs shortest paths in Oe(n3=2) rounds. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC, pages 199{205, 2018.

[7] Kook Jin Ahn and Sudipto Guha. Graph sparsi cation in the semi-streaming model. In Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP, pages 328{338, 2009.

[8] Matti Astrand, Patrik Floreen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto. A local 2-approximation algorithm for the vertex cover problem. In Proceedings of the 23rd International Symposium on Distributed Computing, DISC, pages 191{205, 2009.

[9] Matti Astrand and Jukka Suomela. Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, pages 294{302, 2010.

[10] Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Gha ari, and Gregory Schwartzman. Distributed approximation of maximum independent set and maximum matching. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC, pages 165{174, 2017.

[11] Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. A distributed (2+ )- approximation for vertex cover in o(log / log log ) rounds. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC, pages 3{8, 2016.

[12] Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 623{632, 2002.

[13] Leonid Barenboim. On the locality of some NP-complete problems. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming, ICALP, pages 403{415, 2012. [OpenAIRE]

[14] Leonid Barenboim. Deterministic ( + 1)-coloring in sublinear (in ) time in static, dynamic, and faulty networks. J. ACM, 63(5):47:1{47:22, 2016.

[15] Leonid Barenboim and Michael Elkin. Deterministic distributed vertex coloring in polylogarithmic time. J. ACM, 58(5):23:1{23:25, 2011.

4 research outcomes, page 1 of 1
Abstract
This paper proves strong lower bounds for distributed computing in the CONGEST model, by presenting the bit-gadget: a new technique for constructing graphs with small cuts. The contribution of bit-gadgets is twofold. First, developing careful sparse graph constructions with small cuts extends known techniques to show a near-linear lower bound for computing the diameter, a result previously known only for dense graphs. Moreover, the sparseness of the construction plays a crucial role in applying it to approximations of various distance computation problems, drastically improving over what can be obtained when using dense graphs. Second, small cuts are essential for proving super-linear lower bounds, none of which were known prior to this work. In fact, they allow us to show near-quadratic lower bounds for several problems, such as exact minimum vertex cover or maximum independent set, as well as for coloring a graph with its chromatic number. Such strong lower bounds are not limited to NP-hard problems, as given by two simple graph problems in P which are shown to require a quadratic and near-quadratic number of rounds. All of the above are optimal up to logarithmic factors. In addition, in this context, the complexity of the all-pairs-shortest-paths problem is discussed. Finally, it is shown that graph constructions for CONGEST lower bounds translate to lower bounds for the semi-streaming model, despite being very different in its nature.
Comment: This is work is a merger of arXiv:1605.05109 and arXiv:1705.05646
Persistent Identifiers

doi: 10.1145/3469834

Subjects
free text keywords: Mathematics (miscellaneous), Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Data Structures and Algorithms, Mathematics, Independent set, Quadratic equation, Logarithm, Dense graph, Context (language use), Vertex cover, Discrete mathematics, Distributed algorithm, Upper and lower bounds
Related Organizations
View more
Funded by
EC| BANDWIDTH
Project
BANDWIDTH
The cost of limited communication bandwidth in distributed computing
  • Funder: European Commission (EC)
  • Project Code: 755839
  • Funding stream: H2020 | ERC | ERC-STG
Download fromView all 2 versions
Open Access
arXiv.org e-Print Archive
Preprint . 2019
Providers: arXiv.org e-Print Archive
null
ACM Transactions on Algorithms
Article . 2021
Providers: Crossref

[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.

[2] Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1681{1697, 2015.

[3] Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and xed parameter subquadratic algorithms for radius and diameter in sparse graphs. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 377{391, 2016.

[4] Pierre Aboulker, Marthe Bonamy, Nicolas Bousquet, and Louis Esperet. Distributed coloring in sparse graphs with fewer colors. In ACM Symposium on Principles of Distributed Computing, PODC, pages 419{425, 2018.

[5] Udit Agarwal and Vijaya Ramachandran. A faster deterministic distributed algorithm for weighted apsp through pipelining. CoRR, abs/1804.05441, 2018.

[6] Udit Agarwal, Vijaya Ramachandran, Valerie King, and Matteo Pontecorvi. A deterministic distributed algorithm for exact weighted all-pairs shortest paths in Oe(n3=2) rounds. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC, pages 199{205, 2018.

[7] Kook Jin Ahn and Sudipto Guha. Graph sparsi cation in the semi-streaming model. In Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP, pages 328{338, 2009.

[8] Matti Astrand, Patrik Floreen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto. A local 2-approximation algorithm for the vertex cover problem. In Proceedings of the 23rd International Symposium on Distributed Computing, DISC, pages 191{205, 2009.

[9] Matti Astrand and Jukka Suomela. Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, pages 294{302, 2010.

[10] Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Gha ari, and Gregory Schwartzman. Distributed approximation of maximum independent set and maximum matching. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC, pages 165{174, 2017.

[11] Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. A distributed (2+ )- approximation for vertex cover in o(log / log log ) rounds. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC, pages 3{8, 2016.

[12] Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 623{632, 2002.

[13] Leonid Barenboim. On the locality of some NP-complete problems. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming, ICALP, pages 403{415, 2012. [OpenAIRE]

[14] Leonid Barenboim. Deterministic ( + 1)-coloring in sublinear (in ) time in static, dynamic, and faulty networks. J. ACM, 63(5):47:1{47:22, 2016.

[15] Leonid Barenboim and Michael Elkin. Deterministic distributed vertex coloring in polylogarithmic time. J. ACM, 58(5):23:1{23:25, 2011.

4 research outcomes, page 1 of 1
graphPowered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue