Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier

Abstract

The dynamic set cover problem has been subject to extensive research since the pioneering works of [Bhattacharya et al, 2015] and [Gupta et al, 2017]. The input is a set system $(U,S)$ on a fixed collection $S$ of sets and a dynamic universe of elements, where each element appears in a most $f$ sets and the cost of each set lies in the range $[1/C,1]$, and the goal is to efficiently maintain an approximately-minimum set cover under insertions and deletions of elements. Most previous work considers the low-frequency regime, namely $f=O(\log n)$, and this line of work has culminated with a deterministic $(1+\epsilon )f$-approximation algorithm with amortized update time $O(\frac{f^2}{{\epsilon }^3}+\frac{f}{{\epsilon }^2}\log C)$ [Bhattacharya et al, 2021]. In the high-frequency regime of $f=\Omega (\log n)$, an $O(\log n)$-approximation algorithm with amortized update time $O(f\log n)$ was given by [Gupta et al, 2017]. Interestingly, at the intersection of the two regimes, i.e., $f=\Theta (\log n)$, the state-of-the-art results coincide: approximation $\Theta (f)=\Theta (\log n)$ with amortized update time $O(f^2)=O(f\log n)=O({\log }^{2}n)$. Up to this date, no previous work achieved update time of $o(f^2)$. In this paper we break the $\Omega (f^2)$ update time barrier via the following results: (1) $(1+\epsilon )f$-approximation can be maintained in $O\left(\frac{f}{{\epsilon }^3}{\log }^{\ast }f+\frac{f}{{\epsilon }^3}\log C\right)=O_{\epsilon ,C}(f{\log }^{\ast }f)$ expected amortized update time; our algorithm works against an adaptive adversary. (2) $(1+\epsilon )f$-approximation can be maintained deterministically in $O\left(\frac{1}{\epsilon }f\log f+\frac{f}{{\epsilon }^3}+\frac{f\log C}{{\epsilon }^2}\right)=O_{\epsilon ,C}(f\log f)$ amortized update time.

Major revision. Accepted to SODA 2025