More Web Proxy on the site http://driver.im/

research-article

Public Access

An optimal distributed (Δ+1)-coloring algorithm?

Authors:

Seth PettieAuthors Info & Claims

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Pages 445 - 456

https://doi.org/10.1145/3188745.3188964

Published: 20 June 2018 Publication History

Abstract

Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for (Δ+1)-list coloring in the randomized LOCAL model running in O(log^∗n + Det_d(poly logn)) time, where Det_d(n′) is the deterministic complexity of (deg+1)-list coloring (v’s palette has size deg(v)+1) on n′-vertex graphs. This improves upon a previous randomized algorithm of Harris, Schneider, and Su (STOC 2016). with complexity O(√logΔ + loglogn + Det_d(poly logn)), and (when Δ is sufficiently large) is much faster than the best known deterministic algorithm of Fraigniaud, Heinrich, and Kosowski (FOCS 2016), with complexity O(√Δlog^2.5Δ + log^* n).

Our algorithm appears to be optimal. It matches the Ω(log^∗n) randomized lower bound, due to Naor (SIDMA 1991) and sort of matches the Ω(Det(poly logn)) randomized lower bound due to Chang, Kopelowitz, and Pettie (FOCS 2016), where Det is the deterministic complexity of (Δ+1)-list coloring. The best known upper bounds on Det_d(n′) and Det(n′) are both 2^{O(√logn′)} by Panconesi and Srinivasan (Journal of Algorithms 1996), and it is quite plausible that the complexities of both problems are the same, asymptotically.

Supplementary Material

MP4 File (4a-3.mp4)

Download
26.09 MB

References

[1]

N. Alon, L. Babai, and A. Itai. 1986.

[2]

A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem. J. Algor. 7 (1986), 567–583. 6 Recall that Det and Det d are the deterministic complexities of ( ∆ + 1)-list coloring and (deg +1)-list coloring.

Digital Library

[3]

B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin. 1989.

[4]

Network Decomposition and Locality in Distributed Computation. In Proceedings 30th IEEE Symposium on Foundations of Computer Science (FOCS). 364–369.

Digital Library

[5]

L. Barenboim. 2015. Deterministic ( ∆ + 1)-Coloring in Sublinear (in ∆) Time in Static, Dynamic and Faulty Networks. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC). 345–354. 2767386.2767410

Digital Library

[6]

L. Barenboim, M. Elkin, and F. Kuhn. 2014. Distributed ( ∆ +1)-Coloring in Linear (in ∆) Time. SIAM J. Comput. 43, 1 (2014), 72–95.

[7]

L. Barenboim, M. Elkin, S. Pettie, and J. Schneider. 2016.

[8]

The Locality of Distributed Symmetry Breaking. J. ACM 63, 3, Article 20 (2016), 20:1–20:45 pages.

Digital Library

[9]

T. Bisht, K. Kothapalli, and S. V. Pemmaraju. 2014. Brief announcement: Superfast t -ruling sets. In Proceedings 33rd ACM Symposium on Principles of Distributed Computing (PODC). 379–381.

Digital Library

[10]

Y.-J. Chang, W. Li, and S. Pettie. 2017. An Optimal Distributed ( ∆+1)-Coloring Algorithm? CoRR abs/1711.01361 (2017). arXiv: 1711.01361 http://arxiv.org/abs/ 1711.01361

[11]

Y.-J. Chang, T. Kopelowitz, and S. Pettie. 2016. An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model. In Proceedings 57th IEEE Symposium on Foundations of Computer Science (FOCS). 615– 624.

[12]

Y.-J. Chang and S. Pettie. 2017. A Time Hierarchy Theorem for the LOCAL Model. In Proceedings 58th IEEE Symposium on Foundations of Computer Science (FOCS).

[13]

D. P. Dubhashi and A. Panconesi. 2009.

[14]

Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.

Digital Library

[15]

D. P. Dubhashi and D. Ranjan. 1998. Balls and bins: A study in negative dependence. J. Random Structures and Algs. 13, 2 (1998), 99–124.

Digital Library

[16]

M. Elkin, S. Pettie, and H.-H. Su. 2015.

[17]

(2 ∆ − 1)-Edge Coloring is Much Easier than Maximal Matching in the Distributed Setting. In Proceedings 26th ACM-SIAM Symposium on Discrete Algorithms (SODA). 355–370.

Digital Library

[18]

M. Fischer and M. Ghaffari. 2017.

[19]

Sublogarithmic Distributed Algorithms for Lovász Local Lemma with Implications on Complexity Hierarchies. In Proceedings 31st International Symposium on Distributed Computing (DISC). 18:1–18:16.

[20]

M. Fischer, M. Ghaffari, and F. Kuhn. 2017.

[21]

Deterministic Distributed Edge Coloring via Hypergraph Maximal Matching. In Proceedings 58th IEEE Symposium on Foundations of Computer Science (FOCS).

[22]

P. Fraigniaud, M. Heinrich, and A. Kosowski. 2016. Local conflict coloring. In Proceedings 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 625–634.

[23]

M. Ghaffari. 2016. An improved distributed algorithm for maximal independent set. In Proceedings 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 270–277.

Digital Library

[24]

A. Goldberg, S. Plotkin, and G. Shannon. 1987. Parallel symmetry-breaking in sparse graphs. In Proceedings of the nineteenth annual ACM symposium on Theory of computing. ACM, 315–324.

Digital Library

[25]

A. V Goldberg and S. A Plotkin. 1987. Parallel ( ∆+ 1)-coloring of constant-degree graphs. Inform. Process. Lett. 25, 4 (1987), 241–245.

Digital Library

[26]

D. Harris, J. Schneider, and H.-H. Su. 2016. Distributed ( ∆+1)-Coloring in Sublogarithmic Rounds. In Proceedings 48th ACM Symposium on Theory of Computing (STOC). 465–478.

Digital Library

[27]

W. Hoeffding. 1963.

[28]

Probability Inequalities for Sums of Bounded Random Variables. J. Amer. Statist. Assoc. 58, 301 (1963), 13–30.

[29]

Ö. Johansson. 1999. Simple Distributed ∆ + 1-coloring of Graphs. Info. Proc. Lett. 70, 5 (1999), 229–232.

Digital Library

[30]

F. Kuhn, T. Moscibroda, and R. Wattenhofer. 2016. Local Computation: Lower and Upper Bounds. J. ACM 63, 2 (2016), 17:1–17:44.

Digital Library

[31]

F. Kuhn and R. Wattenhofer. 2006.

[32]

On the complexity of distributed graph coloring. In Proceedings 25th Annual ACM Symposium on Principles of Distributed Computing (PODC). 7–15.

Digital Library

[33]

N. Linial. 1992. Locality in Distributed Graph Algorithms. SIAM J. Comput. 21, 1 (1992), 193–201.

Digital Library

[34]

M. Luby. 1986.

[35]

A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 4 (1986), 1036–1053.

[36]

M. Naor. 1991. A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring. SIAM J. Discrete Mathematics 4, 3 (1991), 409–412. 1137/0404036

[37]

A. Panconesi and A. Srinivasan. 1996. On the Complexity of Distributed Network Decomposition. J. Algor. 20, 2 (1996), 356–374.

Digital Library

[38]

D. Peleg. 2000.

[39]

Distributed Computing: A Locality-Sensitive Approach. SIAM.

Cited By

Coy SCzumaj ADavies-Peck PMishra G(2024)Parallel Derandomization for Coloring*2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS57955.2024.00098(1058-1069)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPS57955.2024.00098
Ghaffari MGrunau C(2024)Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00007(2148-2179)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00007
Delporte-Gallet CFauconnier HFraigniaud PRabie M(2024)Distributed Computing in the Asynchronous LOCAL ModelTheoretical Computer Science10.1016/j.tcs.2024.114952(114952)Online publication date: Nov-2024
https://doi.org/10.1016/j.tcs.2024.114952
Show More Cited By

Index Terms

An optimal distributed (Δ+1)-coloring algorithm?
1. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms

Recommendations

Near-optimal distributed degree+1 coloring
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

We present a new approach to randomized distributed graph coloring that is simpler and more efficient than previous ones. In particular, it allows us to tackle the (deg+1)-list-coloring (D1LC) problem, where each node v of degree d_v is assigned a ...
Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma
Special Issue on Soda'18 and Regular Papers

The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree Δ. In this article, we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as ...
Distributed (δ+1)-coloring in linear (in δ) time
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

The distributed (Δ + 1)-coloring problem is one of most fundamental and well-studied problems in Distributed Algorithms. Starting with the work of Cole and Vishkin in 86, there was a long line of gradually improving algorithms published. The current ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

June 2018

1332 pages

ISBN:9781450355599

DOI:10.1145/3188745

General Chairs:
Ilias Diakonikolas
University of Southern California, USA
,
David Kempe
University of Southern California, USA
,
Program Chair:
Monika Henzinger
University of Vienna, Austria

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

STOC '18

Sponsor:

SIGACT

STOC '18: Symposium on Theory of Computing

June 25 - 29, 2018

CA, Los Angeles, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
515
Total Downloads

Downloads (Last 12 months)84
Downloads (Last 6 weeks)9

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Coy SCzumaj ADavies-Peck PMishra G(2024)Parallel Derandomization for Coloring*2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS57955.2024.00098(1058-1069)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPS57955.2024.00098
Ghaffari MGrunau C(2024)Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00007(2148-2179)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00007
Delporte-Gallet CFauconnier HFraigniaud PRabie M(2024)Distributed Computing in the Asynchronous LOCAL ModelTheoretical Computer Science10.1016/j.tcs.2024.114952(114952)Online publication date: Nov-2024
https://doi.org/10.1016/j.tcs.2024.114952
Assadi SChakrabarti AGhosh PStoeckl MGeerts FNgo HSintos S(2023)Coloring in Graph Streams via Deterministic and Adversarially Robust AlgorithmsProceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3584372.3588681(141-153)Online publication date: 18-Jun-2023
https://dl.acm.org/doi/10.1145/3584372.3588681
Ghaffari MGrunau CSaha BServedio R(2023)Faster Deterministic Distributed MIS and Approximate MatchingProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585243(1777-1790)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585243
Christiansen ANowicki KRotenberg ESaha BServedio R(2023)Improved Dynamic Colouring of Sparse GraphsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585111(1201-1214)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585111
Fuchs MKuhn FAgrawal KShun J(2023)Brief Announcement: List Defective Colorings: Distributed Algorithms and ApplicationsProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591319(489-492)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591319
Fryganiotis NPapavassiliou SPelekis C(2023)A note on the network coloring game: A randomized distributed (Δ + 1)-coloring algorithmInformation Processing Letters10.1016/j.ipl.2023.106385(106385)Online publication date: Feb-2023
https://doi.org/10.1016/j.ipl.2023.106385
Balliu AGhaffari MKuhn FOlivetti D(2023)Node and edge averaged complexities of local graph problemsDistributed Computing10.1007/s00446-023-00453-136:4(451-473)Online publication date: 5-Jul-2023
https://doi.org/10.1007/s00446-023-00453-1
Balliu ABrandt SKuhn FOlivetti DLeonardi SGupta A(2022)Distributed ∆-coloring plays hide-and-seekProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520027(464-477)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520027
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents