Faster Sublinear Maximal Independent Set Size

Peter Kiss, Arash Kooroshnezhad

We give a sublinear-time algorithm for estimating the size of a maximal independent set in a graph using adjacency-query access with expected running time $\tilde{O}(n^{1+1/3})$, i…