Yaowei Long

SODA Conference 2025 Conference Paper

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies

• Yaowei Long
• Seth Pettie
• Thatchaphol Saranurak

FOCS Conference 2025 Conference Paper

Parallel (1+ε)-Approximate Multi-Commodity Min-Cost Flow in Almost Optimal Depth and Work

• Bernhard Haeupler
• Yonggang Jiang
• Yaowei Long
• Thatchaphol Saranurak
• Shengzhe Wang

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.

SODA Conference 2025 Conference Paper

Unbreakable Decomposition in Close-to-Linear Time

• Aditya Anand 0001
• Euiwoong Lee
• Jason Li 0006
• Yaowei Long
• Thatchaphol Saranurak

FOCS Conference 2024 Conference Paper

Dynamic Deterministic Constant-Approximate Distance Oracles with n ε Worst-Case Update Time

• Bernhard Haeupler
• Yaowei Long
• Thatchaphol Saranurak

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 n 2-Ω(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.

STOC Conference 2023 Conference Paper

Tight Conditional Lower Bounds for Vertex Connectivity Problems

• Zhiyi Huang
• Yaowei Long
• Thatchaphol Saranurak
• Benyu Wang

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 m 1+ 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 m 1+ o (1) time, raising the hope of putting all variants of vertex connectivity problems into the almost-linear-time regime too. We show that this hope is impossible, assuming conjectures on finding 4-cliques. Moreover, we essentially settle the complexity landscape by giving tight bounds for combinatorial algorithms in dense graphs. There are three separate regimes: (1) all-pairs and Steiner vertex connectivity have complexity Θ( n 4 ), (2) single-source vertex connectivity has complexity Θ( n 3 ), and (3) single-source-single-sink and global vertex connectivity have complexity Θ( n 2 ). For graphs with general density, we obtain tight bounds of Θ( m 2 ), Θ( m 1.5 ), Θ( m ), respectively, assuming Gomory-Hu trees for element connectivity can be computed in almost-linear time.

FOCS Conference 2022 Conference Paper

Near-Optimal Deterministic Vertex-Failure Connectivity Oracles

• Yaowei Long
• Thatchaphol Saranurak

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)$.

SODA Conference 2021 Conference Paper

Planar Distance Oracles with Better Time-Space Tradeoffs

• Yaowei Long
• Seth Pettie

In a recent breakthrough, Charalampopoulos, Gawrychowski, Mozes, and Weimann [9] showed that exact distance queries on planar graphs could be answered in n o (1) time by a data structure occupying n 1+ 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) = n o (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 n 1+ o (1) space and log 2+ o (1) n query time, or n log 2+ o (1) n space and n o (1) query time. All previous oracles with Õ (1) query time occupy space n 1+Ω(1), and all previous oracles with space Õ ( n ) answer queries in n Ω(1) time.