CS Paper Radar

Incremental Minimum Spanning Trees on a Napkin

Lucian Bicsi, Adrian Budău

cs.DS ·submitted 2026-11-03 22:39 UTC · v1

Abstract

In the incremental minimum spanning forest problem, weighted edges arrive one at a time. After each insertion we must report the edge that leaves the minimum spanning forest, and queries ask for the bottleneck distance of two vertices: the smallest possible maximum edge cost on a path between them. Link-cut trees solve both in $O(\log n)$ amortized time. In 2021 we wrote the folklore BottleneckTree, a short competitive-programming structure that stores one parent pointer and one cost per vertex, and conjectured that it also runs in $O(\log n)$ amortized time. We show that this conjecture is false: on a family of inputs, its amortized cost per operation is $Ω(\sqrt{n})$. We then present a structure with the same state, two arrays and a single loop, and prove that it runs in $O(\log n)$ amortized time per insertion and per query. Unlike the AM-tree of Ding, Gu and Sun, which attains the same bound, it stores no subtree sizes and maintains no balance invariant. For a connected graph with distinct costs, the structure can be viewed as an implicit link-cut tree on the Kruskal reconstruction tree: each rotation corresponds to exactly one preferred-child change, and each skip acts on a stale path-parent pointer. In experiments it is 1.3-2.1 times faster than the folklore BottleneckTree on insertions, up to 480 times faster on its adversarial input, and 6.3-16 times faster than an explicit link-cut tree.

Comment
20 pages, 5 figures, 3 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Two $(2+ε)$-Approximation Algorithms for Minimum Spanning Tree Interdiction

cs.DS ·2026-11-18 ·Junjie Luo, Changjun Wang, Chenhao Wang, Wei Yu
similarity 0.69
Abstract

Minimum spanning tree interdiction asks for edge deletions within a budget that maximize the weight of a remaining minimum spanning tree. We give two deterministic $(2+ε)$-approximation algorithms for every fixed $ε>0$, improving the previous best factor of $4$. Both algorithms respect the original budget and run in $N^{O(1/ε)}$ time for $0<ε\le1$, where $N$ is the binary input size. The first algorithm uses two weight thresholds to choose initial deletions that force every remaining spanning tree to contain edges at or above these thresholds. It then uses the remaining budget to further increase the MST weight through Lagrangian rounding. The second algorithm achieves the same guarantee through a different decomposition: it enumerates vertex partitions and heavy trees connecting their parts, then approximates a bounded-weight interdiction problem within the parts. An objective-preserving reduction from Maximum Components shows that, assuming the Small Set Expansion Hypothesis and $\mathsf P\ne\mathsf{NP}$, no deterministic polynomial-time $(2-δ)$-approximation exists for any fixed $0<δ<1$, even on simple graphs with weights in $\{0,1\}$. Thus, our approximation guarantee is conditionally tight up to an arbitrarily small additive constant. Finally, the MST guarantee yields a $(4+ε)$-approximation for metric-TSP interdiction.

0.15

Dynamic Steiner Tree under Edge Updates

cs.DS ·2026-11-03 ·Jeff Giliberti, MohammadTaghi Hajiaghayi, Mohammad Mahdavi, Xinchen Yang
hot direction similarity 0.68
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

Directed Global Minimum Cut in Almost-Linear Time

cs.DS ·2026-10-07 ·Henry Fleischmann, Jason Li, Thatchaphol Saranurak, Benyu Wang
highly cited similarity 0.67
Abstract · 11 pages, 4 figures

We give a randomized reduction from global minimum cut in a directed graph with $n$ vertices and $m$ weighted edges to maximum-flow computations on graphs of total size $\widetilde{O}(m)$. For polynomially bounded integral weights, this yields the first almost-linear $m^{1+o(1)}$-time algorithm [vdBCK+23], improving the previous $m^{1+o(1)}\min\{\sqrt{n},n/m^{1/3}\}$ bound [CLN+22]. Previous work reduced finding the minimum cut to constructing a 1-respecting arborescence, a directed spanning tree with exactly one edge crossing a minimum cut [CLN+22]. They then construct such a tree by sampling from a $(1+ε)$-approximate arborescence packing, which currently requires superlinear time. Our algorithm sidesteps constructing the packing entirely and relies on a novel iterative arborescence sampling procedure. We show that, after $O(\log n)$ rounds of sampling, our final arborescence 1-respects the minimum cut with constant probability.

0.48

Optimal Online Weighted Connectivity Augmentation

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

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

cs.DS ·2026-09-30 ·Simon Meierhans, Maximilian Probst Gutenberg, Yu-Cheng Yeh
top venue similarity 0.66
Abstract · To appear in FOCS 2026

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.

0.24

Amortized Cell-Probe Lower Bounds for Dynamic Boolean Problems

cs.DS cs.CC ·2026-11-08 ·Young Kun Ko
theoryhot direction similarity 0.66
Abstract · 20 pages

We prove the first unconditional amortized $Ω\big((\log N/\log\log N)^2\big)$ cell-probe lower bound for a Boolean dynamic problem. For insert-only multiphase Disjointness with $N$ query sets over $[N]$ and word size $w=Θ(\log N)$, a fixed distribution of interleaved insertions and queries forces this expected average cost per operation, excluding preprocessing. The bound allows sufficiently small constant error for each query of every fixed legal sequence and imposes no restriction on individual operation costs. It transfers to incremental directed reachability, incremental subgraph connectivity, and fully dynamic triangle detection. We also prove $t_q=Ω\big((\log N/\log(t_uw))^2\big)$ for amortized insertion time $1\le t_u=N^{o(1)}$ and expected query time $t_q$, when the number of insertions before the final query is not announced in advance. We reach the quadratic-logarithmic scale with bounded error by combining interleaving with the 2.5-round communication framework [Ko26a, Ko26b] and controlling errors among accepted simulations.

0.27

Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion Constraints

cs.DS cs.CC ·2026-11-03 ·Zemin Chao, Jianhe Cen, Hengzhao Ma, Hongzhi Wang
theory similarity 0.66
Abstract

We characterize the optimal space for one-pass spanning-forest computation in dynamic streams of $v$-vertex simple graphs with failure probability at most $δ$. Nelson and Yu proved an $Ω(v\log^2v\log(v/δ))$-bit lower bound, establishing the AGM algorithm's optimality for each fixed $0<ε<1$ and $2^{-v^{1-ε}}<δ\le1/4$. We resolve the remaining high-confidence regime: for every $0<δ\le1/4$, matching lower bounds and an algorithm give \[ Θ\!\left(\min\left\{v^2,\;v\log(v/δ)\log^2\!\left(2+\frac{v}{\log(v/δ)}\right)\right\}\right) \] bits, improving space by up to a factor of $Θ((\log v/\log\log v)^2)$ in this regime. We also study streams with at most $Z$ previously inserted edges deleted and not yet reinserted at report time, where the integer $Z\ge0$ is given in advance. Total deletions, restorations, and intermediate absence counts are unrestricted. For a single report and every $0<δ\le1/4$, matching lower bounds and a one-pass randomized algorithm yield optimal space $Θ(\mathcal L(v,Z,\log(1/δ)))$ bits, where $x_Z(t)=\min\{Z+1,v,\sqrt{vt}\}$ and \[ \mathcal L(v,Z,t)=v\log v\min\{\log^2v,\log^2(Z+2)\} +vt\log\!\left(1+\frac{x_Z(t)}t\right)\log\!\left(1+\frac v{x_Z(t)}\right). \] At zero error, a lower bound for all zero-error algorithms and a matching deterministic algorithm give optimal space \[ Θ\!\left(\min\{v^2,v(Z+1)\log(1+v/(Z+1))\}\right) \] bits. Together, these results characterize the memory required across all confidence levels and report-time edge-loss bounds.

0.28

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.65
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