# Fast Deterministic Distributed Algorithms for Sparse Spanners

• Bilel Derbel
• Cyril Gavoille
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4056)

## Abstract

This paper concerns the efficient construction of sparse and low stretch spanners for unweighted arbitrary graphs with n nodes. All previous deterministic distributed algorithms, for constant stretch spanner of o(n 2) edges, have a running time Ω(n ε ) for some constant ε> 0 depending on the stretch. Our deterministic distributed algorithms construct constant stretch spanners of o(n 2) edges in o(n ε ) time for any constant ε> 0.

More precisely, in the Linial’s free model, we construct in $$n^{O(1/\sqrt{\log n})}$$ time, for every graph, a 5-spanner of O(n 3/2) edges. The result is extended to O( k2.322)-spanners with O(n 1 + 1/k) edges for every parameter k ≥1. If the minimum degree of the graph is $$\Omega(\sqrt{n})$$, then, in the same time complexity, a 9-spanner with O(n) edges can be constructed.

## Keywords

Distributed algorithms graph spanners time complexity Linial’s free model deterministic and randomized algorithms

## References

1. 1.
Awerbuch, B.: Complexity of network synchronization. Journal of the Association for Computing Machinery 32, 804–823 (1985)
2. 2.
Awerbuch, B.: Optimal distributed algorithms for minimum weight spanning tree, counting, leader election and related problems. In: 19th Annual ACM Symposium on Theory of Computing (STOC), May 1987, pp. 230–240. ACM Press, New York (1987)Google Scholar
3. 3.
Awerbuch, B., Berger, B., Cowen, L.J., Peleg, D.: Near-linear cost sequential and distributed constructions of sparse neighborhood coverss. In: 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS), November 1993, pp. 638–647. IEEE Computer Society Press, Los Alamitos (1993)Google Scholar
4. 4.
Awerbuch, B., Berger, B., Cowen, L.J., Peleg, D.: Fast distributed network decompositions and covers. Journal of Parallel and Distributed Computing 39, 105–114 (1996)
5. 5.
Awerbuch, B., Berger, B., Cowen, L.J., Peleg, D.: Near-linear time construction of sparse neighborhood covers. SIAM Journal on Computing 28(1), 263–277 (1998)
6. 6.
Awerbuch, B., Peleg, D.: Sparse partitions. In: 31th Annual IEEE Symposium on Foundations of Computer Science (FOCS), October 1990, pp. 503–513. IEEE Computer Society Press, Los Alamitos (1990)Google Scholar
7. 7.
Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: New constructions of (α,β)-spanners and purely additive spanners. In: 16th Symposium on Discrete Algorithms (SODA), January 2005, pp. 672–681. ACM-SIAM, New York (2005)Google Scholar
8. 8.
Baswana, S., Sen, S.: A simple linear time algorithm for computing a (2k − 1)-spanner of O(n 1 + 1/k) size in weighted graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 384–396. Springer, Heidelberg (2003)
9. 9.
Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in $$\tilde{O}(n^2)$$ time. In: 15th Symposium on Discrete Algorithms (SODA), January 2004, pp. 271–280. ACM-SIAM, New York (2004)Google Scholar
10. 10.
Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing 28(1), 210–236 (1998)
11. 11.
Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control 70(1), 32–53 (1986)
12. 12.
Cowen, L.J.: Compact routing with minimum stretch. Journal of Algorithms 38(1), 170–183 (2001)
13. 13.
Derbel, B., Mosbah, M., Zemmari, A.: Fast distributed graph partition and application. In: 20th IEEE International Parallel & Distributed Processing Symposium (IPDPS), April 2006, IEEE Computer Society Press, Los Alamitos (2006)Google Scholar
14. 14.
Eilam, T., Gavoille, C., Peleg, D.: Compact routing schemes with low stretch factor. Journal of Algorithms 46, 97–114 (2003)
15. 15.
Elkin, M.: Computing almost shortest paths. In: 20th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 53–62. ACM Press, New York (2001)Google Scholar
16. 16.
Elkin, M.: A faster distributed protocol for constructing a minimum spanning tree. In: 15th Symposium on Discrete Algorithms (SODA), January 2004, pp. 359–368. ACM-SIAM, New York (2004)Google Scholar
17. 17.
Elkin, M.: Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problems. In: 36th Annual ACM Symposium on Theory of Computing (STOC), May 2004, pp. 331–340. ACM Press, New York (2004)Google Scholar
18. 18.
Elkin, M., Peleg, D.: (1 + ε,β)-spanner constructions for general graphs. SIAM Journal on Computing 33(3), 608–631 (2004)
19. 19.
Elkin, M., Zhang, J.: Efficient algorithms for constructing (1 + ε,β)-spanners in the distributed and streaming models. In: 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), July 2004, pp. 160–168. ACM Press, New York (2004)Google Scholar
20. 20.
Gavoille, C., Peleg, D., Pérennès, S., Raz, R.: Distance labeling in graphs. Journal of Algorithms 53(1), 85–112 (2004)
21. 21.
Goldberg, A.V., Plotkin, S.A., Shannon, G.E.: Parallel symmetry-breaking in sparse graphs. SIAM Journal on Discrete Mathematics 1(4), 434–446 (1988)
22. 22.
Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol. 3724, pp. 273–287. Springer, Heidelberg (2005)
23. 23.
Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), July 2004, pp. 300–309. ACM Press, New York (2004)Google Scholar
24. 24.
Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: 17th Symposium on Discrete Algorithms (SODA), January 2006, pp. 980–989. ACM-SIAM, New York (2006)
25. 25.
Kutten, S., Peleg, D.: Fast distributed construction of small k-dominating sets and applications. Journal of Algorithms 28(1), 40–66 (1998)
26. 26.
Linial, N.: Distributive graph algorithms - Global solutions from local data. In: 28th Annual IEEE Symposium on Foundations of Computer Science (FOCS), October 1987, pp. 331–335. IEEE Computer Society Press, Los Alamitos (1987)Google Scholar
27. 27.
Linial, N.: Locality in distributed graphs algorithms. SIAM Journal on Computing 21(1), 193–201 (1992)
28. 28.
Lotker, Z., Patt-Shamir, B., Pavlov, E., Peleg, D.: Minimum-weight spanning tree construction in O(loglogn) communication rounds. SIAM Journal on Discrete Mathematics 35(1), 120–131 (2005)
29. 29.
Lotker, Z., Patt-Shamir, B., Peleg, D.: Distributed MST for constant diameter graphs. In: 20th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 63–71. ACM Press, New York (2001)Google Scholar
30. 30.
Lovász, L.: On the ratio of optimal integral and fractional covers. Discrete Mathematics 13, 383–390 (1975)
31. 31.
Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing 15(4), 1036–1053 (1986)
32. 32.
Moran, S., Snir, S.: Simple and efficient network decomposition and synchronization. Theoretical Computer Science 243(1-2), 217–241 (2000)
33. 33.
Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. Journal of Algorithms 20(2), 356–374 (1996)
34. 34.
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications (2000)Google Scholar
35. 35.
Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM Journal on Computing 30(5), 1427–1442 (2000)
36. 36.
Peleg, D., Ullman, J.D.: An optimal synchornizer for the hypercube. SIAM Journal on Computing 18(4), 740–747 (1989)
37. 37.
Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. Journal of the ACM 36(3), 510–530 (1989)
38. 38.
Penso, L.D., Valmir, C.B.: A distributed algorithm to find k-dominating sets. Discrete Applied Mathematics 141(1-3), 243–253 (2004)
39. 39.
Roditty, L., Thorup, M., Zwick, U.: Roundtrip spanners and roundtrip routing in directed graphs. In: 13th Symposium on Discrete Algorithms (SODA), January 2002, pp. 844–851. ACM-SIAM (2002)Google Scholar
40. 40.
Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 261–272. Springer, Heidelberg (2005)
41. 41.
Thorup, M., Zwick, U.: Compact routing schemes. In: 13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), July 2001, pp. 1–10. ACM Press, New York (2001)Google Scholar
42. 42.
Thorup, M., Zwick, U.: Approximate distance oracles. Journal of the ACM 52(1), 1–24 (2005)
43. 43.
Wenger, R.: Extremal graphs with no C 4’s, C 6’s, or C 10’s. Journal of Combinatorial Theory, Series B 52(1), 113–116 (1991)