On Distributed Colouring of Hyperbolic Random Graphs

We analyse the performance of simple distributed colouring algorithms under the assumption that the input graph is a hyperbolic random graph (HRG), a generative model capturing key properties of real-world networks such as power-law degree distributions and large clustering coefficients. Motivated by the shift from worst-case analysis to more realistic network models, we study the number of rounds and size of the colour space required to colour HRGs in the distributed setting.

In the conceivable simplest algorithm each vertex selects a colour uniformly at random and keeps it permanently if no neighbour tries the same colour; otherwise it discards the candidate colour choice and tries a fresh random colour in the next round.

• We first show that this randomised algorithm terminates in exactly two rounds a.a.s. when given a colour space of 𝜀 ⋅ Δ, for any constant 𝜀 > 0, while failing w.h.p. if the colour space is only 𝜒 ⋅ 𝑛 𝛿 for some small constant 𝛿 > 0.

• We then consider another classic variation of that random colour trial algorithm that resolves conflicts by prioritising nodes with smaller IDs. While it also colours with colour space 𝜀 ⋅ Δ in two rounds, it w.h.p. fails to do so with Δ/ log Ω(1) Δ ≫ 𝜒 colours.

• Lastly, inspired by the structure of HRGs, we consider a variant of the random colour trial algorithm that prioritises high-degree vertices. It achieves a valid colouring in two rounds a.a.s. using only Δ 1-𝛿 colours for some constant 𝛿 > 0. We also show that our bound on the colour space is asymptotically tight (up to polylogarithmic factors) for certain values of the power-law exponent. All three randomised algorithms are extremely simple and run in the bandwidth-restricted CONGEST model. These positive results demonstrate that constant-time algorithms can outperform the classical Ω(log * 𝑛) lower bound for the Δ + 1-vertex colouring problem in worst-case graphs, established by [Linial; FOCS '87] and [Naor; SIAM Journal Disc. Math. '91].

Our results rely on several new structural insights into HRGs, which may be of independent interest. More generally, our results contribute to the line of research of simple algorithms beating the general lower bounds on HRGs like Ω(𝑛) for computing the shortest path [Bläsius, Freiberger, Friedrich, Katzmann, Montenegro-Retana and Thieffry; Transactions of Algorithms '24].