Abstract

Title: An LCA for Greedy Set Cover
 

Abstract: We study the Set Cover problem in the setting of Local Computation (LCAs). In the classical setting, the Set Cover problem is known to have simple linear-time algorithms in two regimes of approximation: (i) a $1 + \ln n$-approximate algorithm and (ii) an $f$-approximate algorithm.
While efficient LCAs achieving $O(f)$-approximations with $\text{poly}(\Delta, f)$ queries follow from prior work – [Kapralov, Mitrovic, Norouzi-Fard, Tardos SODA ‘20] and [Ghaffari FOCS ‘22], the state-of-art algorithm achieving $O(\log \Delta)$ approximation –  [Grunau, Mitrovic, Rubinfeld, Vakilian SODA ‘20] – requires exponential in $\log^2 \Delta + \log \Delta \log f$ queries. All of these algorithms are derived from distributed algorithms for these problems. They can be interpreted as sparsifying the input graph so that the corresponding distributed algorithm has a similar output. We show that a simple pruning procedure can sparsify the input instance so that its “average degree” is at most $O(\log \Delta \log f)$. With a slightly more involved procedure, it can also be reduced to a constant. Our procedure reduces the exponent of the state-of-the-art to $\tilde{O}(\log \Delta \log f)$ and $\log \Delta \log f$ respectively.