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

The dynamic set cover problem has been subject to extensive research since the pioneering works of [BHI, ICALP'15] and [GKKP17, STOC'17]. 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]; the ultimate goal is to maintain a set cover under insertions and deletions of elements, with optimal bounds on both the approximation factor and the update time.

Most previous works considers the low-frequency regime, namely f = O(log n), and this line of work has culminated with a deterministic (1 + ϵ)f -approximation algorithm with amortized update time O( f 2 ϵ 3 + f ϵ 2 log C) [BHNW, SODA'21] and a randomized f -approximation algorithm against an oblivious adversary with expected amortized update time O(f 2 ) for the unweighted case [AS, ESA'21]. In the high-frequency regime of f = Ω(log n), an O(log n)-approximation algorithm with amortized update time O(f log n) was given by [GKKP17, STOC'17], and recently [SU, STOC'23] showed that the same update time of O(f log n) suffices for achieving approximation (1 + ϵ) ln n.

Interestingly, at the intersection of the two regimes, i.e., f = Θ(log n), the state-of-the-art results coincide (ignoring the dependencies on ϵ and C): approximation Θ(f ) = Θ(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 ), even allowing randomization against an oblivious adversary and even for a worse approximation guarantee.

In this paper we break the Ω(f 2 ) update time barrier via the following results: