# A Deterministic Parallel APSP Algorithm and its Applications

Adam Karczmarz<EMAIL_ADDRESS>Supported by ERC Consolidator Grant
772346 TUgbOAT, the Polish National Science Centre 2018/29/N/ST6/00757 grant,
and by the Foundation for Polish Science (FNP) via the START programme.
Institute of Informatics, University of Warsaw, Poland  Piotr Sankowski
<EMAIL_ADDRESS>Supported by ERC Consolidator Grant 772346 TUgbOAT.
Institute of Informatics, University of Warsaw, Poland

###### Abstract

In this paper we show a deterministic parallel all-pairs shortest paths
algorithm for real-weighted directed graphs. The algorithm has
$\widetilde{O}(nm+(n/d)^{3})$ work and $\widetilde{O}(d)$ depth for any depth
parameter $d\in[1,n]$. To the best of our knowledge, such a trade-off has only
been previously described for the real-weighted single-source shortest paths
problem using randomization [Bringmann et al., ICALP‘17]. Moreover, our result
improves upon the parallelism of the state-of-the-art randomized parallel
algorithm for computing transitive closure, which has
$\widetilde{O}(nm+n^{3}/d^{2})$ work and $\widetilde{O}(d)$ depth [Ullman and
Yannakakis, SIAM J. Comput. ‘91].

Our APSP algorithm turns out to be a powerful tool for designing efficient
planar graph algorithms in both parallel and sequential regimes. By suitably
adjusting the depth parameter $d$ and applying known techniques, we obtain:

  1. (1)

nearly work-efficient $\widetilde{O}(n^{1/6})$-depth parallel algorithms for
the real-weighted single-source shortest paths problem and finding a bipartite
perfect matching in a planar graph,

  2. (2)

an $\widetilde{O}(n^{9/8})$-time sequential strongly polynomial algorithm for
computing a minimum mean cycle or a minimum cost-to-time-ratio cycle of a
planar graph,

  3. (3)

a slightly faster algorithm for computing so-called external dense distance
graphs of all pieces of a recursive decomposition of a planar graph.

One notable ingredient of our parallel APSP algorithm is a simple
deterministic $\widetilde{O}(nm)$-work $\widetilde{O}(d)$-depth procedure for
computing $\widetilde{O}(n/d)$-size hitting sets of shortest $d$-hop paths
between all pairs of vertices of a real-weighted digraph. Such hitting sets
have also been called $d$-hub sets. Hub sets have previously proved especially
useful in designing parallel or dynamic shortest paths algorithms and are
typically obtained via random sampling. Our procedure implies, for example, an
$\widetilde{O}(nm)$-time deterministic algorithm for finding a shortest
negative cycle of a real-weighted digraph. Such a near-optimal bound for this
problem has been so far only achieved using a randomized algorithm [Orlin et
al., Discret. Appl. Math. ‘18].

##  1 Introduction

The _all-pairs shortest paths problem_ (APSP) is one of the most fundamental
graph problems. It has been studied in numerous variants, for many
computational models and graph classes. In this paper we study the APSP
problem on real-weighted, possibly sparse graphs in the parallel setting.

The efficiency of a parallel algorithm is usually characterized using the
notions of _work_ and _depth_ (also called  _span_ or  _time_). The work is
the total number of primitive operations performed. The depth is the longest
chain of sequential dependencies between these operations. A parallel
algorithm of work $W(n)$ and depth $D(n)$ (where $n$ is the problem size) can
be generally scheduled to run in $\widetilde{O}(D(n))$ time using
$\widetilde{O}(W(n)/D(n))$ processors [10], where the $\widetilde{O}(\cdot)$
notation suppresses $O(\operatorname{polylog}{n})$ factors. The quantity
$W(n)/D(n)$ is often called the _parallelism_ of a parallel algorithm. An
algorithm is called _nearly work-efficient_ if $W(n)=\widetilde{O}(T(n))$,
where $T(n)$ is the best known time bound needed to solve the problem using a
sequential algorithm.

There exists a very simple folklore parallel algorithm for the APSP problem
via repeatedly squaring the weighted adjacency matrix using min-plus product.
It has $\widetilde{O}(n^{3})$ work and $O(\operatorname{polylog}{n})$ depth.
This can be slightly tweaked to obtain polylogarithmic-factor improvement in
work and depth [25]. However, these algorithms are nearly work-efficient only
for dense graphs since the best known sequential algorithms run in
$\widetilde{O}(nm)$ time [30, 54]. Hence, we are missing APSP algorithms
competitive with the state-of-the-art sequential algorithms even for
moderately dense graphs.

Dealing with sparser graphs in the parallel setting turns out to be a much
more challenging task even for an easier problem of computing the transitive
closure. To the best of our knowledge, the state-of-the-art for parallel
transitive closure for sparse graphs is the classical tradeoff of Ullman and
Yannakakis [60]. They showed a Monte Carlo randomized parallel algorithm with
$\widetilde{O}(nm+n^{3}/d^{2})$ work and $\widetilde{O}(d)$ depth for any
parameter $d\in[1,n]$. Hence, their algorithm is nearly work-efficient for
$d=\widetilde{\Omega}(n/\sqrt{m})$ and can achieve parallelism of order
$\widetilde{O}(m^{3/2})$ while being nearly work-efficient.

###  1.1 Our Results and Related Work

Our main result is a _deterministic_ parallel all-pairs shortest paths
algorithm for _real-weighted_ directed graphs that improves upon the 30-year-
old randomized transitive closure trade-off of [60].

######  Theorem 1.

Let $G$ be a real-weighted digraph. For any $d\in[1,n]$, there exists a
deterministic parallel algorithm computing all-pairs shortest paths in $G$
with $\widetilde{O}(nm+(n/d)^{3})$ work and $\widetilde{O}(d)$ depth.

Observe that our algorithm is nearly work-efficient for
$d=\Omega(n^{2/3}/m^{1/3})$, which is $\Omega(n^{1/3})$ for sparse graph. As a
result, as long as the number of used processors is
$p=\widetilde{O}(n^{1/3}m^{4/3})$, we can compute all-pairs shortest paths in
$\widetilde{O}(nm/p)$ parallel time. To the best of our knowledge, such a
tradeoff for _real-weighted_ digraphs has only been achieved for _single-
source shortest paths_ (SSSP) and _negative cycle detection_ problems [11].
Both of these results require randomization, whereas our algorithm is
deterministic. Bringmann et al. [11] also show a deterministic variant of
their algorithm with work $\widetilde{O}(nmd+(n/d)^{3})$ that is not nearly
work-efficient unless the graph is dense.111Bringmann et al. [11, Theorem 19]
mistakenly state the work of their algorithm to be
$\widetilde{O}(nm+(n/d)^{3}+n^{2}d)$ – even though in Section 4.1.2 they
correctly bound the work in the first step of their algorithm to be
$\Theta(nmd)$.

In the aforementioned previous results [60, 11], randomization is used only
for computing a small subset of $V$ that is, roughly speaking, guaranteed to
contain some vertex of each ’’long‘‘ shortest path consisting of at least $h$
hops. Following [33], we call such set a $h$-hub set of $G$ (a formal
definition is deferred to Section 3)222Zwick [66] uses the name _bridging set_
for an analogous concept. Some works also use the term _hitting set_ , but
hitting set is a more general notion, which in our paper is used in multiple
different contexts.. A classical argument of Ullman and Yannakakis [60] shows
that a randomly sampled $\Theta((n/h)\cdot\log{n})$-size subset of $V$
constitutes an $h$-hub set with high probability.

We show that for any $h\in[1,n]$, an $h$-hub set of size $\widetilde{O}(n/h)$
can be computed deterministically using $\widetilde{O}(nm)$ work and
$\widetilde{O}(h)$ depth. Our procedure works in presence of negative edge
weights and even – to some extent – when negative cycles are allowed. The
constructed hub set is guaranteed to hit all-pairs shortest $h$-hop paths
(which are well-defined regardless of whether the APSP problem is feasible)
unless the shortest (in terms of hops) negative cycle has at most $h$ edges.
As a by-product, we also obtain the following result in the sequential regime.

######  Theorem 2.

Let $G$ be a real-weighted directed graph. A shortest (in terms of hops)
negative-weight cycle in $G$ can be found deterministically in
$O(nm\log^{2}{n})$ time.

So far, an $\widetilde{O}(nm)$ bound for the shortest negative cycle problem
has only been obtained using a randomized algorithm by Orlin et al. [53]333The
algorithm of [53] runs in $O(nm\log{n})$ expected time. However, if one aims
at high-probability correctness, its running time is $O(nm\log^{2}{n})$ which
matches our bound.. The best known deterministic algorithms [57, 58] require
$\widetilde{\Omega}(n^{3})$ worst-case time. One can easily argue that our
bound is the best possible, up to polylogarithmic factors, unless an
unexpected algorithmic breakthrough is made, that would imply progress for
other core problems as well. In particular, the shortest negative cycle
captures the unweighted directed girth problem (for which the trivial $O(nm)$
bound stands for decades). Moreover, one should not hope for an
$O(n^{3-\epsilon})$ fast matrix multiplication-based algorithm since the
shortest negative cycle problem also captures the negative triangle detection
problem known to be subcubic-equivalent to the APSP problem [64].

We believe that our procedure for computing hub sets might be useful in
obtaining other deterministic sequential and parallel algorithms. As a direct
application of our APSP algorithm one can obtain, e.g., more efficient
parallel algorithms for computing closeness centrality [4]. Moreover, as shown
below, we can use it to improve algorithms for several planar graph problems.

####  1.1.1 Applications for planar graphs

##### Nearly work-efficient parallel algorithms.

Theorem 1 can be used to highly parallelize the framework used by
Fakcharoenphol and Rao [20] to obtain nearly optimal algorithms for two
fundamental planar graph problems.

######  Theorem 3.

Let $G$ be a real-weighted planar digraph. There exists a deterministic
parallel algorithm for negative cycle detection and single-source shortest
paths in $G$ with $\widetilde{O}(n)$ work and $\widetilde{O}(n^{1/6})$ depth.

By a well-known duality-based reduction [50], this also implies _feasible
flow_ and _bipartite perfect matching_ algorithms with the same bounds. It is
worth noting that even though there exist $O(\operatorname{polylog}n)$ depth
algorithms (i.e., belonging to NC class) for finding perfect matchings in
bipartite planar graphs, they are very far from being work-efficient [50, 47].
The same applies to the $\widetilde{O}(\sqrt{n})$-depth algorithm implied by
the interior-point method-based result for general graphs [24]. Since the
$s,t$-max flow problem on planar graphs with capacities $[1,C]$ can be reduced
to $O(\log{C})$ feasible flow computations [50], this also yields a nearly
work-efficient $\widetilde{O}(n^{1/6})$-depth algorithm for maximum $s,t$-flow
with polynomially bounded capacities. Similar bounds can be obtained for the
related _replacement paths_ problem using the recent reduction [16] to the
all-edge shortest cycles problem (see Section 4.2 and Appendix A).

To the best of our knowledge, the parallel complexity of the aforementioned
problems on planar graphs has not achieved much attention in recent years.
However, one can easily obtain near-optimal work and
$\widetilde{O}(\sqrt{n})$-depth algorithm for these problems using the
breakthrough framework of Fakcharoenphol and Rao [20]. In this framework, one
repeatedly computes all-pairs shortest paths on certain _dense distance
graphs_ using multiple runs of a clever implementation of Dijkstra‘s algorithm
(so-called FR-Dijkstra). Unfortunately, it is not clear how to break the
$\Omega(\sqrt{n})$ depth bound this way since Dijkstra‘s algorithm is
inherently sequential. Our improved depth bound is obtained by replacing the
simple-minded Dijkstra-based APSP algorithm with that of Theorem 1. As we
show, the Monge property of dense distance graphs that is crucial for the
efficiency of FR-Dijkstra can also be employed in our algorithm to yield a
significant parallel speed-up.

##### Minimum mean and cost-to-time ratio cycle problems.

By plugging in our parallel negative cycle detection algorithm into Megiddo‘s
_parametric search_ framework [48] we obtain improved _strongly polynomial_
algorithms for the minimum mean cycle and minimum cost-to-time ratio
cycle444Also known as the _minimum ratio cycle_ problem. problems on planar
graphs (for formal definitions of these problems, refer to Section 4.3).

######  Theorem 4.

Let $G$ be a real-weighed planar graph. There exists an
$\widetilde{O}(n^{9/8})$-time strongly polynomial algorithm for computing a
minimum ratio cycle (and thus also a minimum mean cycle) in $G$.

The minimum mean cycle and minimum cost-to-time ratio cycle problems are
classical graph problems studied since the seventies. They are used to
construct strongly polynomial algorithms for computing minimum-cost flows
[59]. Moreover, via the cut-cycle duality in planar graphs, both problems have
found practical applications in the area of image segmentation [29, 61, 62,
63]

It is known that both problems can be reduced to negative cycle detection via
binary search [42]. However, this way we can obtain only weakly polynomial
time algorithms with running times dependent on the magnitude of edge weights.
For general graphs, the classical algorithm of Karp [34] solves the minimum
mean cycle problem in $O(nm)$ time, matching the best known strongly
polynomial negative cycle detection bound achieved by the Bellman-Ford
algorithm. Karp‘s algorithm (and other minimum mean cycle algorithms for
general graphs [26, 65]) operates on limited-hop shortest paths. As a result
it is not clear how to take advantage of planarity to speed it up555At-
most-$h$-hop shortest paths connecting pairs of vertices of a single face of a
plane graph do not seem to admit algorithmically useful properties, like the
non-crossing property of usual shortest paths..

The $\widetilde{O}(nm)$ bound has not been matched to date for the more
general minimum cost-to-time ratio problem which seems to be the original
inspiration for the invention of the parametric search technique [48] that
later found other applications (e.g., [1]). This technique can be used to
convert an efficient parallel negative cycle detection algorithm into a
strongly polynomial minimum ratio cycle algorithm. The best known strongly
polynomial $\widetilde{O}(m^{3/4}n^{3/2})$ bound for the minimum ratio cycle
problem is due to Bringmann et al. [11] and also follows by plugging their
aforementioned parallel negative cycle detection algorithm into Megiddo‘s
framework.

It seems that no strongly polynomial algorithms for the minimum mean cycle
problem to date have been designed specifically for planar graphs. However, by
plugging in previously known parallel negative cycle detection algorithms [20,
44] into the parametric search framework, one would only obtain
$\widetilde{O}(n^{3/2})$-time strongly polynomial algorithms. Theorem 4
improves upon this significantly.

##### Computing external dense distance graphs.

Finally, our parallel APSP algorithm can be used to improve the bound for
computing so-called _external dense distance graphs_ wrt. a planar graph‘s
recursive decomposition – an important black box with applications in
computing maximum flows [46], minimum cuts [9], and constructing distance
oracles [14, 15, 51].

Suppose a planar graph $G$ is recursively decomposed using small cycle
separators [49] of size $O(\sqrt{n})$ until the obtained pieces have constant
size. The decomposition procedure produces a binary tree $\mathcal{T}(G)$
whose nodes correspond to subgraphs of $G$ (_pieces_). The _boundary vertices_
$\partial{H}$ of a piece $H\in\mathcal{T}(G)$ are vertices that $H$ shares
with the remaining part $G-H$ of the entire graph $G$. We denote by $DDG_{H}$
the _dense distance graph_ – a complete weighted graph on $\partial{H}$ whose
edge weights represent distances between all pairs of vertices of
$\partial{H}$ in $H$. Efficient construction of piecewise DDGs and FR-Dijkstra
alone are enough to obtain e.g., nearly linear-space static and dynamic exact
distance oracles with sublinear query time [20, 31, 37]. Originally,
Fakcharoenphol and Rao [20] gave an $O(n\log^{3}{n})$ algorithm for computing
each of the graphs $DDG_{H}$, $H\in\mathcal{T}(G)$, inductively, based on the
children graphs $DDG_{H_{1}},DDG_{H_{2}}$. The key ingredient in their
algorithm was the aforementioned fast implementation of Dijkstra‘s algorithm
on a dense distance graph.

Later, Klein [37] showed a more efficient, $O(n\log^{2}{n})$-time algorithm
that computed every $DDG_{H}$ directly, by building the so-called multiple-
source shortest paths (MSSP) data structure for each piece
$H\in\mathcal{T}(G)$ separately. This was possible since the total size of all
pieces $H$ of the decomposition is $O(n\log{n})$. However, some important
applications [14, 15, 9, 46, 51] also require _external_ graphs $DDG_{G-H}$
representing distances between $\partial{H}$ in the complement graph $G-H$
(for all $H\in\mathcal{T}(G)$). In this case Klein‘s approach fails since the
total size of all possible graphs $G-H$ is $\Omega(n^{2})$. Instead, one has
to stick to the original inductive method of [20] and compute each
$DDG_{G-H_{i}}$ based on $DDG_{G-H}$ and $DDG_{H_{3-i}}$ (where, again, $H$ is
a parent of $H_{1},H_{2}$ in $\mathcal{T}(G)$). This takes $O(n\log^{3}{n})$
time through all $H$. We show that our parallel APSP algorithm can be used to
obtain an algorithm whose running time almost matches the $O(n\log^{2}{n})$
MSSP-based bound.

######  Lemma 5.

The external dense distance graphs $DDG_{G-H}$ for all $H\in\mathcal{T}(G)$
can be computed in $O(n\log^{2}{n}\cdot\log\log{n}\cdot\alpha(n))$ time.

###  1.2 Further Related Work

For general directed graphs, the parallel _single-source shortest paths_
problem (SSSP) is much better understood. Ullman and Yannakakis [60] showed an
$\widetilde{O}(m\sqrt{n})$-work algorithm with $\widetilde{O}(\sqrt{n})$ depth
for unweighted digraphs. Besides the aforementioned result of Bringmann et al.
[11] and $\widetilde{\Theta}(n)$-depth parallel implementations of Dijkstra‘s
algorithm [12], all known parallel exact SSSP algorithms work for weighted
graphs with _non-negative_ and _integral_ weights bounded by $W$ and are
weakly polynomial. Klein and Subramanian [41] generalized the bound of [60] to
the weighted setting at the cost of $\widetilde{O}(\log{W})$ factor in
work/depth bounds. In this setting, they also gave a nearly work-efficient
polylog-depth algorithm for planar graphs [40]. Spencer [56] gave a trade-off
algorithm with $\widetilde{O}((n^{3}/d^{2}+m)\log{W})$ work and
$\widetilde{O}(d)$ depth. Forster and Nanongkai [22] in turn have recently
shown a trade-off algorithm with $\widetilde{O}((md+mn/d+(n/d)^{3})\log{W})$
work and $\widetilde{O}(d)$ depth.

Recently, following similar results for single-source reachability [21, 45],
Cao et al. [13] showed that $(1+\epsilon)$-approximate single-source shortest
paths can be found using near-optimal work $\widetilde{O}(m\log{W})$ and
$\widetilde{O}(n^{1/2+o(1)})$ depth. Note that this SSSP algorithm, if run
from every source, yields a nearly work-efficient (approximate) APSP
algorithm, but with polynomially worse depth than ours.

Finally, parallel single-source shortest paths problems in _undirected_ graphs
have also received much attention, both in the exact [8, 18, 55] and the
approximate [3, 19, 43] setting.

###  1.3 Technical Overview

Our parallel APSP algorithm is based on the techniques used in the state-of-
the-art Monte Carlo randomized decremental all-pairs shortest paths algorithm
for weighted digraphs, due to Bernstein [7]. Without loss of generality assume
that our depth parameter is a power of two, i.e., $d=2^{K}$. Our algorithm
makes use of a _hierarchy_ of hub sets
$V=H_{1},H_{2},\ldots,H_{2^{i}},\ldots,H_{d}\subseteq V$ such that each
$H_{2^{i}}$ is a $2^{i}$-hub set of $G$ and has size $O((n/2^{i})\log{n})$.
Roughly speaking, this means that for all pairs $u,v\in V$, some shortest
$u\to v$ path, if it consists of at least $2^{i}$ edges, contains a vertex of
$H_{2^{i}}$.

Let us start with describing a randomized version of our algorithm. A well-
known fact attributed to Ullman and Yannakakis [60] states that picking each
$H_{2^{i}}$ to be a random $\Theta((n/2^{i})\cdot\log{n})$-subset of $V$
guarantees that $H_{2^{i}}$ forms a $2^{i}$-hub-set of $G$ with high
probability.

Rather than using the inherently sequential Dijkstra‘s algorithm, as
sequential $\widetilde{O}(nm)$-time APSP algorithms [30, 54] do, we rely
exclusively on the Bellman-Ford algorithm. A variant of Bellman-Ford
algorithm, given a source $s$, maintains _distance labels_ and performs a
number of _steps_ relaxing all edges in arbitrary order in $O(m)$ time. After
$k$ steps, the distance label of $v\in V$ is equal to the length
$\delta_{G}^{k}(s,v)$ of a shortest at-most-$k$-hop path from $s$ to $v$. In a
single step, for each vertex we need to combine edge relaxations ending in
this vertex, so a single step requires $O(\operatorname{polylog}{n})$ depth.
Consequently, performing $k$ steps of Bellman-Ford requires $O(mk)$ work but
only $\widetilde{O}(k)$ depth.

The key idea behind Bernstein‘s algorithm [7] is that computing shortest paths
$\delta_{G}(u,v)$ for $(u,v)\in H_{2^{i}}\times V$ can be reduced to computing
_at-most- $2^{i+1}$-hop_ shortest paths on a graph $G_{i,s}$ obtained from $G$
by augmenting it with $|H_{2^{i+1}}|=O(n)$ auxiliary edges $st$ for all $t\in
H_{2^{i+1}}$, such that the weight of $st$ equals the distance
$\delta_{G}(s,t)$ from $s$ to $t$. This idea suggests an inductive algorithm
that, given distances for all pairs in $(H_{2^{i+1}}\times V)\cup(V\times
H_{2^{i+1}})$, where $i<K$, lifts them to distances for all pairs in
$(H_{2^{i}}\times V)\cup(V\times H_{2^{i}})$ using $|H_{2^{i}}|$ parallel
$2^{i+1}$-step Bellman-Ford runs. These can be performed in
$O(|H_{2^{i}}|\cdot 2^{i}\cdot m)=O(nm\log{n})$ work and
$\widetilde{O}(2^{i})$ depth. Eventually, since $H_{1}=V$, we obtain the all-
pairs distances in $G$. Summing through all inductive steps, the work is
$O(nm\log{n}\log{d})$, whereas the depth is
$\widetilde{O}\left(2^{1}+\ldots+2^{K}\right)=\widetilde{O}\left(2^{K}\right)=\widetilde{O}(d)$.

The last thing missing in the above algorithm is the induction base, i.e.,
computing $\delta_{G}(s,t)$ for all $s,t\in H_{d}$ in only $\widetilde{O}(d)$
depth.666The all-pairs distances for $H_{d}$ can be lifted to distances for
all pairs in $(H_{d}\times V)\cup(V\times H_{d})$ using $\widetilde{O}(nm)$
work and $\widetilde{O}(d)$ depth as in the inductive step by setting
$H_{2d}:=H_{d}$. This is where we depart from Bernstein‘s approach [7]. Note
that lengths $\delta_{G}^{d+1}(s,t)$ of shortest at-most-$(d+1)$ hop paths
from all $s\in H_{d}$ can be computed using $(d+1)$-step parallel Bellman-Ford
using $O(|H_{d}|dm)=O(nm\log{n})$ work and $\widetilde{O}(d)$ depth. In order
to combine these bounded-hop lengths into actual distances between $s,t\in
H_{d}$, we switch to the repeated-squaring algorithm for dense graphs, as was
also done in the parallel SSSP [11] and transitive closure [60]
algorithms.777The same strategy of switching to a dense-graph algorithm has
also proved useful in obtaining a deterministic incremental algorithm for APSP
in weighted directed graphs [33]. Namely, we run this algorithm on a complete
graph $G_{d}$ on $H_{d}$ whose edge $uv$ has weight $\delta_{G}^{d+1}(u,v)$.
The correctness of this approach follows by observing that a shortest $s\to t$
path that uses more than $d+1$ hops has to encounter an intermediate vertex
$z\in H_{d}$ after no more than $d+1$ hops. The
$O(\operatorname{polylog}{n})$-depth repeated-squaring algorithm adds an
$\widetilde{O}((n/d)^{3})$ term to the work but does not increase the depth,
up to polylogarithmic factors.

##### Computing hub sets deterministically.

Now let us briefly describe how to derandomize the above parallel APSP
algorithm by replacing sampling with a deterministic preprocessing step that
computes all hub sets $H_{1},\ldots,H_{d}$ within $\widetilde{O}(nm)$ work and
$\widetilde{O}(d)$ depth.

Previous results in the parallel and dynamic graph algorithms literature [11,
33, 35] that used deterministic $h$-hub sets typically obtained them by (1)
computing (or maintaining – in the dynamic setting) at-most-$h$-hop shortest
paths between all pairs of vertices $s,t\in V$, and (2) running a greedy
$O(\log{n})$-approximation algorithm for computing a $O((n/h)\log{n})$-size
hitting set of a family of $h$-element subsets of an $n$-element universe (see
e.g., [35] for analysis). Unfortunately, the first step of this approach seems
to require $\Omega(nmh)$ time.

To obtain an improved bound, we reuse the inductive approach. Specifically, we
show that given a hub set $H_{2^{i}}$, one can obtain a $2^{i+1}$-hub set
$H_{2^{i+1}}$ of size $O((n/2^{i})\cdot\log{n})$ by running the aforementioned
greedy hitting set algorithm on shortest $2^{i}$-hop paths from
$H_{2^{i}}$888A somewhat similar trick has been used in [33] for improving the
state-of-the-art randomized partially dynamic APSP algorithms [7, 5] from
Monte Carlo to Las Vegas.. Constructing these paths using Bellman-Ford costs
$O(|H_{2^{i}}|\cdot 2^{i}\cdot m)=O(nm\log{n})$ time and requires
$\widetilde{O}(2^{i})$ depth. Luckily, the deterministic greedy hitting set
algorithm has its nearly work-efficient parallel version with
$O(\operatorname{polylog}{n})$ depth [6]. Therefore, one can construct $H_{d}$
using $\widetilde{O}(nm)$ work and $\widetilde{O}(d)$ depth.

It is worth noting that the analysis of the above algorithm breaks if the
shortest negative cycle in $G$ has at most $d$ edges. We stress that this is
not a problem for the APSP application though, since any negative cycles in
$G$ make the APSP problem infeasible. That being said, our deterministic hub
set algorithm can be easily extended to correctly report the shortest negative
cycle within the same bounds and thus match the randomized bound of [53] for
the shortest negative cycle problem.

We also remark that even though the hub sets are very useful in designing
dynamic graph algorithms, it is unlikely that our construction can help match
the best known randomized bounds for dynamic problems (like [7]) using
deterministic algorithms. The power of a randomly sampled hub set $H$ (and,
possibly, the so-called _oblivious adversary_ assumption) lies in the fact
that $H$ retains its guarantees through all, in particular _future_ , versions
of a dynamic graph.

##### Comparison to the transitive closure algorithm of [60].

Ullman and Yannakakis [60] use a single randomly sampled $d$-hub set $H_{d}$
of size $O((n/d)\log{n})$. In similar way they compute reachability between
the nodes of $H_{d}$ in $\widetilde{O}(nm+(n/d)^{3})$ work and
$\widetilde{O}(d)$ depth – they first apply limited-depth BFS from all
$H_{d}$, and then use repeated squaring. Adding the $\widetilde{O}((n/d)^{2})$
’’shortcuts‘‘ between $H_{d}$ to $G$ reduces $G$‘s diameter to
$\widetilde{O}(d)$. Finally, a limited-depth BFS is run from each source in
parallel. Since the augmented graph has $\widetilde{O}(m+(n/d)^{2})$ edges,
this takes $\widetilde{O}(nm+n^{3}/d^{2})$ work and $\widetilde{O}(d)$ depth.
The efficiency of this approach crucially relies on the fact that BFS has
near-linear work and, as a result, does not generalize to real-weighted graphs
which require using Bellman-Ford.

##### Planar graph applications.

All of the numerous consequences of our parallel APSP algorithm for planar
graphs essentially follow by showing improved parallel and sequential bounds
for the following problem, which we call _dense distance graph APSP_ (DDG
APSP).

Let $H_{1},H_{2}\in\mathcal{T}(G)$ be two pieces of a recursive decomposition
of $G$ and let $b=|\partial{H_{1}}|+|\partial{H_{2}}|$. We would like to
compute all-pairs shortest paths in the graph $DDG_{H_{1}}\cup DDG_{H_{2}}$.

A parallel algorithm solving the above problem using $T(b,d)=\Omega(b^{2})$
work and $\widetilde{O}(d)$ depth, plugged in the framework of Fakcharoenphol
and Rao [20], implies:

  * •

An $\widetilde{O}\left(n+T(\sqrt{n},d)\right)$-work and
$\widetilde{O}(d)$-depth algorithm for negative-cycle detection on real-
weighted planar graphs. Via known reductions [50, 16], the same bound can be
achieved for the feasible flow, bipartite perfect matching, and replacement
paths problems.

  * •

$\widetilde{O}\left(nd+T(\sqrt{n},d)\right)$-time sequential strongly
polynomial algorithms for minimum mean and minimum cost-to-time ratio cycle
problems.

Moreover, a sequential algorithm solving the DDG APSP problem in
$S(b)=\Omega(b^{2})$ time implies an $O(S(\sqrt{n})\log{n})$ algorithm for
computing all external dense distance graphs $DDG_{G-H}$ for
$H\in\mathcal{T}(G)$.

Fakcharoenphol and Rao‘s [20] algorithm for solving DDP APSP uses Johnson‘s
[30] approach: first a feasible price function is computed using Bellman-Ford
algorithm to reduce the task to the non-negatively weighted case.
Subsequently, Dijkstra‘s algorithm is run from each of $\Omega(b)$ sources.
Fakcharoenphol and Rao gave a very efficient Dijkstra implementation running
in $O(b\log^{2}{b})$ time on $DDG_{H_{1}}\cup DDG_{H_{2}}$. They also showed
that a single step of Bellman-Ford can be performed on $DDG_{H_{1}}\cup
DDG_{H_{2}}$ in $O(b\log{b})$ time. Klein et al. [39] later noticed that a
Bellman-Ford step can be performed in $O(b\cdot\alpha(b))$ time. By these
bounds, the dense distance graph APSP can be solved sequentially in
$O(b^{2}\log{b})$ time and using a parallel algorithm with
$\widetilde{O}(b^{2})$ work and $\widetilde{O}(b)$ depth.

We show that the dense distance graph APSP problem can be solved using a
parallel algorithm with work $\widetilde{O}(b^{2}+(b/d)^{3})$ and depth
$\widetilde{O}(d)$. This essentially follows by using a more efficient
parallel implementation of a Bellman-Ford step in the algorithm of Theorem 1.
As observed in [20], a Bellman-Ford step on a dense distance graph can be
rephrased as computing column minima of a certain matrix with Monge property
(a _Monge matrix_ , in short). Since column minima of a Monge matrix can be
computed using a polylogarithmic time parallel algorithm [2], a single
Bellman-Ford step can be implemented using only $\widetilde{O}(b)$ work and
$O(\operatorname{polylog}{n})$ depth, even though $DDG_{H_{1}}\cup
DDG_{H_{2}}$ has $\Omega(b^{2})$ edges.

Moreover, we show a faster sequential algorithm for DDG APSP with
$O(b^{2}\log{b}\cdot\log{\log{b}}\cdot\alpha(b))$ running time. First, we
observe that our parallel APSP algorithm (given a feasible price function) has
a sequential implementation with
$O\left(n\cdot\mathcal{B}(n,m)\cdot\log{n}\cdot\log{d}+\left(\frac{n}{d}\log{n}\right)\cdot\mathcal{D}(n,m)\right)$
time, where $\mathcal{B}(n,m)$ denotes the cost of a single Bellman-Ford step,
and $\mathcal{D}(n,m)$ denotes the cost of a single Dijkstra step (on a graph
with $n$ vertices and $m$ edges). Second, we leverage the asymmetry between
the $O(b\cdot\alpha(b))$ cost of a Bellman-Ford step and the $O(b\log^{2}{b})$
cost of running FR-Dijkstra on $DDG_{H_{1}}\cup DDG_{H_{2}}$. To obtain our
improved bound, it is enough to choose $d=\log^{2}{b}$.

##  2 Preliminaries

In this paper we deal with _real-weighted directed_ graphs. We write $V(G)$
and $E(G)$ to denote the sets of vertices and edges of $G$, respectively. A
graph $H$ is a _subgraph_ of $G$, which we denote by $H\subseteq G$, if and
only if $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$. We write $uv\in E(G)$
when referring to edges of $G$ and use $w_{G}(uv)$ to denote the weight of
$uv$. If $uv\notin E$, we assume $w_{G}(uv)=\infty$.

A sequence of edges $P=e_{1}\ldots e_{k}$, where $k\geq 1$ and
$e_{i}=u_{i}v_{i}\in E(G)$, is called an $s\to t$ path in $G$ if $s=u_{1}$,
$v_{k}=t$ and $v_{i-1}=u_{i}$ for each $i=2,\ldots,k$. For brevity we
sometimes also express $P$ as a sequence of $k+1$ vertices $u_{1}u_{2}\ldots
u_{k}v_{k}$ or as a subgraph of $G$ with vertices
$\\{u_{1},\ldots,u_{k},v_{k}\\}$ and edges $\\{e_{1},\ldots,e_{k}\\}$. The
_hop-length_ $|P|$ is equal to the number of edges in $P$. We also say that
$P$ is a _$k$ -hop path_. The _length_ of the path $\ell(P)$ is defined as
$\ell(P)=\sum_{i=1}^{k}w_{G}(e_{i})$. For convenience, we sometimes consider a
single edge $uv$ as a path of hop-length $1$. If $P_{1}$ is a $u\to v$ path
and $P_{2}$ is a $v\to w$ path, we denote by $P_{1}\cdot P_{2}$ (or simply
$P_{1}P_{2}$) a path obtained by concatenating $P_{1}$ with $P_{2}$.

We define $\delta^{k}_{G}(u,v)$ to be the length of the shortest path from $u$
to $v$ among paths of at most $k$ edges. Formally,
$\delta^{k}_{G}(u,v)=\min\\{\ell(P):u\to v=P\subseteq G\text{ and }|P|\leq
k\\}$. The _distance_ $\delta_{G}(u,v)$ between the vertices $u,v\in V(G)$ is
the length of the shortest $u\to v$ path in $G$, or $\infty$, if no $u\to v$
path exists in $G$. In other words, $\delta_{G}(u,v)=\min_{k\geq
0}\delta_{G}^{k}(u,v)$. Note that the distance is well-defined only if $G$
contains no negative cycles. It is well known that $G$ has no negative cycles
if and only if there exists a _feasible price function_ $p:v\to\mathbb{R}$
satisfying $w_{G}(e)+p(u)-p(v)\geq 0$ for all $uv=e\in E(G)$. We define
_minimal_ paths as follows.

######  Definition 6.

We call a $u\to v$ path $P\subseteq G$ _minimal_ if
$\ell(P)=\delta^{|P|}_{G}(u,v)<\delta^{|P|-1}_{G}(u,v)$.

######  Observation 7.

All subpaths of a minimal path are also minimal.

If the graph $G$ that we refer to is clear from the context, we sometimes omit
the subscript $G$ and write $w(uv)$, $\delta(u,v)$, $\delta^{k}(u,v)$ etc.
instead of $w_{G}(u,v)$, $\delta_{G}(u,v)$, $\delta^{k}_{G}(u,v)$, etc.,
respectively.

##### Parallel model.

Formally, we use the work-depth model as used in recent literature on parallel
reachability and shortest paths, e.g., [21, 43]. An algorithm in this PRAM
model differs from a sequential algorithm only by the inclusion of the
_parallel foreach_ loops. The work of an algorithm is the total number of
operations performed if all parallel foreach loops were executed sequentially.
The _depth_ of an algorithm is the total number of operations performed by
sequential steps, plus the sum, over all parallel foreach loops, of the
maximum (sequential) iteration cost of a loop. In order to not focus on low-
level details, we specify neither what is the depth overhead of a $k$-way
parallel foreach loop, nor what is the precise shared memory access model
(e.g., EREW, CREW). Instead, we state all our parallel work and depth bounds
using $\widetilde{O}(\cdot)$ notation that suppresses polylogarithmic factors.
This is justified by the existence of general reductions between these
different PRAM variants that yield only polylogarithmic multiplicative
overhead in work and depth [28].

##### Bellman-Ford algorithm.

The Bellman-Ford algorithm is a classical algorithm for computing shortest
paths from a single source $s$ or detecting a negative cycle if one exists. It
maintains a distance label vector $d:V\to\mathbb{R}$, where initially $d(s)=0$
and $d(v)=\infty$ for all $v\in V\setminus\\{s\\}$, and proceeds in _steps_.
Classically, a _Bellman-Ford step_ consists of performing _edge relaxations_ ,
i.e., substitutions $d(v):=\min(d(v),d(u)+w(uv))$ for all edges $e=uv$, in any
order. It is well-known that: (1) if $d(v)\neq\infty$ then $d(v)$ is a length
of some $s\to v$ path in $G$, (2) after $k$ Bellman-Ford steps we have
$d(v)\leq\delta_{G}^{k}(s,v)$ for all $v\in V$, (3) if $d(u)+w(uv)<d(v)$ for
some $uv\in E$ after $n-1$ steps, then $G$ has a negative cycle, (4) if $G$
has no negative cycle and $s$ can reach every other vertex, then the obtained
distance label vector constitutes a feasible price function of $G$. A single
Bellman-Ford step clearly takes $O(m)$ time, so the Bellman-Ford algorithm
runs in $O(mk)$ time if $k$ steps are performed. However, in general, the
results of individual relaxations in a single step may depend on the results
of relaxations that happened earlier in that step.

In this paper we actually use a variant of the Bellman-Ford algorithm that
might converge to the answer slower, but is easier to reason about. Namely, in
a single _step_ , _for all $v$ at once_, we replace $d(v)$ with
$\min\left(d(v),\min_{uv\in E}\\{d(u)+w(uv)\\}\right)$. Equivalently, at the
beginning of a step we could store a copy of vector $d$ as $d^{\prime}$, and
then again _relax_ the edges in any order, where the relaxation is now a
substitution $d(v):=\min(d(v),d^{\prime}(u)+w(uv))$. It is easy to prove that
in this variant, after $k$ steps we have precisely $d(v)=\delta_{G}^{k}(v)$
for all $v\in V$. The properties (3) and (4) of the classical Bellman-Ford
algorithm hold for this variant as well. Moreover, the result of each
relaxation now only depends on the distance labels in the previous step.
Consequently, for this variant, a single Bellman-Ford step can be clearly
performed in parallel using $\widetilde{O}(m)$ work and
$O(\operatorname{polylog}{n})$ depth.

##### Hitting sets.

Let $\mathcal{F}$ be a collection of subsets of some universe $U$. Then
$X\subseteq U$ is called a _hitting set_ of $\mathcal{F}$ if $X\cap
S\neq\emptyset$ for all $S\in\mathcal{F}$.

######  Lemma 8 ([6, 35]).

Let $\Pi$ be a collection of $k$ _simple_ $h$-hop paths of $G$ (i.e., $k$
$(h+1)$-element subsets of $V(G)$). A hitting set $\Pi$ of size
$O((n/h)\cdot\log{k})$ can be computed in a deterministic way:

  * •

sequentially using a greedy algorithm in $O(kh+n)$ time,

  * •

using a parallel algorithm with $O(\operatorname{polylog}{n})$ depth and
$\widetilde{O}(kh+n)$ work.999The algorithm of Berger et al. [6] actually
produces a hitting set a constant-factor larger than the greedy algorithm.

##  3 A Parallel APSP Algorithm

In this section we describe the main result of this paper. Our algorithm will
use the concept of an $h$-hub set, as defined below.

######  Definition 9.

We call a set $H_{h}\subseteq V$ a $h$-hub set if for all $u,v\in V$ such that
$\delta^{h}_{G}(u,v)<\delta^{h-1}_{G}(u,v)$ there exists a minimal path
$P=u\to v$ in $G$ such that $|P|=h$ and $P$ goes through a vertex of $H_{h}$.

The following randomized construction of $h$-hub sets is attributed to Ullman
and Yannakakis [60].

######  Fact 10 ([60]).

For any $h\in[1,n]$, a random $\Theta\left(\frac{n}{h}\log{n}\right)$-element
subset of $V$ constitutes an $h$-hub set of $G$ with high
probability101010Here we abuse the notation slightly. Formally, by increasing
the constant $c\geq 1$ hidden in the $\Theta$ notation, one can achieve
probability $1-1/n^{c}$..

First, we will show how having hub sets for various values $h$ leads to a
randomized algorithm, whereas the deterministic construction of hubs will
follow.

###  3.1 The Algorithm

In the remaining part of this section we assume that $G$ has no negative
cycles. We will deal with negative cycle detection later on.

Let $d\in[1,n]$ be a parameter that controls the depth of our algorithm. By
possibly decreasing the demanded depth by just a constant factor, we can
assume, without loss of generality, that $d=2^{K}$, where $K$ is an integer.
We first show how to compute APSP given hub sets
$V=H_{1},H_{2},\ldots,H_{2^{i}},\ldots H_{d}$, where each $H_{2^{i}}$ has size
$O((n/2^{i})\cdot\log{n})$. By Fact 10, all these hub sets can be obtained
with $\widetilde{O}(n)$ work and $O(\operatorname{polylog}{n})$ depth using
sampling.

The first step of our algorithm is to compute shortest $\leq(d+1)$-hop
distances $\delta^{d+1}_{G}(s,t)$ for all $s,t\in H_{d}$. This can be done by
running $(d+1)$ steps of the Bellman-Ford algorithm from all $s\in H_{d}$ in
parallel using $\widetilde{O}(|H_{d}|\cdot d\cdot m)=\widetilde{O}(nm)$ work
and $\widetilde{O}(d)$ depth, or in $O(nm\log{n})$ time sequentially.

Let $G_{d}$ be defined as a complete graph on $H_{d}$ with weights given by
$w_{G_{d}}(uv)=\delta^{d+1}_{G}(u,v)$ for all $u,v\in H_{d}$. The second step
is computing the actual shortest paths $\delta_{G}(s,t)$ for all $s,t\in
H_{d}$ by running the APSP algorithm based on repeated-squaring (of the
weighted adjacency matrix using min-plus product) on the graph $G_{d}$.

######  Lemma 11.

Let $s,t\in H_{d}$. Then $\delta_{G_{d}}(s,t)=\delta_{G}(s,t)$.

###### Proof.

Since the edge lengths in $G_{d}$ encode path lengths in $G$, we clearly have
$\delta_{G_{d}}(s,t)\geq\delta_{G}(s,t)$. Let $h$ be the hop-length of a
minimal shortest $s\to t$ path in $G$, i.e., minimum $h$ such that
$\delta^{h}_{G}(s,t)=\delta_{G}(s,t)$. We prove
$\delta_{G_{d}}(s,t)\leq\delta_{G}(s,t)$ by induction on $h$.

If $h\leq d+1$, then
$\delta_{G}(s,t)=\delta^{d+1}_{G}(s,t)=w_{G_{d}}(st)\geq\delta_{G_{d}}(s,t)$.
Otherwise, suppose $h>d+1$ and consider some minimal shortest $s\to t$ path
$P$ in $G$. Let us write $P=P^{\prime}QP^{\prime\prime}$, where
$|P^{\prime}|,|P^{\prime\prime}|\geq 1$, $|Q|=d$, and $Q$ is a $p\to q$ path,
$p,q\in V$. Since $P$ is minimal, so is $Q$ (by Observation 7) and, as a
result, we have $\delta^{d-1}_{G}(p,q)>\delta^{d}_{G}(p,q)$. Therefore, by the
definition of a $d$-hub set, there exists a path $Q^{\prime}=p\to q$ in $G$
with length $\delta^{d}_{G}(p,q)=\ell(Q)$, $|Q^{\prime}|=|Q|$, and going
through a vertex $z\in H_{d}$. Consequently,
$P^{\prime}Q^{\prime}P^{\prime\prime}$ is a minimal shortest $s\to t$ path
with $z\in H_{d}$ as an intermediate vertex. By Observation 7, this implies
$\delta^{h-1}_{G}(s,z)=\delta_{G}(s,z)$ and
$\delta^{h-1}_{G}(z,t)=\delta_{G}(z,t)$. By the inductive assumption we
conclude $\delta_{G_{d}}(s,z)=\delta_{G}(s,z)$ and
$\delta_{G_{d}}(z,t)=\delta_{G}(z,t)$. Finally, by $z\in V(G_{d})$ and
triangle inequality we obtain
$\delta_{G_{d}}(s,t)\leq\delta_{G_{d}}(s,z)+\delta_{G_{d}}(z,t)=\delta_{G}(s,z)+\delta_{G}(z,t)=\delta_{G}(s,t)$.
∎

The repeated squaring APSP algorithm has
$\widetilde{O}(|H_{d}|^{3})=\widetilde{O}((n/d)^{3})$ work and
$O(\operatorname{polylog}{n})$ depth (one can also think of the min-plus
product as $n$ Bellman-Ford steps that can be performed in parallel, and hence
a single product requires $O(\operatorname{polylog}{n})$ depth). If one wanted
to implement this step sequentially, the Floyd-Warshall APSP algorithm would
yield $O((n/d)^{3}\log^{3}{n})$ time.

Finally, the last step is to inductively compute, for each $k=K,\ldots,$ down
to $0$, the distances $\delta_{G}(s,t)$ for all pairs
$(s,t)\in(H_{2^{k}}\times V)\cup(V\times H_{2^{k}})$. Recall that we have set
$H_{0}=V$, so after completing the step for $k=0$, this will give the all-
pairs distance matrix as desired.

For convenience, let us set $H_{2^{K+1}}:=H_{2^{K}}$. Let us focus on
computing $\delta_{G}(s,t)$ for $s\in H_{2^{k}}$ and all $t\in V$ assuming
that the steps for larger $k$ have already been completed and so the distances
$\delta_{G}(u,v)$ for $(u,v)\in(H_{2^{k+1}}\times V)\cup(V\times H_{2^{k+1}})$
are already known. Actually, for the inductive step we only require these
distances for the pairs from $(H_{2^{k+1}}\times
H_{2^{k}})\cup(H_{2^{k}}\times H_{2^{k+1}})$, which implies that in the first
step (for $k=K$) they can be retrieved from the distance matrix of $G_{d}$.
Computing $\delta_{G}(s,t)$ for $(s,t)\in V\times H_{2^{k}}$ is symmetric. Let
$G_{k,s}$ be $G$ with an auxiliary edge $e_{v}=sv$ of weight
$w_{G_{k,s}}(e_{v})=\delta_{G}(s,v)$ added for all $v\in H_{2^{k+1}}$. Observe
that all the auxiliary edges‘ weights have been already computed in the
previous step. We compute the desired distances $\delta_{G}(s,t)$ by running
$2^{k+1}+1$ steps of the Bellman-Ford algorithm from each $s\in H_{d}$ (in
parallel). This costs $\widetilde{O}(|H_{2^{k}}|\cdot m\cdot
2^{k})=\widetilde{O}(mn)$ work and $\widetilde{O}(2^{k})$ depth in parallel,
or $O(nm\log{n})$ time sequentially.

Note that through all $k$, the total work is $\widetilde{O}(nm)$, whereas the
depth is $\widetilde{O}(d)$. The sequential time cost of the final phase is
$O(nm\log{n}\log{d})$. The correctness of the above algorithm follows from the
lemma below.

######  Lemma 12.

For any $(s,t)\in H_{2^{k}}\times V$,
$\delta_{G_{k,s}}^{2^{k+1}+1}(s,t)=\delta_{G}(s,t)$.

###### Proof.

Let $b:=2^{k+1}+1$. Since $G\subseteq G_{k,s}$, and the auxiliary edges encode
some path lengths in $G$, we clearly have
$\delta_{G_{k,s}}^{b}(s,t)\geq\delta_{G_{k,s}}(s,t)=\delta_{G}(s,t)$.

Let us now prove $\delta_{G_{k,s}}^{b}(s,t)\leq\delta_{G}(s,t)$. Let $P$ be a
minimal shortest $s\to t$ path in $G$. If $|P|\leq b$, then our claim holds by
$G\subseteq G_{k,s}$. Suppose $|P|>b$. Let us write $P=QR$, where
$|R|=2^{k+1}$ and $R=u\to t$. Observe that the path $R$ is shortest and
minimal. Hence, by the definition of $H_{2^{k+1}}$, there exists a minimal
shortest path $R^{\prime}=u\to t$ going through a vertex $z\in H_{2^{k+1}}$
and $|R^{\prime}|=2^{k+1}$. Therefore, $QR^{\prime}$ is also a minimal
shortest $s\to t$ path. Let us express $QR^{\prime}$ as $P_{1}P_{2}$, where
$P_{2}$ is a minimal shortest $z\to t$ path. Note that we have $|P_{2}|\leq
2^{k+1}$. Moreover, $\ell(P_{1})=\delta_{G}(s,z)=w_{G_{k,s}}(e_{z})$. Hence,
the $s\to t$ path $e_{z}P_{2}$ of length $\delta_{G}(s,t)$ is contained in
$G_{k,s}$ and its hop-length does not exceed $2^{k+1}+1=b$. Its existence
implies $\delta_{G_{k,s}}^{b}(s,t)\leq\delta_{G}(s,t)$. ∎

Hence, we obtain the following lemma.

######  Lemma 13.

Let $d=2^{K}\leq n$ and assume that $G$ does not contain a negative cycle.
Given a collection of sets $H_{2^{k}}$, where $k=0,\ldots,K$, such that
$H_{2^{k}}$ is a $2^{k}$-hub set of $G$ of size $O((n/2^{k})\log{n})$, all-
pairs shortest paths can be computed in parallel using $\widetilde{O}(nm)$
work and $\widetilde{O}(d)$ depth, or sequentially in $O(nm\log{n}\log{d})$
time.

###  3.2 Deterministic Construction of Hubs

In this section we show how to construct hub sets in a deterministic way. We
start with a few technical lemmas.

######  Lemma 14.

Let $H_{h}$ be a $h$-hub set of $G$. Let $\Pi$ be a collection of minimal
$h$-hop paths $P_{st}=s\to t$, one path for each pair $(s,t)\in H_{h}\times V$
for which such a minimal path exists.

Let $B$ be a hitting set of $\Pi$. Then $B$ is a $2h$-hub set of $G$.

###### Proof.

We need to prove that, for each $u,v\in V$ such that
$\delta^{2h}_{G}(u,v)<\delta^{2h-1}_{G}(u,v)$, there exists a minimal $2h$-hop
$u\to v$ path in $G$ going through a vertex of $B$. To this end, let $P$ be
some minimal $u\to v$ path such that $|P|=2h$. Split $P$ evenly into two paths
$P_{1}P_{2}$ of hop-length $h$. Note that, by Observation 7, every subpath of
$P$, in particular $P_{1}=u\to w$, is minimal. Since $H_{h}$ is a hub set,
there is a vertex $z\in H_{h}$ on some minimal path $Q=u\to w$ such that
$|Q|=h$. Let $P^{\prime}=QP_{2}$, and let us express $P^{\prime}=RST$ so that
$S=z\to y$ is a path satisfying $|S|=h$. Note that by minimality of
$P^{\prime}$, $S$ is also minimal. Therefore,
$\delta_{G}^{h}(z,y)<\delta_{G}^{h-1}(z,y)$, and thus we have a minimal $z\to
y$ path $P_{zy}$ of hop-length $h$ in $\Pi$. Finally, observe that $RP_{zy}T$
is a minimal $u\to v$ path of hop-length $2h$ and goes through a vertex of $B$
by the definition of a hitting set of $\Pi$. ∎

######  Lemma 15.

Suppose that $G$ has no negative cycles with at most $h$ edges. Then every
minimal $h$-hop path in $G$ is simple.

###### Proof.

A non-simple path contains a cycle. If a minimal $h$-hop path $P$ contained a
non-negative cycle, there would exist a path of hop-length $<h$ and length no
more than $\ell(P)$, thus contradicting minimality of $P$. If $P$ contained a
negative cycle, the cycle would have at most $h$ edges. ∎

######  Lemma 16.

Suppose that $G$ has no negative cycles with at most $h$ edges. Let $H_{h}$ be
a $h$-hub set of $G$. Then in $O(|H_{h}|hm)$ time we can:

  * •

construct a $2h$-hub set $H_{2h}$ of $G$ such that
$|H_{2h}|=O((n/h)\cdot\log{n})$,

  * •

find a shortest negative cycle in $G$ with no more than $2h$ edges, if one
exists.

###### Proof.

To find $H_{2h}$, we first compute shortest $\leq h$-hop paths from all $s\in
H_{h}$ to all $v\in V$ using $h$ steps of Bellman-Ford algorithm in
$O(|H_{h}|hm)$ time. Note that indeed minimal $h$-hop paths can be inferred
from the Bellman-Ford execution by storing (1) the distance labels $d_{i}$
from all the steps, and (2) the predecessor vectors $p_{i}$ such that

$d_{i+1}(v)=\min_{uv\in E}\\{d_{i}(u)+w(uv)\\}=d_{i}(p_{i}(v))+w(p_{i}(v)v).$

Clearly, an $s\to v$ minimal path of hop-length $h$ exists if
$d_{h}(v)<d_{h-1}(v)$ and it can be easily reconstructed from the predecessor
vectors. Since no negative cycle in $G$ has $\leq h$ edges, by Lemma 15, the
computed minimal $h$-hop paths are all simple. As a result, by Lemma 8, we can
compute a hitting set $B$ of size $O((n/h)\log{n})$ of these paths in
$O((|H_{h}|\cdot n)\cdot h)$ time. By Lemma 14, $B$ constitutes a $2h$-hub set
of $G$.

Suppose a shortest negative cycle $C=v_{1}\ldots v_{k}$ with $|C|=k\in(h,2h]$
exists in $G$. Since $C$ has a minimal number of hops (in particular, it is
simple), the subpath $P=v_{1}\to v_{h+1}$ of $C$ satisfies
$\delta_{G}^{h}(v_{1},v_{h+1})\leq\ell(P)<\delta_{G}^{h-1}(v_{1},v_{h+1})$. As
a result, and by the definition of $H_{h}$, there exists a $h$-hop minimal
path $P^{\prime}=v_{1}\to v_{h+1}$ such that $z\in H_{h}\cap V(P^{\prime})$
and $\ell(P^{\prime})\leq\ell(P)$. Hence, if we replace the prefix $P$ of $C$
with $P^{\prime}$, we obtain another shortest negative cycle $C^{\prime}$ with
$|C^{\prime}|\in(h,2h]$ and going through $z$. It follows that
$\delta_{G}^{2h}(z,z)<0$. By performing $2h$ Bellman-Ford steps from all $z\in
H_{h}$ independently we can thus find the smallest $k\leq 2h$ such that
$\delta^{k}(z,z)<0$ for some $z\in H_{h}$, if one exists. This $k$ clearly
equals $|C|$. Since we have to check all $z\in H_{h}$, this takes
$O(|H_{h}|hm)$ time through all $z$. ∎

We are now ready to describe the preprocessing step of our APSP algorithm that
computes the hub sets $H_{1},\ldots,H_{d=2^{K}}$ and possibly detects the
shortest negative cycle. Let us first discuss a sequential algorithm. We
proceed inductively, using Lemma 16.

We set $H_{2^{0}}=V$. For each $k=0,\ldots,K-1$ we proceed as follows. We
maintain an invariant that $G$ contains no negative cycles of hop-length at
most $2^{k}$ and $|H_{k}|=O((n/2^{k})\log{n})$. Hence, the invariant is true
initially for $k=0$ since, clearly, there are no single-edge negative cycles.
By our invariant, we can apply Lemma 16 for $h=2^{k}$ and thus in
$O(nm\log{n})$ time either detect a shortest negative cycle with no more than
$2h$ edges (and declare the APSP problem infeasible) or construct a
$2^{k+1}$-hub set $H_{2^{k+1}}$ of size $O((n/2^{k+1})\log{n})$ and guarantee
the invariant for $k+1$.

The above sequential algorithm trivially implies a parallel algorithm: all the
above $O(\log{d})$ steps of our computation can be implemented using a number
of parallel invocations of an $O(d)$-step Bellman-Ford algorithm and an
$O(\operatorname{polylog}{n})$-depth parallel computation (as given in Lemma
8) of a small hitting set of a collection of simple paths with a total hop-
length of $O(n^{2}\log{n})$ (the collection in step $k$ has
$O((n^{2}/2^{k})\cdot\log{n})$ paths of length $\Theta(2^{k})$). We thus
obtain the following theorem.

######  Theorem 17.

Let $d=2^{K}\leq n$. Then, a shortest negative cycle of $G$, provided it has
hop-length at most $d$, can be computed deterministically:

  * •

in $O(nm\log{n}\log{d})$ time using a sequential algorithm,

  * •

using a parallel algorithm with $\widetilde{O}(nm)$ work and
$\widetilde{O}(d)$ depth.

If no negative cycle of hop-length at most $d$ exists in $G$, then the
algorithm can produce, within the same time bounds, a collection of sets
$H_{2^{k}}$, where $k=0,\ldots,K$, such that $H_{2^{k}}$ is a $2^{k}$-hub set
of $G$ of size $O((n/2^{k})\cdot\log{n})$.

Together with Lemma 13 this finishes the proof of our main theorem. See 1 As a
corollary, we also obtain the following theorem. See 2

##  4 Planar Graph Algorithms

In this section we present our improved planar graph algorithms. We start from
describing the framework used by Fakcharoenphol and Rao [20] to solve the
negative cycle detection problem on planar graphs in near-linear time. This
framework forms the basis for all our parallel and sequential algorithms. We
remark that the negative cycle detection algorithm of [20] has been
subsequently improved by Klein et al. [39], whereas the currently best known
bound $O(n\log^{2}{n}/\log\log{n})$ is due to Mozes and Wulff-Nilsen [52].
These algorithms take a slightly simpler recursive approach, but the
fundamental difference compared to [20] is using Klein‘s MSSP algorithm [37]
on each piece $H$ with reduced costs for computing $DDG_{H}$ in
$O((|V(H)|+|\partial{H}|^{2})\log{n})$ time. This approach allows to avoid
using the costly FR-Dijkstra (Lemma 19) and thus saves at least a $O(\log{n})$
factor in the running time. However, it seems that Klein‘s MSSP algorithm is
inherently sequential and this is why in the following we will stick to the
original approach of [20].

Transferring the approach of [20] to the parallel setting directly leads to
$\widetilde{O}(\sqrt{n})$-depth work-efficient parallel algorithms for single
source shortest paths and negative cycle detection. We first show how to
improve the depth to $\widetilde{O}(n^{1/6})$ using our parallel APSP
algorithm. Using this, we later show improved algorithms for minimum cost-to-
time ratio cycle problem and external dense distance graphs computation.

###  4.1 The Framework of Fakcharoenphol and Rao [20]

Let $H$ be a weighted plane digraph with a distinguished set $\partial{H}$ of
_boundary vertices_ that necessarily lie on a $O(1)$ faces of $H$. We denote
by $DDG_{H}$ (a _dense distance graph_) the complete weighted graph on
$\partial{H}$ whose edge weights represent distances between all pairs of
vertices of $\partial{H}$ in $H$. Fakcharoenphol and Rao [20] developed the
concept of a dense distance graph along with efficient algorithms for
constructing and processing DDGs as a way to obtain their breakthrough
$O(n\log^{3}{n})$-time algorithm for negative cycle detection in a real-
weighted planar digraph. We now review a variant of this algorithm using
slightly more modern terminology.

After augmenting $G$ to be connected and triangulated, $G$ is recursively
decomposed using small cycle separators [49] of size $O(\sqrt{n})$ until the
obtained pieces have constant size. The decomposition procedure produces in
$O(n\log{n})$ time a binary tree $\mathcal{T}(G)$ whose nodes correspond to
subgraphs of $G$ (_pieces_), with the root being all of $G$ and the leaves
being pieces of constant size. We identify each piece $H$ with the node
representing it in $\mathcal{T}(G)$. We can thus abuse notation and write
$H\in\mathcal{T}(G)$. The _boundary vertices_ $\partial{H}$ of a piece $H$ are
vertices that $H$ shares with some other piece $Q\in\mathcal{T}(G)$ that is
not $H$‘s ancestor. For convenience we extend the boundary set $\partial{L}$
of a leaf piece $L$ to its entire vertex set $V(L)$. It is known that (see
e.g., [9, 38]) one can additionally guarantee that for each piece
$H\in\mathcal{T}(G)$, (1) $H$ is connected, (2) $\partial{H}$ lies on some
$O(1)$ faces of $H$, and (3) $|\partial{H}|=O(\sqrt{n})$. Moreover, one can
assume that $\sum_{H\in\mathcal{T}(G)}|V(H)|=O(n\log{n})$ and
$\sum_{H\in\mathcal{T}(G)}|\partial{H}|^{2}=O(n\log{n})$.

Given the decomposition, the algorithm processes the pieces
$H\in\mathcal{T}(G)$ bottom-up. Clearly, if any piece contains a negative
cycle, the whole $G$ does so as well. On the other hand, if $H$ contains no
negative cycle, the dense distance graph $DDG_{H}$ on $\partial{H}$ is well-
defined. Therefore, the computation for a piece $H$ either detects a negative
cycle in $H$ or produces $DDG_{H}$ otherwise. Let $H_{1},H_{2}$ be the
children of the node $H$ in $\mathcal{T}(G)$ and suppose neither of them
contains a negative cycle. Let $H^{\prime}=DDG_{H_{1}}\cup DDG_{H_{2}}$. It
can be easily shown that (1) $H$ contains a negative cycle if and only if
$H^{\prime}$ contains a negative cycle, (2) for any $u,v\in\partial{H}$, if
$H$ contains no negative cycle, then
$\delta_{H}(u,v)=\delta_{H^{\prime}}(u,v)$. Consequently, in the algorithm of
[20], for each piece $H$ we first run Bellman-Ford-based SSSP algorithm on
$H^{\prime}$ which either detects a negative cycle or produces a feasible
price function $p$ on $H^{\prime}$. The second step is to compute all-pairs
shortest paths on $H^{\prime}$ by running
$|\partial{H_{1}}\cup\partial{H_{2}}|$ Dijkstra-based single-source
computations with edge costs in $H^{\prime}$ reduced with $p$. The graph
$DDG_{H}$ can be easily obtained from the computed distance matrix since
$\partial{H}\subseteq\partial{H_{1}}\cup\partial{H_{2}}$.

Since each $DDG_{H}$ has $|\partial{H}|^{2}$ edges, using Bellman-Ford and
Dijkstra naively would lead to
$\widetilde{O}\left(\sum_{H\in\mathcal{T}(G)}|\partial{H}|^{3}\right)=\widetilde{O}(n^{3/2})$
running time. The main contribution of [20] lies in showing that the special
structure of a dense distance graph (that is, the distance matrix behind
$DDG_{H}$ consists of two so-called _staircase Monge matrices_) can be
leveraged to speed up naive implementations of these algorithms. The original
implementations of [20] have been slightly improved, and currently we have the
following bounds.

######  Lemma 18 ([20, 39]).

A single step of Bellman-Ford algorithm can be simulated on $DDG_{H_{1}}\cup
DDG_{H_{2}}$ in $O\left((|\partial{H_{1}}|+|\partial{H_{2}}|)\alpha(n)\right)$
time, where $\alpha(n)$ is the inverse Ackermann function.

The above lemma is a simple application of the algorithm of Klawe and Kleitman
[36] for computing row minima of a staircase $m\times m$ Monge matrix in
$O(m\alpha(m))$ time.

######  Lemma 19 (FR-Dijkstra [20, 23]).

Given a feasible price function $p$ on $DDG_{H_{1}}\cup DDG_{H_{2}}$, one can
simulate Dijkstra‘s algorithm on $DDG_{H_{1}}\cup DDG_{H_{2}}$ in
$O\left((|\partial{H_{1}}|+|\partial{H_{2}}|)\frac{\log^{2}{n}}{\log^{2}{\log{n}}}\right)$
time.

The above lemmas imply that the running time of Fakcharoenphol and Rao‘s
algorithm is
$O\left(\sum_{H\in\mathcal{T}(G)}|\partial{H}|\log^{2}{n}/\log^{2}\log{n}\right)=O(n\log^{3}{n}/\log^{2}\log{n})$.

##### A parallel implementation.

We note that the above algorithm can be easily turned into a parallel
algorithm with $\widetilde{O}(n)$ work and $\widetilde{O}(\sqrt{n})$ depth, as
explained below.

First, computing the decomposition within $\widetilde{O}(n)$ work and
$O(\operatorname{polylog}{n})$ depth follows from the fact that
$O(\sqrt{n})$-size simple cycle separators can be computed within these bounds
[40, 49]. Next, it is known that row minima of a staircase Monge matrix can be
computed using near-linear work and $O(\operatorname{polylog}{n})$ depth [2].
This implies the following.

######  Lemma 20.

A single step of Bellman-Ford algorithm can be simulated on $DDG_{H_{1}}\cup
DDG_{H_{2}}$ using a parallel algorithm with
$\widetilde{O}\left(|\partial{H_{1}}|+|\partial{H_{2}}|\right)$ work and
$O(\operatorname{polylog}{n})$ depth.

Consequently, the Bellman-Ford algorithm can be simulated on $DDG_{H_{1}}\cup
DDG_{H_{2}}$ using
$\widetilde{O}\left((|\partial{H_{1}}|+|\partial{H_{2}}|)^{2}\right)$ work and
$\widetilde{O}(|\partial{H_{1}}|+|\partial{H_{2}}|)=\widetilde{O}(\sqrt{n})$
depth.

Finally, since each of $|\partial{H}|$ Dijkstra‘s algorithm runs used to
compute $DDG_{H}$ based on $DDG_{H_{1}}$ and $DDG_{H_{2}}$ are independent,
they can be performed in parallel to give $\widetilde{O}(\sqrt{n})$ depth
bound on this step. As the depth of $\mathcal{T}(G)$ is $O(\log{n})$, the
total work is $\widetilde{O}(n)$, whereas the total depth is
$\widetilde{O}(\sqrt{n})$.

###  4.2 A Faster Nearly Work-Efficient Parallel SSSP Algorithm

In this section we apply our parallel APSP algorithm to obtain a polynomially
smaller bound on the depth required to detect a negative cycle and to compute
single-source shortest paths in a real-weighted planar digraph.

First, observe that having an APSP algorithm that can handle negative cycle
detection on the fly allows us to replace the two-phase Bellman-Ford-Dijkstra
approach in the framework of Fakcharoenphol and Rao. Indeed, then for each
piece $H$ all we do is computing $DDG_{H}$ by running the all-pairs shortest
paths algorithm directly on $DDG_{H_{1}}\cup DDG_{H_{2}}$, without using price
functions that reduce the problem to the non-negatively weighted case.

Recall that the algorithm of Theorem 1 is a certain combination of a number of
limited-hop Bellman-Ford invocations on various graphs $G^{\prime}$ obtained
from $G$ by adding $O(n)$ auxiliary edges, and a single run of a repeated
squaring algorithm. In fact, if we were able to execute a single Bellman-Ford
step on such a graph $G^{\prime}$ using $O(t(n,m))$ work and
$O(\operatorname{polylog}{n})$ depth, the algorithm of Theorem 1 would have
$\widetilde{O}(n^{2}+n\cdot t(n,m)+(n/d)^{3})$ work and $\widetilde{O}(d)$
depth for any $d$. We use this fact to prove the following lemma.

######  Lemma 21.

Let $H_{1},H_{2}$ be the children of a node $H\in\mathcal{T}(G)$. Let
$b=|\partial{H_{1}}|+|\partial{H_{2}}|$. We can compute all-pairs shortest
paths in $DDG_{H_{1}}\cup DDG_{H_{2}}$ (and thus obtain $DDG_{H}$), using a
parallel algorithm with $\widetilde{O}(b^{2})$ work and
$\widetilde{O}(b^{1/3})$ depth. If the problem is infeasible, the algorithm
detects a negative cycle within the same bounds.

###### Proof.

Let $X$ be the graph $DDG_{H_{1}}\cup DDG_{H_{2}}$ with some $O(b)$ auxiliary
edges added. Every Bellman-Ford step in the algorithm of Theorem 1 run on
$DDG_{H_{1}}\cup DDG_{H_{2}}$ is performed on a graph of this form. Hence, it
is enough to show how to perform a Bellman-Ford step on $X$, which can have
$\Omega(b^{2})$ edges. Since in a Bellman-Ford step the order of edge
relaxations is arbitrary, we can first relax all edges of $DDG_{H_{1}}\cup
DDG_{H_{2}}$ and then all the auxiliary edges. Relaxing the former takes
$O(b)$ work and $O(\operatorname{polylog}{n})$ depth by Lemma 20. The latter
can be relaxed within the same bounds naively. Hence, the APSP algorithm of
Theorem 1 can be implemented so that it has $\widetilde{O}(b^{2}+(b/d)^{3})$
work and $\widetilde{O}(d)$ depth for any $d$. By choosing $d=b^{1/3}$ we
obtain the desired bounds. ∎

See 3

###### Proof.

To obtain a parallel negative cycle detection algorithm, we simply replace the
Bellman-Ford and Dijkstra steps in the computation for each piece
$H\in\mathcal{T}(G)$ in the algorithm of Fakcharoenphol and Rao [20] by a
single computation of $DDG_{H}$ from $DDG_{H_{1}}$ and $DDG_{H_{2}}$ as in
Lemma 21. The work remains
$\widetilde{O}\left(\sum_{H\in\mathcal{T}(G)}|\partial{H}|^{2}\right)=\widetilde{O}(n)$,
whereas the depth is

$\widetilde{O}\left(\max_{H\in\mathcal{T}(G)}|\partial{H}|^{1/3}\right)=\widetilde{O}((\sqrt{n})^{1/3})=\widetilde{O}(n^{1/6}).$

In order to solve the single-source shortest paths problem one can use a trick
first described by Cohen [17] (and also used in [32]). Denote by $H^{*}$ a
complete graph on $\partial{H_{1}}\cup\partial{H_{2}}$ whose edge weights
represent distances in $DDG_{H_{1}}\cup DDG_{H_{2}}$. Note that $H^{*}$ is
precisely the graph that we compute using our new APSP algorithm to obtain
$DDG_{H}\subseteq H^{*}$. Now, consider the graph

$G^{*}=\left(\bigcup_{\text{non-leaf
}H\in\mathcal{T}(G)}H^{*}\right)\cup\left(\bigcup_{\text{leaf
}L\in\mathcal{T}(G)}L\right).$

Since $G\subseteq G^{*}$ and the edges in $G^{*}$ correspond to paths in $G$,
it is clear that $\delta_{G}(s,t)=\delta_{G^{*}}(s,t)$ for all $s,t\in V(G)$.
However, as proven in [17, 32], the graph $G^{*}$, although no longer planar,
has hop-diameter $O(\log{n})$. In other words, we in fact have
$\delta_{G^{*}}^{O(\log{n})}(s,t)=\delta_{G}(s,t)$ for all $s,t\in V$. As a
result, shortest paths in $G$ from a single source $s$ can be found by running
$O(\log{n})$ simple-minded Bellman-Ford steps from $s$ on $G^{*}$. Since
$|E(G^{*})|=\widetilde{O}\left(n+\sum_{H\in\mathcal{T}(G)}|\partial{H}|^{2}\right)=\widetilde{O}(n)$,
this takes $\widetilde{O}(n)$ work and $O(\operatorname{polylog}{n})$ depth. ∎

######  Corollary 22.

The following problems on planar directed graphs have nearly work-efficient
algorithms with $\widetilde{O}(n^{1/6})$ depth:

  1. (1)

computing a feasible flow111111That is, given a vertex demand function
$b:V\to\mathbb{R}$, a flow $f$ such that the excess $e_{f}(v)$ of each vertex
$v$ is $b(v)$.for real-weighted capacities,

  2. (2)

computing a bipartite perfect matching,

  3. (3)

computing a maximum $s,t$-flow for polynomially bounded integral edge
capacities,

  4. (4)

finding a shortest cycle going through each $e\in E(G)$,

  5. (5)

finding $s,t$-replacement paths.

###### Proof.

For the feasible flow problem, Miller and Naor [50] gave a duality-based
nearly work-efficient, $O(\operatorname{polylog}{n})$-depth reduction to the
real-weighted single-source shortest paths problem.

Bipartite perfect matching is directly reducible to the feasible flow problem
by setting the vertex demands on one side of the graph to $-1$ and on the
other side to $1$.

The maximum $s,t$-flow problem can be reduced at the cost of $O(\log{nC})$
multiplicative overhead to the feasible flow problem via binary search over
the flow value, where the edge capacities are from $\mathbb{Z}\cap[0,C]$. This
implies an $\widetilde{O}(n)$ work and $\widetilde{O}(n^{1/6})$ depth
algorithm for that problem if $C=\operatorname{poly}{n}$.

In Appendix A we describe how external dense distance graphs, defined and
discussed later in this Section, can be used to compute the shortest cycles
through all edges within desired bounds.

Finally, Chechik and Nechushtan [16] have recently shown that one can reduce
the $s,t$-replacement paths problem (using a planarity-preserving near-linear
time reduction) to computing the shortest cycles through all edges of a fixed
shortest path of a graph. All the reduction does is basically computing a
shortest $s\to t$ path $P$ in $G$ and reversing it. Therefore, by Theorem 3,
the reduction can be performed in a nearly work-efficient manner using
$\widetilde{O}(n^{1/6})$ depth. The final step is to compute shortest cycles
through all edges of the reversed path $P$, which can be done by item (4). ∎

###  4.3 Minimum Cost-To-Time Ratio Cycle

In this section we assume that each edge $e$ of a planar digraph $G$ is
assigned, besides a real weight $w(e)$, a time parameter
$t(e)\in\mathbb{R}_{>0}$. Our goal is to compute a directed cycle $C\subseteq
G$ minimizing the value $\lambda^{*}=\frac{\sum_{e\in C}w(e)}{\sum_{e\in
C}t(e)}$. Such a cycle is called a _minimum cost-to-time ratio cycle_ , or
_minimum ratio cycle_ , in short. In the special case when $t(e)=1$ for all
$e\in E$, $C$ is called a _minimum mean cycle_.

##### Parametric search.

It is well-known that one can reduce the minimum ratio cycle problem to the
negative cycle detection problem using binary search, as follows. The binary
search algorithm maintains an interval $[\lambda_{1},\lambda_{2}]$ such that
$\lambda^{*}\in[\lambda_{1},\lambda_{2}]$. Given some
$\lambda\in[\lambda_{1},\lambda_{2}]$, we wish to decide whether
$\lambda^{*}<\lambda$ or $\lambda\leq\lambda^{*}$. Note that
$\lambda^{*}<\lambda$ if and only if there exists a cycle $C$ such that

$\sum_{e\in C}w(e)-\lambda\cdot t(e)<0.$

This condition can be clearly checked by running a negative cycle detection
algorithm on the graph $G_{\lambda}$ obtained from $G$ by changing the edge
weight function to $w_{\lambda}(e):=w(e)-\lambda t(e)$. By picking
$\lambda=(\lambda_{1}+\lambda_{2})/2$, this also allows us to shrink the
interval $[\lambda_{1},\lambda_{2}]$ by half using a single negative cycle
detection step. If all the edge weights and times are integers whose absolute
values are bounded by $W$, the algorithm stops in $O(\log{(nW)})$ steps. Since
negative cycle detection can be solved in $\widetilde{O}(n)$ time for planar
graphs, this leads to a weakly polynomial $\widetilde{O}(n\log{W})$-time
algorithm for the minimum ratio cycle problem.

Megiddo‘s _parametric search_ technique can be used to convert a strongly
polynomial _parallel_ negative cycle detection algorithm into a strongly
polynomial time minimum ratio cycle algorithm. All known strongly polynomial
algorithms for this problem use variants of this technique.

Suppose we have two strongly polynomial negative cycle detection algorithms:
(1) a parallel one $\mathcal{P}$ with work $W(n,m)$ and depth $D(n,m)$, and
(2) a sequential one $\mathcal{S}$ with running time $T(n,m)$. Additionally,
suppose the parallel algorithm operates on edge weights/times (and all the
stored values dependent on the weights) only by either additions/subtractions
and comparisons.

The idea is, conceptually, to simulate (sequentially) the parallel algorithm
$\mathcal{P}$ ’’generically‘‘ on all the possible graphs $G_{\lambda}$ with
$\lambda\in[\lambda_{1},\lambda_{2}]$ (where $[\lambda_{1},\lambda_{2}]$
shrinks in time). This, in particular, means that the edge weights of
$G_{\lambda}$ and all the stored values (e.g., the distance labels in Bellman-
Ford algorithm) are linear functions of the form $-\lambda\cdot a+b$. Adding
and subtracting linear functions can be done straightforwardly. Moreover,
adding or subtracting such linear functions clearly leads to functions of the
same form. However, the result of a comparison of two values parameterized by
$\lambda$ generally depends on $\lambda$, and different results of such a
comparison might cause different flow of $\mathcal{P}$ in the future – we
would need to handle both branches of the algorithm‘s flow if we wanted to
detect a negative cycle in all $G_{\lambda}$. However, this is not our goal:
we only care about locating $\lambda^{*}$. So, instead, whenever $\mathcal{P}$
performs a comparison $-\lambda a+b<-\lambda c+d$, we compute the breakpoint
$x=(d-b)/(c-a)$ (for $c\neq a$) and use the sequential negative cycle
detection algorithm on $G_{x}$ to test whether $\lambda^{*}<x$ or
$\lambda^{*}\geq x$. This allows us to decide which branch would be chosen for
$\lambda=\lambda^{*}$ and discard the other branch (i.e., shrink
$[\lambda_{1},\lambda_{2}]$ to either $[\lambda_{1},x]$ or $[x,\lambda_{2}]$).
Note that this already implies a strongly polynomial bound of $O(W(n,m)\cdot
T(n,m))$ since $\mathcal{P}$ performs $O(W(n,m))$ comparisons.

However, one can use the parallelism of $\mathcal{P}$ to do better. In each of
$O(D(n,m))$ parallel steps $s$, $\mathcal{P}$ performs some number $p_{s}$ of
comparisons, whose results depend on where $\lambda^{*}$ lies relatively to
some breakpoints $\lambda_{1}=x_{0}\leq x_{1}<\ldots<x_{p_{s}}\leq
x_{p_{s}+1}=\lambda_{2}$, where the sum of $p_{s}$ over all parallel steps $s$
is $O(W(n,m))$. Note that the breakpoints can be sorted in
$\widetilde{O}(p_{s})$ time. Afterwards, we can find such $x_{i}$ that
$\lambda^{*}\in[x_{i},x_{i+1}]$ via binary search using $O(\log{(W(n,m))})$
sequential negative cycle detection runs. Observe that this allows us to
choose the correct branch for all the comparisons in parallel step $s$ at once
in just $\widetilde{O}(T(n,m))$ time. Consequently, we obtain a (sequential)
strongly polynomial algorithm with $\widetilde{O}(W(n,m)+D(n,m)\cdot T(n,m))$
running time.

##### Planar graphs.

Note that all our algorithms (and therefore also the algorithm of Lemma 20)
indeed operate on edge weights only by performing additions and comparisons.
Hence, by plugging the algorithm of Theorem 3 as both the parallel and
sequential algorithm into the parametric search framework, we already obtain
an $\widetilde{O}(n^{7/6})$-time strongly polynomial minimum ratio cycle
algorithm (then, $T(n,m),W(n,m)\in\widetilde{O}(n)$ and
$D(n,m)=\widetilde{O}(n^{1/6})$).

However, we can do better by slightly decreasing the depth of the parallel
algorithm of Theorem 3 at the cost of increasing its work (we stress that we
still stick to using a sequential algorithm with $T(n,m)=\widetilde{O}(n)$).
Recall from the proof of Lemma 21 that we could actually achieve depth
$\widetilde{O}(d)$ within work bounded by

$\widetilde{O}\left(n+\sum_{H\in\mathcal{T}(G)}|\partial{H}|^{3}/d^{3}\right)=\widetilde{O}\left(n+\frac{\sqrt{n}}{d^{3}}\sum_{H\in\mathcal{T}(G)}|\partial{H}|^{2}\right)=\widetilde{O}(n+n^{3/2}/d^{3}).$

As a result, we can obtain a minimum ratio cycle algorithm that runs in time
$\widetilde{O}(dn+n^{3/2}/d^{3})$ for any $d$. We balance these terms by
choosing $d=n^{1/8}$ and obtain the following theorem.

See 4

###  4.4 Faster Computation of External DDGs

Piecewise dense distance graphs $DDG_{H}$ for $H\in\mathcal{T}(G)$ have
numerous other applications in sequential planar graph algorithms beyond
negative cycle detection. Typically, though, they are computed using the
aforementioned Klein‘s MSSP data structure [37] in
$O((|H|+|\partial{H}|^{2})\log{n})$ time rather than inductively in
$O\left((|\partial{H_{1}}|^{2}+|\partial{H_{2}}|^{2})\frac{\log^{2}{n}}{\log^{2}{\log{n}}}\right)$
time using FR-Dijkstra. However, in some situations, only the latter inductive
method can be applied. One such application is computing so-called _external
dense distance graphs_ , i.e., the graphs $DDG_{G-H}$ for all
$H\in\mathcal{T}(G)$, where $G-H$ is the graph obtained from $G$ by removing
the vertices $V(H)\setminus\partial{H}$. We set $\partial{(G-H)}:=\partial{H}$
since indeed $\partial{H}$ contains all vertices that $G-H$ shares with $H$.
One can also argue that if the faces of $H$ containing $\partial{H}$ are
simple and disjoint121212Dealing with non-simple or non-disjoint faces is
merely a tedious technical difficulty (see e.g., [14, 27, 31]) – they can be
avoided by suitably extending the input graph along with its decomposition.,
$\partial{H}$ can be assumed to lie on $O(1)$ faces of $G-H$ as well.

It is well-known (and also not difficult to prove, see, e.g., [51]) that if
$H_{2}$ is a sibling of node $H_{1}$, whereas $H$ is $H_{1}$‘s parent in
$\mathcal{T}(G)$, then $DDG_{G-H_{1}}$ can be obtained by computing all-pairs
shortest paths on $DDG_{G-H}\cup DDG_{H_{2}}$ Using FR-Dijkstra (Lemma 19),
this takes
$O\left((|\partial{H}|^{2}+|\partial{H_{2}}|^{2})\frac{\log^{2}{n}}{\log^{2}{\log{n}}}\right)=O\left((|\partial{H_{1}}|^{2}+|\partial{H_{2}}|^{2})\frac{\log^{2}{n}}{\log^{2}{\log{n}}}\right)$
time and thus $O\left(n\frac{\log^{3}{n}}{\log^{2}{\log{n}}}\right)$ time
through all pieces $H\in\mathcal{T}(G)$. On the other hand, using MSSP to
compute all the external dense distance graphs is very inefficient, since
clearly $\sum_{H\in\mathcal{T}(G)}|V(G-H)|=\Omega(n^{2})$. In fact, the
inductive FR-Dijkstra-based approach has been so far the only known way to
compute external dense distance graphs efficiently. External DDGs alone can be
used to compute, for example, shortest cycles through all edges of the graph
(see Appendix A). They have also proved useful in obtaining very efficient
algorithms for maximum flow and minimum cut related problems [9, 46].
Moreover, the computation of external dense distance graphs is the bottleneck
of construction algorithms for, e.g., so-called cycle-MSSP [51] data
structure, or distance oracles supporting failed vertices [15].

The below lemma shows that by combining the sequential version of our APSP
algorithm with FR-Dijkstra we can obtain faster – by a factor of almost
$\Theta(\log{n})$ – algorithm for inductively computing dense distance graphs.
For simplicity, we focus on computing $DDG_{H}$ from $DDG_{H_{1}}\cup
DDG_{H_{2}}$, as the algorithm for computing $DDG_{G-H}$ (as argued above) is
identical.

######  Lemma 23.

Let $H_{1},H_{2}$ be the children of node $H\in\mathcal{T}(G)$. Let
$b=|\partial{H_{1}}|+|\partial{H_{2}}|$. We can compute all-pairs shortest
paths in $DDG_{H_{1}}\cup DDG_{H_{2}}$ in
$O(b^{2}\log{n}\cdot\log\log{n}\cdot\alpha(n))$ sequential time. If the
problem is infeasible, the algorithm finds a negative cycle within the same
bounds.

###### Proof.

By Lemma 18, in $O(b^{2}\cdot\alpha(n))$ time we can either find a negative
cycle in $DDG_{H_{1}}\cup DDG_{H_{2}}$ or compute a feasible price function
$p$ on that graph. The price function allows us to make the weights in each
$DDG_{H_{i}}$ non-negative. Now we use the sequential version of the algorithm
of Theorem 1 with two changes. First, we use a combination of Lemma 18 and
$O(b)$ naive relaxations for each Bellman-Ford step performed as we did in the
proof of Lemma 21. Even more importantly, we replace the
$O((n/d)^{3}\log^{3}{n})$ time Floyd-Warshall-based APSP computation of
shortest paths between all $s,t\in H_{d}$ with $|H_{d}|$ invocations of FR-
Dijkstra, as given in Lemma 19. As a result, the running time of the APSP
algorithm becomes

$O\left(b\cdot(b\cdot\alpha(n))\cdot\log{n}\log{d}+\left(\frac{b}{d}\log{n}\right)\cdot
b\log^{2}{n}\right)=O\left(b^{2}\log{n}\cdot\left(\alpha(n)\log{d}+\frac{\log^{2}{n}}{d}\right)\right).$

We obtain the desired bound by choosing $d=\log^{2}{n}$. ∎

Lemma 23 easily implies the following lemma. See 5

## References

  * [1] Pankaj K. Agarwal, Micha Sharir, and Sivan Toledo.  Applications of parametric searching in geometric optimization.  J. Algorithms, 17(3):292–318, 1994.  doi:10.1006/jagm.1994.1038.
  * [2] Alok Aggarwal, Dina Kravets, James K. Park, and Sandeep Sen.  Parallel searching in generalized monge arrays.  Algorithmica, 19(3):291–317, 1997.  doi:10.1007/PL00009175.
  * [3] Alexandr Andoni, Clifford Stein, and Peilin Zhong.  Parallel approximate undirected shortest paths via low hop emulators.  In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 322–335, 2020.  doi:10.1145/3357713.3384321.
  * [4] D. A. Bader and K. Madduri.  Parallel algorithms for evaluating centrality indices in real-world networks.  In 2006 International Conference on Parallel Processing (ICPP‘06), pages 539–550, 2006.
  * [5] Surender Baswana, Ramesh Hariharan, and Sandeep Sen.  Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths.  J. Algorithms, 62(2):74–92, 2007.  doi:10.1016/j.jalgor.2004.08.004.
  * [6] Bonnie Berger, John Rompel, and Peter W. Shor.  Efficient NC algorithms for set cover with applications to learning and geometry.  J. Comput. Syst. Sci., 49(3):454–477, 1994.  doi:10.1016/S0022-0000(05)80068-6.
  * [7] Aaron Bernstein.  Maintaining shortest paths under deletions in weighted directed graphs.  SIAM J. Comput., 45(2):548–574, 2016.  doi:10.1137/130938670.
  * [8] Guy E. Blelloch, Yan Gu, Yihan Sun, and Kanat Tangwongsan.  Parallel shortest paths using radius stepping.  In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Asilomar State Beach/Pacific Grove, CA, USA, July 11-13, 2016, pages 443–454, 2016.  doi:10.1145/2935764.2935765.
  * [9] Glencora Borradaile, Piotr Sankowski, and Christian Wulff-Nilsen.  Min _st_ -cut oracle for planar graphs with near-linear preprocessing time.  ACM Trans. Algorithms, 11(3):16:1–16:29, 2015.  doi:10.1145/2684068.
  * [10] Richard P. Brent.  The parallel evaluation of general arithmetic expressions.  J. ACM, 21(2):201–206, 1974.  doi:10.1145/321812.321815.
  * [11] Karl Bringmann, Thomas Dueholm Hansen, and Sebastian Krinninger.  Improved algorithms for computing the cycle of minimum cost-to-time ratio in directed graphs.  In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 124:1–124:16, 2017.  doi:10.4230/LIPIcs.ICALP.2017.124.
  * [12] Gerth Stølting Brodal, Jesper Larsson Träff, and Christos D. Zaroliagis.  A parallel priority queue with constant time operations.  J. Parallel Distributed Comput., 49(1):4–21, 1998.  doi:10.1006/jpdc.1998.1425.
  * [13] Nairen Cao, Jeremy T. Fineman, and Katina Russell.  Efficient construction of directed hopsets and parallel approximate shortest paths.  In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 336–349. ACM, 2020.  doi:10.1145/3357713.3384270.
  * [14] Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, and Oren Weimann.  Almost optimal distance oracles for planar graphs.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 138–151, 2019.  doi:10.1145/3313276.3316316.
  * [15] Panagiotis Charalampopoulos, Shay Mozes, and Benjamin Tebeka.  Exact distance oracles for planar graphs with failing vertices.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 2110–2123, 2019.  doi:10.1137/1.9781611975482.127.
  * [16] Shiri Chechik and Moran Nechushtan.  Simplifying and unifying replacement paths algorithms in weighted directed graphs.  In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), pages 29:1–29:12, 2020.  doi:10.4230/LIPIcs.ICALP.2020.29.
  * [17] Edith Cohen.  Efficient parallel shortest-paths in digraphs with a separator decomposition.  J. Algorithms, 21(2):331–357, 1996.  doi:10.1006/jagm.1996.0048.
  * [18] Edith Cohen.  Using selective path-doubling for parallel shortest-path computations.  J. Algorithms, 22(1):30–56, 1997.  doi:10.1006/jagm.1996.0813.
  * [19] Edith Cohen.  Polylog-time and near-linear work approximation scheme for undirected shortest paths.  J. ACM, 47(1):132–166, 2000.  doi:10.1145/331605.331610.
  * [20] Jittat Fakcharoenphol and Satish Rao.  Planar graphs, negative weight edges, shortest paths, and near linear time.  J. Comput. Syst. Sci., 72(5):868–889, 2006.  doi:10.1016/j.jcss.2005.05.007.
  * [21] Jeremy T. Fineman.  Nearly work-efficient parallel algorithm for digraph reachability.  In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 457–470. ACM, 2018.  doi:10.1145/3188745.3188926.
  * [22] Sebastian Forster and Danupon Nanongkai.  A faster distributed single-source shortest paths algorithm.  In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 686–697. IEEE Computer Society, 2018.  doi:10.1109/FOCS.2018.00071.
  * [23] Pawel Gawrychowski and Adam Karczmarz.  Improved bounds for shortest paths in dense distance graphs.  In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, pages 61:1–61:15, 2018.  doi:10.4230/LIPIcs.ICALP.2018.61.
  * [24] Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, and Éva Tardos.  Using interior-point methods for fast parallel algorithms for bipartite matching and related problems.  SIAM J. Comput., 21(1):140–150, February 1992.  doi:10.1137/0221011.
  * [25] Y. Han, V. Pan, and John Reif.  Efficient parallel algorithms for computing all pair shortest paths in directed graphs.  In Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’92, page 353–362, New York, NY, USA, 1992\. Association for Computing Machinery.  doi:10.1145/140901.141913.
  * [26] Mark Hartmann and James B. Orlin.  Finding minimum cost to time ratio cycles with small integral transit times.  Networks, 23(6):567–574, 1993.  doi:10.1002/net.3230230607.
  * [27] Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, and Piotr Sankowski.  Decremental single-source reachability in planar digraphs.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 1108–1121. ACM, 2017.  doi:10.1145/3055399.3055480.
  * [28] Joseph JáJá.  An Introduction to Parallel Algorithms.  Addison-Wesley, 1992.
  * [29] Ian Jermyn and Hiroshi Ishikawa.  Globally optimal regions and boundaries as minimum ratio weight cycles.  IEEE Trans. Pattern Anal. Mach. Intell., 23(10):1075–1088, 2001\.  doi:10.1109/34.954599.
  * [30] Donald B. Johnson.  Efficient algorithms for shortest paths in sparse networks.  J. ACM, 24(1):1–13, 1977.  doi:10.1145/321992.321993.
  * [31] Haim Kaplan, Shay Mozes, Yahav Nussbaum, and Micha Sharir.  Submatrix maximum queries in monge matrices and partial monge matrices, and their applications.  ACM Trans. Algorithms, 13(2):26:1–26:42, 2017.  doi:10.1145/3039873.
  * [32] Adam Karczmarz.  Decremental transitive closure and shortest paths for planar digraphs and beyond.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 73–92. SIAM, 2018.  doi:10.1137/1.9781611975031.5.
  * [33] Adam Karczmarz and Jakub Łącki.  Reliable hubs for partially-dynamic all-pairs shortest paths in directed graphs.  In 27th Annual European Symposium on Algorithms, ESA 2019, pages 65:1–65:15, 2019.  doi:10.4230/LIPIcs.ESA.2019.65.
  * [34] Richard M. Karp.  A characterization of the minimum cycle mean in a digraph.  Discret. Math., 23(3):309–311, 1978.  doi:10.1016/0012-365X(78)90011-0.
  * [35] Valerie King.  Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs.  In 40th Annual Symposium on Foundations of Computer Science, FOCS ‘99, 17-18 October, 1999, New York, NY, USA, pages 81–91, 1999.  doi:10.1109/SFFCS.1999.814580.
  * [36] Maria M. Klawe and Daniel J. Kleitman.  An almost linear time algorithm for generalized matrix searching.  SIAM J. Discret. Math., 3(1):81–97, 1990.  doi:10.1137/0403009.
  * [37] Philip N. Klein.  Multiple-source shortest paths in planar graphs.  In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pages 146–155, 2005.
  * [38] Philip N. Klein, Shay Mozes, and Christian Sommer.  Structured recursive separator decompositions for planar graphs in linear time.  In Symposium on Theory of Computing Conference, STOC‘13, pages 505–514, 2013.  doi:10.1145/2488608.2488672.
  * [39] Philip N. Klein, Shay Mozes, and Oren Weimann.  Shortest paths in directed planar graphs with negative lengths: A linear-space _O_(_n_ log2 _n_)-time algorithm.  ACM Trans. Algorithms, 6(2):30:1–30:18, 2010.  doi:10.1145/1721837.1721846.
  * [40] Philip N. Klein and Sairam Subramanian.  A linear-processor polylog-time algorithm for shortest paths in planar graphs.  In 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, pages 259–270, 1993.  doi:10.1109/SFCS.1993.366861.
  * [41] Philip N. Klein and Sairam Subramanian.  A randomized parallel algorithm for single-source shortest paths.  J. Algorithms, 25(2):205–220, 1997.  doi:10.1006/jagm.1997.0888.
  * [42] Eugene L. Lawler.  Optimal cycles in doubly weighted linear graphs.  In Theory of Graphs: International Symposium, pages 209–213, 1966\.
  * [43] Jason Li.  Faster parallel algorithm for approximate shortest path.  In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 308–321, 2020.  doi:10.1145/3357713.3384268.
  * [44] Richard J. Lipton and Robert Endre Tarjan.  Applications of a planar separator theorem.  SIAM J. Comput., 9(3):615–627, 1980.  doi:10.1137/0209046.
  * [45] Yang P. Liu, Arun Jambulapati, and Aaron Sidford.  Parallel reachability in almost linear work and square root depth.  In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1664–1686. IEEE Computer Society, 2019.  doi:10.1109/FOCS.2019.00098.
  * [46] Jakub Łącki and Yahav Nussbaum and Piotr Sankowski and Christian Wulff-Nilsen.  Single source - all sinks max flows in planar digraphs.  In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 599–608, 2012.  doi:10.1109/FOCS.2012.66.
  * [47] Meena Mahajan and Kasturi R. Varadarajan.  A new nc-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract).  In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC ’00, page 351–357, New York, NY, USA, 2000. Association for Computing Machinery.  doi:10.1145/335305.335346.
  * [48] Nimrod Megiddo.  Applying parallel computation algorithms in the design of serial algorithms.  J. ACM, 30(4):852–865, 1983.  doi:10.1145/2157.322410.
  * [49] Gary L. Miller.  Finding small simple cycle separators for 2-connected planar graphs.  J. Comput. Syst. Sci., 32(3):265–279, 1986.  doi:10.1016/0022-0000(86)90030-9.
  * [50] Gary L. Miller and Joseph Naor.  Flow in planar graphs with multiple sources and sinks.  SIAM J. Comput., 24(5):1002–1017, 1995.  doi:10.1137/S0097539789162997.
  * [51] Shay Mozes and Christian Sommer.  Exact distance oracles for planar graphs.  In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pages 209–222, 2012.  doi:10.1137/1.9781611973099.19.
  * [52] Shay Mozes and Christian Wulff-Nilsen.  Shortest paths in planar graphs with real lengths in _O_(_n_ log2 _n_ /loglog _n_) time.  In Algorithms - ESA 2010, 18th Annual European Symposium. Proceedings, Part II, pages 206–217, 2010.  doi:10.1007/978-3-642-15781-3˙18.
  * [53] James B. Orlin, K. Subramani, and Piotr J. Wojciechowski.  Randomized algorithms for finding the shortest negative cost cycle in networks.  Discret. Appl. Math., 236:387–394, 2018.  doi:10.1016/j.dam.2017.10.011.
  * [54] Seth Pettie.  A new approach to all-pairs shortest paths on real-weighted graphs.  Theor. Comput. Sci., 312(1):47–74, 2004.  doi:10.1016/S0304-3975(03)00402-X.
  * [55] Hanmao Shi and Thomas H. Spencer.  Time-work tradeoffs of the single-source shortest paths problem.  J. Algorithms, 30(1):19–32, 1999.  doi:10.1006/jagm.1998.0968.
  * [56] Thomas H. Spencer.  Time-work tradeoffs for parallel algorithms.  J. ACM, 44(5):742–778, 1997.  doi:10.1145/265910.265923.
  * [57] K. Subramani.  Optimal length resolution refutations of difference constraint systems.  J. Autom. Reasoning, 43(2):121–137, 2009.  doi:10.1007/s10817-009-9139-4.
  * [58] K. Subramani, Matthew D. Williamson, and Xiaofeng Gu.  Improved algorithms for optimal length resolution refutation in difference constraint systems.  Formal Asp. Comput., 25(2):319–341, 2013.  doi:10.1007/s00165-011-0186-3.
  * [59] Éva Tardos.  A strongly polynomial minimum cost circulation algorithm.  Combinatorica, 5(3):247–256, 1985.  doi:10.1007/BF02579369.
  * [60] Jeffrey D. Ullman and Mihalis Yannakakis.  High-probability parallel transitive-closure algorithms.  SIAM J. Comput., 20(1):100–125, 1991.  doi:10.1137/0220006.
  * [61] Olga Veksler.  Stereo correspondence with compact windows via minimum ratio cycle.  IEEE Trans. Pattern Anal. Mach. Intell., 24(12):1654–1660, 2002\.  doi:10.1109/TPAMI.2002.1114859.
  * [62] Song Wang and Jeffrey Mark Siskind.  Image segmentation with minimum mean cut.  In Proceedings of the Eighth International Conference On Computer Vision (ICCV-01), Vancouver, British Columbia, Canada, July 7-14, 2001 - Volume 1, pages 517–524, 2001.  doi:10.1109/ICCV.2001.10090.
  * [63] Song Wang and Jeffrey Mark Siskind.  Image segmentation with ratio cut.  IEEE Trans. Pattern Anal. Mach. Intell., 25(6):675–690, 2003\.  doi:10.1109/TPAMI.2003.1201819.
  * [64] Virginia Vassilevska Williams and R. Ryan Williams.  Subcubic equivalences between path, matrix, and triangle problems.  J. ACM, 65(5):27:1–27:38, 2018.  doi:10.1145/3186893.
  * [65] Neal E. Young, Robert Endre Tarjan, and James B. Orlin.  Faster parametric shortest path and minimum-balance algorithms.  Networks, 21(2):205–221, 1991.  doi:10.1002/net.3230210206.
  * [66] Uri Zwick.  All pairs shortest paths using bridging sets and rectangular matrix multiplication.  J. ACM, 49(3):289–317, 2002.  doi:10.1145/567112.567114.

##  Appendix A Computing All-Edges Shortest Cycles

The following corollary follows easily by Lemma 21 and extending the algorithm
behind Theorem 3 to also compute external DDGs.

######  Corollary 24.

All external dense distance graphs $DDG_{G-H}$ can be computed in parallel
using $\widetilde{O}(n)$ work and $\widetilde{O}(n^{1/6})$ depth.

This allows us to prove the next lemma.

######  Lemma 25.

Let $G$ be a real-weighted planar digraph with no negative cycles. Then, one
can compute for each $e\in E(G)$ the shortest cycle going through $e$:

  * •

sequentially in $O(n\log^{2}{n}\cdot\log{\log{n}}\cdot\alpha(n))$ time,

  * •

in parallel using $\widetilde{O}(n)$ work and $\widetilde{O}(n^{1/6})$ depth.

###### Proof.

Let $\mathcal{T}(G)$ be the recursive decomposition of $G$. By Lemma 5, we can
compute the external distance graphs $DDG_{G-H}$ for all $H\in\mathcal{T}(G)$
in $O(n\log^{2}{n}\cdot\log{\log{n}}\cdot\alpha(n))$ time. By Corollary 24,
the same task can be completed within $\widetilde{O}(n)$ work and
$\widetilde{O}(n^{1/6})$ depth.

Let $L_{e}$ be any leaf node $L_{e}\in\mathcal{T}(G)$ containing $e=uv$. The
length of the shortest cycle going through $e$ is clearly
$\delta_{G}(v,u)+w(e)$. So we need to compute $\delta_{G}(v,u)$. Since
$\partial{L_{e}}=V(L_{e})$, $u,v\in\partial{L_{e}}$. Consider the graph
$G_{e}=DDG_{G-L_{e}}\cup L_{e}$. We show that
$\delta_{G}(v,u)=\delta_{G_{e}}(v,u)$. Indeed, consider a shortest $v\to u$
path $P=P_{1}\ldots P_{k}$ in $G$ such that each $P_{i}$ is either a maximal
subpath entirely contained in $G-L_{e}$, or a single edge in $L_{e}$. Observe
that if $x_{i}\to y_{i}=P_{i}\subseteq G-L_{e}$, then by maximality and
$u,v\in\partial{L_{e}}$, we have $x_{i},y_{i}\in\partial{L_{e}}$. As a result,
the weight of an edge $x_{i}y_{i}$ in $G_{e}$ is at most
$\delta_{G-L_{e}}(v,u)$ by the definition of $DDG_{G-L_{e}}$. On the other
hand, if $x_{i}y_{i}$ is a single edge in $L_{e}$, then it is also preserved
in $G_{e}$. As a result, a path of length $\ell(P)$ can be found in $G_{e}$.

Since each $G_{e}$ has $O(1)$ size, computing shortest paths in all $G_{e}$
takes linear extra time. As the computations for each $G_{e}$ are independent,
they can be parallelized within $\widetilde{O}(n)$ work and
$O(\operatorname{polylog}{n})$ depth. ∎