Local algorithms for independent sets are half-optimal

Rahman, Mustazee; Virág, Bálint

Abstract

We show that the largest density of factor of i.i.d. independent sets in the d -regular tree is asymptotically at most ( log d ) / d as d → ∞ . 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 in these graphs is asymptotically 2 ( log d ) / d . We prove analogous results for Poisson–Galton–Watson trees, which yield bounds for local algorithms on sparse Erdős–Rényi graphs.

Citation

Rahman, M., & Virág, B. (2017). Local algorithms for independent sets are half-optimal. Annals of Probability, 45(3), 1543-1577. https://doi.org/10.1214/16-aop1094

• Journal Article Type: Article
• Acceptance Date: Jan 11, 2016
• Online Publication Date: May 15, 2017
• Publication Date: 2017
• Deposit Date: Sep 25, 2019
• Publicly Available Date: Oct 4, 2021
• Journal: Annals of Probability
• Print ISSN: 0091-1798
• Publisher: Institute of Mathematical Statistics
• Peer Reviewed: Peer Reviewed
• Volume: 45
• Issue: 3
• Pages: 1543-1577
• DOI: https://doi.org/10.1214/16-aop1094