In the dynamic set cover (SC) problem, the input is a dynamic universe of at most n elements and a fixed collection of m sets, where each element belongs to at most f sets and each set has a cost in [1/C,1]. The objective is to efficiently maintain an approximate minimum SC under element updates. Efficiency is primarily measured by the update time, but another important parameter is the recourse (the number of changes to solution per update). Ideally, one would like to achieve low worst-case bounds on both update time and recourse. One can achieve an approximation of (1+ε)ln n (greedy-based) or (1+ε)f (primal–dual-based) with worst-case update time O(f log n) (ignoring ε-dependencies). However, despite a large body of work, no algorithm with low update time (even amortized) and nontrivial worst-case recourse is known even for unweighted instances (C = 1)! We remedy this by providing a transformation that, given a SC algorithm with approximation α and update time T as a black-box, returns a set cover algorithm with approximation (2 + ε)α, update time O(T + α C) and worst-case recourse O(α C). Our main results are obtained by leveraging this transformation for constant C: - For f = O(log n), applying the transformation on the best primal-dual-based algorithm yields worst-case recourse O(f). For constant f (e.g., vertex cover), we get near-optimal bounds on all parameters. - For f = Ω(log n), applying the transformation on the best greedy-based algorithm yields worst-case recourse O(log n). As our main technical contribution, we show that by opening the black box and exploiting a certain robustness property of the greedy-based algorithm, the worst-case recourse can be reduced to O(1), without sacrificing the other parameters, yielding a ((2 + ε) ln n)-approximation with worst-case update time O(flog n) and O(1) worst-case recourse.

In their breakthrough ICALP’15 paper, Bernstein and Stein presented an algorithm for maintaining a \((3/2+\epsilon)\) -approximate maximum matching in fully dynamic bipartite graphs with a worst-case update time of \(O_{\epsilon}(m^{1/4})\) ; we use the \(O_{\epsilon}\) notation to suppress the \(\epsilon\) -dependence. Their main technical contribution was in presenting a new type of bounded-degree subgraph, which they named an edge degree constrained subgraph (EDCS) , which contains a large matching—of size that is smaller than the maximum matching size of the entire graph by at most a \(3/2+\epsilon\) factor. They demonstrate that the EDCS can be maintained with a worst-case update time of \(O_{\epsilon}(m^{1/4})\) , and their main result follows as a direct corollary. In their followup SODA’16 paper, Bernstein and Stein generalized their result for general graphs, achieving the same update time of \(O_{\epsilon}(m^{1/4})\) , albeit with an amortized rather than worst-case bound. To date, the best deterministic worst-case update time bound for any better-than-2 approximate matching is \(O(\sqrt{m})\) [Neiman and Solomon, STOC’13] and [Gupta and Peng, FOCS’13]; allowing randomization (against an oblivious adversary) one can achieve a much better (still polynomial) update time for approximation slightly below 2 [Behnezhad et al., SODA’20]. In this work we ( quasi nanos, gigantium humeris insidentes ) simplify the approach of Bernstein and Stein for bipartite graphs, which allows us to generalize it to general graphs while maintaining the same \(O_{\epsilon}(m^{1/4})\) bound on the worst-case update time. Moreover, our approach is density-sensitive : If the arboricity of the dynamic graph is always bounded by \(\alpha\) , then the worst-case update time of the algorithm is \(O_{\epsilon}(\sqrt{\alpha})\) .

The dynamic set cover problem has been subject to growing research attention in recent years. In this problem, we are given as input a dynamic universe of at most$n$elements and a fixed collection of$m$sets, where each element appears in a most$f$sets and the cost of each set is in [1/C, 1], and the goal is to efficiently maintain an approximate minimum set cover under element updates. Two algorithms that dynamize the classic greedy algorithm are known, providing$O(\log n)$and$((1+\epsilon)\ln n)$-approximation with amortized update times$O(f \log n)$and,$O(\frac{f \log n}{\epsilon})$, respectively [GKKP (STOC'17); SU (STOC'23)]. The question of whether one can get approximation$O(\log n)$(or even worse) with low worst-case update time has remained open — only the naive$O(f\cdot n)$time bound is known, even for unweighted instances. In this work we devise the first amortized greedy algorithm that is amenable to an efficient deamortization, and also develop a lossless deamortization approach suitable for the set cover problem, the combination of which yields a$((1+\epsilon)\ln n){-}$approximation algorithm with a worst-case update time of$O(\frac{f \log n}{\epsilon^{2}})$. Our worst-case time bound — the first to break the naive$O(f\cdot n)$bound — matches the previous best amortized bound, and actually improves its$\epsilon$-dependence. Further, to demonstrate the applicability of our deamortization approach, we employ it, in conjunction with the primal-dual amortized algorithm of [BHN (FOCS'19)], to obtain a$((1+\epsilon)f)$-approximation algorithm with a worst-case update time of$O(\frac{f \log n}{\epsilon^{2}})$, improving over the previous best bound of$O(\frac{f \cdot \log ^{2}(C n)}{-3})\ [$BHNW (SODA'21)]. Finally, as direct implications of our results for set cover, we (i) achieve the first nontrivial worst-case update time for the dominating set problem, and (ii) improve the state-of-the-art worst-case update time for the vertex cover problem.

The minimum set cover (MSC) problem admits two classic algorithms: a greedy lnn-approximation and a primal-dual f-approximation, where n is the universe size and f is the maximum frequency of an element. Both algorithms are simple and efficient, and remarkably — one cannot improve these approximations under hardness results by more than a factor of (1+є), for any constant є > 0.