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

research-article

The complexity of distributed edge coloring with small palettes

Authors:

Jara UittoAuthors Info & Claims

SODA '18: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms

Pages 2633 - 2652

Published: 07 January 2018 Publication History

Abstract

The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree Δ. In this paper we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as follows.

• We simplify the round elimination technique of Brandt et al. [9] and prove that (2Δ − 2)-edge coloring requires Ω(log_Δ log n) time w.h.p. and Ω(log_Δ n) time deterministically, even on trees. The simplified technique is based on two ideas: the notion of an irregular running time (in which network components terminate the algorithm at prescribed, but irregular times) and some general observations that transform weak lower bounds into stronger ones.

• We give a randomized edge coloring algorithm that can use palette sizes as small as [EQUATION], which is a natural barrier for randomized approaches. The running time of the algorithm is at most O(log Δ · T_LLL), where T_LLL is the complexity of a permissive version of the constructive Lovász local lemma.

• We develop a new distributed Lovász local lemma algorithm for tree-structured dependency graphs, which leads to a (1 + ϵ)Δ-edge coloring algorithm for trees running in O(log log n) time. This algorithm arises from two new results: a deterministic O(log n)-time LLL algorithm for tree-structured instances, and a randomized O(log log n)-time graph shattering method for breaking the dependency graph into independent O(log n)-size LLL instances.

• A natural approach to computing (Δ + 1)-edge colorings (Vizing's theorem) is to extend partial colorings by iteratively re-coloring parts of the graph, e.g., via "augmenting paths." We prove that this approach may be viable, but in the worst case requires recoloring subgraphs of diameter Ω(Δ log n). This stands in contrast to distributed algorithms for Brooks' theorem [32], which exploit the existence of O(log_Δ n)-length augmenting paths.

References

[1]

E. Arjomandi. An efficient algorithm for colouring the edges of a graph with Δ + 1 colours. INFOR: Information Systems and Operational Research, 20(2):82--101, 1982.

[2]

B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin. Network decomposition and locality in distributed computation. In Proceedings 30th IEEE Symposium on Foundations of Computer Science (FOCS), pages 364--369, 1989.

Digital Library

[3]

L. Barenboim. 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), pages 345--354, 2015.

Digital Library

[4]

L. Barenboim and M. Elkin. Deterministic distributed vertex coloring in polylogarithmic time. J. ACM, 58(5):23, 2011.

Digital Library

[5]

L. Barenboim, M. Elkin, and F. Kuhn. Distributed (Δ + 1)-coloring in linear (in Δ) time. SIAM J. Comput., 43(1):72--95, 2014.

[6]

L. Barenboim, M. Elkin, and T. Maimon. Deterministic distributed (Δ + o(Δ))-edge-coloring, and vertex-coloring of graphs with bounded diversity. In Proceedings of the 2017 ACM Symposium on Principles of Distributed Computing (PODC), pages 175--184, 2017.

Digital Library

[7]

L. Barenboim, M. Elkin, S. Pettie, and J. Schneider. The locality of distributed symmetry breaking. J. ACM, 63(3):20:1--20:45, 2016.

Digital Library

[8]

B. Bollobás. Extremal graph theory, volume 11 of London Mathematical Society Monographs. Academic Press Inc. {Harcourt Brace Jovanovich Publishers}, London, 1978.

[9]

S. Brandt, O. Fischer, J. Hirvonen, B. Keller, T. Lempiäinen, J. Rybicki, J. Suomela, and J. Uitto. A lower bound for the distributed Lovász local lemma. In Proceedings 48th ACM Symposium on the Theory of Computing (STOC), pages 479--488, 2016.

Digital Library

[10]

Y.-J. Chang, Q. He, W. Li, S. Pettie, and J. Uitto. The complexity of distributed edge coloring with small palettes. CoRR, abs/1708.04290, 2017.

[11]

Y.-J. Chang, T. Kopelowitz, and S. Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. In Proceedings 57th IEEE Symposium on Foundations of Computer-Science (FOCS), pages 615--624, 2016.

[12]

Y.-J. Chang and S. Pettie. A time hierarchy theorem for the LOCAL model. In Proceedings 58th IEEE Symposium on Foundations of Computer Science (FOCS), pages 156--167, 2017.

[13]

K.-M. Chung, S. Pettie, and H.-H. Su. Distributed algorithms for the Lovász local lemma and graph coloring. Distributed Computing, 30:261--280, 2017.

Digital Library

[14]

A. Czygrinow, M. Hanckowiak, and M. Karonski. Distributed O(Δ log n)-edge-coloring algorithm. In Proc. ESA 2001, pages 345--355, 2001.

Digital Library

[15]

X. Dahan. Regular graphs of large girth and arbitrary degree. Combinatorica, 34(4):407--426, 2014.

Digital Library

[16]

D. P. Dubhashi, D. A. Grable, and A. Panconesi. Near-optimal, distributed edge colouring via the nibble method. Theor. Comput. Sci., 203(2):225--251, 1998.

Digital Library

[17]

M. Elkin, S. Pettie, and H. H. Su. (2Δ − 1)-edge coloring is much easier than maximal matching in the distributed setting. In Proceedings 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 355--370, 2015.

Digital Library

[18]

M. Fischer and M. Ghaffari. Sublogarithmic distributed algorithms for Lovász local lemma with implications on complexity hierarchies. In Proceedings 31st International Symposium on Distributed Computing (DISC), pages 18:1--18:16, 2017.

[19]

M. Fischer, M. Ghaffari, and F. Kuhn. Deterministic distributed edge coloring via hypergraph maximal matching. In Proceedings 58th IEEE Symposium on Foundations of Computer Science (FOCS), pages 180--191, 2017.

[20]

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

[21]

H. N. Gabow, T. Nishizeki, O. Kariv, D. Leven, and O. Terada. Algorithms for edge-coloring graphs. Technical Report TRECIS-8501, Tohoku University, 1985.

[22]

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

Digital Library

[23]

M. Ghaffari, J. Hirvonen, F. Kuhn, Y. Maus, J. Suomela, and J. Uitto. Improved distributed degree splitting and edge coloring. In Proceedings 31st International Symposium on Distributed Computing (DISC), pages 19:1--19:15, 2017.

[24]

M. Ghaffari and H.-H. Su. Distributed degree splitting, edge coloring, and orientations. In Proceedings 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2505--2523, 2017.

Digital Library

[25]

I. Holyer. The NP-completeness of edge-coloring. SIAM Journal on Computing, 10(4):718--720, 1981.

[26]

H. J. Karloff and D. B. Shmoys. Efficient parallel algorithms for edge coloring problems. J. Algorithms, 8(1):39--52, 1987.

Digital Library

[27]

F. Kuhn and R. Wattenhofer. On the complexity of distributed graph coloring. In Proceedings 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 7--15, 2006.

Digital Library

[28]

N. Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193--201, 1992.

Digital Library

[29]

G. L. Miller and J. H. Reif. Parallel tree contraction-Part I: fundamentals. Advances in Computing Research, 5:47--72, 1989.

[30]

R. A. Moser and G. Tardos. A constructive proof of the general Lovász local lemma. J. ACM, 57(2), 2010.

Digital Library

[31]

M. Naor. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Discrete Mathematics, 4(3):409--412, 1991.

[32]

A. Panconesi and A. Srinivasan. The local nature of Δ-coloring and its algorithmic applications. Combinatorica, 15(2):255--280, 1995.

[33]

A. Panconesi and A. Srinivasan. On the complexity of distributed network decomposition. J. Algor., 20(2):356--374, 1996.

Digital Library

[34]

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

Digital Library

[35]

S. Pettie and H.-H. Su. Distributed algorithms for coloring triangle-free graphs. Information and Computation, 243:263--280, 2015.

Digital Library

[36]

V. G. Vizing. On an estimate of the chromatic class of a p-graph. Diskret. Analiz No., 3:25--30, 1964.

Cited By

Bhattacharya SGrandoni FWajc DMarx D(2021)Online edge coloring algorithms via the nibble methodProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458232(2830-2841)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458232
Achlioptas DGouleakis TIliopoulos FScheideler CSpear M(2020)Simple Local Computation Algorithms for the General Lovász Local LemmaProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400250(1-10)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400250
Duan RHe HZhang TChan T(2019)Dynamic edge coloring with improved approximationProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310552(1937-1945)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310552
Show More Cited By

The complexity of distributed edge coloring with small palettes
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

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 ...
Coloring k-colorable graphs using relatively small palettes

We obtain the following new coloring results: • A 3-colorable graph on n vertices with maximum degree Δ can be colored, in polynomial time, using O((Δ log Δ)^1/3 . log n) colors. This slightly improves an O((Δ^1/3log^1/2 Δ) . log n) bound given by Karger, ...
Coloring k-colorable graphs using smaller palettes
SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms
We obtain the following new coloring results:
- A 3-colorable graph on n vertices with maximum degree Δ can be colored, in polynomial time, using Ο((Δ log Δ)1/3 ·log n) colors. This slightly improves an Ο((Δ1/3 log1/2; Δ) · log n) bound given by Karger, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '18: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms

January 2018

2859 pages

ISBN:9781611975031

Program Chair:
Artur Czumaj
University of Warwick, United Kingdom

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2018

Check for updates

Qualifiers

Research-article

Conference

SODA '18

Sponsor:

SIGACT

SODA '18: Symposium on Discrete Algorithms

January 7 - 10, 2018

Louisiana, New Orleans

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
65
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bhattacharya SGrandoni FWajc DMarx D(2021)Online edge coloring algorithms via the nibble methodProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458232(2830-2841)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458232
Achlioptas DGouleakis TIliopoulos FScheideler CSpear M(2020)Simple Local Computation Algorithms for the General Lovász Local LemmaProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400250(1-10)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400250
Duan RHe HZhang TChan T(2019)Dynamic edge coloring with improved approximationProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310552(1937-1945)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310552
Su HVu HCharikar MCohen E(2019)Towards the locality of Vizing’s theoremProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316393(355-364)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316393
Bossek JSudholt DFriedrich TDoerr CArnold D(2019)Time complexity analysis of RLS and (1 + 1) EA for the edge coloring problemProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3299904.3340311(102-115)Online publication date: 27-Aug-2019
https://dl.acm.org/doi/10.1145/3299904.3340311
Brandt SRobinson PEllen F(2019)An Automatic Speedup Theorem for Distributed ProblemsProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331611(379-388)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3331611
Balliu AHirvonen JOlivetti DSuomela JRobinson PEllen F(2019)Hardness of Minimal Symmetry Breaking in Distributed ComputingProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331605(369-378)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3331605
Ghaffari MKuhn FMaus YUitto JDiakonikolas IKempe DHenzinger M(2018)Deterministic distributed edge-coloring with fewer colorsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188906(418-430)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188906
Balliu AHirvonen JKorhonen JLempiäinen TOlivetti DSuomela JDiakonikolas IKempe DHenzinger M(2018)New classes of distributed time complexityProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188860(1307-1318)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188860

View Options

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