Local algorithms for independent sets are half-optimal

DOI10.1214/16-AOP1094MaRDI QIDQ2012245zbMATH OpenFDO

Authors Mustazee Rahman, Balint Virag

Publication date 28 July 2017

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.0485

zbMATH Keywords

Erdős-Rényi random graphsindependent setlocal algorithmrandom regular graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Stationary stochastic processes (60G10) Randomized algorithms (68W20)

Abstract: We show that the largest density of factor of i.i.d. independent sets on the d-regular tree is asymptotically at most (log d)/d as d tends to infinity. This matches the lower bound given by previous constructions. It follows that the largest independent sets given by local algorithms on random d-regular graphs have the same asymptotic density. In contrast, the density of the largest independent sets on these graphs is asymptotically 2(log d)/d. We also prove analogous results for Poisson-Galton-Watson trees, which yield bounds for local algorithms on sparse Erdos-Renyi graphs.

Review text

This paper considers independent sets in a random \(d\)-regular graph for large \(d\). In particular, it considers the size of independent sets that can be the output of a local algorithm that constructs independent sets. The term ``local refers to the assumption that the algorithm takes decisions about a vertex of the input graph based on the neighbourhood around this vertex within some bounded distance \(r\). The authors show several results about the sizes of the independent sets that can be produced by such an algorithm. Among other results, they show that such an independent set cannot be larger than \((1+ \varepsilon) d/ \log d\). Note that this is approximately half the independence number, which has been shown to be asymptotic to \(2 d /\log d\), by independent works of \textit{B. Bollobás} [Random graphs. 2nd ed. Cambridge: Cambridge University Press (2001; Zbl 0979.05003)], \textit{B. D. McKay} [Ars Comb. 23A, 179--185 (1987; Zbl 0644.05028)] as well as \textit{A. M. Frieze} and \textit{T. Łuczak} [J. Comb. Theory, Ser. B 54, No. 1, 123--132 (1992; Zbl 0771.05088)]. This result is proved through another key inequality that is also proved in the paper regarding the sizes of the intersections of such independent sets. Similar results are deduced for \(G(n,\lambda/n)\) random graphs, considering algorithms that act locally on a Galton-Watson tree whose offspring distribution is Poisson with parameter \(\lambda>0\).

Recommendations

• Limits of local algorithms over sparse random graphs
• Limits of local algorithms over sparse random graphs
• Large independent sets in random regular graphs
• Local algorithms, regular graphs of large girth, and random regular graphs
• Locally dense independent sets in regular graphs of~large~girth -- an example of a new approach

Cited in

(55)

• Large independent sets in random regular graphs
• Spectral measures of factor of i.i.d. processes on vertex-transitive graphs
• Local algorithms, regular graphs of large girth, and random regular graphs
• Entropy and expansion
• The overlap gap property in principal submatrix recovery
• Ising model on trees and factors of IID
• Minimum 2-dominating sets in regular graphs
• Optimal low-degree hardness of maximum independent set
• Sparse high-dimensional linear regression. Estimating squared error and a phase transition
• Total domination in regular graphs
• Computational barriers to estimation from low-degree polynomials
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• Entropy inequalities for factors of IID
• Energy landscape for large average submatrix detection problems in Gaussian random matrices
• Suboptimality of local algorithms for a class of max-cut problems
• On the almost eigenvectors of random regular graphs
• Asymptotic bounds on total domination in regular graphs
• Improved replica bounds for the independence ratio of random regular graphs
• A tale of two balloons
• Performance of sequential local algorithms for the random NAE-K-SAT problem
• Uncover Low Degree Vertices and Minimise the Mess: Independent Sets in Random Regular Graphs
• Optimal Randomized Algorithms for Local Sorting and Set-Maxima
• Correlation bounds for distant parts of factor of IID processes
• Sofic homological invariants and the weak Pinsker property
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• Mutual information decay for factors of i.i.d.
• Walksat Stalls Well Below Satisfiability
• Factor of iid percolation on trees
• Brief Announcement
• Colouring graphs with forbidden bipartite subgraphs
• Simple and local independent set approximation
• Local approximation of the maximum cut in regular graphs
• Limits of local algorithms over sparse random graphs
• The largest hole in sparse random graphs
• A factor of i.i.d. with uniform marginals and infinite clusters spanned by equal labels
• Free Energy Wells and Overlap Gap Property in Sparse PCA
• Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks
• Algorithmic obstructions in the random number partitioning problem
• Borel fractional colorings of Schreier graphs
• Shattering versus metastability in spin glasses
• Optimizing mean field spin glasses with external field
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
• Greedy maximal independent sets via local limits
• Cryptography from planted graphs: security with logarithmic-size messages
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• On perfectly friendly bisections of random graphs
• Tight Lipschitz hardness for optimizing mean field spin glasses
• The low-degree hardness of finding large independent sets in sparse random hypergraphs
• Shattering in the Ising p-spin glass model
• The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
• Sampling from mean-field Gibbs measures via diffusion processes
• The algorithmic phase transition of random graph alignment problem
• Sharp phase transitions for the overlap gap property
• Parametric RDT approach to computational gap of symmetric binary perceptron
• Finding one community in a sparse graph

This page was built for publication: Local algorithms for independent sets are half-optimal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012245)