Fast Distributed MIS and Maximal Matching on Spatial and PLB-Bounded Scale-Free Networks

Abstract We prove an axiomatic meta-theorem that yields O(log log n)-round randomized algorithms for maximal independent set (MIS) and maximal matching on broad classes of scale-free networks. Our framework unifies two settings: (i) geometry-driven rank-1 models (e.g., GIRG and soft-HRG) via a single high-probability “uniformity” event E that regularizes occupancies, cross-edges, and hub counts across all shells without referring to degree- or priority-defined sets; and (ii) power-law-bounded (PLB) degree families captured by PLB-U (upper tail), PLB-L (lower tail), and PLB-N (size-biased neighbor tail). The algorithms process vertices in degree bands. Hub–hub sparsity (from PLB-U via a weight pivot) gives bounded degeneracy within each band; R = O(1) independent micro-iterations of randomized greedy per phase stabilize progress by concentration. We expose a κ-fraction of edges per vertex using a per-edge public hash, and use PLB-N to sum the decaying band-mass effects across bands. Let γ = τ − 2 ∈ (0, 1) and choose any constant κ ∈ (0, 1/4). Then the per-phase survival probability for degree about B^J is exp(−Θ(BJ(γ − κ(1 − γ)))). Setting κ_eff = (γ − κ(1 − γ))/2 > 0 yields a double-exponential degree cascade Δᵢ₊₁ ≤ Δ_i1 − κ_eff with high probability. After O((1/κ_eff) log log n) phases, the maximum degree drops to polylog(n); any standard finisher with round complexity O(log Δ) + poly(log log n) then completes in O(log log n) rounds. Under geometry, the residual also finishes in O(log log n) rounds (and in O(1) on typical threshold-HRG instances). In CONGEST, messages are O(log n) bits per edge per round.