Large independent sets on random $d$-regular graphs with fixed degree $d$

Abstract

This paper presents a linear prioritized local algorithm that computes large independent sets on a random $d$-regular graph with small and fixed degree $d$. We studied experimentally the independence ratio obtained by the algorithm when $d\in [3,100]$. For all $d\in [5,100]$, our results are larger than lower bounds calculated by exact methods, thus providing improved estimates of lower bounds.