We study connectivity oracle under vertex failures, one of the most fundamental graph data structures with many applications. We provide a new deterministic connectivity oracle that handles update in O(k⁶) time and answers query in O(k) time, while using 2^O(k²) n + O(k²n α_c(n)) space and k^O(k²) n + O(m + k³ n log² n + k⁶n log n) preprocessing time. Although some previous works achieve k² ⋅ n^o(1) update time and O(k) query time [Long and Saranurak, 2022; Yaowei Long and Yunfan Wang, 2024], the update time is still n-dependent, while oracles that have n-independent update and query times [Michal Pilipczuk et al., 2022; Jan van den Brand and Thatchaphol Saranurak, 2019] cannot achieve optimal O(k) query time [Monika Henzinger et al., 2015] and often have Ω(n²) space and processing time. Our solution would be the first vertex-failure connectivity oracle that achieves O(k) query time with update time completely independent of n, while improving space usage and having competitive preprocessing time.

In the online Steiner forest problem we are given a graph G, and a sequence of terminal pairs (u_i,v_i) which arrive in an online fashion. We are asked to maintain a low-cost subgraph in which each u_i is connected to v_i for all the pairs that have arrived so far. If we are not allowed to delete edges from our solution, then the best possible competitive ratio is Θ(log n). In this work, we initiate the study of low-recourse algorithms for online Steiner forest. We give an algorithm that maintains a constant-competitive solution and has an amortized recourse of O(log n), i.e., inserts and deletes O(log n) edges per demand on average.

A fault-tolerant distance labeling scheme assigns a label to each vertex and edge of an undirected weighted graph G with n vertices so that, for any edge set F of size |F| ≤ f, one can approximate the distance between p and q in G ∖ F by reading only the labels of F ∪ {p,q}.

We show the existence of length-constrained expander decomposition in directed graphs and undirected vertex-capacitated graphs. Previously, its existence was shown only in undirected edge-capacitated graphs [Bernhard Haeupler et al., 2022; Haeupler et al., 2024]. Along the way, we prove the multi-commodity maxflow-mincut theorems for length-constrained expansion in both directed and undirected vertex-capacitated graphs. Based on our decomposition, we build a length-constrained flow shortcut for undirected vertex-capacitated graphs, which roughly speaking is a set of edges and vertices added to the graph so that every multi-commodity flow demand can be routed with approximately the same vertex-congestion and length, but all flow paths only contain few edges. This generalizes the shortcut for undirected edge-capacitated graphs from [Bernhard Haeupler et al., 2024]. Length-constrained expander decomposition and flow shortcuts have been crucial in the recent algorithms in undirected edge-capacitated graphs [Bernhard Haeupler et al., 2024; Haeupler et al., 2024]. Our work thus serves as a foundation to generalize these concepts to directed and vertex-capacitated graphs.

We present a parallel algorithm for computing ($1+ \epsilon$)-approximate min-cost flow on an undirected graph with m edges, where capacities and costs are assigned to both edges and vertices. Our algorithm achieves $\hat{O}(m)$ work and $\hat{O}(1)$ depth when $\epsilon\gt 1 / \operatorname{polylog}(m)$, making both the work and depth almost optimal, up to a subpolynomial factor. Previous algorithms with $\hat{O}(m)$ work required $\Omega(m)$ depth, even for special cases of min-cost flow with only edge capacities or max flow with vertex capacities. Our result generalizes prior almost-optimal parallel $(1+\epsilon)$-approximation algorithms for these special cases, including shortest paths [1]–[3] and max flow with only edge capacities [4], [5]. Our key technical contribution is the first construction of length-constrained flow shortcuts with $(1+\epsilon)$ length slack, $\hat{O}(1)$ congestion slack, and $\hat{O}(1)$ step bound. This provides a strict generalization of the influential concept of $(\hat{O}(1), \epsilon)$-hopsets [6], allowing for additional control over congestion. Previous lengthconstrained flow shortcuts [7] incur a large constant in the length slack, which would lead to a large approximation factor. To enable our flow algorithms to work under vertex capacities, we also develop a close-to-linear time algorithm for computing length-constrained vertex expander decomposition. Building on Cohen’s idea of path-count flows [8], we further extend our algorithm to solve $(1+\epsilon)$-approximate k-commodity min-cost flow problems with almost-optimal $\hat{O}(m k)$ work and $\hat{O}(1)$ depth, independent of the number of commodities k.

Unbreakable decomposition, introduced by [CLP+19, CKL+20], has proven to be one of the most powerful tools for parameterized graph cut problems in recent years. Unfortunately, all known constructions require at least Ωk (mn2) time, given an undirected graph with n vertices, m edges, and cut-size parameter k. In this work, we show the first close-to-linear time parameterized algorithm that computes an unbreakable decomposition. More precisely, for any 0 < ∈ ≤ 1, our algorithm runs in time and computes a (O (k/∈ ),k ) unbreakable tree decomposition of the input graph, where each bag has adhesion at most O (k/∈ ).

We consider the problem of assigning short labels to the vertices and edges of a graph G so that given any query 〈s, t, F 〉 with |F | ≤ f, we can determine whether s and t are still connected in G — F, given only the labels of F ∪ {s, t }.

We present a new distance oracle in the fully dynamic setting: given a weighted undirected graph G = (V, E) with$n$vertices undergoing both edge insertions and deletions, and an arbitrary parameter$\epsilon\in[1/\log^{c}n, 1$where$c$> 0 is a small constant, we can deterministically maintain a data structure with$O(n^{\epsilon})$worst-case update time that, given any pair of vertices (u, v), returns a$2^{\text{poly}(1/\epsilon)}$-approximate distance between$u$and$v$in poly(1/E) log log$n$query time. Our algorithm significantly advances the state-of-the-art in two aspects, both for fully dynamic algorithms and even decremental algorithms. First, no existing algorithm with worst-case update time guarantees a o($n$)-approximation while also achieving an n2-Ω(1)update and$n^{o(1)}$query time, while our algorithm offers a constant$O_{\epsilon}(1)$-approximation with$O(n^{\epsilon})$update time and$o_{\epsilon}$(log log n) query time. Second, even if amortized update time is allowed, it is the first deterministic constant-approximation algorithm with$n^{1-\Omega(1)}$update and query time. The best result in this direction is the recent deterministic distance oracle by Chuzhoy and Zhang [STOC 2023] which achieves an approxi- mation of (log log$n)^{2^{O (1 / \epsilon^3)}}$with amortized update time of$O(n^{\epsilon)}$and query time of$2^{\mathrm{p}\circ 1\mathrm{y}(1/\epsilon)}\log n$log log n. We obtain the result by dynamizing tools related to length- constrained expanders [Haeupler-Racke-Ghaffari, STOC 2022; Haeupler-Hershkowitz-Tan, FOCS 2024]. Our technique com- pletely bypasses the 40-year-old Even-Shiloach tree, which has remained the most pervasive tool in the area but is inherently amortized.

We study the \emph{sensitivity oracles problem for subgraph connectivity} in the \emph{decremental} and \emph{fully dynamic} settings. In the fully dynamic setting, we preprocess an $n$-vertices $m$-edges undirected graph $G$ with $n_{\rm off}$ deactivated vertices initially and the others are activated. Then we receive a single update $D\subseteq V(G)$ of size $|D| = d \leq d_{\star}$, representing vertices whose states will be switched. Finally, we get a sequence of queries, each of which asks the connectivity of two given vertices $u$ and $v$ in the activated subgraph. The decremental setting is a special case when there is no deactivated vertex initially, and it is also known as the \emph{vertex-failure connectivity oracles} problem. We present a better deterministic vertex-failure connectivity oracle with $\widehat{O}(d_{\star}m)$ preprocessing time, $\widetilde{O}(m)$ space, $\widetilde{O}(d^{2})$ update time and $O(d)$ query time, which improves the update time of the previous almost-optimal oracle [Long-Saranurak, FOCS 2022] from $\widehat{O}(d^{2})$ to $\widetilde{O}(d^{2})$. We also present a better deterministic fully dynamic sensitivity oracle for subgraph connectivity with $\widehat{O}(\min\{m(n_{\rm off} + d_{\star}),n^ω\})$ preprocessing time, $\widetilde{O}(\min\{m(n_{\rm off} + d_{\star}),n^{2}\})$ space, $\widetilde{O}(d^{2})$ update time and $O(d)$ query time, which significantly improves the update time of the state of the art [Hu-Kosinas-Polak, 2023] from $\widetilde{O}(d^{4})$ to $\widetilde{O}(d^{2})$. Furthermore, our solution is even almost-optimal assuming popular fine-grained complexity conjectures.

We study the fine-grained complexity of graph connectivity problems in unweighted undirected graphs. Recent development shows that all variants of edge connectivity problems, including single-source-single-sink, global, Steiner, single-source, and all-pairs connectivity, are solvable in m1+o(1) time, collapsing the complexity of these problems into the almost-linear-time regime. While, historically, vertex connectivity has been much harder, the recent results showed that both single-source-single-sink and global vertex connectivity can be solved in m1+o(1) time, raising the hope of putting all variants of vertex connectivity problems into the almost-linear-time regime too.

We consider the problem of preprocessing a weighted directed planar graph in order to quickly answer exact distance queries. The main tension in this problem is between space S and query time Q , and since the mid-1990s all results had polynomial time-space tradeoffs, e.g., Q = ~ Θ( n/√ S ) or Q = ~Θ( n 5/2 /S 3/2 ). In this article we show that there is no polynomial tradeoff between time and space and that it is possible to simultaneously achieve almost optimal space n 1+ o (1) and almost optimal query time n o (1) . More precisely, we achieve the following space-time tradeoffs: n 1+ o (1) space and log 2+ o (1) n query time, n log 2+ o (1) n space and n o (1) query time, n 4/3+ o (1) space and log 1+ o (1) n query time. We reduce a distance query to a variety of point location problems in additively weighted Voronoi diagrams and develop new algorithms for the point location problem itself using several partially persistent dynamic tree data structures.

We revisit the vertex-failure connectivity oracle problem. This is one of the most basic graph data structure problems under vertex updates, yet its complexity is still not well-understood. We essentially settle the complexity of this problem by showing a new data structure whose space, preprocessing time, update time, and query time are simultaneously optimal up to sub-polynomial factors assuming popular conjectures. Moreover, the data structure is deterministic.More precisely, for any integer $d_{\star}$, the data structure preprocesses a graph G with n vertices and m edges in $\hat{O}\left(m d_{\star}\right)$ time and uses $\tilde{O}\left(\min \left\{m, n d_{\star}\right\}\right)$ space. Then, given the vertex set D to be deleted where $|D|=d \leq d_{\star}$, it takes $\hat{O}\left(d^{2}\right)$ updates time. Finally, given any vertex pair $(u, v)$, it checks if u and v are connected in $G \backslash D$ in $O(d)$ time. This improves the previously best deterministic algorithm by Duan and Pettie [SICOMP 2020] in both space and update time by a factor of d. It also significantly speeds up the $\Omega\left(\min \left\{m n, n^{\omega}\right\}\right)$ preprocessing time of all known (even randomized) algorithms with update time at most $\tilde{O}\left(d^{5}\right)$.

In a recent breakthrough, Charalampopoulos, Gawrychowski, Mozes, and Weimann [9] showed that exact distance queries on planar graphs could be answered in no(1) time by a data structure occupying n1+o(1) space, i.e., up to o(1) terms, optimal exponents in time (0) and space (1) can be achieved simultaneously. Their distance query algorithm is recursive: it makes successive calls to a point-location algorithm for planar Voronoi diagrams, which involves many recursive distance queries. The depth of this recursion is non-constant and the branching factor logarithmic, leading to (log n)ω(1) = no(1) query times. In this paper we present a new way to do point-location in planar Voronoi diagrams, which leads to a new exact distance oracle. At the two extremes of our space-time tradeoff curve we can achieve either n1+o(1) space and log2+o(1) n query time, or n log2+o(1) n space and no(1) query time. All previous oracles with Õ(1) query time occupy space n1+Ω(1), and all previous oracles with space Õ(n) answer queries in nΩ(1) time.