Distributed Fractional Local Ratio and Independent Set Approximation

We consider the Maximum Weight Independent Set problem, with a focus on obtaining good approximations for graphs of small maximum degree \(\varDelta \) . We give deterministic local algorithms running in time \(\mathop {\textrm{poly}}\limits (\varDelta , \log n)\) that come close to matching the best centralized results known and improve the previous distributed approximations by a factor of about 2. More precisely, we obtain approximations below \(\frac{\varDelta +1/2}{2}\) , and a further improvement to \(8/5+\varepsilon \) when \(\varDelta =3\) . Technically, this is achieved by leveraging the fractional local ratio technique, for a first application in a distributed setting.