Efficient Deterministic Distributed Coloring with Small Bandwidth

2019/12/05 by Bamberger, Philipp, Kuhn, Fabian, Maus, Yannic · 2 citations
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.1912.02814

Abstract

We show that the (degree+1)-list coloring problem can be solved deterministically in O(D ⋅ log n ⋅log²Δ) rounds in the \CONGEST model, where D is the diameter of the graph, n the number of nodes, and Δ the maximum degree. Using the recent polylogarithmic-time deterministic network decomposition algorithm by Rozhoň and Ghaffari [STOC 2020], this implies the first efficient (i.e., \polylog n-time) deterministic \CONGEST algorithm for the (Δ+1)-coloring and the (degree+1)-list coloring problem. Previously the best known algorithm required 2^{O(√(log n))} rounds and was not based on network decompositions. Our techniques also lead to deterministic (degree+1)-list coloring algorithms for the congested clique and the massively parallel computation (MPC) model. For the congested clique, we obtain an algorithm with time complexity O(logΔ⋅loglogΔ), for the MPC model, we obtain algorithms with round complexity O(log²Δ) for the linear-memory regime and O(log²Δ+ log n) for the sublinear memory regime.

Cited by

• Distributed (Δ+1)-Coloring in Graphs of Bounded Neighborhood Independence
• Two for One, One for All: Deterministic LDC-based Robust Computation in Congested Clique

Related

• Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition
• Ultrafast Distributed Coloring of High Degree Graphs
• Distributed Graph Coloring Made Easy
• Faster Deterministic Distributed Coloring Through Recursive List Coloring
• Near-Optimal Distributed Degree+1 Coloring