Abstract
We design centralized local algorithms for: maximal independent set, maximal matching, and graph coloring. The improvement is threefold: the algorithms are deterministic, stateless, and the number of probes is O(log* n), where n is the number of vertices of the input graph. Our algorithms for maximal independent set and maximal matching improves over previous randomized algorithms by Alon et al. (SODA 2012) and Mansour et al. (ICALP 2012). In these previous algorithms, the number of probes and the space required for storing the state between queries are poly(logn).
We also design the first centralized local algorithm for graph coloring.
Our graph coloring algorithms are deterministic and stateless. Let Δ denote the maximum degree of a graph over n vertices. Our algorithm for coloring the vertices by Δ + 1 colors requires O(log* n) probes for constant degree graphs. Surprisingly, for the case where the number of colors is O(Δ2 logΔ), the number of probes of our algorithm is O(Δ·log* n + Δ2), that is, the number of probes is sublinear if \(\Delta = o(\sqrt{n})\), i.e., our algorithm applies for graphs with unbounded degrees.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Alon, N., Rubinfeld, R., Vardi, S., Xie, N.: Space-efficient local computation algorithms. In: SODA, pp. 1132–1139 (2012)
Barenboim, L., Elkin, M.: Distributed (Δ+1)-coloring in linear (in Δ) time. In: STOC, pp. 111–120 (2009)
Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. and Cont. 70(1), 32–53 (1986)
Even, G., Medina, M., Ron, D.: Best of two local models: Local centralized and local distributed algorithms. CoRR, abs/1402.3796 (2014)
Goldberg, A.V., Plotkin, S.A., Shannon, G.E.: Parallel symmetry-breaking in sparse graphs. SIDMA 1(4), 434–446 (1988)
Kuhn, F.: Weak graph colorings: distributed algorithms and applications. In: SPAA, pp. 138–144. ACM (2009)
Linial, N.: Locality in distributed graph algorithms. SICOMP 21(1), 193–201 (1992)
Mansour, Y., Rubinstein, A., Vardi, S., Xie, N.: Converting online algorithms to local computation algorithms. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 653–664. Springer, Heidelberg (2012)
Mansour, Y., Vardi, S.: A local computation approximation scheme to maximum matching. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) RANDOM 2013 and APPROX 2013. LNCS, vol. 8096, pp. 260–273. Springer, Heidelberg (2013)
H.: N Nguyen and K. Onak. Constant-time approximation algorithms via local improvements. In: FOCS, pp. 327–336 (2008)
Onak, K., Ron, D., Rosen, M., Rubinfeld, R.: A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In: SODA, pp. 1123–1131 (2012)
Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Dist. Comp. 14(2), 97–100 (2001)
Panconesi, A., Sozio, M.: Fast primal-dual distributed algorithms for scheduling and matching problems. Dist. Comp. 22(4), 269–283 (2010)
Parnas, M., Ron, D.: Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theo. Comp. Sci. 381(1), 183–196 (2007)
Peleg, D.: Distributed computing: a locality-sensitive approach, vol. 5. SIAM (2000)
Reingold, O., Vardi, S.: New techniques and tighter bounds for local computation algorithms. CoRR, abs/1404.5398 (2014)
Rubinfeld, R., Tamir, G., Vardi, S., Xie, N.: Fast local computation algorithms. In: ICS, pp. 223–238 (2011)
Suomela, J.: Survey of local algorithms. ACM Comput. Surv. 45(2), 24:1–24:40 (2013)
Yoshida, Y., Yamamoto, M., Ito, H.: Improved constant-time approximation algorithms for maximum matchings and other optimization problems. SICOMP 41(4), 1074–1093 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Even, G., Medina, M., Ron, D. (2014). Deterministic Stateless Centralized Local Algorithms for Bounded Degree Graphs. In: Schulz, A.S., Wagner, D. (eds) Algorithms - ESA 2014. ESA 2014. Lecture Notes in Computer Science, vol 8737. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44777-2_33
Download citation
DOI: https://doi.org/10.1007/978-3-662-44777-2_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44776-5
Online ISBN: 978-3-662-44777-2
eBook Packages: Computer ScienceComputer Science (R0)