Large independent sets on random d-regular graphs with d small
Raffaele Marino, Scott Kirkpatrick · arXiv (Cornell University) · 2020
In this paper, we present a prioritized local algorithm that computes a maximal independent set on a random $d$-regular graph with small and fixed connectivity $d$. Combining different strategies, we compute new lower bounds on the independence ratio $\forall d \in [5,100]$, $d\in \mathbb{N}$. All the new bounds improve upon the best previous bounds. Moreover, for independent set in random $3$-regular graph, we experimentally extrapolate, by finite-size analysis, the asymptotic value of the independence ratio at $\alpha_{LB}=0.445327$.