Linear-in-\(\varDelta \) lower bounds in the LOCAL model. (English) Zbl 1423.68192
Summary: By prior work, there is a distributed graph algorithm that finds a maximal fractional matching (maximal edge packing) in \(O(\varDelta )\) rounds, independently of \(n\); here \(\varDelta \) is the maximum degree of the graph and \(n\) is the number of nodes in the graph. We show that this is optimal: there is no distributed algorithm that finds a maximal fractional matching in \(o(\varDelta )\) rounds, independently of \(n\). Our work gives the first linear-in-\(\varDelta \) lower bound for a natural graph problem in the standard \(\mathsf{LOCAL }\) model of distributed computing – prior lower bounds for a wide range of graph problems have been at best logarithmic in \(\varDelta \).
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 68W15 | Distributed algorithms |
Keywords:
local distributed algorithms; lower bounds; maximal edge packing; maximal fractional matchingReferences:
| [1] | Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567-583 (1986). doi:10.1016/0196-6774(86)90019-2 · Zbl 0631.68063 · doi:10.1016/0196-6774(86)90019-2 |
| [2] | Angluin, D.: Local and global properties in networks of processors. In: Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC 1980), pp. 82-93. ACM Press (1980). doi:10.1145/800141.804655 |
| [3] | Åstrand, M., Floréen, P., Polishchuk, V., Rybicki, J., Suomela, J., Uitto, J.: A local 2-approximation algorithm for the vertex cover problem. In: Proceedings of the 23rd International Symposium on Distributed Computing (DISC 2009), Lecture notes in computer science, vol. 5805, pp. 191-205. Springer (2009). doi:10.1007/978-3-642-04355-0_21 · Zbl 1261.68161 |
| [4] | Åstrand, M., Suomela, J.: 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 2010), pp. 294-302. ACM Press (2010). doi:10.1145/1810479.1810533 · Zbl 0845.68006 |
| [5] | Barenboim, L., Elkin, M.: Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool (2013). doi:10.2200/S00520ED1V01Y201307DCT011 · Zbl 1310.68004 |
| [6] | Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. In: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), pp. 321-330. IEEE Computer Society Press (2012). doi:10.1109/FOCS.2012.60 · Zbl 1426.68020 |
| [7] | Czygrinow, A., Hańćkowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: Proceedings of the 22nd International Symposium on Distributed Computing (DISC 2008), Lecture Notes in Computer Science, vol. 5218, pp. 78-92. Springer (2008). doi:10.1007/978-3-540-87779-0_6 · Zbl 1161.68865 |
| [8] | Floréen, P., Hassinen, M., Kaasinen, J., Kaski, P., Musto, T., Suomela, J.: Local approximability of max-min and min-max linear programs. Theory Comput. Syst. 49(4), 672-697 (2011). doi:10.1007/s00224-010-9303-6 · Zbl 1253.68360 · doi:10.1007/s00224-010-9303-6 |
| [9] | Göös, M., Hirvonen, J., Suomela, J.: Lower bounds for local approximation. J. ACM 60(5), 39:1-39:23 (2013). doi:10.1145/2528405. arXiv:1201.6675 · Zbl 1281.68235 · doi:10.1145/2528405 |
| [10] | Göös, M., Hirvonen, J., Suomela, J.: Linear-in-\[ \varDelta\] Δ lower bounds in the LOCAL model. In: Proceedings of the 33rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2014), pp. 86-95. ACM Press (2014). doi:10.1145/2611462.2611467. arXiv:1304.1007 · Zbl 1321.68281 |
| [11] | Göös, M., Suomela, J.: No sublogarithmic-time approximation scheme for bipartite vertex cover. In: Proceedings of the 26th International Symposium on Distributed Computing (DISC 2012), Lecture Notes in Computer Science, vol. 7611, pp. 181-194. Springer (2012). doi:10.1007/978-3-642-33651-5_13. arXiv:1205.4605 · Zbl 1377.68318 |
| [12] | Hańćkowiak, M., Karoński, M., Panconesi, A.: On the distributed complexity of computing maximal matchings. In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998), pp. 219-225. Society for Industrial and Applied Mathematics (1998) · Zbl 0930.68167 |
| [13] | Hańćkowiak, M., Karoński, M., Panconesi, A.: On the distributed complexity of computing maximal matchings. SIAM J. Discrete Math. 15(1), 41-57 (2001). doi:10.1137/S0895480100373121 · Zbl 0987.05079 · doi:10.1137/S0895480100373121 |
| [14] | Hasemann, H., Hirvonen, J., Rybicki, J., Suomela, J.: Deterministic local algorithms, unique identifiers, and fractional graph colouring. In: Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012), Lecture Notes in Computer Science, vol. 7355, pp. 48-60. Springer (2012). doi:10.1007/978-3-642-31104-8_5 · Zbl 1332.68277 |
| [15] | Hirvonen, J., Suomela, J.: Distributed maximal matching: greedy is optimal. In: Proceedings of the 31st Annual ACM Symposium on Principles of Distributed Computing (PODC 2012), pp. 165-174. ACM Press (2012). doi:10.1145/2332432.2332464. arXiv:1110.0367 · Zbl 1301.68204 |
| [16] | Israeli, A., Itai, A.: A fast and simple randomized parallel algorithm for maximal matching. Inf. Process. Lett. 22(2), 77-80 (1986). doi:10.1016/0020-0190(86)90144-4 · Zbl 0588.68036 |
| [17] | Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC 2004), pp. 300-309. ACM Press (2004). doi:10.1145/1011767.1011811 · Zbl 1321.68478 |
| [18] | Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 980-989. ACM Press (2006). doi:10.1145/1109557.1109666 · Zbl 1192.68044 |
| [19] | Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: lower and upper bounds (2010). arXiv:1011.5470 · Zbl 1426.68092 |
| [20] | Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing (PODC 2006), pp. 7-15. ACM Press (2006). doi:10.1145/1146381.1146387 · Zbl 1314.68161 |
| [21] | Lenzen, C., Wattenhofer, R.: Leveraging Linial’s locality limit. In: Proceedings of the 22nd International Symposium on Distributed Computing (DISC 2008), Lecture Notes in Computer Science, vol. 5218, pp. 394-407. Springer (2008). doi:10.1007/978-3-540-87779-0_27 · Zbl 1161.68344 |
| [22] | Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193-201 (1992). doi:10.1137/0221015 · Zbl 0787.05058 · doi:10.1137/0221015 |
| [23] | Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036-1053 (1986). doi:10.1137/0215074 · Zbl 0619.68058 · doi:10.1137/0215074 |
| [24] | Mayer, A., Naor, M., Stockmeyer, L.: Local computations on static and dynamic graphs. In: Proceedings of the 3rd Israel Symposium on the Theory of Computing and Systems (ISTCS 1995), pp. 268-278. IEEE (1995). doi:10.1109/ISTCS.1995.377023 · Zbl 1281.68235 |
| [25] | Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput. 24(6), 1259-1277 (1995). doi:10.1137/S0097539793254571 · Zbl 0845.68006 · doi:10.1137/S0097539793254571 |
| [26] | Neumann, B.H.: On ordered groups. Am. J. Math. 71(1), 1-18 (1949). doi:10.2307/2372087 · Zbl 0031.34201 · doi:10.2307/2372087 |
| [27] | Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Distrib. Comput. 14(2), 97-100 (2001). doi:10.1007/PL00008932 · Zbl 1448.68474 · doi:10.1007/PL00008932 |
| [28] | Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia (2000) · Zbl 0959.68042 |
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.
