Local algorithms for independent sets are half-optimal

DOI10.1214/16-AOP1094zbMATH Open1377.60049arXiv1402.0485MaRDI QIDQ2012245FDOQ2012245

Balint Virag, Mustazee Rahman

Publication date: 28 July 2017

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

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.

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

zbMATH Keywords

independent setrandom regular graphs[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Erd%EF%BF%BD%EF%BF%BDs-R%EF%BF%BD%EF%BF%BDnyi+random+graphs&go=Go Erd��s-R��nyi random graphs]local algorithm

Mathematics Subject Classification ID

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

Cited In (44)

• Mutual information decay for factors of i.i.d.
• Factor of IID Percolation on Trees
• Algorithmic obstructions in the random number partitioning problem
• Asymptotic bounds on total domination in regular graphs
• Optimal low-degree hardness of maximum independent set
• Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks
• Cryptography from planted graphs: security with logarithmic-size messages
• Brief Announcement
• Suboptimality of local algorithms for a class of max-cut problems
• Local approximation of the maximum cut in regular graphs
• Walksat Stalls Well Below Satisfiability
• Colouring graphs with forbidden bipartite subgraphs
• Entropy and expansion
• Correlation Bounds for Distant Parts of Factor of IID Processes
• Computational barriers to estimation from low-degree polynomials
• Shattering versus metastability in spin glasses
• A factor of i.i.d. with uniform marginals and infinite clusters spanned by equal labels
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• Entropy inequalities for factors of IID
• Sparse high-dimensional linear regression. Estimating squared error and a phase transition
• Minimum 2-dominating sets in regular graphs
• Free Energy Wells and Overlap Gap Property in Sparse PCA
• Borel fractional colorings of Schreier graphs
• On perfectly friendly bisections of random graphs
• Optimal Randomized Algorithms for Local Sorting and Set-Maxima
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• Sofic homological invariants and the Weak Pinsker Property
• Tight Lipschitz hardness for optimizing mean field spin glasses
• Total domination in regular graphs
• The overlap gap property in principal submatrix recovery
• The largest hole in sparse random graphs
• Improved replica bounds for the independence ratio of random regular graphs
• A tale of two balloons
• Simple and local independent set approximation
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• Greedy maximal independent sets via local limits
• Spectral measures of factor of i.i.d. processes on vertex-transitive graphs
• Energy landscape for large average submatrix detection problems in Gaussian random matrices
• On the almost eigenvectors of random regular graphs
• Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem
• Optimizing mean field spin glasses with external field
• Ising model on trees and factors of IID
• 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)