Distributed lower bounds for ruling sets. (English) Zbl 1539.68371
Summary: Given a graph \(G=(V,E)\), an \((\alpha,\beta)\)-ruling set is a subset \(S\subseteq V\) such that the distance between any two vertices in \(S\) is at least \(\alpha\), and the distance between any vertex in \(V\) and the closest vertex in \(S\) is at most \(\beta\). We present lower bounds for distributedly computing ruling sets. More precisely, for the problem of computing a \((2,\beta)\)-ruling set (and hence also any \((\alpha,\beta)\)-ruling set with \(\alpha>2)\) in the LOCAL model of distributed computing, we show the following, where \(n\) denotes the number of vertices, \(\Delta\) the maximum degree, and \(c\) is some universal constant independent of \(n\) and \(\Delta\): (a) Any deterministic algorithm requires \(\Omega(\min\{ \tfrac{\log\Delta}{\beta\log\log\Delta},\log_\Delta n\})\) rounds for all \(\beta\le c \cdot\min\{\sqrt{\tfrac{\log\Delta}{\log\log\Delta}},\log_\Delta n\}\). By optimizing \(\Delta\), this implies a deterministic lower bound of \(\Omega(\sqrt{\frac{\log n}{\beta\log\log n}})\) for all \(\beta\le c\,\sqrt[3]{\tfrac{\log n}{\log\log n}} \). (b) Any randomized algorithm requires \(\Omega(\min\{\frac{\log\Delta}{\beta\log\log\Delta},\log_\Delta\log n\})\) rounds for all \(\beta\le c\cdot\min\{\sqrt{\tfrac{\log\Delta}{\log\log\Delta}},\log_\Delta\log n\}\). By optimizing \(\Delta\), this implies a randomized lower bound of \(\Omega(\sqrt{\tfrac{\log \log n}{\beta\log\log\log n}})\) for all \(\beta\le c\,\sqrt[3]{\tfrac{\log\log n}{\log\log\log n}}\). For \(\beta > 1\), this improves on the previously best lower bound of \(\Omega(\log^* n)\) rounds that follows from the 30-year-old bounds of N. Linial [SIAM J. Comput. 21, No. 1, 193–201 (1992; Zbl 0787.05058)] and M. Naor [SIAM J. Discrete Math. 4, No. 3, 409–412 (1991; Zbl 0738.68007)] (resp., \( \Omega(1)\) rounds if \(\beta \in \omega(\log^* n))\). For \(\beta = 1\), i.e., for the problem of computing a maximal independent set (which is nothing else than a \((2,1)\)-ruling set), our results improve on the previously best lower bound of \(\Omega(\log^* n)\) on trees, as our bounds already hold on trees. For the maximal independent set on general graphs, a deterministic lower bound of \(\Omega(\min\{\Delta, \log_{\Delta} n\})\) and a randomized lower bound of \(\Omega(\min\{\Delta, \log_{\Delta} \log n\})\) were already known due to A. Balliu et al. [FOCS 2019, 481–497 (2019; doi:10.1109/FOCS.2019.00037)].
MSC:
| 68W15 | Distributed algorithms |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68W20 | Randomized algorithms |
Keywords:
distributed computing; LOCAL model; lower bounds; maximal independent set; ruling set; round eliminationSoftware:
GitHubReferences:
| [1] | N. Alon, L. Babai, and A. Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, J. Algorithms, 7 (1986), pp. 567-583, https://doi.org/10.1016/0196-6774(86)90019-2. · Zbl 0631.68063 |
| [2] | B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin, Network decomposition and locality in distributed computation, in Proceedings of the 30th Annual Symposium on Foundations of Computer Science, 1989, pp. 364-369, https://doi.org/10.1109/SFCS.1989.63504. |
| [3] | A. Balliu, S. Brandt, Y. Efron, J. Hirvonen, Y. Maus, D. Olivetti, and J. Suomela, Classification of distributed binary labeling problems, in Proceedings of the 34th International Symposium on Distributed Computing, 2020. · Zbl 1540.68163 |
| [4] | A. Balliu, S. Brandt, J. Hirvonen, D. Olivetti, M. Rabie, and J. Suomela, Lower bounds for maximal matchings and maximal independent sets, in Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, Baltimore, MD, 2019, pp. 481-497, https://doi.org/10.1109/FOCS.2019.00037. |
| [5] | A. Balliu, J. Hirvonen, D. Olivetti, and J. Suomela, Hardness of minimal symmetry breaking in distributed computing, in Proceedings of the ACM Symposium on Principles of Distributed Computing, 2019, pp. 369-378, https://doi.org/10.1145/3293611.3331605. · Zbl 07298699 |
| [6] | L. Barenboim and M. Elkin, Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition, Distrib. Comput., 22 (2010), pp. 363-379, https://doi.org/10.1007/s00446-009-0088-2. · Zbl 1231.68174 |
| [7] | L. Barenboim and M. Elkin, Deterministic distributed vertex coloring in polylogarithmic time, J. ACM, 58 (2011), pp. 23:1-23:25, https://doi.org/10.1145/2027216.2027221. · Zbl 1281.68164 |
| [8] | L. Barenboim and M. Elkin, Distributed Graph Coloring: Fundamentals and Recent Developments, Vol. 4, 2013, Morgan & Claypool, https://doi.org/10.2200/S00520ED1V01Y201307DCT011. · Zbl 1310.68004 |
| [9] | L. Barenboim, M. Elkin, and F. Kuhn, Distributed \(( \Delta+1)\)-coloring in linear (in \(\Delta )\) time, SIAM J. Comput., 43 (2014), pp. 72-95, https://doi.org/10.1137/12088848X. · Zbl 1311.68185 |
| [10] | L. Barenboim, M. Elkin, S. Pettie, and J. Schneider, The locality of distributed symmetry breaking, J. ACM, 63 (2016), pp. 1-45, https://doi.org/10.1145/2903137. · Zbl 1426.68020 |
| [11] | T. Bisht, K. Kothapalli, and S. V. Pemmaraju, Brief announcement: Super-fast \(t\)-ruling sets, in Proceedings of the 2014 Symposium on Principles of Distributed Computing, 2014, pp. 379-381, https://doi.org/10.1145/2611462.2611512. |
| [12] | S. Brandt, An automatic speedup theorem for distributed problems, in Proceedings of the ACM Symposium on Principles of Distributed Computing, Toronto, 2019, pp. 379-388, https://doi.org/10.1145/3293611.3331611. · Zbl 07298700 |
| [13] | S. Brandt, An Automatic Speedup Theorem for Distributed Problems, arXiv:1902.09958, 2019. · Zbl 07298700 |
| [14] | S. Brandt, O. Fischer, J. Hirvonen, B. Keller, T. Lempiäinen, J. Rybicki, J. Suomela, and J. Uitto, A lower bound for the distributed lovász local lemma, in Proceedings of the 48th ACM Symposium on Theory of Computing, ACM Press, 2016, pp. 479-488, https://doi.org/10.1145/2897518.2897570. · Zbl 1375.68191 |
| [15] | S. Brandt and D. Olivetti, Truly tight-in-\( \Delta\) bounds for bipartite maximal matching and variants, in Proceedings of PODC 20, 2020, pp. 69-78, https://doi.org/10.1145/3382734.3405745. · Zbl 07323172 |
| [16] | Y. Chang, T. Kopelowitz, and S. Pettie, An exponential separation between randomized and deterministic complexity in the LOCAL model, SIAM J. Comput., 48 (2019), pp. 122-143, https://doi.org/10.1137/17M1117537. · Zbl 1404.05203 |
| [17] | Y. Chang, W. Li, and S. Pettie, An optimal distributed \(( \Delta +1)\)-coloring algorithm?, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 445-456, https://doi.org/10.1145/3188745.3188964. · Zbl 1427.68355 |
| [18] | Y.-J. Chang, Q. He, W. Li, S. Pettie, and J. Uitto, Distributed edge coloring and a special case of the constructive Lovász local lemma, ACM Trans. Algorithms, 16 (2020), pp. 8:1-8:51, https://doi.org/10.1145/3365004. · Zbl 1454.68167 |
| [19] | K. Chung, S. Pettie, and H. Su, Distributed algorithms for the Lovász local lemma and graph coloring, Distrib. Comput., 30 (2017), pp. 261-280, https://doi.org/10.1007/s00446-016-0287-6. · Zbl 1419.68213 |
| [20] | X. Dahan, Regular graphs of large girth and arbitrary degree, Combinatorica, 34 (2014), pp. 407-426. · Zbl 1340.05117 |
| [21] | P. Fraigniaud, M. Heinrich, and A. Kosowski, Local conflict coloring, in Proceedings of the 57th Annual Symposium on Foundations of Computer Science, IEEE, 2016, pp. 625-634, https://doi.org/10.1109/FOCS.2016.73. |
| [22] | B. Gfeller and E. Vicari, A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs, in Proceedings of the ACM Symposium on Principles of Distributed Computing, 2007, pp. 53-60, https://doi.org/10.1145/1281100.1281111. · Zbl 1283.68398 |
| [23] | M. Ghaffari, An improved distributed algorithm for maximal independent set, in Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 270-277, https://doi.org/10.1137/1.9781611974331.ch20. · Zbl 1411.68175 |
| [24] | M. Ghaffari, Distributed maximal independent set using small messages, in Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 805-820, https://doi.org/10.1137/1.9781611975482.50. · Zbl 1431.68132 |
| [25] | M. Ghaffari, C. Grunau, and V. Rozhoň, Improved Deterministic Network Decomposition, CoRR, https://arxiv.org/abs/2007.08253, 2020. · Zbl 07298253 |
| [26] | M. Ghaffari, J. Hirvonen, F. Kuhn, and Y. Maus, Improved distributed \(\Delta \)-coloring, in Proceedings of the ACM Symposium on Principles of Distributed Computing, 2018, pp. 427-436, https://doi.org/10.1145/3212734.3212764. · Zbl 1428.68377 |
| [27] | M. Ghaffari and J. Portmann, Improved network decompositions using small messages with applications on MIS, neighborhood covers, and beyond, in Proceedings of the 33rd International Symposium on Distributed Computing, 2019, pp. 18:1-18:16, https://doi.org/10.4230/LIPIcs.DISC.2019.18. · Zbl 1515.68372 |
| [28] | M. Göös, J. Hirvonen, and J. Suomela, Linear-in-delta lower bounds in the LOCAL model, in Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014, pp. 86-95, https://doi.org/10.1145/2611462.2611467. · Zbl 1321.68281 |
| [29] | M. Henzinger, S. Krinninger, and D. Nanongkai, A deterministic almost-tight distributed algorithm for approximating single-source shortest paths, in Proceedings of the 48th Symposium on Theory of Computing, 2016, pp. 489-498, https://doi.org/10.1145/2897518.2897638. · Zbl 1375.68218 |
| [30] | R. M. Karp and A. Wigderson, A fast parallel algorithm for the maximal independent set problem, J. ACM, 32 (1985), pp. 762-773, https://doi.org/10.1145/4221.4226. · Zbl 0633.68026 |
| [31] | K. Kothapalli and S. V. Pemmaraju, Super-fast 3-ruling sets, in Annual Conference on Foundations of Software Technology and Theoretical Computer Science (IARCS 2012), Vol. 18, 2012, pp. 136-147, https://doi.org/10.4230/LIPIcs.FSTTCS.2012.136. · Zbl 1354.68126 |
| [32] | F. Kuhn, Y. Maus, and S. Weidner, Deterministic distributed ruling sets of line graphs, in Structural Information and Communication Complexity-25th International Colloquium, Ma’ale HaHamisha, Israel, 2018, pp. 193-208, https://doi.org/10.1007/978-3-030-01325-7_19. · Zbl 1517.68299 |
| [33] | F. Kuhn, T. Moscibroda, and R. Wattenhofer, Local computation: Lower and upper bounds, J. ACM, 63 (2016), pp. 17:1-17:44, https://doi.org/10.1145/2742012. · Zbl 1426.68092 |
| [34] | C. Lenzen and R. Wattenhofer, MIS on trees, in Proceedings of the ACM Annual Symposium on Principles of Distributed, 2011, pp. 41-48, https://doi.org/10.1145/1993806.1993813. · Zbl 1321.68482 |
| [35] | N. Linial, Locality in distributed graph algorithms, SIAM J. Comput., 21 (1992), pp. 193-201, https://doi.org/10.1137/0221015. · Zbl 0787.05058 |
| [36] | M. Luby, A simple parallel algorithm for the maximal independent set problem, SIAM J. Comput., 15 (1986), pp. 1036-1053, https://doi.org/10.1137/0215074. · Zbl 0619.68058 |
| [37] | M. Naor, A lower bound on probabilistic algorithms for distributive ring coloring, SIAM J. Discrete Math., 4 (1991), pp. 409-412, https://doi.org/10.1137/0404036. · Zbl 0738.68007 |
| [38] | M. Naor and L. J. Stockmeyer, What can be computed locally?, SIAM J. Comput., 24 (1995), pp. 1259-1277, https://doi.org/10.1137/S0097539793254571. · Zbl 0845.68006 |
| [39] | D. Olivetti, Round Eliminator: A Tool for Automatic Speedup Simulation, https://github.com/olidennis/round-eliminator, 2019. · Zbl 07323209 |
| [40] | S. Pai, G. Pandurangan, S. V. Pemmaraju, T. Riaz, and P. Robinson, Symmetry breaking in the CONGEST model: Time- and message-efficient algorithms for ruling sets, in Proceedings of 31st International Symposium on Distributed Computing, LIPIcs Leibniz Int. Proc. Inform. 91, Schloss Dagstuhl, Wadern, 2017, pp. 38:1-38:16, https://doi.org/10.4230/LIPIcs.DISC.2017.38. · Zbl 1380.68433 |
| [41] | A. Panconesi and A. Srinivasan, On the complexity of distributed network decomposition, J. Algorithms, 20 (1996), pp. 356-374, https://doi.org/10.1006/jagm.1996.0017. · Zbl 0844.68005 |
| [42] | D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM, Philadelphia, 2000, https://doi.org/10.1137/1.9780898719772. · Zbl 0959.68042 |
| [43] | V. Rozhoň and M. Ghaffari, Polylogarithmic-time deterministic network decomposition and distributed derandomization, in Proceedings of the 52nd Annual ACM Symposium on Theory of Computing, 2020. · Zbl 07298253 |
| [44] | J. Schneider, M. Elkin, and R. Wattenhofer, Symmetry breaking depending on the chromatic number or the neighborhood growth, Theoret. Comput. Sci., 509 (2013), pp. 40-50, https://doi.org/10.1016/j.tcs.2012.09.004. · Zbl 1416.68140 |
| [45] | J. Schneider and R. Wattenhofer, A new technique for distributed symmetry breaking, in Proceedings of the 2010 Annual ACM Symposium on Principles of Distributed Computing, 2010, pp. 257-266, https://doi.org/10.1145/1835698.1835760. · Zbl 1315.68275 |
| [46] | J. Schneider and R. Wattenhofer, An optimal maximal independent set algorithm for bounded-independence graphs, Distrib. Comput., 22 (2010), pp. 349-361, https://doi.org/10.1007/s00446-010-0097-1. · Zbl 1231.68092 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
