Distributed Symmetry Breaking on Hyperbolic Random Graphs
2026-07-10 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors study special network models called hyperbolic random graphs (HRGs) that resemble real-world networks like the internet. They focus on how quickly certain tasks, like maximal independent set (MIS) and maximal matching (MM), can be solved in distributed systems when the network follows an HRG structure. While previous work showed a very fast solution for another task (Δ+1 coloring), the authors prove that MIS and MM are much harder on HRGs, requiring more rounds. They establish new lower bounds for these problems and also create algorithms that nearly match these bounds, improving over known results for worst-case networks.
hyperbolic random graphsdistributed algorithmsmaximal independent setmaximal matchingΔ+1 coloringLOCAL modellower boundsnetwork clusteringpower law distributionsymmetry-breaking
Authors
Yannic Maus, Janosch Ruff, Sonia Simons, George Skretas
Abstract
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].