Distributed Symmetry Breaking on Hyperbolic Random Graphs
For researchers in distributed computing and network algorithms, this work reveals that HRGs, despite enabling fast coloring, impose fundamental lower bounds for other symmetry-breaking problems, and provides nearly matching upper bounds.
The paper studies distributed symmetry-breaking problems on hyperbolic random graphs (HRGs), proving that maximal independent set (MIS) and maximal matching (MM) require Ω(log log n / log log log n) rounds, while providing algorithms that solve them in Õ(log^{5/3} log n) rounds, showing polynomial tightness.
Real-world networks like the internet share patterns like a power law degree distribution and a high clustering coefficient. Many of these properties are captured by the generative model of hyperbolic random graphs (HRGs), which provides a theoretical framework for studying such networks. Motivated by the observation that several algorithms perform better on real-world networks than their worst-case guarantees suggest, we design and analyse distributed algorithms under the assumption that the input graph is an HRG. Indeed, prior work has shown that the classical symmetry-breaking problem of $Δ+1$ colouring, where $Δ$ is the maximum degree of the graph, can be solved in 2 rounds on HRGs [Maus and Ruff; SODA'26]. In stark contrast to this 2-round algorithm for $Δ+1$ colouring, we prove that the related symmetry-breaking problems of maximal independent set (MIS) and maximal matching (MM) are substantially harder: we establish a lower bound of $Ω\left(\frac{\log\log n}{\log\log\log n}\right)$ for MIS and MM on HRGs. Our lower bound techniques rely on new structural insights that may be of independent interest: we show that HRGs contain $d$-ary trees with large height and degree which enables us to adapt and lift prior impossibility results for distributed algorithms to the setting of HRGs. We also show that these lower bounds are polynomial tight: we design algorithms tailored to HRGs that solve MIS and MM in $\tilde{\mathcal{O}}(\log^{5/3}\log n)$ rounds with high probability in the LOCAL model, improving over the general worst-case lower bound of $Ω\left(\min\left\{\log Δ, \sqrt{\log n}\right\}\right)$ rounds [Khoury and Schild; FOCS'25].