The notion of Las Vegas algorithms was introduced by Babai (1979) and can be defined in two ways: * In Babai's original definition, a randomized algorithm is called Las Vegas if it has a finitely bounded running time and certifiable random failure. * Another definition widely accepted today is that Las Vegas algorithms refer to zero-error randomized algorithms with random running times. The equivalence between the two definitions is straightforward. Specifically, for randomized algorithms with certifiable failures, repeatedly running the algorithm until no failure is encountered allows for faithful simulation of the correct output when it executes successfully. We show that a similar perfect simulation can also be achieved in distributed local computation. Specifically, in the LOCAL model, with polylogarithmic overhead in time complexity, any Las Vegas algorithm with finitely bounded running time and locally certifiable failures can be converted to a zero-error Las Vegas algorithm. This transformed algorithm faithfully reproduces the correct output of the original algorithm in successful executions.

We study polynomial-time approximation algorithms for two closely-related problems, namely computing shortcuts and transitive-closure spanners (TC spanners). For a directed unweighted graph \(G = (V,E)\) and an integer \(d\), a set of edges \(E' \subseteq V \times V\) is called a \(d\)-TC spanner of \(G\) if the graph \(H := (V, E')\) has (i) the same transitive-closure as \(G\) and (ii) diameter at most~\(d\). The set \(E'' \subseteq V \times V\) is a \(d\)-shortcut of \(G\) if \(E \cup E''\) is a \(d\)-TC spanner of \(G\). Our focus is on the following \((\alpha_D, \alpha_S)\)-approximation algorithm: given a directed graph \(G\) and integers \(d\) and \(s\) such that \(G\) admits a \(d\)-shortcut (respectively \(d\)-TC spanner) of size \(s\), find a \((d \alpha_D)\)-shortcut (resp. \((d \alpha_D)\)-TC spanner) with \(s \alpha_S\) edges, for as small \(\alpha_S\) and \(\alpha_D\) as possible. These problems are important special cases of graph sparsification and arise naturally in the context of reachability problems across computational models.

We study the problem of computing a minimum \(s-t\) cut in an unweighted, undirected graph via cut queries. In this model, the input graph is accessed through an oracle that, given a subset of vertices \(S \subseteq V\), returns the size of the cut \((S, V\ \unicode{x005C}\ S)\).

We study the succinct representations of vertex cuts by centralized oracles and labeling schemes. For an undirected \(n\)-vertex graph \(G = (V,E)\) and integer parameter \(f \ge 1\), the goal is supporting vertex cut queries: Given \(F \subseteq V\) with \(|F| \le f\), determine if \(F\) is a vertex cut in \(G\). In the centralized data structure setting, it is required to preprocess \(G\) into an \(f\)-vertex cut oracle that can answer such queries quickly, while occupying only small space. In the labeling setting, one should assign a short label to each vertex in \(G\), so that a cut query \(F\) can be answered by merely inspecting the labels assigned to the vertices in \(F\).

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 G=(V,E) with m edges, we can add m1+o(1) “shortcut” edges E+ from the transitive closure E* of G so that G+(u,v) ≤ mo(1) for all (u,v)∈ E*, where G+=(V,E∪ E+). The conjecture was refuted by Hesse [Hesse, SODA’03], followed by significant efforts in the last few years to optimize the lower bounds.

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 vertices, m edges whose weights are integer in {−W,…,W}, our algorithm either computes all distances from a source s or reports a negative cycle in time O(m)· log(nW) time.

We show that every directed graph G with n vertices and m edges admits a directed acyclic graph (DAG) with m1+o(1) edges, called a DAG projection, that can either (1+1/polylog (n))-approximate distances between all pairs of vertices (s,t) in G, or no(1)-approximate maximum flow between all pairs of vertex subsets (S,T) in G. Previous similar results suffer a Ω(logn) approximation factor for distances [Assadi, Hoppenworth, Wein, STOC’25] [Filtser, SODA’26] and, for maximum flow, no prior result of this type is known.

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.

For n -vertex m -edge graphs with integer polynomially-bounded costs and capacities, we provide a randomized parallel algorithm for the minimum cost flow problem with \(\tilde{O}(m+n^ {1.5}) \) work and \(\tilde{O}(\sqrt {n}) \) depth. On moderately dense graphs ( m > n 1.5 ), our algorithm is the first one to achieve both near-linear work and sub-linear depth. Previous algorithms are either achieving almost optimal work but are highly sequential [18], or achieving sub-linear depth but use super-linear work [49, 62]. Our result also leads to improvements for the special cases of max flow, bipartite maximum matching, shortest paths, and reachability. Notably, the previous algorithms achieving near-linear work for shortest paths and reachability all have depth \(n^{o(1)}\cdot \sqrt {n} \) [26, 33]. Our algorithm consists of a parallel implementation of [11]. One important building block is a parallel batch-dynamic expander decomposition, which we show how to obtain from the recent parallel expander decomposition of [17]. Other versions. An extended abstract of this paper was previously published in the Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2025.

A recent breakthrough by [LNPSY STOC'21] showed that solving s-t vertex connectivity is sufficient (up to polylogarithmic factors) to solve (global) vertex connectivity in the sequential model. This raises a natural question: What is the relationship between s-t and global vertex connectivity in other computational models? In this paper, we demonstrate that the connection between global and s-t variants behaves very differently across computational models. In parallel and distributed models, we obtain almost tight reductions from global to s-t vertex connectivity. In PRAM, this leads to a $n^{ω+o(1)}$-work and $n^{o(1)}$-depth algorithm for vertex connectivity, improving over the 35-year-old $Õ(n^{ω+1})$-work $O(\mathrm{log}^2n)$-depth algorithm by [LLW FOCS'86], where $ω$ is the matrix multiplication exponent and $n$ is the number of vertices. In CONGEST, the reduction implies the first sublinear-round vertex connectivity algorithm when the diameter is moderately small. This answers an open question in [JM STOC'23]. In contrast, we show that global vertex connectivity is strictly harder than s-t vertex connectivity in the two-party communication setting, requiring $n^{1.5}$ bits of communication. The s-t variant was known to be solvable in $Õ(n)$ communication [BvdBEMN FOCS'22]. Our results resolve open problems raised by [MN STOC'20, BvdBEMN FOCS'22, AS SOSA'23]. At the heart of our results is a new graph decomposition framework we call common-neighborhood clustering, which can be applied in multiple models. Finally, we observe that global vertex connectivity cannot be solved without using s-t vertex connectivity by proving an s-t to global reduction in dense graphs in the PRAM and communication models.

Peer Reviewed

This paper presents parallel, distributed and quantum algorithms for single-source shortest paths when edges can have negative weights (negative-weight SSSP). We show a framework that reduces negative-weight SSSP in all these setting to $n^{o(1)}$ calls to any SSSP algorithm that works with a virtual source. More specifically, for a graph with $m$ edges, $n$ vertices, undirected hop-diameter $D$, and polynomially bounded integer edge weights, we show randomized algorithms for negative-weight SSSP with (i) $W_{SSSP}(m,n)n^{o(1)}$ work and $S_{SSSP}(m,n)n^{o(1)}$ span, given access to an SSSP algorithm with $W_{SSSP}(m,n)$ work and $S_{SSSP}(m,n)$ span in the parallel model, (ii) $T_{SSSP}(n,D)n^{o(1)}$, given access to an SSSP algorithm that takes $T_{SSSP}(n,D)$ rounds in $\mathsf{CONGEST}$, (iii) $Q_{SSSP}(m,n)n^{o(1)}$ quantum edge queries, given access to a non-negative-weight SSSP algorithm that takes $Q_{SSSP}(m,n)$ queries in the quantum edge query model. This work builds off the recent result of [Bernstein, Nanongkai, Wulff-Nilsen, FOCS'22], which gives a near-linear time algorithm for negative-weight SSSP in the sequential setting. Using current state-of-the-art SSSP algorithms yields randomized algorithms for negative-weight SSSP with (i) $m^{1+o(1)}$ work and $n^{1/2+o(1)}$ span in the parallel model, (ii) $(n^{2/5}D^{2/5} + \sqrt{n} + D)n^{o(1)}$ rounds in $\mathsf{CONGEST}$, (iii) $m^{1/2}n^{1/2+o(1)}$ quantum queries to the adjacency list or $n^{1.5+o(1)}$ quantum queries to the adjacency matrix. Our main technical contribution is an efficient reduction for computing a low-diameter decomposition (LDD) of directed graphs to computations of SSSP with a virtual source. Efficiently computing an LDD has heretofore only been known for undirected graphs in both the parallel and distributed models.

We present an algorithm for distributed networks to efficiently find a small vertex cut in the CONGEST model. Given a positive integer κ, our algorithm can, with high probability, either find κ vertices whose removal disconnects the network or return that such κ vertices do not exist. Our algorithm takes κ3· Õ(D+√n) rounds, where n is the number of vertices in the network and D denotes the network’s diameter. This implies Õ(D+√n) round complexity whenever κ=polylog(n).

Contention resolution on a multiple-access communication channel is a classical problem in distributed and parallel computing. In this problem, a set of nodes arrive over time, each with a message it intends to send. Time proceeds in synchronous slots, and in each slot each node can broadcast its message or remain idle. If in a slot one node broadcasts alone, it succeeds; otherwise, if multiple nodes broadcast simultaneously, messages collide and none succeeds. Nodes can differentiate collision and silence (that is, no node broadcasts) only if a collision detection mechanism is available. Ideally, a contention resolution algorithm should satisfy at least three criteria: (a) low time complexity (i.e., high throughput), meaning it does not take too long for all nodes to succeed; (b) low energy complexity, meaning each node does not make too many broadcast attempts before it succeeds; and (c) strong robustness, meaning the algorithm can maintain good performance even if interference is present. Such interference is often modeled by jamming---a jammed slot always generates collision. Previous work has shown, with collision detection, there are "perfect" contention resolution algorithms satisfying all three criteria. On the other hand, without collision detection, it was not until 2020 that an algorithm was discovered which can achieve optimal time complexity and low energy cost, assuming there is no jamming. More recently, the trade-off between throughput and robustness was studied. However, an intriguing and important question remains unknown: without collision detection, are there "perfect" contention resolution algorithms? In other words, when collision detection is absent and jamming is present, can we achieve both low total time complexity and low per-node energy cost? In this paper, we answer the above question affirmatively. Specifically, a new randomized algorithm for robust contention resolution is developed, assuming collision detection is not available. Lower bound results demonstrate it achieves both optimal time complexity and optimal energy complexity. If all nodes start execution simultaneously---which is often referred to as the "static case" in literature---another algorithm is developed that runs even faster. The separation on time complexity suggests, for robust contention resolution without collision detection, "batch" instances (that is, nodes start simultaneously) are inherently easier than "scattered" ones (that is, nodes arrive over time).

In this paper, we consider contention resolution on a multiple-access communication channel. In this problem, a set of nodes arrive over time, each with a message it intends to send. In each time slot, each node may attempt to broadcast its message or remain idle. If a single node broadcasts in a slot, the message is received by all nodes; otherwise, if multiple nodes broadcast simultaneously, a collision occurs and none succeeds. If collision detection is available, nodes can differentiate collision and silence (i.e., no node broadcasts). Performance of contention resolution algorithms is often measured by throughput---the number of successful transmissions within a period of time; whereas robustness is often measured by jamming resistance---a jammed slot always generates a collision. Previous work has shown, with collision detection, optimal constant throughput can be attained, even if a constant fraction of all slots are jammed. The situation when collision detection is not available, however, remains unclear.