CS Paper Radar

Dynamic Connectivity, Minimum Spanning Tree, and 2-Edge Connectivity with Polylogarithmic Worst-Case Update Time

Simon Meierhans, Maximilian Probst Gutenberg, Yu-Cheng Yeh

cs.DS ·submitted 2026-09-30 18:00 UTC · v1
top venue

Abstract

We give fully dynamic algorithms for maintaining connectivity, minimum spanning tree, and $2$-edge connectivity of a graph with worst-case polylogarithmic update time. Our algorithms are randomized and succeed with high probability against an adaptive adversary. For the minimum spanning tree and $2$-edge connectivity problems, this improves over the subpolynomial update time bounds obtained by Nanongkai, Saranurak, and Wulff-Nilsen [FOCS'17], Jin and Sun [FOCS'21], and Jin, Sun, and Thorup [SODA'24], respectively. The only randomized component of our algorithms is the computation of static expander decompositions, and a deterministic algorithm for said problem would directly imply deterministic algorithms for all three problems. This reduction is novel even for the connectivity problem.

Comment
To appear in FOCS 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Dynamic Steiner Tree under Edge Updates

cs.DS ·2026-11-03 ·Jeff Giliberti, MohammadTaghi Hajiaghayi, Mohammad Mahdavi, Xinchen Yang
hot direction similarity 0.73
Abstract

The Steiner tree problem is the canonical generalization of minimum spanning tree (MST). When connectivity is required only among a fixed subset of vertices (terminals), the goal is to maintain a minimum-cost tree connecting these terminals as the graph undergoes edge updates. While dynamic MST has been studied since the 1980s~[Frederickson, STOC'83, SICOMP'85], and the first sublinear-in-$n$ dynamic MST algorithm dates back almost thirty-five years to Eppstein, Galil, Italiano, and Nissenzweig~[FOCS'92, JACM'97], achieving sublinear-in-$n$ update time for dynamic Steiner tree has long remained open, as a single edge update can invalidate many routes in the underlying terminal metric closure. We present the first fully dynamic algorithm for Steiner tree that achieves a constant-factor approximation with sublinear-in-$n$ update time. For any fixed $0<ζ<1/2$, our deterministic algorithm maintains an $O_ζ(1)$-approximate Steiner tree for undirected graphs with polynomially bounded edge weights in $\widetilde O(n^{1/2+ζ})$ amortized update time, answering cost queries in $O(1)$ time, and reporting an explicit tree in $\widetilde O(n^{1+ζ})$ time. Our approach combines periodic terminal-metric rebuilds on a dynamic spanner with a top-tree dynamic program that localizes edge deletions and reconnects surviving components through a dynamic distance sparsifier. Along the way, we give a simpler randomized insertion-only algorithm with a better, explicit approximation ratio.

0.25

Incremental Exact Vertex Connectivity

cs.DS ·2026-10-15 ·Felix Adena, Monika Henzinger, Christoph Kern, Daniel Rutschmann
top venuetheory similarity 0.72
Abstract · To appear at SODA 2027. Added missing literature

We study the problem of maintaining the vertex connectivity $κ$ of a graph under edge insertions. For undirected graphs, our algorithm uses $O(κ^4 \log^2 n)$ amortized time per edge insertion. After each edge insertion, the algorithm outputs the current value of $κ$, plus a set of $κ$ vertices whose removal disconnects the graph. Our algorithm is Monte-Carlo randomized and works with a randomness-adaptive adversary. The algorithm also works on directed graphs against an oblivious adversary, which is equivalent to an output-adaptive adversary if we only have to output the current value of $κ$. Previously, algorithms using SPQR trees could maintain the vertex connectivity in undirected graphs with $O(\log n)$ time per edge insertion for $κ\le 3$, but no algorithm with $o(n)$ time per edge insertion was known for $κ\ge 4$. Moreover, for $κ\ge 4$, on general directed graphs or sparse undirected graphs, no algorithm faster than recomputation from scratch was known. We complement our algorithm with a conditional lower bound: Under the OMv conjecture, any insertions-only algorithm that outputs the current value of $κ$ after every insertion needs $Ω(n^{1-\varepsilon})$ amortized time per edge insertion for $κ= Θ(n)$. Previous conditional lower bounds for this problem only apply to worst case running time, or algorithms that support both edge insertions and edge deletions.

0.65

Approximating Minimum Spanning Trees in Metrics under Semi-Random Corruptions

cs.DS ·2026-10-29 ·Aditya Anand, Anupam Gupta, Rajesh Jayaram, Euiwoong Lee, Ali Vakilian
publishedhot direction similarity 0.70
Abstract · SODA 2027

We study the problem of finding minimum spanning trees in semi-random corrupted metrics. In this problem proposed by Bateni, Dharangutte, Jayaram, and Wang (COLT'24), we start with a metric space $\mathcal{M} = (X, d)$. The adversary independently corrupts each pairwise distance with probability $p$. The algorithm only observes these possibly corrupted distances and must output a spanning tree whose expected cost (in the true metric) is multiplicatively close to the minimum spanning tree cost. Prior work showed that losing a factor of $Ω(\log n)$ is necessary, even if the algorithm may adaptively select $O(n/\log n)$ points and probe the true distances between them. However, no upper bounds were known. We study three regimes based on whether the adversary can only increase, decrease, or arbitrarily change the corrupted distances. We show the following: (1) In the increase-only setting, we give a polynomial-time $O(1)$-approximation algorithm for any constant $0 \le p < 1$. (2) In the decrease-only setting, we give an $O(\log n)$-approximation algorithm for any constant $0 \le p < 1$. Additionally, we show an $O(\log^4 n)$-approximation algorithm that runs in quasi-polynomial time $n^{O(\log n)}$, for any constant $p \leq 0.1$. Moreover, we show that a polynomial-time algorithm computing an $n^{1/3-\varepsilon}$-approximation is unlikely to exist. (3) In the general setting, where the adversary can both increase and decrease distances, we show an $O(\log n)$-approximation algorithm for every $0 \leq p < \frac{1}{4}$. Further, we show that no $o(n)$-approximation is possible for $\frac{1}{2} \leq p < 1$. Our algorithms answer the main open question in Bateni et al.'s work; moreover, the $O(\log n)$-approximations in the latter two settings are information-theoretically optimal.

0.35

Faster Dynamic Maximal Independent Set against Adaptive Adversaries

cs.DS ·2026-11-04 ·Hongyi Chen, Shuyan Fan, Tianyi Zhang
similarity 0.70
Abstract

We study the fully dynamic maximal independent set (MIS) problem: maintaining an MIS in an undirected graph on $n$ vertices with at most $m$ edges under edge insertions and deletions. Against an oblivious adversary, which fixes the edge update sequence in advance, the randomized algorithms of Behnezhad et al. (2019) and Chechik and Zhang (2019) achieve polylogarithmic update time. Against an adaptive adversary, which may choose each update after observing the previously reported MISs, the best previously known update bound was $O(m^{2/3})$, given by the deterministic algorithm of Gupta and Khan (2018, 2021). Assuming the combinatorial Boolean matrix multiplication hypothesis, Bernstein et al. (2026) proved that any combinatorial algorithm against an adaptive adversary requires at least $m^{1/2-o(1)}$ update time even under edge insertions alone, leaving a polynomial gap between upper and lower bounds. We present a randomized fully dynamic MIS algorithm with $\widetilde O(m^{5/8})=\widetilde O(m^{2/3-1/24})$ update time against adaptive adversaries. This gives the first polynomial improvement over the $m^{2/3}$ bound for adaptive fully dynamic MIS.

0.20

Polynomial Lower Bounds for Distributed Graph Sketching with Tiny Error: Connectivity and Spanning Tree Construction

cs.DS cs.DC ·2026-09-05 ·Peter Robinson, Ming Ming Tan
theory similarity 0.70
Abstract

We present the first polynomial lower bounds for several fundamental problems in the distributed graph sketching model in the tiny-error regime, which includes deterministic algorithms as a special case. In the graph sketching model, every node sends a single message to the referee who does not have any prior knowledge of the graph and must output the answer. While the work of Nelson and Yu (SODA 2019) and Yu (SODA 2021) showed that $Θ( \log^3n )$ is optimal for constructing a spanning forest or deciding whether the graph is connected with error at most $\frac{1}{\text{poly}(n)}$ , their approach does not yield any stronger bounds for significantly smaller error probabilities. Our main result is to show that solving either connectivity or spanning tree construction with error at most $δ$ requires messages of length $Ω( \min\{n, \log_2 \frac{1}δ\}^{1/3} )$, which implies that algorithms with exponentially small error must send messages of $Ω( n^{1/3} )$ bits in the worst case. Our results significantly narrows the current gap between the Jelani-Yu threshold of $Θ( \log^3n )$ and the trivial upper bound of sending $O(n)$ bits per node for deterministic graph sketching. We also extend our results to $k$-edge connectivity. For any $k=O(n^{1/7})$, we recover the same bound of $Ω( k )$ on the message length for algorithms with exponentially small error that was shown by Robinson and Tan (PODS 2026) only for deterministic algorithms. Finally, for $k=n^{o(1)}$, our result implies a stronger lower bound of $Ω_ε( n^ε )$ bits, for any constant $ε<\tfrac{1}{3}$.

0.09

Deterministic Incremental Triconnectivity in $O(\log^2 n)$ Worst-Case Time

cs.DS ·2026-10-23 ·Niels Inselmann Christiansen, Eva Rotenberg
similarity 0.69
Abstract

We consider the problem of maintaining the triconnectivity in a graph $G$ in the incremental dynamic setting. We consider updates in the form of edge insertions and edge subdivisions, and triconnectivity queries, i.e. queries that take as input variables the vertices $a$ and $b$ and are of the form ''are there at least three vertex disjoint paths between $a$ and $b$?''. All algorithms presented in this paper are deterministic. When starting from a biconnected graph, all updates take worst-case $O(\log n)$ time, and all queries are answered in $O(\log n)$ time. By combining this result for biconnected graphs with a result of Holm and Rotenberg [SODA'20] we get a deterministic algorithm for general graphs with a worst-case update and query time of $O(\log^2 n)$. Both algorithms represent an improvement of the state-of-the-art by a factor of $O(\log n)$.

0.22

Optimal Online Weighted Connectivity Augmentation

cs.DS ·2026-10-30 ·Mohit Garg, Felix Hommelsheim, Alexander Lindermayr
theory similarity 0.68
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

Parallel Spanning Forest and Biconnectivity for Well-Connected Graph in Sub-Logarithmic Time

cs.DS ·2026-11-11 ·Bojun Liu, S. Cliff Liu, Shuaibo Yang
theory similarity 0.68
Abstract

We give a randomized ARBITRARY CRCW PRAM algorithm for computing a spanning forest of an \(n\)-vertex, \(m\)-edge graph. Let \(d\) be the maximum component diameter. With good probability, the algorithm runs in \(O(\log d+\log\log n)\) time using \(O(m+n)\) processors and outputs a rooted spanning forest of original edges with maximum depth \(2^{O(\log d+\log\log n)}\). For finding bridges, our algorithm identifies every bridge edge in \(O(\log d+\log\log n)\) time. For biconnectivity, it outputs all blocks in \(O(\log d+\log d'+\log\log n)\) time, where \(d'\) is the bi-diameter. All these problems are fundamental in graph algorithms with numerous applications. Our results improve the best previous time bounds parameterized by the number of vertices and diameter. Finally, we prove deterministic \(Ω(\log n/\log\log n)\) lower bounds for outputting a DFS Sequence, a weighted spanning forest, and an ear decomposition.

0.13