CS Paper Radar

Faster Directed Hopsets, Distance Preservers, and Deterministic Shortcut Sets

Ben Bals, Daniel Dadush, Gary Hoppenworth, Yasamin Nazari, Rajath Rao K. N

cs.DS ·submitted 2026-10-08 14:39 UTC · v1

Abstract

While there have been many recent advances in getting better tradeoffs for directed distance structures such as hopsets, shortcut sets and distance preservers, most known algorithms are inefficient. In this work we provide three results: - Faster algorithms for directed $(1+ε)$-hopsets, matching the state-of-the-art size/hopbound trade-offs of Bernstein & Wein [SODA23]. Our algorithm is first designed for DAGs and then extended to general graphs (up to $n^{o(1)}$ factors) using the recent DAG projection result of Haeupler, Jiang, and Saranurak [STOC26]. - Faster \textit{deterministic} algorithms for constructing shortcut sets, matching the state-of-the-art size/hopbound tradeoffs of Kogan & Parter [SODA22A]. - Using our improved directed hopset construction, we get significantly faster algorithms for computing source-wise distance preservers. This algorithm is based on speeding-up reductions of Kogan & Parter [SODA22B] by using certain structural properties of our hopsets.

Closest papers

Nearest neighbours by meaning across the whole index.

On the Communication Complexity of Shortcut Set Computation

cs.DS ·2026-11-06 ·Gregory Bodwin, Luba Samborska
theory similarity 0.68
Abstract

A recent breakthrough of Kogan and Parter (SODA '22) provided the first polynomial improvement in decades on the size/diameter tradeoff available for shortcut sets. However, algorithmic applications of shortcut sets have mostly not taken advantage of these new bounds. A barrier is that many shortcut set applications occur in \emph{decentralized} settings, and we generally lack decentralized algorithms implementing the Kogan-Parter bounds. To this end, we study the \emph{communication complexity} of constructing Kogan-Parter shortcut sets. The edges of an $n$-node directed graph are split between two players, Alice and Bob, who are also given a target diameter $D$. Our main result is a protocol that, for $D \le n^{1/3}$, allows Alice and Bob to agree on a shortcut set matching the Kogan-Parter tradeoff between size and diameter, while exchanging only $\Oish(n^2 / D^2)$ bits of communication. We also provide (non-matching) lower bounds on the communication complexity required to find a correct $D$-diameter shortcut set of any size. The main technical ingredient for the upper bounds is a low-communication protocol for finding a \emph{path cover}, a common subroutine in shortcut set constructions that has attracted some independent interest. Our protocol crucially avoids applications of Menger's theorem or antichain decompositions, as often done in prior work. On the lower bounds side, we relate the communication complexity of the shortcut set problem to the size of bridge-free path systems.

0.23

A Simple Algorithm for the Directed Multiple Source Replacement Paths Problem

cs.DS ·2026-08-17 ·Kaito Harada, Taisuke Izumi
publishedtheory similarity 0.65
Abstract · 15 pages, 1 figure. To appear in SOSA 2027

In the replacement paths (RP) problem, we are given a graph $G = (V, E)$ with $n = |V|$ and $m = |E|$, together with two vertices $s, t \in V$, and are asked to compute the shortest-path distance from $s$ to $t$ in $G \setminus e$ for every failed edge $e \in E$. The multiple source replacement paths (MSRP) problem is its natural generalization: given a set $S \subseteq V$ of $σ$ sources, compute the replacement path distances for all pairs in $S \times V$. In this paper, we present a randomized combinatorial algorithm that solves MSRP on unweighted directed graphs in $\tilde{O}(m\sqrt{σn} + σn^2)$ time, with all the output distances correct with high probability. This improves the best known bound $\tilde{O}(m\min\{σ\sqrt{n}, n\} + σn^2)$ for directed graphs, which is obtained either by running the single source RP algorithm of Chechik and Magen [ICALP'20] from each source separately or by constructing and querying the all-pairs distance sensitivity oracle of Bernstein and Karger [STOC'09]. Our running time is essentially tight among combinatorial algorithms because Gupta, Jain, and Modi [PODC'20] proved a lower bound of $m{(σn)}^{1/2-o(1)}$ for such algorithms, which holds even on undirected graphs, and the additive term $σn^2$ is proportional to the time needed to write down the $Θ(σn^2)$ output distances. The algorithm is also remarkably simple.

0.41

Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense Graphs

cs.DS ·2026-10-23 ·Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
similarity 0.65
Abstract · 101 pages

We give a combinatorial algorithm that computes an exact minimum-cost flow in $n^{2+o(1)}$ time. This is the first combinatorial improvement since Goldberg-Tarjan [GT87], and is almost optimal in dense graphs. All previous faster algorithms, including the almost-linear-time algorithm of Chen et al. [CKL+22], rely on interior-point methods. Our main conceptual contribution is a black-box reduction from exact minimum-cost flow on general graphs to its approximation on DAGs, with only an $n^{o(1)}$ loss on the running time. This reduction allows future work on combinatorial minimum-cost flow to focus on DAGs, typically much easier to handle than general graphs. Our $n^{2+o(1)}$-time algorithm follows by combining this reduction with a simple augmenting-path-based approximation algorithm on DAGs. The reduction is based on a new structural result, called a flow-cost-preserving DAG projection. Given an arbitrary directed graph, this construction produces a DAG that approximately preserves both the congestion of flows and their cost up to a small loss.

0.48

An Optimal Structure for All-Pairs Nearest Mincuts and Sensitivity Oracles for Edge Insertions

cs.DS ·2026-09-25 ·Koustav Bhanja, Yotam Kenneth-Mordoch, Asaf Petruschka
similarity 0.63
Abstract

Given an undirected weighted graph $G=(V,E)$ on $n$ vertices, the classical Gomory-Hu tree of $G$ is a structure that encodes an arbitrary minimum $s,t$-cut for every $s,t\in V$ using just $O(n)$ space. In this work, we ask whether the same compactness is achievable for the natural and structured family of all-pairs \textit{nearest minimum cuts}. The nearest minimum $(s,t)$-cut is the unique inclusion-wise minimal one among all minimum $s,t$-cuts containing $s$. This family has proven useful in a wide range of applications, including fault-tolerant reachability, minimum cut sensitivity oracles, cactus representations, and fast Gomory-Hu tree constructions. Despite its fundamental role, no subquadratic space representation is known for them to date. The $O(n)$ space representations are known only in single-source settings, where given a source $s$, one can report the nearest minimum $(t,s)$-cut for any $t\in V\setminus \{s\}$. We close this gap by presenting the first optimal space representation of all-pairs nearest minimum cuts, providing a natural analogue of the Gomory-Hu tree. Our main result is an $O(n)$ space structure that encodes the nearest minimum cut between every pair of vertices. Furthermore, given any pair $s,t\in V$, it can report the nearest minimum $s,t$-cut in $O(n)$ time. Both bounds match those of the Gomory-Hu tree and are worst-case optimal. As an application, we design an all-pairs minimum cut sensitivity oracle for edge insertion: a data structure that occupies $O(n)$ space and, given any edge $e$, can determine for all pairs $s,t\in V$ whether the minimum $s,t$-cut value increases upon insertion of $e$ in $O(n^2)$ total time. Existing insertion sensitivity oracles were either limited to the single-source setting or used $O(n^2)$ space for all-pairs [Baswana, Gupta, and Knollmann, Algorithmica'22; Baswana and Pandey, SODA'22].

0.32

$\tilde{O}(1)$-Depth Parallel Reachability Faster than Transitive Closure

cs.DS ·2026-08-13 ·Shimon Kogan, Merav Parter
top venuetheory similarity 0.63
Abstract · Accepted to FOCS 2026

A $d$-shortcut of a directed graph $G=(V,E)$ is a subset of edges drawn from the transitive closure $TC(G)$ whose addition reduces the graph diameter to at most $d$. In the special case $d=1$, computing a $1$-shortcut is \emph{equivalent} to computing the transitive closure. For larger values of $d$, a lower bound of [Hesse, SODA 2003] shows that $n^δ$-shortcuts, for small constants $δ>0$, may still contain a large fraction of the edges of $TC(G)$, suggesting that shortcut construction may remain as hard as transitive closure even in this regime. Consequently, since $\widetilde{O}(d)$-depth parallel reachability algorithms rely on computing $d$-shortcuts, achieving $\widetilde{O}(1)$ depth by this approach has so far required computing the full transitive closure. Assuming $ω=2$, the PS-AE-Triangle hypothesis of [Abboud, Bringmann, Fischer, and Künnemann, SODA 2024] yields a conditional $T^{4/3-o(1)}$ time barrier for computing transitive closure when $T\leq n^{3/2}$, where $T=|TC(G)|$. In this work, we bypass the transitive-closure barrier for $\widetilde{O}(1)$-depth parallel reachability. We introduce randomized $d$-shortcut constructions that already circumvent this barrier for $d=3$ and, more generally, for every even $d\geq4$ up to $O(\log n)$. Our approach yields a randomized $\widetilde{O}(1)$-depth parallel reachability algorithm with total work $\widetilde{O}(T^{ω/2})$, which becomes $\widetilde{O}(T)$ when $ω=2$, falling below this conditional $T^{4/3-o(1)}$ barrier throughout that regime. Under the current bound of $ω$, this gives $\widetilde{O}(T^{1.186})$ work, improving on the current $T^{1.3459+o(1)}$ sequential-time bound for transitive closure due to Abboud et al. Thus, although $\widetilde{O}(1)$-shortcuts might be almost as dense as the full transitive closure, they can nevertheless be computed substantially faster.

0.31

Partially Dynamic Single-Source Shortest Paths in Almost-Linear Time

cs.DS ·2026-10-05 ·Bin Cui, Hanqing Li, Xupeng Miao, Haoze Wang
similarity 0.62
Abstract · v2: Added a deterministic almost-linear-time incremental SSSP algorithm with efficient approximate path reporting

We study $(1+ε)$-approximate single-source distances in directed graphs with positive integer edge weights in $[1,W]$. For every $0<ε\le1$, we give deterministic data structures for either edge insertions or edge deletions with total update time $m^{1+o(1)}ε^{-1}\log W$, where $m\ge n$ bounds the total number of initially present and inserted edges. Both structures explicitly maintain approximate distance estimates, answer distance queries in constant time, and identify unreachable vertices exactly. The incremental structure additionally reports a simple $(1+ε)$-approximate source path $P$ in $O(|P|)$ time. Our decremental structure gives the first almost-linear-time algorithm. It improves the previous best randomized expected bound of $\widetilde O(\min\{n^2,mn^{2/3}\})$ against an oblivious adversary [BPW20]. Our incremental bound improves the $ε^{-B}$ dependence of the $B$-level recursive algorithm of [Liu26] to an explicit $ε^{-1}$ factor while retaining almost-linear dependence on $m$. Our algorithms use modified interior point methods. For edge deletions, we extend the single-pair distance framework of [vBCKLMPSS24] to all targets simultaneously. A shared potential and one dynamic minimum-ratio cut instance support global updates to the distance labels. Our main insight is that constant relative cut balance certifies approximate distances at every target. For edge insertions, we develop an analogous circulation-based formulation implemented through the dynamic minimum-ratio cycle structure of [CKLMP24]. We also give a black-box reduction from distance estimates to path reporting in incremental graphs, with $m^{1+o(1)}ε^{-1}\log W$ additional maintenance time. This reduction may be of independent interest.

0.21

Quasi-polynomial-sized vertex multicut-mimicking networks and kernelization for Vertex Multiway Cut

cs.DS ·2026-11-05 ·Eduard Eiben, Roohani Sharma, Magnus Wahlström
survey similarity 0.62
Abstract

We give deterministic polynomial-time constructions of vertex multicut-mimicking networks of quasi-polynomial size. Given a graph G, a terminal set T, and a positive integer c, our algorithm constructs a graph with |T|^7 c^{O( log c ) } vertices that preserves every minimum vertex multiway cut value of at most c, for every partition of the terminals. Setting c=|T| gives an exact vertex multicut-mimicking network with |T|^{O( log |T| ) } vertices, resolving an open question of Wahlström [ACM Transactions on Algorithms 2022], who showed a bound of κ^{O( log^3 κ)} for the edge multicut-mimicking variant, where κ:= \sum_{t \in T} |N_G(t)| is the capacity of the terminal set, which was later improved to κ^{O( log^2 κ)} by Anand, Lee, Li and Saranurak [STOC 2024]. As applications of our vertex multicut-mimicking network, we obtain deterministic kernels of size k^{O( log k )} for Vertex Multiway Cut, p^{O(1)} k^{O(log k)} for Vertex Multicut with p requests and |Γ|^{O(1)} k^{O( log k)} for Group Feedback Vertex Set, where k is the deletion budget and Γis a finite group. Our first kernelization result, in particular, resolves an open question by Wahlström [ACM Transactions on Algorithms 2022], which was reiterated in a recent survey on kernelization by Jansen [Computer Science Reviews 2026]. Also, to the best of our knowledge, our kernel for Vertex Multicut is the first one whose size is completely polynomial in p and (quasi-polynomial) super-polynomial only in k. Finally, again using our vertex multicut-mimicking network for graphs, we obtain a hyperedge multicut-mimicking network for hypergraphs, which preserves hypergraph edge-multicuts of size up to c, of size |T|^{O(1)} c^{O(log c)}. Our result removes the dependence on the rank of the hypergraph from the exponent of the size bound, that existed in prior work.

0.29

Roundtrip All-Pairs Shortest Paths in Directed Graphs

cs.DS ·2026-11-03 ·Shiri Chechik, Gur Lifshitz
similarity 0.62
Abstract

We study approximation algorithms for All-Pairs Shortest Paths (APSP) in directed graphs under the roundtrip metric. In directed graphs, even finite-factor approximation of ordinary one-way distances must distinguish reachable from unreachable vertex pairs, and therefore computes transitive closure, a problem equivalent to Boolean matrix multiplication (BMM) under standard reductions. The roundtrip distance, defined as $\text{dist}_G(u \leftrightarrows v) = \text{dist}_G(u \to v) + \text{dist}_G(v \to u)$, offers a natural and robust relaxation. It measures the cost of traveling from $u$ to $v$ and back, satisfies the triangle inequality, and is inherently symmetric. While this metric has become central to the study of directed roundtrip spanners and compact routing, the fundamental problem of all-pairs roundtrip distance approximation has remained largely unexplored. In this work, we present a comprehensive study of roundtrip APSP and distance oracles, presenting several new lower and upper bounds. On the algorithmic side, our main result is a combinatorial algorithm that computes a stretch-$3$ approximation to all-pairs roundtrip distances in $\widetilde{O}(n^2 + \min\{m\sqrt{n},\, m^{1/3}n^{5/3}\})$ time. For edge weights in $[1,W]$, we also obtain a $(3+\varepsilon)$-approximation in $\widetilde O((n^{2.037}+nm^{2/3})\log(nW)/\varepsilon)$ time and a $(4+\varepsilon)$-approximation in $\widetilde O(n^{2.032}\log(nW)/\varepsilon)$ time using fast matrix multiplication. On the hardness side, we show that any stretch below $3$ would imply a breakthrough for BMM. We also obtain additional tradeoffs between stretch and running time.

0.27