Thatchaphol Saranurak

activity

20122026

most citedUnifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture

215 citations · 318 across the 83 of their papers we have counts for

collaborators

96 papers

cs.DS2026

Directed Global Minimum Cut in Almost-Linear Time

Henry Fleischmann, Jason Li, Thatchaphol Saranurak +1

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…

cs.DS2026

Deterministic Edge-Fault-Tolerant Connectivity Labeling Schemes with Nearly Optimal Label Size

Yaowei Long, Seth Pettie, Thatchaphol Saranurak

For an undirected graph $G = (V, E)$ and a fault bound $f$ , an edge-fault-tolerant connectivity labeling scheme assigns short labels to vertices and edges, so that for any vertex pa…

cs.DS2026

Connectivity Oracles Under Vertex Failures via a Simple and Fast Low-Degree Steiner Forest Decomposition

Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak +1

We study the low-degree Steiner forest decomposition. Given a graph $G = (V, E)$ and a terminal set $U \subseteq V$ , the standard decomposition returns a set $X \subseteq V$ of size at…

cs.DS2026

Incremental Directed Minimum Cut by Dynamizing Gabow's Algorithm

Thatchaphol Saranurak, Kaiyang Xie, Zhaienhe Zhou

We give the first incremental algorithm for directed global minimum cut. Given a directed graph with $n$ vertices undergoing $m$ edge insertions, our deterministic algorithm explic…

cs.DS2026

Minimum Degree Spanning Tree: $(1 + ε, 1)$ -Approximation in Near-Linear Time

Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak +1

The minimum degree spanning tree problem is a classic NP-hard problem whose optimal approximation guarantee was established since the early 1990s: Fürer and Raghavachari [FR92] gav…

cs.DS2026

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition

Xizhe Li, Yaowei Long, David Pidugu +2

We give an improved connectivity oracle under vertex failures. After a set of $k$ vertices fails, our oracle performs an $O (k^{6})$ -time update independent of the graph size $n$ , a…

cs.DS2026

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth

Vikrant Ashvinkumar, Aaron Bernstein, Maximilian Probst Gutenberg +1

We present parallel algorithms for computing single-source reachability and shortest paths on directed $n$ -vertex $m$ -edge graphs using near-linear $O ~ (m)$ work and $o(\sqrt…

cs.DS2026

DAG Projections: Reducing Distance and Flow Problems to DAGs

Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak

We show that every directed graph $G$ with $n$ vertices and $m$ edges admits a directed acyclic graph (DAG) with $m^{1 + o (1)}$ edges, called a DAG projection, that can either $(1+1/…

cs.DS2026

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures

Bernhard Haeupler, Yaowei Long, Antti Roeyskoe +1

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| \…

cs.DS2026

Expander Decomposition with Almost Optimal Overhead

Nikhil Bansal, Arun Jambulapati, Thatchaphol Saranurak

We present the first polynomial-time algorithm for computing a near-optimal \emph{flow}-expander decomposition. Given a graph $G$ and a parameter $ϕ$ , our algorithm removes at most…

cs.DS2025

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies

Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak +1

We give almost-linear-time algorithms for approximating rooted minimum cut and maximum arborescence packing in directed graphs, two problems that are dual to each other [Edm73]. Mo…

cs.DS2025

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers

Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak

We present the first deterministic nearly-linear time algorithm for single-source shortest paths with negative edge weights on directed graphs: given a directed graph $G$ with $n$ …

cs.DS2025

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching

Matija Bucić, Zhongtian He, Shang-En Huang +1

We design efficient deterministic algorithms for finding short edge-disjoint paths in expanders. Specifically, given an $n$ -vertex $m$ -edge expander $G$ of conductance $ϕ$ and mini…

cs.DS2025

Reviving Thorup's Shortcut Conjecture

Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg +7

We aim to revive Thorup's conjecture [Thorup, WG'92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph…

cs.DS2025

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

Bernhard Haeupler, Yonggang Jiang, Yaowei Long +2

We present a parallel algorithm for computing $(1 + ε)$ -approximate mincost flow on an undirected graph with $m$ edges, where capacities and costs are assigned to both edges and vert…

cs.DS2025

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems

Aaron Bernstein, Sayan Bhattacharya, Nick Fischer +2

We establish the first update-time separation between dynamic algorithms against oblivious adversaries and those against adaptive adversaries in natural dynamic graph problems, bas…

cs.DS2025

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs

Aaron Bernstein, Joakim Blikstad, Jason Li +2

We give a combinatorial algorithm for computing exact maximum flows in directed graphs with $n$ vertices and edge capacities from ${1, \dots, U}$ in $O ~ (n^{2} lo g U)$ time,…

cs.DS2025

Near-Optimal Fault-Tolerant Strong Connectivity Preservers

Gary Hoppenworth, Thatchaphol Saranurak, Benyu Wang

A $k$ -fault-tolerant connectivity preserver of a directed $n$ -vertex graph $G$ is a subgraph $H$ such that, for any edge set $F \subseteq E (G)$ of size $∣ F ∣ \leq k$ , the strongly co…

cs.DS2025

Reducing Shortcut and Hopset Constructions to Shallow Graphs

Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak

We introduce a blackbox framework that simplifies all known parallel algorithms with near-linear work for single-source reachability and shortest paths in directed graphs. Specific…

cs.DS2025

Deterministic Almost-Linear-Time Gomory-Hu Trees

Amir Abboud, Rasmus Kyng, Jason Li +5

Given an $m$ -edge, undirected, weighted graph $G = (V, E, w)$ , a Gomory-Hu tree $T$ (Gomory and Hu, 1961) is a tree over the vertex set $V$ such that all-pairs mincuts in $G$ are prese…

cs.DS2025

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs

Aditya Anand, Euiwoong Lee, Jason Li +1

Given a directed graph $G$ with $n$ vertices and $m$ edges, a parameter $k$ and two disjoint subsets $S, T \subseteq V (G)$ , we show that the number of all-subsets important separato…

cs.DS2025

Deterministic Dynamic Maximal Matching in Sublinear Update Time

Aaron Bernstein, Sayan Bhattacharya, Peter Kiss +1

We give a fully dynamic deterministic algorithm for maintaining a maximal matching of an $n$ -vertex graph in $O ~ (n^{8/9})$ amortized update time. This breaks the long-standi…

cs.DS2025

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time

Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak

Expander graphs are known to be robust to edge deletions in the following sense: for any online sequence of edge deletions $e_{1}, e_{2}, \dots, e_{k}$ to an $m$ -edge graph $G$ that is…

cs.DS2025

Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts

Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak +1

We show the existence of length-constrained expander decomposition in directed graphs and undirected vertex-capacitated graphs. Previously, its existence was shown only in undirect…

Directed Global Minimum Cut in Almost-Linear Time

Deterministic Edge-Fault-Tolerant Connectivity Labeling Schemes with Nearly Optimal Label Size

Connectivity Oracles Under Vertex Failures via a Simple and Fast Low-Degree Steiner Forest Decomposition

Incremental Directed Minimum Cut by Dynamizing Gabow's Algorithm

Minimum Degree Spanning Tree: (1+ε,1)-Approximation in Near-Linear Time

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth

DAG Projections: Reducing Distance and Flow Problems to DAGs

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures

Expander Decomposition with Almost Optimal Overhead

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching

Reviving Thorup's Shortcut Conjecture

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

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs

Near-Optimal Fault-Tolerant Strong Connectivity Preservers

Reducing Shortcut and Hopset Constructions to Shallow Graphs

Deterministic Almost-Linear-Time Gomory-Hu Trees

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs

Deterministic Dynamic Maximal Matching in Sublinear Update Time

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time

Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts

Minimum Degree Spanning Tree: $(1 + ε, 1)$ -Approximation in Near-Linear Time

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