Introduction

Let G = (V, E) be a directed graph with m edges, n vertices, and real-valued edge lengths ¸: E ae R. For a fixed source vertex s, the single-source shortest path (SSSP) problem is to compute either a negative length cycle in G, or the shortest-path distance from s to every other vertex in G. The textbook O(mn) time dynamic programming algorithm; discovered in the 1950's by Shimbel [19], Ford [12], Bellman [3], and Moore [17]; is a staple of introductory algorithms courses. Until very recently, it was also the fastest algorithm for this problem.

There are much faster algorithms for important special cases. When the edge weights are nonnegative, Dijkstra's algorithm takes O(m + n log n) time [9,13]. There is also a long line of research when the edge weights are integer [14,15,18,20,8,5,2,7,4,6], leading to a remarkable nearly linear running time in [4]. These algorithms all have at least a logarithmic dependence on the magnitude of the most negative edge weight.

The textbook bound of O(mn) held its ground until a recent and exciting breakthrough by Fineman [11], who gave an Õ! mn 8/9 " randomized time algorithm in the Real RAM model. ( Õ(• • •) hides log(n) factors.) Many of the interesting ideas in this work are detailed below in Section 2.

This work was inspired by [11]. Building on Fineman's ideas, we obtain:

Theorem 1.1. There is a (Las Vegas) randomized algorithm solving the SSSP problem for real-weighted graphs that runs in O 1 mn 4/5 log 2/5 n + n 9/5 log 7/5 n 2 randomized time with high probability.

The algorithm follows the same general framework laid out by [11], which eliminates negative edges incrementally along randomly sampled "independent sets" or "sandwiches" of negative edges. An interesting idea that we found useful was to focus on "proper" walks, where all the negative edges are required to be distinct, and on "proper hop distances", which consider proper walks with an exact number of negative edges (or "hops"). Morally, it is much harder for a random sample of negative edges to preserve a negative proper hop distance between two vertices, especially when the number of hops is large. This fact allows us to aggressively sample larger "sandwiches" for the same amount of e ort. We explain in greater detail below.

Preliminaries

Let G = (V, E) be a directed graph with m edges, n vertices, and real-valued edge lengths ¸: E ae R. We let k denote the number of negative edges in G. The distance from u to v is defined as the infimum length over all walks from u to v. We let d(u, v) denote the distance from u to v with respect to ¸. More generally, for vertex sets S and T , we let d(S, T ) denote the minimum distance d(s, t) over all s oe S and t oe T . {huan1754, jin453, krq}@purdue.edu. Purdue University, West Lafayette, Indiana. YH was supported in part by NSF grant IIS-2007481. PJ and KQ were supported in part by NSF grant CCF-2129816.

Vertex potentials. Given vertex potentials

for an edge e = (u, v). Johnson [16] observed that the potentials Ï(v) = d(V, v) give ¸Ï(e) Ø 0 for all e (assuming there are no negativelength cycles). We let G Ï denote the graph with edges reweighted by Ï and d Ï denote distances with respect to

¸Ï.

We say that potentials Ï are valid if ¸Ï(e) Ø 0 for all e with ¸(e) Ø 0; i.e., Ï does not introduce any new negative edges. Given two valid potentials Ï 1 and Ï 2 , max{Ï 1 , Ï 2 } and min{Ï 1 , Ï 2 } are also valid potentials. If Ï 1 is valid for G, and Ï 2 is valid for G Ï1 , then Ï 1 + Ï 2 is valid for G.

We say that Ï neutralizes a negative edge e if ¸Ï(e) Ø 0. This work, like other previous work since [15], iteratively computes and integrates valid potentials Ï that neutralize more and more negative edges, until all edges are nonnegative.

Preprocessing and negative vertices. By standard techniques, we may assume the maximum in-degree and out-degree are both O(m/n). We also preprocess the input graph G as follows [11]. For each vertex v, let

oe E} be the minimum length of the edges leaving v. Consider the graph G Õ where we:

1. Replace each vertex v with two vertices v ≠ , v + , and an arc

G Õ has similar size to G, and distances in G Õ give distances in G. Additionally, all the negative edges in G Õ have the form (v ≠ , v + ) for some vertex v. So there are at most n/2 negative edges, and each negative edge (u, v) is the unique outgoing edge of its tail u.

Henceforth we assume that G has at most n/2 negative edges, and that each negative edge (u, v) is the unique incoming edge of its head v and the unique outgoing edge of its tail u. We identify each negative edge (u, v) with its tail u, and call u a negative vertex. When there is no risk of confusion, we may reference a negative edge by its negative vertex and vice-versa. For example, we say we neutralize a negative vertex when we mean we neutralize its associated negative edge.

We let N denote the set of negative vertices in G. For a set of negative vertices S, we let G S denote the subgraph obtained by restricting the set of negative edges to those corresponding to S.

When computing Johnson's potentials Ï(v) = d(V, v), any nontrivial shortest walk to v might as well start with a negative edge. Therefore

Hop distance. The number of hops in a walk is the number of negative edges along the walk, counted with repetition. An r-hop walk is a walk with at most r negative edges. For an integer r, and vertices s, t oe V , we let d r (s, t) denote the infimum length over all r-hop walks from s to t. Hop distances obey the recurrence

Also, for r oe N and any set of vertices S, the potentials

For fixed s, and r oe N, one can compute the r-hop distance d r (s, v) for all v oe V by a hybrid of Dijkstra's algorithm and Bellman-Ford-Moore-Shimbel in O(rm + rn log n) time [10,4]. The algorithm can be inferred from (2.1): given d r (s, u) for all u, we can compute min uoeN d r (s, u) + d 1 (u, t) for all t with a single call to Dijkstra's algorithm over an appropriate auxiliary graph. By maintaining parent pointers, we can also obtain the walks supporting the r-hop distances.

More generally, hop distance can be defined with respect to any set of vertices S that contains N , and the observations above would still hold. We need this generalization for the following reason. Our algorithm, following [11], reweights the graph along multiple valid potential functions in a single iteration. The initial potential functions in an iteration are not intended to neutralize any edges but rather massage the graph for subsequent steps. However, they may incidentally neutralize some negative edges, which can decrease the hop counts of walks and disrupt various assumptions about hop distances. To avoid this, like [11], we freeze the set of negative vertices at the beginning of each iteration. During an iteration, we continue to refer to a negative vertex as negative even if its associated edge becomes nonnegative. This ensures the identity

for any potential Ï within an iteration.

Remote edges, betweenness, and sandwiches. We say that one vertex u can negatively reach another vertex v if there is a negative length walk from u to v. More specifically, we say that u can negatively reach v in h hops if there is a negative walk from u to v with at most h negative edges.

For a parameter r oe N, and a set of negative vertices U ™ V , U is r-remote if U can reach at most n/r vertices via negative r-hop paths. They are important because they can be neutralized e ciently. (As stated, [11,Lemma 3.3] reports the existence of a negative cycle, but the algorithm can easily be amended to return the negative cycle. The same comment applies to Lemma 2.2 below.)

To generate r-remote sets, [11] introduced the notions of betweenness and negative sandwiches. For a parameter r oe N, and s, t oe V , the r-betweenness is defined as the number of vertices v such that d r (s, v) + d r (v, t) < 0. [11] gave the following randomized procedure to reduce the betweenness of all pairs of vertices. " time randomized algorithm that returns either a set of valid potentials Ï or a negative cycle. With high probability, all pairs (s, t) oe V ◊ V have r-betweenness (at most) n/b with respect to ¸Ï.

[11] defines a negative sandwich as a triple (s, U, t), where s, t oe V , and U ™ N , such that d 1 (s, u) < 0 and d 1 (u, t) < 0 for all u oe U . We generalize this as follows. For a parameter h, a weak h-hop negative sandwich is a triple (s, U, t) such that d h (s, u) + d h (u, t) AE 0 for all u oe U . The following lemma, converting sandwiches into remote edges when the betweenness is low, generalizes [11, Corollary 3.9] from negative sandwiches to weak multi-hop negative sandwiches.

Lemma 2.3. Let (s, U, t) be a weak h-hop negative sandwich and let (s, t) have (r + h)-betweenness n/r. Then one can compute valid potentials

Proof. Without loss of generality, we assume all the vertices are reachable from s. (Given potentials making U r-remote in the subgraph reachable from s, assign the remaining vertices the maximum of these potentials.) Define

where (a) is because

Thus a vertex v is negatively reachable in r steps from U only if d r+h (s, v) + d r+h (v, t) < 0. There are only n/r such vertices, making U r-remote. As for the running time, it takes O((r

Sketch of [11]. To help motivate the preliminaries above, and to place ensuing ideas in their proper context, we briefly sketch the existing Õ! mn 8/9 " randomized time algorithm of [11]. Call a set of negative vertices U independent if d 1 (U, x) Ø 0 for all x oe U . If U is independent, then in the graph restricting the negative vertices to U , we have d(V, x) = d 1 (V, x) for all x. Thus an independent set can be neutralized by Johnson's technique in nearly linear time.

Suppose there are currently k negative vertices and edges in G. [11] gives a randomized algorithm that produces either an independent set or a negative sandwich of size ! k 1/3 " . The independent set can be neutralized directly in nearly linear time. To neutralize the negative sandwich with Lemma 2.1, we need the endpoints of the sandwich to have low betweenness. Thus [11] first spends Õ! mk 2/9 " time to decrease the k 1/9 -betweenness to n/k 1/9 for all pairs of vertices, before sampling the independent set or negative sandwich. Then, if the sample returns a negative sandwich, the negative sandwich is neutralized in Õ! mk 2/9 " time. One way or another, it takes Õ! mk 2/9 " time to neutralize k 1/3 negative edges. It takes Õ! mn 8/9 " randomized time overall to repeat these steps until there are no negative edges remaining.

Proper multi-hop walks

Let h oe N be a parameter to be determined. Consider the following stricter notion of hops and hop distance. We define a proper h-hop walk as a walk with exactly h negative edges and where all negative vertices are distinct. For vertices s, t, let dh (s, t) denote the infimum length over all proper h-hop walks from s to t. We call dh (s, t) the proper h-hop distance from s to t.

Computing proper hop distances is tricky because negative vertices cannot repeat. Even if there are no negative cycles, and all distances are attained by paths, standard algorithms will still want to reuse negative edges in order to meet the hop requirement. For small values of h, single-source proper h-hop distances can be computed with high probability in Õ! 2 O(h) m " randomized time using color-coding techniques [1]. Fortunately, we can sidestep computing proper h-hop distances altogether, and take h to be much larger, with the following lemma.

Lemma 3.1.

There is an O(h(m + n log n))-time algorithm that, given a set of negative vertices S, returns either a negative cycle, a pair s, t oe S with dh (s, t) < 0, or the distances d(V, t) in G S for all t oe V .

Proof. Consider the subgraph G S . We first compute d h≠1 (S, t) and d h (S, t) (and the supporting walks) for all

* for all t oe V . Otherwise, d h (S, t) < d h≠1 (S, t) AE 0 for some t oe S. Consider the h-hop walk attaining d h (S, t). We know this walk has exactly h negative edges because it has length less than d h≠1 (S, t). If some negative vertex repeats, then the cycle along the walk between occurrences must be a negative cycle, since otherwise removing the cycle would give an (h ≠ 1)-hop walk to t with length less than d h≠1 (S, t). If the negative vertices are distinct, then we have a proper h-hop walk to t with negative length, as desired.

Sampling weak negative sandwiches

Recall that weak negative sandwiches can be e ciently neutralized by the techniques in Section 2. Similar to [11], we try to find large sandwiches quickly by random sampling. We leverage proper h-hop distances to increase the size of the sandwich by a factor of ( Ô h).

Lemma 4.1. For h = (log n), there is a randomized algorithm that, in O(h(m + n log n)) randomized time, returns either a negative cycle, a weak h-hop sandwich (s, U, t), or a set of negative vertices S and the distances d(V, v) for all vertices v in the subgraph G S . With high probability, we have |U |, |S| Ø 1 Ô hk 2 (when they are returned by the algorithm). Proof. Let q = 2  k/h. Let S ™ N randomly sample each negative vertex independently with probability 1/q. S has at least k/2q = Ô kh/4 negative vertices with high probability by the multiplicative Cherno bound. Applying Lemma 3.1 to S, we obtain either (a) a negative cycle, (b) the distances d(V, t) for all vertices t in G S , or (c) a pair of s, t oe S with dh (s, t) < 0. The negative cycle and the distances are returned immediately. In the third case, we return the sandwich (s, B s,t , t), where B s,t def = ) u oe N : d h (s, u) + d h (u, t) < 0 * , in O(h(m + n log n)) time. We say that an ordered pair (s, t) is sampled by S if s oe S, t oe S, and dh (s, t) < 0 in G S . Call (s, t) weak if |B s,t | AE Ô kh, and strong otherwise. We claim that with high probability no weak pairs are sampled by S. This is where proper hop distance comes to the fore: any proper h-hop walk from s to t with negative length must include at least h ≠ 1 vertices from B s,t \ {s, t}. For fixed s, t, |B s,t fl S| is a sum of independent {0, 1}-random variables. If (s, t) is weak, then this sum has mean at most h/2. Since h = (log n), by the multiplicative Cherno bound, |B s,t fl S| AE h, hence (s, t) is not sampled, with high probability. By the union bound, S samples at least Ô kh/4 negative vertices and no weak pairs with high probability. Then |S| and |B s,t | (when available) both have the desired size. 5 Putting it all together We now present the overall algorithm and analysis, combining ingredients from Section 2 with the new sampling techniques from Section 4. Theorem 5.1. There is a (Las Vegas) randomized algorithm solving the SSSP problem for real-weighted graphs that runs in O 1 mn 4/5 log 2/5 n + n 9/5 log 7/5 n 2 randomized time with high probability. Proof. The algorithm iteratively tries to compute valid potentials Ï that neutralizes some of the remaining negative edges, until no negative edges remain. We describe a single iteration. Suppose there are k negative edges. We assume that k = ! log 7 n " , since otherwise we can use Johnson's technique with k-hop distances in O(k(m + n log n)) time. Let h = k 1/5 / log 2/5 n = (log n). By Lemma 2.2, in O ! h 2 (m log n + n log 2 n) " time, we compute either a negative cycle (and halt) or compute valid potentials Ï 1 that, with high probability, reduce the O(h)-betweenness of all pairs of vertices to n/h. Henceforth we work in G Ï1 . Next we invoke Lemma 4.1. If it returns a negative cycle then we halt. If it returns a set of negative vertices S, and all the Johnson potentials Ï 2 (v) = d(V, v) in G S , then we re-weight the graph with Ï 2 and neutralize S. Otherwise we obtain a weak h-hop negative sandwich (s, U, t). If the betweenness-reduction succeeded, then by Lemma 2.3, we either return a negative cycle or compute potentials Ï 2 that make U h-remote in O(h(m + n log n)) time. Note that we can test if U is indeed h-remote in the same amount of time. If not, then the betweennessreduction failed, and we restart the iteration. Otherwise, by Lemma 2.1, we either find a negative cycle (and halt) or compute potentials Ï 3 neutralizing U (in G Ï1+Ï2 ) in O((h + |U |/h)(m + n log n)) time. Altogether, with high probability of success, and in O !! h 2 log n + ¸/h " (m + n log n) " randomized time, we either neutralize ¸= 1 Ô kh 2 negative edges, or return a negative cycle. Starting from at most n negative vertices, it takes O 1  n/h log n 2 successful iterations to reduce the number of negative vertices to O ! log 7 n " . By the union bound, all the iterations succeed with high probability. The running time is dominated by the time spent to reduce the number of negative vertices by half. Thus the overall running time is O !! n 1/2 h 3/2 log n + n/h " (m + n log n) " = O 1 mn 4/5 log 2/5 n + n 9/5 log 7/5 n 2 with high probability.