research-article

Near-optimal distributed degree+1 coloring

Authors:

Magnús M. Halldórsson,

Alexandre Nolin,

Tigran TonoyanAuthors Info & Claims

STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

Pages 450 - 463

https://doi.org/10.1145/3519935.3520023

Published: 10 June 2022 Publication History

Abstract

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 palette of d_v+1 colors, and the objective is to find a proper coloring using these palettes. While for (Δ+1)-coloring (where Δ is the maximum degree), there is a fast randomized distributed O(log³logn)-round algorithm due to Chang, Li, and Pettie, no o(logn)-round algorithms are known for the D1LC problem.

We give a randomized distributed algorithm for D1LC that is optimal under plausible assumptions about the deterministic complexity of the problem. Using the recent deterministic algorithm of Ghaffari and Kuhn, our algorithm runs in O(log³ logn) time, matching the best bound known for (Δ+1)-coloring. A key contribution is a subroutine to generate slack for D1LC, which almost immediately leads to a palette sparsification theorem for D1LC when placed into the framework of works by Assadi, Chen, and Khanna and Alon and Assadi. That gives fast algorithms for D1LC in three different models: an O(1)-round algorithm in the MPC model with Õ(n) memory per machine; a single-pass semi-streaming algorithm in dynamic streams; and an Õ(n√n)-time query algorithm.

References

[1]

Noga Alon and Sepehr Assadi. 2020. Palette Sparsification Beyond (Δ +1) Vertex Coloring. In APPROX/RANDOM (LIPIcs, Vol. 176). LZI, 6:1–6:22.

[2]

Noga Alon, László Babai, and Alon Itai. 1986. A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem. J. of Algorithms, 7, 4 (1986), 567–583.

Digital Library

[3]

Sepehr Assadi, Yu Chen, and Sanjeev Khanna. 2019. Sublinear algorithms for (Δ + 1) vertex coloring. In SODA. SIAM, 767–786.

[4]

Sepehr Assadi and Chen Wang. 2022. Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions. In ITCS (LIPIcs, Vol. 215). LZI, 10:1–10:20.

[5]

Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin. 1989. Network Decomposition and Locality in Distributed Computation. In FOCS. IEEE Computer Society, 364–369.

[6]

Alkida Balliu, Fabian Kuhn, and Dennis Olivetti. 2020. Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta. In PODC. ACM.

[7]

Étienne Bamas and Louis Esperet. 2019. Distributed Coloring of Graphs with an Optimal Number of Colors. In STACS (LIPIcs, Vol. 126). LZI, 10:1–10:15.

[8]

Leonid Barenboim. 2016. Deterministic (Δ +1)-Coloring in Sublinear (in Δ ) Time in Static, Dynamic, and Faulty Networks. J. ACM, 63, 5 (2016), 47:1–47:22.

Digital Library

[9]

Leonid Barenboim and Michael Elkin. 2011. Deterministic Distributed Vertex Coloring in Polylogarithmic Time. J. ACM, 58, 5 (2011), 23:1–23:25.

Digital Library

[10]

Leonid Barenboim and Michael Elkin. 2011. Distributed deterministic edge coloring using bounded neighborhood independence. In PODC. ACM, 129–138.

[11]

Leonid Barenboim, Michael Elkin, and Uri Goldenberg. 2018. Locally-Iterative Distributed (Δ +1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models. In PODC. ACM, 437–446.

[12]

Leonid Barenboim, Michael Elkin, and Fabian Kuhn. 2014. Distributed (Delta+1)-Coloring in Linear (in Delta) Time. SIAM Journal on Computing, 43, 1 (2014), 72–95.

Digital Library

[13]

Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. 2016. The Locality of Distributed Symmetry Breaking. J. ACM, 63, 3 (2016), 20:1–20:45.

Digital Library

[14]

József Beck. 1991. An algorithmic approach to the Lovász local lemma. I. Random Structures & Algorithms, 2, 4 (1991), 343–365.

Digital Library

[15]

Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. 2019. The Complexity of (Δ +1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation. In PODC. ACM, 471–480.

[16]

Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. 2019. An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. SIAM Journal on Computing, 48, 1 (2019), 122–143.

Digital Library

[17]

Yi-Jun Chang, Wenzheng Li, and Seth Pettie. 2020. Distributed (Δ +1)-Coloring via Ultrafast Graph Shattering. SIAM Journal of Computing, 49, 3 (2020), 497–539.

[18]

Artur Czumaj, Peter Davies, and Merav Parter. 2020. Simple, Deterministic, Constant-Round Coloring in the Congested Clique. In PODC. ACM, 309–318.

[19]

Benjamin Doerr. 2020. Probabilistic Tools for the Analysis of Randomized Optimization Heuristics. Springer International Publishing, 1–87. isbn:978-3-030-29414-4

[20]

Devdatt P. Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press. isbn:978-0-521-88427-3

[21]

Michael Elkin, Seth Pettie, and Hsin-Hao Su. 2015. (2Δ -1)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting. In SODA. SIAM, 355–370.

[22]

Manuela Fischer, Mohsen Ghaffari, and Fabian Kuhn. 2017. Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching. In FOCS. IEEE Computer Society, 180–191.

[23]

Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. 2016. Local Conflict Coloring. In FOCS. IEEE Computer Society, 625–634.

[24]

Dmitry Gavinsky, Shachar Lovett, Michael Saks, and Srikanth Srinivasan. 2015. A tail bound for read-k families of functions. Random Structures & Algorithms, 47, 1 (2015), 99–108.

Digital Library

[25]

Mohsen Ghaffari, David G. Harris, and Fabian Kuhn. 2018. On Derandomizing Local Distributed Algorithms. In FOCS. IEEE Computer Society, 662–673.

[26]

Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, and Yannic Maus. 2018. Improved Distributed Delta-Coloring. In PODC. ACM, 427–436.

[27]

Mohsen Ghaffari and Fabian Kuhn. 2021. Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition. In FOCS. IEEE Computer Society, 1009–1020.

[28]

A.V. Goldberg, S.A. Plotkin, and G.E. Shannon. 1988. Parallel Symmetry-Breaking in Sparse Graphs. SIAM Journal on Discrete Mathematics, 1, 4 (1988), 434–446.

Digital Library

[29]

Magnús M. Halldórsson, Fabian Kuhn, and Yannic Maus. 2020. Distance-2 Coloring in the CONGEST Model. In PODC. ACM, 233–242.

[30]

Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, and Alexandre Nolin. 2020. Coloring Fast Without Learning Your Neighbors’ Colors. In DISC. LZI, 39:1–39:17.

[31]

Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, and Tigran Tonoyan. 2021. Efficient Randomized Distributed Coloring in CONGEST. In STOC. ACM, 1180–1193.

[32]

Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin, and Tigran Tonoyan. 2021. Near-Optimal Distributed Degree+1 Coloring. CoRR, abs/2112.00604 (2021), (full version of this paper).

[33]

Magnús M. Halldórsson, Alexandre Nolin, and Tigran Tonoyan. 2021. Ultrafast Distributed Coloring of High Degree Graphs. CoRR, abs/2105.04700 (2021).

[34]

David G. Harris. 2019. Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs. In FOCS. IEEE Computer Society, 700–724.

[35]

David G. Harris, Johannes Schneider, and Hsin-Hao Su. 2018. Distributed (Δ + 1)-coloring in sublogarithmic rounds. J. ACM, 65 (2018), 19:1–19:21.

Digital Library

[36]

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

[37]

Öjvind Johansson. 1999. Simple Distributed Δ +1-Coloring of Graphs. Inf. Process. Lett., 70, 5 (1999), 229–232.

Digital Library

[38]

Kishore Kothapalli, Christian Scheideler, Melih Onus, and Christian Schindelhauer. 2006. Distributed coloring in ~ O( ologn) bit rounds. In IPDPS. IEEE.

[39]

Fabian Kuhn. 2009. Weak graph colorings: distributed algorithms and applications. In SPAA. ACM, 138–144.

[40]

Fabian Kuhn. 2020. Faster Deterministic Distributed Coloring Through Recursive List Coloring. In SODA. SIAM, 1244–1259.

[41]

Fabian Kuhn and Roger Wattenhofer. 2006. On the complexity of distributed graph coloring. In PODC. ACM, 7–15.

[42]

Nathan Linial. 1992. Locality in Distributed Graph Algorithms. SIAM Journal on Computing, 21, 1 (1992), 193–201.

Digital Library

[43]

M. Luby. 1986. A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM Journal on Computing, 15 (1986), 1036–1053.

Digital Library

[44]

Yannic Maus and Tigran Tonoyan. 2020. Local Conflict Coloring Revisited: Linial for Lists. In DISC. LZI, 16:1–16:18.

[45]

Moni Naor. 1991. A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring. SIAM Journal on Discrete Mathematics, 4, 3 (1991), 409–412.

Digital Library

[46]

Alessandro Panconesi and Aravind Srinivasan. 1992. Improved Distributed Algorithms for Coloring and Network Decomposition Problems. In STOC. ACM, 581–592.

[47]

Alessandro Panconesi and Aravind Srinivasan. 1995. The Local Nature of Delta-Coloring and its Algorithmic Applications. Combinatorica, 15, 2 (1995), 255–280.

[48]

Merav Parter and Hsin-Hao Su. 2018. Randomized (Δ +1)-Coloring in O( olog^* Δ ) Congested Clique Rounds. In DISC (LIPIcs, Vol. 121). LZI, 39:1–39:18.

[49]

David Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM.

Digital Library

[50]

Bruce A. Reed. 1998. ω, Δ, and χ. J. Graph Theory, 27, 4 (1998), 177–212.

Digital Library

[51]

Václav Rozhoň and Mohsen Ghaffari. 2020. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In STOC. ACM, 350–363.

[52]

Johannes Schneider and Roger Wattenhofer. 2010. A new technique for distributed symmetry breaking. In PODC. ACM, 257–266.

[53]

Mario Szegedy and Sundar Vishwanathan. 1993. Locality based graph coloring. In STOC. ACM, 201–207.

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
Assadi S(2023)Recent Advances in Multi-Pass Graph Streaming Lower BoundsACM SIGACT News10.1145/3623800.362380854:3(48-75)Online publication date: 11-Sep-2023
https://doi.org/10.1145/3623800.3623808
Maus Y(2023)Distributed Graph Coloring Made EasyACM Transactions on Parallel Computing10.1145/360589610:4(1-21)Online publication date: 14-Dec-2023
https://dl.acm.org/doi/10.1145/3605896
Show More Cited By

Index Terms

Near-optimal distributed degree+1 coloring
1. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms

Recommendations

An optimal distributed (Δ+1)-coloring algorithm?
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

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′) ...
Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering

Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper, we present a new algorithm for $(\Delta+1)$-list coloring in the randomized ${LOCAL}$ model running in $O({Det}_{\scriptscriptstyle d}(\...
Broadcasting in undirected ad hoc radio networks
Special issue: PODC 02

We consider distributed broadcasting in radio networks, modeled as undirected graphs, whose nodes have no information on the topology of the network, nor even on their immediate neighborhood. For randomized broadcasting, we give an algorithm working in ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

June 2022

1698 pages

ISBN:9781450392648

DOI:10.1145/3519935

General Chair:
Stefano Leonardi
Sapienza University of Rome, Italy
,
Program Chair:
Anupam Gupta
Carnegie Mellon University, USA

Copyright © 2022 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: 10 June 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '22

Sponsor:

SIGACT

STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing

June 20 - 24, 2022

Rome, Italy

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
147
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Oct 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
Assadi S(2023)Recent Advances in Multi-Pass Graph Streaming Lower BoundsACM SIGACT News10.1145/3623800.362380854:3(48-75)Online publication date: 11-Sep-2023
https://doi.org/10.1145/3623800.3623808
Maus Y(2023)Distributed Graph Coloring Made EasyACM Transactions on Parallel Computing10.1145/360589610:4(1-21)Online publication date: 14-Dec-2023
https://dl.acm.org/doi/10.1145/3605896
Fryganiotis NPapavassiliou SPelekis C(2023)A note on the network coloring gameInformation Processing Letters10.1016/j.ipl.2023.106385182:COnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.ipl.2023.106385
Adamson DHalldórsson MNolin A(2023)Distributed Coloring of HypergraphsStructural Information and Communication Complexity10.1007/978-3-031-32733-9_5(89-111)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-32733-9_5

View Options

Get Access

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents