Dominating Set in Geometry-Driven Scale-Free Graphs: Uniform Logarithmic Separators and Polynomial-Time Exact Algorithms
Ankit Chauhan · 2025
We prove that in spatial scale-free networks where geometry suppresses long edges sufficiently strongly, the Dominating Set problem is solvable in polynomial time with high probability. For Euclidean GIRGs in d ≥ 2 with degree-tail exponent τ ∈ (2, 3) and geometry parameter α, if α > τ − 1 then there exists a single high-probability event on which every geometryaligned subproblem admits an O(log n) vertex separator; hence tw(G) = O(log n) and a DP yields an exact polynomial-time algorithm for Dominating Set. For threshold HRGs, we uniformly restate ESA'16's regimes (parameter α HRG , degree exponent β = 2α HRG + 1): O(log n) separators when α HRG > 1 and O(log 2 n) at α HRG = 1, now as a single-event guarantee. At the GIRG/HRG boundaries we obtain O(log 2 n) separators; for GIRG with α < τ − 1 we give rough-order polynomial separators n γ +o(1). Proofs combine a corridor/shell construction, stochastic domination by a subcritical Poisson Galton-Watson process, hub packing, and a tuned union bound; at the boundary we use a Freedman martingale with bounded increments. All separator/treewidth upper bounds rely only on an upper bound on the edge kernel, while the DP consults realized adjacencies inside bags.