We give the first algorithms for fully dynamic set cover with non-trivial worst-case guarantees for both recourse and update time. Specifically, we achieve O(logn) recourse and f· log(n) update time in the worst-case, for both approximation regimes: O(logn) and O(f) approximation. Prior to our work, all results for this problem either settled for amortized bounds on recourse and update time, or obtained f· log(n) update time in the worst-case but at the cost of Ω(m) worst-case recourse. (Here, m, n, f respectively denote the number of sets, maximum number of elements, and maximum frequency.)

We give an algorithm for finding the arboricity of a weighted, undirected graph, defined as the minimum number of spanning forests that cover all edges of the graph, in $\sqrt{n} m^{1+o(1)}$ time. This improves on the previous best bound of $\tilde{O}(nm)$ for weighted graphs and $\tilde{O}\left(\mathrm{~m}^{3/2}\right)$ for unweighted graphs (Gabow 1995) for this problem. The running time of our algorithm is dominated by a logarithmic number of calls to a directed global minimum cut subroutine – if the running time of the latter problem improves to $m^{1+o(1)}$ (thereby matching the running time of maximum flow), the running time of our arboricity algorithm would improve further to $m^{1+o(1)}$. We also give a new algorithm for computing the entire cut hierarchy – laminar multiway cuts with minimum cut ratio in recursively defined induced subgraphs – in $m n^{1+o(1)}$ time. The cut hierarchy yields the ideal edge loads (Thorup 2001) in a fractional spanning tree packing of the graph which, we show, also corresponds to a max-entropy solution in the spanning tree polytope. For the cut hierarchy problem, the previous best bound was $\tilde{O}\left(n^{2} m\right)$ for weighted graphs and $\tilde{O}\left(n m^{3/2}\right)$ for unweighted graphs.

Karger (STOC 1995) gave the first FPTAS for the network (un)reliability problem, setting in motion research over the next three decades that obtained increasingly faster running times, eventually leading to a Õ(n2)-time algorithm (Karger, STOC 2020). This represented a natural culmination of this line of work because the algorithmic techniques used can enumerate Θ(n2) (near)-minimum cuts. In this paper, we go beyond this quadratic barrier and obtain a faster FPTAS for the network unreliability problem. Our algorithm runs in m1+o(1) + Õ)(n1.5) time.

The hypergraph unreliability problem asks for the probability that a hypergraph gets disconnected when every hyperedge fails independently with a given probability. For graphs, the unreliability problem has been studied over many decades, and multiple fully polynomial-time approximation schemes are known starting with the work of Karger (STOC 1995). In contrast, prior to this work, no non-trivial result was known for hypergraphs (of arbitrary rank). In this paper, we give quasi-polynomial time approximation schemes for the hypergraph unreliability problem. For any fixed ε ∈ (0, 1), we first give a (1+ε)-approximation algorithm that runs in mO(logn) time on an m-hyperedge, n-vertex hypergraph. Then, we improve the running time to m· nO(log2 n) with an additional exponentially small additive term in the approximation.

We give an almost-linear time algorithm for the Steiner connectivity augmentation problem: given an undirected graph, find a smallest (or minimum weight) set of edges whose addition makes a given set of terminals τ-connected (for any given τ > 0). The running time of our algorithm is dominated by polylogarithmic calls to any maximum flow subroutine; using the recent almost-linear time maximum flow algorithm (Chen et al., FOCS 2022), we get an almost-linear running time for our algorithm as well. This is tight up to the polylogarithmic factor even for just two terminals. Prior to our work, an almost-linear (in fact, near-linear) running time was known only for the special case of global connectivity augmentation, i.e., when all vertices are terminals (Cen et al., STOC 2022). We also extend our algorithm to the closely related Steiner splitting-off problem, where the edges incident on a vertex have to be split-off while maintaining the (Steiner) connectivity of a given set of terminals. Prior to our work, a nearly-linear time algorithm was known only for the special case of global connectivity (Cen et al., STOC 2022). The only known generalization beyond global connectivity was to preserve all pairwise connectivities using a much slower algorithm that makes n calls to an all-pairs maximum flow (or Gomory-Hu tree) subroutine (Lau and Yung, SICOMP 2013), as against polylog(n) calls to a (single-pair) maximum flow subroutine in this work. * Ruoxu Cen and Debmalya Panigrahi were supported in part by NSF grants CCF-1750140 (CAREER Award) and CCF-1955703.

We give an algorithm for augmenting the edge connectivity of an undirected graph by using the isolating cuts framework (Li and Panigrahi, FOCS ‘20). Our algorithm uses poly-logarithmic calls to any max-flow algorithm, which yields a running time of Õ(m + n3/2) and improves on the previous best time of Õ(n2) (Benczúr and Karger, SODA ‘98) for this problem. We also obtain an identical improvement in the running time of the closely related edge splitting off problem in undirected graphs.

We give an Õ(m)-time algorithm for the edge connectivity augmentation problem and the closely related edge splitting-off problem. This is optimal up to lower order terms and closes the long line of work on these problems.

We give an algorithm to find a minimum cut in an edge-weighted directed graph with$n$vertices and$m$edges in$\tilde{O}(n\cdot\max\{m^{2/3},\ n\})$time. This improves on the 30 year old bound of$\tilde{O}(nm)$obtained by Hao and Orlin for this problem. Using similar techniques, we also obtain$\tilde{O}(n^{2}/\epsilon^{2})$-time$(1+{\epsilon})$-approximation algorithms for both the minimum edge and minimum vertex cuts in directed graphs, for any fixed$\epsilon$. Before our work, no (1 +$\epsilon)$-approximation algorithm better than the exact runtime of$\tilde{O}(nm)$is known for either problem. Our algorithms follow a two-step template. In the first step, we employ a partial sparsification of the input graph to preserve a critical subset of cut values approximately. In the second step, we design algorithms to find the (edge/vertex) mincut among the preserved cuts from the first step. For edge mincut, we give a new reduction to$\tilde{O}(\min\{{n}/m^{1/3}, \sqrt{n}\}){-}$calls of any maxflow subroutine, via packing arborescences in the sparsifier. For vertex mincut, we develop new local flow algorithms to identify small unbalanced cuts in the sparsified graph.

In this paper, we consider the problem of designing cut sparsifiers and sketches for directed graphs. To bypass known lower bounds, we allow the sparsifier/sketch to depend on the balance of the input graph, which smoothly interpolates between undirected and directed graphs. We give nearly matching upper and lower bounds for both for-all (cf. Benczúr and Karger, STOC 1996) and for-each (Andoni et al., ITCS 2016) cut sparsifiers/sketches as a function of cut balance, defined the maximum ratio of the cut value in the two directions of a directed graph (Ene et al., STOC 2016). We also show an interesting application of digraph sparsification via cut balance by using it to give a very short proof of a celebrated maximum flow result of Karger and Levine (STOC 2002).

A roundtrip spanner of a directed graph G is a subgraph of G preserving roundtrip distances approximately for all pairs of vertices. Despite extensive research, there is still a small stretch gap between roundtrip spanners in directed graphs and undirected graphs. For a directed graph with real edge weights in [1,W], we first propose a new deterministic algorithm that constructs a roundtrip spanner with (2k-1) stretch and O(k n^(1+1/k) log (nW)) edges for every integer k > 1, then remove the dependence of size on W to give a roundtrip spanner with (2k-1) stretch and O(k n^(1+1/k) log n) edges. While keeping the edge size small, our result improves the previous 2k+ε stretch roundtrip spanners in directed graphs [Roditty, Thorup, Zwick'02; Zhu, Lam'18], and almost matches the undirected (2k-1)-spanner with O(n^(1+1/k)) edges [Althöfer et al. '93] when k is a constant, which is optimal under Erdös conjecture.