MIS and Maximal Matching Prove Harder Than Coloring on Hyperbolic Random Graphs
New lower bound of Ω(log log n / log log log n) shocks distributed computing theorists.
Hyperbolic Random Graphs (HRGs) are a generative model that captures key properties of real-world networks like the internet: power-law degree distribution and high clustering. Prior work showed that the classic symmetry-breaking problem of Δ+1 coloring can be solved in just 2 rounds on HRGs, suggesting distributed algorithms might excel on these topologies. However, a new paper by Maus, Ruff, Simons, and Skretas reveals that the related problems of Maximal Independent Set (MIS) and Maximal Matching (MM) are far more demanding.
The authors prove a lower bound of Ω(log log n / log log log n) rounds for both MIS and MM on HRGs, using novel structural insights—showing that HRGs contain d-ary trees of large height and degree, allowing them to adapt prior impossibility results. They complement this with almost-tight algorithms that solve MIS and MM in Õ(log^(5/3) log n) rounds in the LOCAL model, beating the general worst-case lower bound of Ω(min(log Δ, √log n)). This work sharpens our understanding of which distributed tasks benefit from network structure and which remain inherently difficult.
- MIS and MM on HRGs require Ω(log log n / log log log n) rounds, drastically more than the 2-round Δ+1 coloring algorithm.
- Lower bound leverages d-ary trees embedded in HRGs to lift existing impossibility results from distributed computing.
- New algorithms achieve MIS/MM in Õ(log^(5/3) log n) rounds, nearly matching the lower bound and outperforming worst-case guarantees.
Why It Matters
Shows that not all symmetry-breaking problems become easy on real-world network topologies, guiding future distributed algorithm design.