Single-Event Uniform Separators in Geometry-Driven Scale-Free Graphs: A Meta Theorem for Exact Algorithms via Treewidth
Ankit Chauhan · 2025
We prove a single-event separator theorem for latent-geometric, rank-1 random graphs with i.i.d. positions, heavy-tailed weights, conditionally independent edges, and an upper distancepenalized kernel. Specializing to Euclidean GIRGs (d ≥ 2, τ ∈ (2, 3), geometry parameter α) we obtain a sharp trichotomy: (i) if α > τ − 1, then every kd-tree box admits an O(log n) vertex separator simultaneously on an event of probability 1 − n −ω(1) ; hence tw(G) = O(log n) and standard TD-DPs give exact polynomial time w.h.p.; (ii) at α = τ − 1, separators are O(log 2 n) and runtimes become quasi-polynomial; (iii) under a two-sided kernel, for α < τ − 1 polynomialsize separators are necessary. Our proofs use corridor/shell exposures with global Poissonization and independent thinning to couple to (sub/super)critical Poisson Galton-Watson processes; heavy vertices are uniformly sparse; at the boundary, a tile-wise Freedman martingale yields the log 2 n bound. All upper bounds use only the upper kernel and conditional independence; realized edges are consulted only to construct bags and inside bags. We also give an O((n+m) log n) tree-decomposition based on edge-LCA on a kd-tree. Beyond GIRG, we instantiate Geometric Chung-Lu and rank-1 Random-Connection models, give the hyperbolic analogue (HRG), and include independent Kleinberg-type long edges.