ABSTRACT
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 → ∞.
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.
- D. Achlioptas, A. Coja-Oghlan, and F. Ricci-Tersenghi. On the solution space geometry of random formulas. Random Structures and Algorithms, 38:251--268, 2011. Google ScholarDigital Library
- D. Aldous. Some open problems. phhttp://www.stat.berkeley.edu/~aldous/ Research/OP/index.html.Google Scholar
- N. Alon and J. Spencer. Probabilistic Method. Wiley, 1992.Google Scholar
- M. Bayati, D. Gamarnik, and P. Tetali. Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. Annals of Probability, to appear. Conference version in Proc. 42nd Ann. Symposium on the Theory of Computing (STOC), 2010. Google ScholarDigital Library
- C. Borgs, J. Chayes, and D. Gamarnik. Convergent sequences of sparse graphs: A large deviations approach. arxiv:1302.4615 {math.PR}, 2013.Google Scholar
- C. Borgs, J. Chayes, L. Lovász, and J. Kahn. Left and right convergence of graphs with bounded degree. http://arxiv.org/abs/1002.0115, 2010.Google Scholar
- C. Borgs, J. Chayes, L. Lovász, V. Sós, and K. Vesztergombi. Convergent graph sequences II: Multiway cuts and statistical physics. Ann. of Math., 176:151--219, 2012.Google ScholarCross Ref
- C. Borgs, J. Chayes, L. Lovász, V. Sós, and K. Vesztergombi. Convergent graph sequences I: Subgraph frequencies, metric properties, and testing. Advances in Math., 219:1801--1851, 208.Google ScholarCross Ref
- A. Coja-Oghlan. On belief propagation guided decimation for random k-sat. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 957--966. SIAM, 2011. Google ScholarDigital Library
- A. Coja-Oghlan and C. Efthymiou. On independent sets in random graphs. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 136--144. SIAM, 2011. Google ScholarDigital Library
- E. Csoka and G. Lippner. Invariant random matchings in cayley graphs. arXiv preprint arXiv:1211.2374, 2012.Google Scholar
- G. Elek and G. Lippner. Borel oracles. an analytical approach to constant-time algorithms. In Proc. Amer. Math. Soc, volume 138, pages 2939--2947, 2010.Google ScholarCross Ref
- A. Frieze. On the independence number of random graphs. Discrete Mathematics, 81:171--175, 1990. Google ScholarDigital Library
- A. Frieze and T. Łuczak. On the independence and chromatic numbers of random regular graphs. Journal of Combinatorial Theory, Series B, 54(1):123--132, 1992. Google ScholarDigital Library
- D. Gamarnik and M. Sudan. Limits of local algorithms over sparse random graphs. Electronic Colloquium on Computational Complexity (ECCC), 20:55, 2013.Google Scholar
- A. Hassidim, J. A. Kelner, H. N. Nguyen, and K. Onak. Local graph partitions for approximation and testing. In FOCS, pages 22--31. IEEE Computer Society, 2009. Google ScholarDigital Library
- H. Hatami, L. Lovász, and B. Szegedy. Limits of local-global convergent graph sequences. Preprint at http://arxiv.org/abs/1205.4356, 2012.Google Scholar
- R. Karp and M. Sipser. Maximum matchings in sparse random graphs. In 22nd Annual Symposium on Foundations of Computer Science, pages 364--375, 1981. Google ScholarDigital Library
- N. Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193--201, 1992. Google ScholarDigital Library
- L. Lovász and B. Szegedy. Limits of dense graph sequences. Journal of Combinatorial Theory, Series B, 96:933--957, 2006. Google ScholarDigital Library
- M. Luby. A simple parallel algorithm for the maximal independent set problem. In R. Sedgewick, editor, STOC, pages 1--10. ACM, 1985. Google ScholarDigital Library
- R. Lyons and F. Nazarov. Perfect matchings as iid factors on non-amenable groups. European Journal of Combinatorics, 32(7):1115--1125, 2011. Google ScholarDigital Library
- M. Mezard and A. Montanari. Information, Physics and Computation. Oxford graduate texts, 2009. Google ScholarDigital Library
- M. Mézard, T. Mora, and R. Zecchina. Clustering of solutions in the random satisfiability problem. Physical Review Letters, 94(19):197205, 2005.Google ScholarCross Ref
- H. N. Nguyen and K. Onak. Constant-time approximation algorithms via local improvements. In FOCS, pages 327--336. IEEE Computer Society, 2008. Google ScholarDigital Library
- M. Parnas and D. Ron. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theor. Comput. Sci., 381(1-3):183--196, 2007. Google ScholarDigital Library
- R. Rubinfeld, G. Tamir, S. Vardi, and N. Xie. Fast local computation algorithms. In B. Chazelle, editor, ICS, pages 223--238. Tsinghua University Press, 2011.Google Scholar
- M. Talagrand. Mean Field Models for Spin Glasses: Volume I: Basic Examples. Springer, 2010.Google Scholar
- M. J. Wainwright and M. I. Jordan. A variational principle for graphical models. In New Directions in Statistical Signal Processing: From Systems to Brain. Cambridge, MA: MIT Press, 2005.Google Scholar
Index Terms
- Limits of local algorithms over sparse random graphs
Recommendations
Equitable coloring of random graphs
An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most one. The least positive integer k for which there exists an equitable coloring of a graph G with k colors is said to be the ...
Properties of regular graphs with large girth via local algorithms
The average-case analysis of probabilistic algorithms has proved to be very successful for finding asymptotic bounds on parameters of random regular graphs. Recently, the authors obtained a general transfer result which translates such bounds into (...
Anti-Ramsey properties of random graphs
We call a coloring of the edge set of a graph G a b-bounded coloring if no color is used more than b times. We say that a subset of the edges of G is rainbow if each edge is of a different color. A graph has property A(b,H) if every b-bounded coloring ...
Comments