2014 · 107 citations · 24 references
ComputingComputer ScienceMathematicsAlgorithmsParallel AlgorithmsParallel ComputingApproximation AlgorithmsGraph AlgorithmsGraph TheoryConstraint Satisfaction SearchIndependent Set AlgorithmsRandom Graph TheoryRandom GraphsRandom Regular GraphsSparse Random GraphsSpin Glasses
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. Research over the years has shown that such algorithms can be surprisingly powerful in terms of computing structures like large independent sets in graphs locally. These algorithms have also been implicitly considered in the work on graph limits, where a conjecture due to Hatami, Lovász and Szegedy [17] implied that local algorithms may be able to compute near-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 smaller that the largest one by a multiplicative factor of at least 1/2+1/(2√2) ≈ .853, asymptotically as d → ∞.
24
Locality in Distributed Graph Algorithms
Nathan Linial · SIAM Journal on Computing · 1992 · 885 citations
Limits of dense graph sequences
László Lovász, Balázs Szegedy · Journal of Combinatorial Theory Series B · 2006 · 840 citations
A simple parallel algorithm for the maximal independent set problem
Michael Luby · 1985 · 343 citations · Full text
Convergent sequences of dense graphs II. Multiway cuts and statistical physics
Christian Borgs, Jennifer Chayes, László Lovász et al. · Annals of Mathematics · 2012 · 316 citations · Full text