Source-linked AI summary
Limits of local algorithms over sparse random graphs
David Gamarnik, Madhu Sudan
TL;DR
The paper asks whether local algorithms can find nearly maximum independent sets in sparse random regular graphs. It proves limits using a clustering property of large independent sets: they either overlap substantially or nearly not at all, ruling out the HLS conjecture and bounding local performance.
Problem
The HLS conjecture proposed that local algorithms could solve maximum independent set nearly optimally on sparse random regular graphs.
Method
The paper proves a clustering property for large independent sets and combines it with a coupling argument showing that successful local algorithms would create forbidden intermediate overlaps.
Results
Every independent set producible by an i.i.d. factor is at most a multiplicative factor γ < 1 of the largest independent set, with γ asymptotically at most 1/2.
Takeaways & Limitations
Clustering directly yields a formal limit on local algorithms for maximum independent set and links algorithmic hardness to solution-space geometry.
Takeaways & Limitations
The proof’s additional factor 1/(2√2) is described as an artifact of the analysis, and the stronger γ = 1/2 claim remains conjectural.
Abstract
from arXiv · showhide
Local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph. Such algorithms use only local information available at nodes to determine local aspects of the global structure, while also potentially using some randomness. Recent research has shown that such algorithms show significant promise in computing structures like large independent sets in graphs locally. Indeed the promise led to a conjecture by Hatami, \Lovasz and Szegedy \cite{HatamiLovaszSzegedy} that local algorithms may be able to compute maximum independent sets in (sparse) random $d$-regular graphs. In this paper we refute this conjecture and show that every independent set produced by local algorithms is multiplicative factor $1/2+1/(2\sqrt{2})$ smaller than the largest, asymptotically as $d\rightarrow\infty$. Our result is based on an important clustering phenomena predicted first in the literature on spin glasses, and recently proved rigorously for a variety of constraint satisfaction problems on random graphs. Such properties suggest that the geometry of the solution space can be quite intricate. The specific clustering property, that we prove and apply in this paper shows that typically every two large independent sets in a random graph either have a significant intersection, or have a nearly empty intersection. As a result, large independent sets are clustered according to the proximity to each other. While the clustering property was postulated earlier as an obstruction for the success of local algorithms, such as for example, the Belief Propagation algorithm, our result is the first one where the clustering property is used to formally prove limits on local algorithms.
1 Introduction
The paper studies local algorithms for maximum independent sets in sparse random regular graphs and refutes the HLS conjecture that such algorithms can approach optimality. It uses clustering of large independent sets to derive performance limits.
- 1 Introduction: Local algorithms use only local graph neighborhoods and randomness while operating in parallel to compute global structures.They have applications in distributed computing, sub-linear algorithms, and heuristics such as Belief Propagation.
- 1 Introduction: The HLS conjecture proposed that reasonable combinatorial optimization problems on random graphs, including maximum independent set, could be solved by local algorithms.The paper focuses on sparse random d-regular graphs.
- 1 Introduction: Clustering results for large independent sets show that solutions tend to have either substantial overlap or nearly empty intersection.Earlier Erdős–Rényi results did not exclude rare pairs with intermediate overlap, motivating the stronger random-regular-graph analysis here.
- 1 Introduction: For sufficiently large d, every two independent sets of size asymptotically (1+β)(log d/d)n have either large or small intersection, with high probability as n →∞.The forbidden intermediate-overlap interval is established by a first moment calculation whose expected count vanishes exponentially fast.
- 1 Introduction: A coupling argument shows that a local algorithm producing independent sets of this size would generate intermediate overlaps, contradicting the clustering property.This contradiction yields the paper’s refutation of the HLS conjecture.
- 1 Introduction: The paper states that local algorithms produce independent sets at most a factor 1/2 of optimal asymptotically in d, while noting the displayed additional factor is an artifact of the analysis.The authors identify this as the first hardness result relying directly on solution-space geometry and clustering.
2 Preliminaries and main result
The paper formalizes local algorithms as radius-limited randomized decision rules on random regular graphs, then refutes the HLS conjecture for maximum independent set when degree is sufficiently large. Its proof combines concentration of locally produced sets with a clustering theorem showing that large independent sets cannot have intermediate overlaps.
- Local algorithms: Local algorithms use only graph neighborhoods and local randomness; an r-local function gives identical decisions under corresponding local isomorphisms and equivalent randomness.An i.i.d. factor is produced by applying such a function to a canonical rooted d-regular tree with independent uniform random inputs.
- Local algorithms: With high probability, the independent set returned by an r-local function on G_d(n) has size α(f)n+o(n).The density α(f) is defined from the expected root decision on the canonical rooted tree.
- Main result: The HLS conjecture asks whether local algorithms can produce independent sets in G_d(n) whose cardinality approaches the largest available independent sets.The paper defines the best locally achievable density as α̂_d, taking suprema over locality radii and r-local independence functions.
- Main result: For every ε>0 and sufficiently large d, the largest independent set obtainable by r-local functions is at most 1/2+ε times the independence ratio, for every r.Thus a multiplicative gap persists between α̂_d and α_d; the result does not exclude equality for small d.
- Clustering and proof: For large d, independent sets of size approximately (1+β)(log d/d)n cannot have intermediate overlap: sufficiently large sets are either substantially overlapping or nearly disjoint.As β approaches 1, the forbidden overlap interval becomes extremely broad, so nearly maximum independent sets either overlap almost entirely or barely intersect.
- Clustering and proof: The proof couples two applications of an r-local function to construct independent sets with intermediate overlap, contradicting the clustering property when the local density is too large.This argument is formalized through the two secondary theorems on overlap structure and coupled local outputs.
3 Proof of Theorem 2.5
The proof combines the existence of independent-set pairs with prescribed overlaps and the absence of such intermediate-overlap pairs to bound every local algorithm's output ratio.
- The proof fixes an r-local function and writes α = α(fr), then targets α/αd ≤ 1/2 + 1/(2√2) + η for sufficiently large d.
- For every γ ∈ [α^2, α], two independent sets of size at least (α − ε)n can be chosen with intersection approximately γn.
- Theorem 2.6 excludes large independent-set pairs whose intersection lies in the intermediate interval around γn.
- Combining the overlap construction with this exclusion yields α ≤ (1 + 1/(2√2) + η)d^-1 log d and therefore α/αd ≤ 1/2 + 1/(2√2).
4 Proof of Theorem 2.7
The proof couples two inputs to the same local algorithm and shows that their output overlap continuously ranges from α^2 to α, producing independent sets with any intermediate overlap.
- For p-correlated inputs, γ(p) is the probability that the local rule selects a vertex under both decisions.
- On locally tree-like neighborhoods, the expected intersection size is γ(p)n + o(n), and concentration gives overlap within εn of this value.
- The endpoint values are γ(1) = α and γ(0) = α^2.
- Continuity of γ(p) implies that every γ ∈ [α^2, α] equals γ(p) for some p.
- Applying the concentration lemma to that p yields two algorithm-generated independent sets whose intersection lies in [(γ − ε)n, (γ + ε)n] with probability at least 1 − ε.
5 Theorem 2.6: Case of the Erd¨os-R´enyi graph G(n, d/n)
For Erdős–Rényi graphs, the proof shows that near-maximum independent sets cannot have overlap in a specified intermediate range by bounding the expected number of such pairs.
- The theorem concerns pairs of near-maximum independent sets whose intersection sizes fall in an intermediate interval.
- The proof counts pairs of independent sets with prescribed sizes and overlap, then shows their expected number vanishes exponentially for forbidden overlaps.
- Markov's inequality and a union bound then establish that no such pairs exist with high probability.
- Setting m = ⌊ns⌋ and k = ⌊nx⌋ parameterizes the independent-set size and intersection size used in the counting argument.
- Stirling and logarithmic asymptotics reduce the normalized logarithm of the expectation to an expression whose negativity is enforced by the choices of β and z.
6 Theorem 2.6: Case of the random regular graph Gd(n)
For random regular graphs, the proof uses the configuration model to reproduce the Erdős–Rényi counting exponent and thereby establish the same forbidden-overlap result.
- The configuration model represents each graph vertex by d replicas paired through a uniformly random matching, then projects matched replicas back to graph edges.
- Conditioning on the absence of loops and parallel edges yields the random regular graph model, and this conditioning is harmless for high-probability statements.
- The proof partitions pairs of independent sets by their size, overlap, and the number of edges between their noncommon parts.
- Therefore the same first-moment argument proves that intermediate-overlap pairs are absent with high probability in random regular graphs.
- After normalizing and simplifying the matching count, the resulting expression agrees with the Erdős–Rényi expression up to an asymptotically negligible term.