The Taub Faculty of Computer Science Events and Talks

This talk focuses on the distributed task of constructing an approximate \emph{maximum weight independent set (MWIS)}. Specifically, we are interested in deterministic CONGEST algorithms whose approximation guarantees are expressed as a function of the graph's \emph{arboricity} $\alpha$.

Generally speaking, efficient deterministic non-trivial approximation algorithms for MWIS were not known until the recent breakthrough of Faour et al.~[SODA 2023] that obtained an $O(\Delta)$-approximation in $O(\log^{2} n)$ rounds on graphs of maximum degree $\Delta$. Combined with a transformation presented by Kawarabayashi et al.~[DISC 2020], one obtains the current state-of-the-art: a $4 (1 + \epsilon) \alpha$-approximation in $O(\log^{3} n)$ rounds. In this talk, I present new algorithms that achieve arboricity-dependent approximations for MWIS.

These algorithms exhibit an approximation-runtime tradeoff: on one endpoint of the spectrum is an improved $(2 + \epsilon) \alpha$ approximation in $O(\alpha \log n)$ rounds; on the other endpoint is an $\alpha^{1 + \epsilon}$-approximation with a significantly faster $O(\log \alpha \log n)$ runtime.

The talk will be self contained.