CS Paper Radar

Connectivity in a New Bounded-Space Dynamic Model

Bardiya Aryanfard, Monika Henzinger, John Kuszmaul, Jakob Nogler, Virginia Vassilevska Williams

cs.DS ·submitted 2026-11-05 17:34 UTC · v1
theory

Abstract

We introduce a new model for dynamic algorithms in which the algorithm has read-only oracle access to a dynamically changing input and random access to its own bounded workspace. It is a dynamic analogue of the time-space tradeoffs for static inputs studied in complexity theory, where only writable memory counts as space. We study dynamic undirected $s$-$t$ connectivity: after every edge update to an $n$-vertex graph, an algorithm with $S$ words of workspace must report whether $s$ and $t$ are connected. The graph is accessed via adjacency list queries (degree, $j$-th neighbor) or adjacency matrix queries. Our algorithms are randomized; our lower bounds hold for randomized algorithms with $cn$ bits of workspace, $c>0$ a small constant ($cn/\log n$ for the worst-case matrix bound). We prove: (1) With adjacency lists, worst-case time $\tildeΘ(n^2/S^2)$ per insertion is necessary and sufficient for incremental algorithms. (2) With an adjacency matrix, worst-case time $\tildeΩ(n^2/S)$ per insertion is necessary for incremental algorithms, and sufficient for $S\ge\sqrt{n}$. (3) With amortization, incremental algorithms achieve $\tilde O(n/S)$ time per insertion with adjacency lists and $\tilde O(n^2/S)$ with an adjacency matrix, while $\tildeΩ(\sqrt{n/S})$ and $\tildeΩ(n\sqrt{n/S})$, respectively, are necessary. (4) Fully dynamic algorithms need amortized time $\tildeΩ(n/S)$ per update with adjacency lists and $\tildeΩ(n^2/S)$ with an adjacency matrix, even on forests, where both bounds are tight (lists: under bounded degree). Conventional dynamic connectivity admits polylogarithmic update time with $Ω(n)$ words of space. In contrast, our lower bounds show that polynomial update time is necessary whenever $S\le n^{1-\varepsilon}$, even for a single pair of vertices and even for incremental algorithms with amortized guarantees.

Comment
Submitted to STOC; shortened abstract to fit arxiv requirements

Closest papers

Nearest neighbours by meaning across the whole index.

Amortized Cell-Probe Lower Bounds for Dynamic Boolean Problems

cs.DS cs.CC ·2026-11-08 ·Young Kun Ko
theoryhot direction similarity 0.70
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

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

Faster Dynamic Maximal Independent Set against Adaptive Adversaries

cs.DS ·2026-11-04 ·Hongyi Chen, Shuyan Fan, Tianyi Zhang
similarity 0.68
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

Testing MAX-CUT in the Adjacency Matrix Model: Tight Non-Adaptive Bounds and a Cubic Adaptive Lower Bound

cs.DS ·2026-10-31 ·Songhua He
theory similarity 0.68
Abstract

We study the query complexity of approximating the MAX-CUT value to additive error $\varepsilon n^2$ in the adjacency matrix model. This was one of the first problems studied in graph property testing [GGR'98]. Previously, the best known upper bound for both adaptive and non-adaptive algorithms was $O(1/\varepsilon^6)$ [RV'07; MS'08; GMRS'22]. The only known lower bound was a trivial $Ω(1/\varepsilon^2)$ bound. We close this gap from both sides for non-adaptive algorithms, proving that its query complexity is exactly $Θ(1/\varepsilon^4)$. We also prove an adaptive $Ω(1/\varepsilon^3)$ lower bound. Our upper bound is achieved by a canonical tester that samples $O(1/\varepsilon^2)$ vertices in expectation and outputs the rescaled MAX-CUT value of the induced subgraph. We prove its correctness by applying spectral truncation to the adjacency matrix, using a geometric argument to control the sampling error of the retained low-rank part and a cut-norm restriction estimate [RV'07] for the remainder. As an application, an analogous proof also yields a tight $O(1/\varepsilon^4)$ non-adaptive query upper bound for MAX-2CSP. For our lower bounds, we show indistinguishability between a uniform random graph and a random graph with a planted hidden partition. For the non-adaptive lower bound, we observe that one plus the $χ^2$-divergence between the query transcript distributions is exactly a normalized Ising partition function, which can be bounded using Boolean hypercontractivity. For the adaptive lower bound, we relate each query's distinguishing power to the prediction, based on previous answers, of whether its endpoints lie in the same part of the hidden partition. We bound the combined advantage of these predictions using the completed transcript, which lets us analyze the adaptively chosen pairs of vertices together despite their dependence on earlier answers.

0.20

Breaking Two Barriers for Dynamic Planar Reachability

cs.DS ·2026-10-09 ·Adam Karczmarz, Michał Włodarczyk
top venuetheory similarity 0.67
Abstract · To appear at SODA 2027

We consider the reachability problem in fully dynamic directed planar graphs: the graph undergoes edge updates (insertions and deletions) and we receive queries asking if one vertex is reachable from another. The current-best online algorithm for dynamic planar reachability spends worst-case time $\widetilde{O}(n^{2/3})$ per query/update [Subramanian, ESA '93]. This can be improved to $\widetilde{O}(n^{1/2})$ in the offline setting or when the embedding is fixed [Diks and Sankowski, ESA '07]. Our contribution is twofold: 1. We present the first algorithm that breaks the square-root barrier for dynamic planar reachability in the offline setting, obtaining time ${O}(n^{0.49})$ per query/update. This shows that the problem is easier than answering distance queries in a dynamic undirected planar graph, for which a conditional lower bound of $n^{1/2 - o(1)}$ is known [Abboud and Dahlgaard, FOCS '16]. Notably, this lower bound applies to both online and offline algorithms. 2. Second, in the general online setting we design a randomized data structure with amortized update and query time ${O}(n^{0.664})$. This is the first improvement upon the exponent $2/3$ in over three decades. The main engine behind our theorems is a new sparsification framework aimed at maintaining information about reachability. Specifically, we study digraphs through the lens of VC dimensionality of certain set systems. First, we design sparse reachability emulators for planar digraphs that preserve the VC dimension. Second, we utilize orderings with a low ``stabbing number'' [Chazelle and Welzl, Discrete Comput. Geom. '89] to compute subquadratic reachability emulators in subquadratic time whenever the VC dimension is bounded.

0.40

Incremental Exact Vertex Connectivity

cs.DS ·2026-10-15 ·Felix Adena, Monika Henzinger, Christoph Kern, Daniel Rutschmann
top venuetheory similarity 0.66
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

Strong Connectivity Oracle for Multiple Failures via Rooted Flow-Augmentation

cs.DS ·2026-11-06 ·Aditya Anand, Thatchaphol Saranurak, Benyu Wang
published similarity 0.66
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

Dynamic Distances Without Matrix Inverse

cs.DS ·2026-10-20 ·Jan van den Brand, Adam Karczmarz, Aryan Patel
top venue similarity 0.66
Abstract · Accepted to SODA 2027

We study the fully dynamic exact distance problem in unweighted directed graphs, where the graph undergoes edge insertions and deletions, and the distance between two query vertices must be reported. Under the combinatorial Boolean matrix multiplication conjecture, any subquadratic-time algorithm for this problem must use algebraic techniques. All prior work uses the polynomial matrix inverse as its algebraic tool, but within subquadratic time, this technique can only maintain distances up to a small-polynomial hop bound. So larger distances must be reassembled from short-range pieces by a combinatorial layer. This hybrid algebraic-combinatorial construction has led to a substantial slowdown for dynamic distances compared to other dynamic graph problems relying on algebraic techniques. We give the first subquadratic-time dynamic distance algorithm built on dynamically maintaining a different algebraic object than the matrix inverse. By maintaining the Frobenius form $A=KCK^{-1}$ of a dynamic generic (i.e., cyclic) matrix $A$, we can query all the powers $A^\ell = K C^\ell K^{-1}$ efficiently. For adjacency matrix~$A$, the smallest $\ell$ with $(A^\ell)_{s,t}\neq 0$ is the $st$-distance in the associated graph. So, unlike dynamic matrix inverse, we get distance information directly without hop truncation, and we no longer need to perform any combinatorial reassembly. This purely algebraic approach to dynamic distances leads to the fastest dynamic distance algorithm with $O(n^{1.58})$ update time. The earlier use of the Frobenius form maintained the dense change of basis $K$ explicitly and required $\tilde O (n^2)$ time per update [KS23]. Our key observation is that this change of basis is highly structured, which lets us maintain it implicitly. This gives the first subquadratic dynamic algorithm for the Frobenius normal form and characteristic polynomial for generic matrices.

0.33