CS Paper Radar

Optimal-Size Strong Connectivity Preservers under Two Edge Failures in Subcubic Time

Wanhee Lee, Chenglin Fan

cs.DS ·submitted 2026-11-12 05:18 UTC · v1
theory

Abstract

A $k$-edge-failure strong connectivity preserver of a directed graph on $N$ vertices is a spanning subgraph that has the same strongly connected components as the input after each set of at most $k$ edge deletions. The lower-bound construction of Baswana, Choudhary, and Roditty [BCR18], adapted to strong connectivity in [CC20], gives the previous best bound of $Ω(2^kN)$ necessary edges. Hoppenworth, Saranurak, and Wang [HSW25] prove an $O(k4^kN\log N)$ upper bound, leaving a logarithmic gap for fixed $k$. We close this gap by giving an explicit strongly connected graph on $N=2^d$ vertices with $N-1+(N/2)\log_2N$ edges, every one of which is necessary in a two-failure preserver. Together with the upper bound of [HSW25], this proves that the optimal size in the worst case is $Θ_k(N\log N)$ for every fixed $k\geq2$, whereas it is $Θ(N)$ for $k=1$ [GIP20]. The same graph has a one-failure preserver with at most $3(N-1)$ edges. We also give a randomized algorithm that either returns a spanning subgraph or reports failure. For every fixed $c,\varepsilon>0$, with probability at least $1-N^{-c}$ it returns a correct preserver for $k=2$ with $O(N\log N)$ edges, in $\widetilde O(N^{(ω+3)/2+\varepsilon})$ time and $\widetilde O(N^2)$ space. Here $ω$ is the matrix multiplication exponent over a fixed finite field.

Comment
43 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Strong Connectivity Oracle for Multiple Failures via Rooted Flow-Augmentation

cs.DS ·2026-11-06 ·Aditya Anand, Thatchaphol Saranurak, Benyu Wang
published similarity 0.67
Abstract · SODA 2027

We present a significantly improved $k$-fault-tolerant strong connectivity oracle, one of the most basic data structures on a directed graph $G$ that, given any set $F$ of failed edges of size $|F|\le k$, answers whether $G \setminus F$ is strongly connected. For every constant $k$, our oracle only uses $n^{1+o(1)}$ space and $n^{o(1)}$ query time. No prior result can achieve $o(n^{2})$ space and $o(n)$ query time, \emph{even when $k=2$}. Previous oracles either require $Ω(n)$ query time [BCR18], or $Ω(n^2)$ space [vdBS19]. Our main technical contribution is a \emph{rooted} version of the highly successful flow augmentation technique, which may be of independent interest. Given a directed graph $G$, an integer $k$, and a source vertex $s$, we can sample a set of edges $A$ such that each minimal $s$-rooted cut of size at most $k$ becomes an $s$-rooted min-cut in $G + A$ with probability $2^{-poly(k)}n^{-o(1)}$.

0.57

Online Survivable Network Design with Arbitrarily Small Connectivity Loss

cs.DS ·2026-11-12 ·MohammadTaghi Hajiaghayi, Saeed Seddighin
similarity 0.66
Abstract

In the online survivable network design problem, a graph with edge costs is known in advance, and requests arrive one at a time. Each request is a pair of vertices $(s,t)$ with a connectivity requirement $k$, and the algorithm must irrevocably buy edges so that $s$ and $t$ are joined by $k$ edge-disjoint paths. The goal is to keep the total cost close to that of an optimal offline solution. Gupta, Krishnaswamy, and Ravi~\cite{GKR12} obtain an $O(k\log^3 n)$-competitive algorithm, where $k$ is the maximum requirement, without relaxing the connectivity requirement. Dehghani, Ehsani, Hajiaghayi, Liaghat, and Seddighin~\cite{DEHLS18} obtain a polylogarithmic competitive ratio when the connectivity requirement is allowed to be relaxed by a factor of $2+\varepsilon$. We show that relaxing the connectivity requirement by a factor of only $1+\varepsilon$ suffices to obtain a polylogarithmic competitive ratio.

0.19

Faster Minimum k-Cut I: Simple and Sparse Weighted Graphs

cs.DS ·2026-08-17 ·Jason Li, Trevor Vaughn
similarity 0.66
Abstract

The minimum $k$-cut problem asks for the fewest edges whose removal leaves an input graph with at least $k$ connected components. Previously, the best algorithm for simple graphs ran in $O_k(n^{(1-\varepsilon)k+O(1)})$ time~\cite{HL22}, showing that the \(n^k\) barrier can be broken up to a polynomial overhead. We give the first $\widetilde O_k(n^{ck})$-time algorithm for Minimum $k$-Cut on simple graphs for an absolute constant $c<1$. More precisely, the running times are $\widetilde O(n^2)$ for $k=3$, $\widetilde O(n^{55/19})$ for $k=4$, and $\widetilde O(n^{4.112007})$ for $k=5$; for every $k\ge6$, the running time is \[ k^{O(k^2)}n^{1+(6k-6)\frac{k-1.749614}{7k-10}}(\log n)^{O(k^2)}, \] whose exponent is $\frac67k-0.132\ldots+O(1/k)$. The algorithm combines three ingredients. First, for weighted Minimum $k$-Cut we give a randomized \[ k^{O(k^2)}n^{k-2}(m+n)\log^3(n) \] -time algorithm: it perturbs the edge weights so that any minimum $k$-cut has a side with boundary strictly smaller than average. These then cut few edges of some tree in a logarithmic-size sample from a tree packing with high probability. After we enumerate them, we recursively compute $(k-1)$-cuts to complete them to the $k$-cuts of which they were a part. A variant of the perturbation and processing the entire packing support give a deterministic $k^{O(k^2)}n^{k+O(1)}$-time variant. Second, for cut size $s$, we give an improved FPT algorithm using a near-linear-time construction of an $(O(s\log^2 n\log\log n),s)$ edge-unbreakable tree decomposition with $O(s\log^2 n\log\log n)$ adhesion; this also gives a near-linear-time approximation algorithm for Minimum $k$-Cut. Third, we refine the border/island framework of~\cite{HL22}, using rectangular matrix multiplication to recover singleton islands and balancing it against the improved FPT algorithm.

0.36

An $O(k\log(n/k))$ Bound on Spanning Bipartite Connectivity

cs.DM math.CO ·2026-09-20 ·G. Gutin, Y. Hao, Y. Zhou
theory similarity 0.65
Abstract · All proofs were written by the authors without the assistance of AI. However, GPT-6 Astra was used to check the correctness of our proofs, a…

For integers $1\le k\le n/2$, let $f(k,n)$ be the least integer $s$ such that every $s$-connected graph on $n$ vertices contains a spanning bipartite $k$-connected subgraph. Thomassen conjectured that $f(k,n)$ is bounded by a function of $k$ alone. Delcourt and Ferber proved $f(k,n)=O(k^3\log n)$, and Yuster subsequently obtained $f(k,n)\le22k^2\log_2 n$. We prove that, for $2\le k\le n/2$, \[ f(k,n)\le\min\left\{n-1,\, \left\lfloor6(k-1)\log_2\frac{n}{k-1}\right\rfloor\right\}. \] In particular, $f(k,n)=O(k\log(n/k))$.

0.32

Optimal Online Weighted Connectivity Augmentation

cs.DS ·2026-10-30 ·Mohit Garg, Felix Hommelsheim, Alexander Lindermayr
theory similarity 0.65
Abstract · 32 pages, 12 figures

In the online Weighted Connectivity Augmentation Problem (WCAP), we are given a $k$-edge-connected graph on $n$ vertices and a set of additional edges, called links, with nonnegative costs. Pairs of vertices arrive one by one, and an online algorithm must immediately and irrevocably buy links so that each pair becomes $(k+1)$-edge-connected. The goal is to minimize the total cost of the purchased links. We obtain a deterministic polynomial-time $O(\log n)$-competitive algorithm for WCAP, improving the previous $O(\log^2 n)$ bound (SODA 2026). Our bound is asymptotically optimal, even for randomized algorithms in the random-order model. The general problem reduces to the case where the underlying graph is a cycle, for which link costs in $\{0,1\}$ already yield an $Ω(\log n)$ lower bound. Surprisingly, for unit costs on a cycle, we obtain a deterministic polynomial-time $4$-competitive algorithm, improving the previous $O(\log n)$ bound (SODA 2026), and prove that this ratio is optimal among deterministic algorithms. Thus, with unit costs, cycles are easier than trees, where the optimal competitive ratio is $Θ(\log n)$.

0.25

Connectivity Oracles Under Vertex Failures via a Simple and Fast Low-Degree Steiner Forest Decomposition

cs.DS ·2026-09-02 ·Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak, Haoze Wang
theory similarity 0.64
Abstract

We study the low-degree Steiner forest decomposition. Given a graph $G=(V,E)$ and a terminal set $U\subseteq V$, the standard decomposition returns a set $X\subseteq V$ of size at most $|U|/2$ and a forest $T\subseteq G-X$ of maximum degree $Δ$ such that, for every connected component $C$ of $G-X$, some connected component of $T$ contains all terminals in $U\cap V(C)$. This is the central decomposition behind several connectivity oracles under vertex failures [DP20, LS22, LW24]. The state-of-the-art algorithms either take $O(mn\log n)$ time with degree bound $4$ [DP20], or take $m^{1+o(1)}$ time with the weaker degree bound $O(\log^{2}n)$ [LW24]. We show that if $T$ is allowed to contain vertices of $X$, then a degree-$4$ decomposition can be computed by a very simple algorithm in $O(mα(n))$ time. Further, we show that this relaxed decomposition is equally useful for constructing connectivity oracles under vertex failures. As a consequence, we obtain a deterministic connectivity oracle under $d$ vertex failures with $\tilde{O}(m)$ space, $\tilde{O}(md_\star)$ preprocessing time ($d_\star$ is an upper bound on the number of failed vertices), $\tilde{O}(d^{2})$ update time, and $O(d)$ query time. Up to polylogarithmic factors, this oracle strictly improves all known oracles; in particular, it removes the $n^{o(1)}$ factors from the preprocessing and update times of [LS22, LW24].

0.24

Sharp bounds and extremal structure of minimally strongly $k$-connected digraphs

cs.DM math.CO ·2026-10-10 ·Junran Yu, Gregory Gutin, Hong-Jian Lai, Xiaoyan Zhang
theory similarity 0.64
Abstract

Let $D$ be a finite simple minimally strongly $k$-connected digraph, where $k\ge 2$, and let $n=|V(D)|$. Mader proved in 1985 that $|A(D)|\le 2k(n-k)$ for all sufficiently large $n$, with equality if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$ (JCTB 1985). We prove that this bound holds whenever $n\ge 3k-1$ and that the order threshold $3k-1$ is best possible. Moreover, if $n\ge 3k$, then equality holds if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$. The threshold $3k$ is also best possible. These results resolve the conjecture of Mader in (JCTB 1985).

0.21

Settling Nondeterministic Communication Complexity of Graph Connectivity

cs.CC ·2026-10-23 ·Zhijun Zhang
publishedtheory similarity 0.64
Abstract

Determining the communication complexity of graph connectivity has been one of the longest standing open problems in communication complexity since the seminal work of Babai, Frankl, and Simon [FOCS'86]. A simple protocol transmits a spanning forest using $O(N\log N)$ communication on $N$-vertex graphs. While this was shown optimal for deterministic protocols by Hajnal, Maass, and Turán [STOC'88], the optimal nondeterministic and randomized complexities have remained unresolved for decades. We settle the nondeterministic communication complexity of graph connectivity by proving an optimal $Ω(N\log N)$ lower bound. The best prior bound was $Ω(N\log\log N)$ due to Raz and Spieker [Combinatorica'95]. Our bound is shown by upper bounding the maximum size of $1$-monochromatic rectangles. Generalizing our techniques to weighted, almost $1$-monochromatic rectangles yields an $Ω(N \cdot \log(\min(1/\varepsilon,N)))$ lower bound for randomized protocols with error probability $\varepsilon$. In particular, this bound is optimal for any polynomially small $\varepsilon$. For constant error probability, we also prove that any $r$-round protocol requires $Ω(N/r \cdot \log N)$ communication, which is optimal for every constant $r$. Previously, optimal $Ω(N\log N)$ lower bounds for graph connectivity were known only for $1$-round [Sun, Woodruff; APPROX/RANDOM'15] and $2$-round protocols [Radhakrishnan, Reddy, Venkat; ITCS'26]. Our proof introduces a new communication problem which can be viewed as a composition of inner product and pointer chasing problems. Our lower bounds can be extended to other fundamental graph properties, and also imply optimality of known query and streaming algorithms for related problems.

0.31