# Fully Dynamic Algorithms for Minimum Weight Cycle
and Related Problems

Adam Karczmarz<EMAIL_ADDRESS>Supported by ERC Consolidator Grant
772346 TUgbOAT and by the Foundation for Polish Science (FNP) via the START
programme. Institute of Informatics, University of Warsaw, Poland

###### Abstract

We consider the directed minimum weight cycle problem in the fully dynamic
setting. To the best of our knowledge, so far no fully dynamic algorithms have
been designed specifically for the minimum weight cycle problem in general
digraphs. One can achieve $\widetilde{O}(n^{2})$ amortized update time by
simply invoking the fully dynamic APSP algorithm of Demetrescu and Italiano
[J. ACM ‘04]. This bound, however, yields no improvement over the trivial
recompute-from-scratch algorithm for sparse graphs.

Our first contribution is a very simple deterministic
$(1+\epsilon)$-approximate algorithm supporting vertex updates (i.e., changing
all edges incident to a specified vertex) in conditionally near-optimal
$\widetilde{O}(m\log{(W)}/\epsilon)$ amortized time for digraphs with real
edge weights in $[1,W]$. Using known techniques, the algorithm can be
implemented on planar graphs and also gives some new sublinear fully dynamic
algorithms maintaining approximate cuts and flows in planar digraphs.

Additionally, we show a Monte Carlo randomized exact fully dynamic minimum
weight cycle algorithm with $\widetilde{O}(mn^{2/3})$ worst-case update that
works for real edge weights. To this end, we generalize the exact fully
dynamic APSP data structure of Abraham et al. [SODA‘17] to solve the
_multiple-pairs shortest paths_ problem, where one is interested in computing
distances for some $k$ (instead of all $n^{2}$) fixed source-target pairs
after each update. We show that in such a scenario,
$\widetilde{O}((m+k)n^{2/3})$ worst-case update time is possible.

##  1 Introduction

The all-pairs shortest paths problem (APSP) is one of the most fundamental
graph problems. Given a real-weighted _directed_ graph $G$ with $n$ vertices,
the goal is to compute the distance matrix between all pairs of vertices $u,v$
in $G$. APSP can be computed in $\widetilde{O}(nm)$ time [30, 43], which is
clearly near-optimal for sparse graphs (since the output consists of $n^{2}$
numbers), but is also conjectured to be optimal for the entire range of
possible graph sparsities. Some of the other core directed graph problems such
as computing the diameter, the radius, or the minimum weight cycle111Also
called the _girth_ , or the _weighted girth_ of a digraph. For simplicity, in
this paper we very often use _minimum weight cycle_ to refer to the _length_
of such a cycle rather than to the actual cycle. Moreover, throughout this
paper, our focus is on computing/maintaining that length instead of the actual
cycle. The obtained algorithms, however, can be easily extended to return a
sought cycle with no additional asymptotic overhead. can be trivially reduced
to APSP in $O(n^{2})$ time by simply inspecting the entries of the distance
matrix. In fact, as shown by Vassilevska Williams and Williams [49], for dense
graphs APSP is known to be subcubically equivalent to many problems which look
easier at first sight, especially because their output is just a single number
(as opposed to $n^{2}$ numbers in APSP). These include e.g., the radius, the
minimum weight cycle, and the second shortest simple $s,t$ path problems. For
all these problems, just like for APSP, the best known algorithms run in
$\widetilde{O}(nm)$ time. Lincoln et al. [38] gave some compelling reasons why
improving upon this bound may also be impossible.

In this paper, our focus is on _fully dynamic_ graph algorithms. Fully dynamic
graph algorithms allow updating the graph under both edge insertions and
deletions, as opposed to _partially dynamic_ algorithms that allow either only
insertions (_incremental_ setting) or only deletions (_decremental_ setting).
Fully dynamic APSP has been widely studied in the past. Demetrescu and
Italiano [19] showed that the distance matrix can be _explicitly_ maintained
in $\widetilde{O}(n^{2})$ _amortized_ time under _vertex updates_ which are
allowed to change all edges incident to a single vertex at once. Thorup [47]
simplified and slightly improved their algorithm. Clearly, if the algorithm is
required to maintain all distances explicitly, one cannot break through the
$O(n^{2})$ time barrier since even a _single_ edge update may change _all_ the
$n^{2}$ pairwise distances. Much of the work in this topic [2, 25, 48] has
been devoted to obtaining good _worst-case_ bounds on the time needed to
recompute the distance matrix and it is known that $\widetilde{O}(n^{2+2/3})$
worst-case update time is possible [2, 25]. Interestingly, none of the known
fully dynamic algorithms for _real-weighted_ dynamic APSP has $o(n^{2})$
update time and a non-trivial query procedure running in $o(m)$ time. Such an
algorithm, with $\widetilde{O}(m\sqrt{n})$ amortized update time and
$\widetilde{O}(n^{3/4})$ query time, has so far been only described for sparse
enough unweighted graphs by Roditty and Zwick [45].

The algorithm of Demetrescu and Italiano [19] immediately implies
$\widetilde{O}(n^{2})$ amortized update bound for fully dynamic variants of
all the most fundamental problems ’’trivially reducible‘‘ to APSP – the
aforementioned diameter, radius, or minimum weight cycle. Surprisingly, as
shown in [4], such an update bound is likely to be the best possible for
maintaining both the diameter and the radius (conditionally on so-called
Strong Exponential Time- and Hitting Set hypotheses [1, 27]), even if the
graph remains sparse at all times and $(3/2-\epsilon)$-approximation is
allowed.

It is thus natural to ask whether there exist fully dynamic algorithms for the
_minimum weight cycle problem_ that improve upon the reduction to fully
dynamic APSP for sparse graphs, possibly allowing some small multiplicative
approximation. The fundamental difference between the minimum weight cycle and
diameter/radius problems is that the trivial reduction of minimum weight cycle
requires reading only $m$ entries of the distance matrix, as opposed to all
$n^{2}$ in the case of radius and diameter. As a result, by using the
aforementioned fully dynamic algorithm of Roditty and Zwick [45], one
immediately gets $\widetilde{O}(mn^{3/4})$ amortized update bound but merely
for _unweighted_ graphs. Note that this bound is always better than recompute-
from-scratch, and is truly subquadratic for sparse graphs. It is however not
clear whether such a bound can be obtained for real-weighted graphs, nor
whether a much better bound is attainable if we allow approximation.

Motivated by the above, in this paper we initiate the study of the directed
minimum weight cycle problem in the fully dynamic setting. To the best of our
knowledge, this problem has not been explicitly studied in the literature
before. It is worth noting, however, that a non-trivial fully dynamic
algorithm has been shown for _undirected planar_ graphs [39].

###  1.1 Our results

#### A fully dynamic approximate minimum weight cycle algorithm.

Our first contribution is a simple deterministic fully dynamic algorithm
maintaining a $(1+\epsilon)$-approximation of the minimum weight $\phi(G)$ of
a cycle in a real-weighted directed graph $G$. If $G$ has a negative cycle,
then we define $\phi(G)=-\infty$, thus allowing the sought cycle to be non-
simple. Note that if we wanted the minimum weight cycle to be simple and
simultaneously allowed negative edge weights, the problem would become NP-hard
via a reduction from Hamiltonian cycle.

######  Theorem 1.

Let $G$ be an initially empty fully dynamic real-weighted digraph such that
the weight of each positive weight cycle in $G$ always belongs to the interval
$[c,C]$, $c,C\in\mathbb{R}$.

There exists an algorithm maintaining an estimate $\phi^{\prime}$ satisfying
$\phi(G)\leq\phi^{\prime}\leq(1+\epsilon)\phi(G)$ under vertex updates to $G$
with amortized update time $O((m+n\log{n})\cdot\log{(C/c)}/\epsilon)$.

By Theorem 1, a simpler amortized update time bound of
$O((m+n\log{n})\cdot\log{(nW)}/\epsilon)$ for the fully dynamic
$(1+\epsilon)$-approximate minimum weight cycle problem can be obtained in two
special cases:

  * •

if $G$ has real-weights in $\\{0\\}\cup[1,W]$,

  * •

if $G$ has integer weights in $(-\infty,W]$.

Via known conditional lower bounds on the static approximate minimum weight
cycle problem, the update time bound in Theorem 1 – as a function of $m$
_alone_ – is near-optimal for both vertex and edge updates if we allow
approximation factor less than $2$ and $O(m^{2-\delta})$ preprocessing time
(for some $\delta>0$). Indeed, Dalirrooyfard and Vassilevska Williams [18]
proved that under so-called $k$-Cycle hypothesis [4], one cannot approximate
the minimum weight cycle within factor less than $2$ in $O(m^{2-\delta})$
time, for any $\delta>0$. Clearly, if there was, say, a dynamic
$3/2$-approximate minimum weight cycle algorithm with $O(m^{2-\delta})$
preprocessing time, $O(m^{1-\delta})$ update time, and the same interface as
our algorithm, $m$ edge/vertex updates would be sufficient to obtain a static
$3/2$-approximate minimum weight cycle algorithm running in $O(m^{2-\delta})$
time. This would refute the $k$-Cycle hypothesis.

Observe that the $\Omega(m^{2-o(1)})$ conditional lower bound [18] (which
implies that the $\Omega(mn^{1-o(1)})$ bound holds for _some_ sparsity $m$) on
the complexity of static approximate minimum weight cycle problem does not
rule out dynamic vertex update bounds of the form
$\widetilde{O}(n^{\alpha}\cdot m^{1-\alpha})$ for some $\alpha\in(0,1]$ or
$\widetilde{O}(m^{1+\beta}/n^{2\beta})$ for some $\beta\in(0,1/2]$, e.g.,
$\widetilde{O}(n)$, $\widetilde{O}(\sqrt{nm})$, or $\widetilde{O}(m^{3/2}/n)$.
However, if we limit ourselves to _’’combinatorial‘‘_ algorithms that do not
rely on fast matrix multiplication, such $O(m^{1-\epsilon})$ bounds are ruled
out for infinitely many sparsities of the form $m=\Theta(n^{1+2/(k-1)})$,
where $k\geq 3$ is an odd integer [18, 38].

We stress that the aforementioned static conditional lower bounds do not rule
out $\widetilde{O}(n)$ or even $\widetilde{O}(\sqrt{nm})$ amortized update
time in the _edge update_ model. In this case, for similar reasons, only
combinatorial approximate algorithms with amortized update time that is
sublinear in $n$ for many sparsities, e.g., $\widetilde{O}(m^{\beta}\cdot
n^{1-2\beta})$ for $\beta\in(0,1/2]$, are unlikely to exist.

#### Fully dynamic cycles, flows, and cuts in planar graph.

Interestingly, if we limit our attention to the case of single edge updates
(as opposed to vertex updates) and real weights in $\\{0\\}\cup[1,W]$, the
amortized update cost of the data structure of Theorem 1 can always be charged
to the cost of performing a single edge update plus a single distance query on
$O(\log{(nW)}/\epsilon)$ fully dynamic _exact_ distance oracles, each
maintaining some subgraph of $G$. For general digraphs, this amounts to
running Dijkstra‘s algorithm in each of these subgraphs since no non-trivial
fully dynamic distance oracles with both update and query time $o(m)$ are
known. However, such dynamic distance oracles are well-known to exist for
planar digraphs [22, 32, 36] which immediately leads to the following result.

######  Theorem 2.

Let $G$ be a planar digraph $G$ with real weights in $\\{0\\}\cup[1,W]$. There
exists an algorithm maintaining an $(1+\epsilon)$-approximate estimate of
$\phi(G)$ under planarity preserving edge insertions and deletions with
amortized update time $\widetilde{O}(n^{2/3}\log{(W)}/\epsilon)$.

Previously, no sublinear fully dynamic algorithm for minimum weight cycle in
planar directed graphs has been described. An _exact_ algorithm for planar
_undirected_ graphs with $\widetilde{O}(n^{5/6})$ update time was given by
Łącki and Sankowski [39].

There is a well-known correspondence between simple cuts in an undirected
plane graph $G$, and simple cycles in its dual $G^{*}$. The correspondence, in
a way, extends to _directed_ planar graphs (see e.g. [37, 40]). Nevertheless,
currently the best known min $s,t$-cut algorithms in planar digraphs [10, 20]
are less efficient and use entirely different techniques than their
counterparts for planar undirected graphs [29]. Generally speaking, for
cut/flow applications, undirected planar graphs proved much more friendly to
work with (see e.g., the discussion in [20] or [40]). As an example of this
phenomenon, an _exact_ fully dynamic max $s,t$-flow _oracle_ (accepting $s,t$
as query parameters) with $\widetilde{O}(n^{2/3})$ update and query time
exists for undirected plane graphs [29], whereas no such dynamic algorithm has
been described for _directed_ plane graphs, even allowing approximation and
just a single fixed source-sink pair.

It is known that in a plane digraph $G$, an $s,t$-flow of value $f$ can be
routed if and only if the dual $G_{s,t,f}^{*}$ of a certain augmentation of
$G_{s,t,f}$ depending on $s,t$ and $f$ contains no negative cycles [20, 31,
41]. Roughly speaking, since the algorithm of Theorem 2 supports negative
weights, by running it on $G_{s,t,f}^{*}$ for $O(\log{(nW)}/\epsilon)$
distinct values of $f$, we obtain the following.

######  Theorem 3.

Let $G$ be a plane embedded digraph with real edge capacities in
$\\{0\\}\cup[1,W]$ and a _fixed_ source/sink pair $s,t$. There exists an
algorithm maintaining a $(1-\epsilon)$-approximate estimate of the value of
maximum $s,t$-flow in $G$ under _embedding preserving_ edge insertions and
deletions with $\widetilde{O}(n^{2/3}\log{(W)}/\epsilon)$ amortized update
time.

To the best of our knowledge, the above constitutes the first known fully
dynamic maximum $s,t$-flow algorithm for plane directed graphs with a
sublinear update time bound.

#### Exact fully dynamic minimum weight cycle and MPSP.

Finally, we consider maintaining the minimum weight cycle _exactly_ in a fully
dynamic _real-weighted_ digraph. We show:

######  Theorem 4.

Let $G$ be a real-weighted digraph. There exists a Monte Carlo randomized
fully dynamic algorithm maintaining $\phi(G)$ under vertex updates with
$O((m+n\log{n})n^{2/3}\log^{4/3}{n})$ worst-case update time. The answers
produced are correct with high probability.222That is, with probability at
least $1-1/n^{c}$ for any chosen constant $c\geq 1$.

Note that for sparse graphs, Theorem 4 allows recomputing the minimum weight
cycle in $\widetilde{O}(n^{5/3})$ time, i.e., polynomially faster than
recompute-from-scratch and the dynamic algorithm of Demetrescu and Italiano
[19]. However, observe that [19] yields a better amortized update bound for
$m=\omega(n^{4/3})$.

In order to obtain Theorem 4, we generalize the fully dynamic APSP algorithm
of Abraham et al. [2] in a non-trivial way to solve what we call the _multiple
pairs shortest paths_ problem (_MPSP_). In the MPSP problem, which may be of
independent interest, one requires to maintain only $k$ fixed entries of the
distance matrix, i.e., after each update we are interested in distances
between some source-target pairs $(s_{i},t_{i})$ for $i=1,\ldots,k$. Recall
that the minimum weight cycle of a directed graph can be computed by
inspecting distances for $m$ source-target pairs. We obtain the following
bound for the fully dynamic MPSP problem.

######  Theorem 5.

Let $G$ be a real-weighted digraph. There exists a Monte Carlo randomized
fully dynamic MPSP data structure supporting vertex updates with
$O((m+n\log{n}+k)n^{2/3}\log^{4/3}{n})$ worst-case update time. The answers
produced are correct with high probability.

Note that the aforementioned data structure of Roditty and Zwick [45]
trivially implies an MPSP data structure for _unweighted_ digraphs with
$\widetilde{O}(m\sqrt{n}+kn^{3/4})$ amortized update bound. Our result shows
that a better (even worst-case) bound for (even real-weighted) sparse graphs
can be achieved if the set of source-target pairs is fixed throughout.

Actually, just as the worst-case update time of the data structure of Abraham
et al. [2] can be very easily improved to $\widetilde{O}(n^{2.5})$ for
_unweighted_ graphs [2, Section 4.2], an unweighted variant of our MPSP data
structure has $\widetilde{O}((m+k)\sqrt{n})$ worst-case update time.

Interestingly, it seems that the other known approaches to fully dynamic APSP
in real-weighted graphs [19, 24, 47], if adjusted, cannot easily yield
subquadratic (in $n$) update times for ’’sparse‘‘ instances of MPSP where
$m,k=O(n)$. This is because they all reconstruct shortest paths in a
hierarchical manner, by inductively stitching [24] or extending [19, 47] paths
recomputed earlier in the process. Even though the number of input source-
target pairs of interest may be small, these may require answers for
$\Theta(n^{2})$ distinct source-target pairs at lower levels of the hierarchy.
The data structure of Abraham et al. [2], on the contrary, does not use a
hierarchical approach and can be thought as using a single ’’stitching
layer‘‘.

Since the algorithm behind Theorem 4 (Theorem 5) is exact, the maintained
information, i.e., the minimum weight of a cycle (the entries of the distance
matrix of interest, resp.) is unique. Therefore, if we are interested in
maintaining the corresponding weight (distances, resp.) only, the bounds in
Theorems 4 and 5 hold against an adaptive adversary. However, if we are
required to output some actual minimum weight cycle (edges on some of the
desired shortest paths, resp.) we have to assume an oblivious
adversary.333Abraham et al. [2] show how to extend their data structure so
that it is capable of tracking lexicographically smallest shortest paths and
thus works against an adaptive adversary, even when returning actual paths is
required. Out of the box, this additional feature costs $\Omega(n^{2})$ extra
time per update, though. Adapting this idea to minimum weight cycle and MPSP
is an interesting possible further step.

###  1.2 Related work

#### Computing minimum weight cycles statically.

The best known algorithm for computing the minimum weight cycle in sparse
graphs exactly runs in $O(nm)$ time [42]. One can improve upon this for graphs
with small integer weights using matrix multiplication [17, 28, 44]. A
subcubic-time $(1+\epsilon)$-approximation can also be achieved this way [11,
50]. Much of the recent work regarded approximating the minimum weight cycle
within factor at least 2 [14, 15, 18].

#### Dynamic APSP.

Apart from the fully dynamic setting, APSP has also been widely studied in
partially dynamic settings. There exist efficient exact algorithms for
_unweighted_ digraphs with $\widetilde{O}(n^{3})$ total update time in both
incremental [5] and decremental [6, 21] settings. The fully dynamic APSP
algorithm [19, 47] is known to have total update time $\widetilde{O}(n^{3})$
in the decremental setting for real-weighted digraphs, but only when each
update removes _all_ edges incident to a vertex (and thus there are at most
$\leq n$ updates). For weighted digraphs, a nearly optimal
$\widetilde{O}(nm\log(W)/\epsilon)$ total update time partially dynamic
algorithm is known in the $(1+\epsilon)$-approximate setting [8]. This
algorithm assumes an oblivious adversary though. Less efficient algorithms
that are either deterministic or assume an adaptive adversary are known [21,
34, 35]. Note that many of the above algorithms maintain the distance matrix
explicitly so they can be obviously used to maintain the minimum weight cycle
(possibly approximately) in the respective partially dynamic scenarios.

Dynamic APSP has also been studied in undirected graphs [7, 9, 13, 16, 24, 26,
46].

###  1.3 Organization of the paper

The rest of this paper is organized as follows. In Section 2 we fix the
notation. In Section 3 we show a fully dynamic _threshold cycle detection_
data structure that constitutes the heart of the fully dynamic
$(1+\epsilon)$-approximate minimum weight cycle algorithm of Theorem 1 proved
in Section 4. The applications of Theorem 1 to planar graph algorithms, in
particular the proofs of Theorems 2 and 3, are covered in detail in Section 5.
In Section 6 we describe the exact fully dynamic minimum weight cycle and
fully dynamic MPSP algorithms.

##  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. We
denote by $n$ and $m$ numbers of vertices and edges (resp.) in the input
graph. 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$.

For an edge set $F$, we sometimes write $G+F$ to denote the graph
$(V(G),E(G)\cup F)$. If $F$ contains an edge $uv$ of weight $x$ and $uv\in
E(G)$, then we assume that $w_{G+F}(uv)=\min(w_{G}(uv),x)$. For an edge $e$ we
sometimes use $G+e$ to denote $G+\\{e\\}$. For a subset $D\subseteq V$, we
define $G\setminus D$ to be the graph $G$ with all edges incident to vertices
in $D$ removed.

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}\\}$. A path
$P$ is _simple_ if $u_{i}\neq u_{j}$ for $i\neq j$. A _cycle_ is a path such
that $u_{1}=v_{k}$. A  _simple cycle_ is a cycle that is a simple path.

The _hop-length_ of $P$ is 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}$.

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$.

Note that the distance is well-defined only if $G$ contains no negative
cycles. It is well-known that (1) $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)$, and (2) given a feasible
price function of $G$, one can compute single-source shortest paths in $G$
using Dijkstra‘s algorithm even if $G$ has edges with negative weights.

Define $\phi(G)$ to be the infimum of $\ell(C)$ through all cycles $C\subseteq
G$. Note that here $C$ is not necessarily a simple cycle: in general finding
minimum weight simple cycles with arbitrary negative weights is NP-hard. In
particular, if $G$ contains no cycles at all, then we define
$\phi(G):=\infty$. If $G$ contains a negative cycle, then $\phi(G)=-\infty$.
On the other hand, if $\phi(G)\geq 0$, then $G$ contains a simple cycle
$C^{\prime}$ with $\ell(C^{\prime})=\phi(G)$. We call any such cycle
$C^{\prime}$ a _minimum weight cycle_. Observe that if $\phi(G)\geq 0$, then
$\phi(G)=\min_{uv\in E(G)}\\{\delta_{G}(v,u)+w_{G}(uv)\\}$.

######  Observation 6.

Let $H$ be a non-negatively weighted digraph and let $v$ be its vertex. The
minimum weight of a cycle in $H$ that goes through $v$ can be computed in
$O(m+n\log{n})$ time.

###### Proof.

First compute single-source shortest paths from $v$ using Dijkstra‘s
algorithm. Note that the minimum weight cycle through $v$ has length
$\min_{uv\in E(H)}\\{\delta_{H}(v,u)+w_{H}(uv)$}. ∎

When characterizing dynamic graph algorithms, we use the term _edge update_ to
refer to a graph update that changes (i.e., inserts, removes, or alters the
weight) a single edge of $G$. On the other hand, a _vertex update_ can change
all edges incident (incoming or outgoing) to a single chosen vertex $v\in
V(G)$. In this case, we say that such a vertex update is _centered_ at $v$.

##  3 Fully dynamic threshold cycle detection

Consider the following decision variant of the fully dynamic minimum weight
cycle problem. Suppose we would like to maintain the information whether the
minimum weight $\phi(G)$ of a cycle in a real-weighted digraph $G$ is below
some threshold $\mu\geq 0$. In this section we show:

######  Theorem 7.

Let $G$ be an initially empty real-weighted digraph and let $\mu\geq 0$. There
exist a fully dynamic algorithm maintaining the information whether
$\phi(G)<\mu$ and supporting vertex updates in $O(m+n\log{n})$ amortized time.

The idea is to keep the edge set $E$ partitioned into two subsets $E_{0}$ and
$E_{1}$ such that the following two invariants are satisfied:

  1. (1)

For $G_{0}=(V,E_{0})$ we have $\phi(G_{0})\geq\mu$.

  2. (2)

If $E_{1}\neq\emptyset$, then $\phi(G)<\mu$.

Observe that by the above invariants, $\phi(G)<\mu$ _if and only if_
$E_{1}\neq\emptyset$.

Let us first consider the case when $G$ has non-negative edges only. Then we
can assume $\mu>0$ since the answer for $\mu=0$ is trivially ’’no‘‘.

We store $E_{1}$ partitioned into subsets $E_{1}(v)$ for $v\in V$, so that
each edge $uv\in E_{1}$ is stored in either $E_{1}(u)$ or $E_{1}(v)$ (this
choice is arbitrary). Since the data structure is initialized with an empty
graph, initially $E_{0}=\emptyset$ and $E_{1}(v)=\emptyset$ for all $v\in V$.

We also store the vertices $v$ with $E_{1}(v)\neq\emptyset$ of $G$ in a list
$Q$ sorted by the time when the last insertion around $v$ happened, i.e., at
the end of $Q$ we have a vertex that has been most recently subject to
insertion of edges around $v$.

Let us now describe an auxiliary procedure $\texttt{update}(v)$ that will be
used to fix the invariants. $\texttt{update}(v)$ does the following. We assume
that $E_{1}(v)\neq\emptyset$. We compute the minimum weight $x$ of a cycle
going through $v$ in $G_{0}+E_{1}(v)=(V,E_{0}\cup E_{1}(v))$ as described in
Observation 6. If $x\geq\mu$, the edges $E_{1}(v)$ are moved to $E_{0}$, and
the set $E_{1}(v)$ is emptied. This change is reflected in $Q$ by removing $v$
from $Q$.

To handle and insertion of a set $F_{v}$ of edges centered at some vertex $v$,
we simply add the edges $F_{v}$ to $E_{1}(v)$, move $v$ to the end of $Q$,
and, if $Q=\\{v\\}$, run $\texttt{update}(v)$.

To handle a deletion of an arbitrary set of edges $F\subseteq E$, we first
remove each edge $f\in F$ from $E_{0}$ or some set $E_{1}(w)$, wherever $f$
resides. If some $E_{1}(w)$ is emptied this way, $w$ is removed from $Q$
accordingly. Next, while $Q\neq\emptyset$, we repeatedly run
$\texttt{update}(v)$ for the first element $v\in Q$ and stop if
$\texttt{update}(v)$ fails to empty the respective set $E_{1}(v)$.

We now prove the correctness of the algorithm, whose pseudocode is given in
Algorithm 1.

Algorithm 1 Detecting a cycle of weight less than $\mu$.

procedure $\texttt{update}(v)$

1: $x:=\text{the minimum weight of a cycle going through }v\text{ in
}G_{0}+E_{1}(v)$

2: if $x\geq\mu$ then

3: $E_{0}:=E_{0}\cup E_{1}(v)$

4: $E_{1}(v):=\emptyset$

5: $Q:=Q\setminus\\{v\\}$

procedure $\texttt{insert}(F_{v}\neq\emptyset)$

1: $E_{1}(v):=E_{1}(v)\cup F_{v}$

2: $\texttt{move-to-back}(Q,v)$

3: if $Q=\\{v\\}$ then

4: $\texttt{update}(v)$

procedure $\texttt{delete}(F\subseteq E(G))$

1: $E_{0}:=E_{0}\setminus F$

2: for $uv=e\in F$ do

3: for $w\in\\{u,v\\}$ do

4: $E_{1}(w):=E_{1}(w)\setminus\\{e\\}$

5: if $E_{1}(w)=\emptyset$ then

6: $Q:=Q\setminus\\{w\\}$

7: while $Q\neq\emptyset$ do

8: $v:=\texttt{front}(Q)$

9: $\texttt{update}(v)$

10: if $E_{1}(v)\neq\emptyset$ then

11: break

function $\texttt{cycle-below-threshold}()$

1: return $Q\neq\emptyset$

######  Observation 8.

Suppose $\phi(G_{0})\geq\mu$ and let $v\in V$. Then $\phi(G_{0}+E_{1}(v))<\mu$
if and only if the shortest cycle going through $v$ in $G_{0}+E_{1}(v)$ has
weight less than $\mu$.

###### Proof.

By $\phi(G_{0})\geq\mu$, a cycle of weight less than $\mu$ in $G_{0}+E_{1}(v)$
has to go through an edge of $E_{1}(v)$. All of these edges are incident to
the vertex $v$. ∎

Clearly, $E_{0}$ and $E_{1}$ form a partition of $E$ after each insertion or
deletion: the procedure update only moves edges from $E_{1}$ to $E_{0}$.

######  Lemma 9.

Invariant (1) is maintained throughout the updates.

###### Proof.

Note that no edge is added to $E_{0}$ outside the update procedure. As a
result, since invariant (1) cannot be broken by removing edges from $G_{0}$,
to establish that invariant (1) is maintained, it is enough to see that update
only adds edges to $E_{0}$ if $\phi(G_{0})\geq\mu$ afterwards. ∎

######  Lemma 10.

Invariant (2) is maintained throughout the updates.

###### Proof.

Let $G^{\prime},G_{0}^{\prime},E_{1}^{\prime}$ denote $G,G_{0},E_{1}$
respectively _before_ the graph update. Suppose that after processing the
update, invariant (2) is broken. Equivalently, $E_{1}\neq\emptyset$ and
$\phi(G)\geq\mu$.

Suppose the update was insertion of edges $F_{v}$ centered at $v$. Since
adding edges can only decrease the minimum weight of a cycle,
$\phi(G^{\prime})\geq\mu$. As invariant (2) was satisfied before,
$E_{1}^{\prime}=\emptyset$. So after $F_{v}$ is moved to $E_{1}(v)$, we indeed
have $Q=\\{v\\}$. Since $\phi(G_{0}+E_{1}(v))\geq\phi(G)\geq\mu$, $E_{1}(v)$
should have been moved to $E_{0}$ by $\texttt{update}(v)$. But
$E_{1}=E_{1}\setminus E_{1}^{\prime}\subseteq E_{1}(v)=\emptyset$, so
$E_{1}=\emptyset$, a contradiction.

Now assume that the update deleted an arbitrary subset of edges. If after some
$\texttt{update}(v)$ call we have $E_{1}(v)\neq\emptyset$, then
$\phi(G_{0}+E_{1}(v))<\mu$, which implies $\phi(G)<\mu$, a contradiction. If
no such $v$ exists, then $Q$ is emptied, i.e., $E_{1}(v)=\emptyset$ for all
$v\in V$ after the deletion is processed. It follows that $E_{1}=\emptyset$,
which again leads to a contradiction. ∎

Now let us analyze the running time of our algorithm.

######  Lemma 11.

Each insertion is processed in $O(m+n\log{n})$ worst-case time.

###### Proof.

An insertion adds $O(n)$ edges to a single set $E_{1}(v)$ and causes at most a
single update call. The running time of update is dominated by the time needed
to find the minimum weight of a cycle going through some vertex $v$ in some
subgraph of the current graph $G$. By Observation 6, this time is no more than
$O(m+n\log{n})$. ∎

######  Lemma 12.

The total time needed to process arbitrary $k$ updates is
$O\left(\sum_{i=1}^{k}(m_{i}+n\log{n})\right)$, where $m_{i}$ is the number of
edges in $G$ when the $i$-th update happened. In other words, the amortized
update time is $O(m+n\log{n})$.

###### Proof.

By Lemma 11, we only need to prove that the deletions take
$O\left(\sum_{i=1}^{k}(m_{i}+n\log{n})\right)$ time in total. The cost of
removing the edges from the sets $E_{0}$ and $E_{1}(w)$, $w\in V$, can be
charged to the insertions which added those edges to the graph.

After updating the edge set, a deletion is handled using a number of
$\texttt{update}(v)$ runs, in the order in which vertices $v$ appear in $Q$.
At most one of these runs leaves $E_{1}(v)$ non-empty afterwards. We charge
the cost of this run to the considered deletion. For all other
$\texttt{update}(v)$ runs during that deletion, they empty the set $E_{1}(v)$
that previously was non-empty. As a result, we can charge the cost of that run
to the last insertion of edges centered at $v$ that happened before the
considered deletion.

We need to prove two things. First of all, to see that no insertion is charged
twice, note that after an insertion is charged for the first time, $E_{1}(v)$
is emptied. So, before $\texttt{update}(v)$ is called next time when handling
a deletion, new edges have to be added to $E_{1}(v)$, which can only happen
during another later insertion centered at $v$.

We also have to prove that just before $E_{1}(v)$ is emptied in
$\texttt{update}(v)$, the number of edges in $G_{0}+E_{1}(v)$ is
$O(|E^{\prime}|)$, where $E^{\prime}$ is the edge set of $G$ immediately after
the last insertion $I$ centered at $v$ happened. To this end, we prove
$E(G_{0})\cup E_{1}(v)\subseteq E^{\prime}$.

We clearly had $E_{1}(v)\subseteq E^{\prime}$ immediately after $I$.
Afterwards no more elements were added to $E_{1}(v)$ (albeit some might have
been removed), so we still have $E_{1}(v)\subseteq E^{\prime}$.

Now suppose there is an edge $e\in E(G_{0})$ with $e\notin E^{\prime}$. Then,
since $G_{0}\subseteq G$, $e$ was inserted into $G$ after the insertion $I$,
as a result of a later insertion $I^{\prime}$ centered at some $w\neq v$. The
edge $e$ could have been added to $G_{0}$ only if $E_{1}(w)$ was emptied
inside $\texttt{update}(w)$ immediately afterwards, but before
$\texttt{update}(v)$ was called. Since $I$ was the last insertion centered at
$v$ before $\texttt{update}(v)$ was called, both $v$ and $w$ were in $Q$ when
$\texttt{update}(w)$ was called. This is a contradiction: update is always
called on the earliest element of $Q$, whereas the fact that $I$ happened
before $I^{\prime}$ implies that $v$ lied earlier than $w$ in $Q$ when
$\texttt{update}(w)$ was called. ∎

######  Remark 13.

When handling a deletion, we could in principle call $\texttt{update}(v)$ for
vertices $v$ with $E_{1}(v)\neq\emptyset$ in arbitrary order, as opposed to in
the order of least recent centered insertions. However, then one could only
show a weaker total update time bound of $O(k(m_{\max}+n\log{n}))$, where
$m_{\max}$ is the maximum number of edges in $G$ during the first $k$ updates.

###  3.1 Negative weights

In this section we extend the obtained basic algorithm to also work with
negative edges. Recall that we still assume $\mu\geq 0$. Note that the case
$\mu=0$ is equivalent to dynamically maintaining whether $G$ has a negative
cycle. Recall that if $G$ has a negative cycle, $\phi(G)=-\infty$.

Unfortunately, in presence of negative weights or cycles we cannot simply use
the algorithm behind Observation 6 to find the minimum weight cycle through a
vertex $v$ in $G_{0}+E_{1}(v)$ as we did in $\texttt{update}(v)$. Instead, we
use the following lemma.

######  Lemma 14.

Let $H$ be a digraph with no negative cycles. Let $p:V\to\mathbb{R}$ be a
feasible price function of $H$. Let $F$ be a set of edges centered at some
vertex $v$.

Then in $O(m+n\log{n})$ time one can find the minimum weight of a cycle going
through $v$ in $H+F$. Moreover, if $H+F$ contains no negative cycles, within
the same time bound one can produce a feasible price function on $H+F$.

###### Proof.

Clearly, since $H$ has no negative cycles, a negative cycle in $H+F$ has to go
through $v$. Let $E_{v}^{+}$ be the set of edges in $H+F$ incoming to $v$.
Note that $H^{\prime}=H+F-E_{v}^{+}$ has no negative cycles. Moreover, since
$H^{\prime}$ differs from $H$ by edges incident to $v$, the edge costs reduced
by $p$ are non-negative for all edges of $H^{\prime}$ possibly except the
outgoing edges of $v$. However, since $v$ has no incoming edges in
$H^{\prime}$, a price function $p^{\prime}$ obtained from $p$ by sufficiently
increasing $p(v)$ (e.g., to $\max\\{p(u)-w(vu):vu\in E(H^{\prime})\\}$) is a
feasible price function of $H^{\prime}$. With price function $p^{\prime}$ in
hand, we can compute distances from $v$ in $H^{\prime}$ using Dijkstra‘s
algorithm in $O(m+n\log{n})$ time.

Now let $x=\min_{uv\in
E_{v}^{+}}\\{\delta_{H^{\prime}}(v,u)+w_{H^{\prime}}(uv)\\}$. Observe that $x$
is indeed the minimum weight of a simple cycle in $H+F$. Moreover, $x\geq 0$
implies that $p^{*}(y):=\delta_{H^{\prime}}(v,y)=\delta_{H+F}(v,y)$ is a
feasible price function on the induced subgraph of $(H+F)[R]$ reachable from
$v$. To extend that price function $p^{*}$ on $R\subseteq V$ to entire $V$, it
is enough to set $p^{*}(z)=p(z)+M$ for all $z\in V\setminus R$, where $M$ is a
sufficiently large number. To see that, note that $p^{*}$ is clearly a
feasible price function on $(H+F)[R]$, $(H+F)[V\setminus R]$, and there are no
edges from $R$ to $V\setminus R$ in $H+F$. For edges $zy\in
E(H+F)\cap((V\setminus R)\times R)$ we have
$w_{H+F}(zy)+p^{*}(z)-p^{*}(y)=w_{H+F}(zy)+p(z)+M-p^{*}(y)$. For

$M=\max\\{p^{*}(y)-p(z)-w_{H+F}(zy):zy\in E(H+F)\cap((V\setminus R)\times
R)\\},$

all the required reduced costs are non-negative. ∎

Now, given Lemma 14, we modify the basic algorithm as follows. In addition to
the partition of $E$ into $E_{0}$ and $E_{1}$, we always maintain a feasible
price function $p_{0}$ on $G_{0}$. Then, in $\texttt{update}(v)$, we use Lemma
14 to find the minimum weight $x$ of a cycle in $G_{0}+E_{1}(v)$. If the edges
$E_{1}(v)$ are moved to $E_{0}$ (and thus $x\geq 0$ since
$\phi(G_{0}+E_{1}(v))\geq\mu\geq 0$), we update the price function $p_{0}$ to
that produced by Lemma 14. Since the worst-case cost of running the algorithm
from Lemma 14 matches that of Observation 6, the time analysis remains
unchanged. Lemmas 9, 10, 12 and 14 together imply Theorem 7.

######  Remark 15.

For the problem of fully dynamically maintaining the information whether $G$
contains a _negative_ cycle (i.e., the special case $\mu=0$) there exists a
better algorithm with $O(m+n\log{n})$ _worst-case_ (as opposed to only
amortized) update time bound (see Theorem 23). In fact, we make use of that
algorithm when obtaining exact algorithms with good worst-case bounds in
Section 6. The main idea is to generalize the problem to maintaining a minimum
cost circulation in the graph $G$ with imposed unit vertex/edge capacities
(the details can be found in Section 6.3). This resembles Gabow‘s reduction of
single-source shortest paths with negative weights to the minimum cost perfect
matching problem [23]. However, the min-cost circulation based algorithm is
not as robust when it comes to obtaining fully dynamic algorithms for planar
graphs (described in Section 5).

##  4 A fully dynamic $(1+\epsilon)$-approximate algorithm

In this section we show how Lemma 12 can be used to obtain an
$(1+\epsilon)$-approximate minimum weight cycle algorithm, for any
$\epsilon\in(0,1]$. Suppose $c\in\mathbb{R}$ ($C\in\mathbb{R}$) is a lower
bound (an upper bound, respectively) on the weight of a _positive_ cycle in
$G$.

Suppose first that $G$ has positively weighted edges. In order to convert the
decision version from Section 3, all we have to do is to run it simultaneously
with $\mu=(1+\epsilon)^{k}$ for all integers
$k=\lceil\log_{1+\epsilon}(c)\rceil,\ldots,\lceil\log_{1+\epsilon}(C)\rceil$.
To maintain an approximate minimum weight of a cycle $G$, one only needs to
keep track of the minimum $k$ such that the fully dynamic decision algorithm
for $(1+\epsilon)^{k}$ returns yes. If no such $k$ exists, $G$ is acyclic
since $\phi(G)<\infty$ implies $\phi(G)\leq C$. Otherwise, we have
$(1+\epsilon)^{k-1}\leq\phi(G)<(1+\epsilon)^{k}$, so indeed $(1+\epsilon)^{k}$
approximates $\phi(G)$ with multiplicative error no more than $(1+\epsilon)$.
Since each of the
$O(\log_{1+\epsilon}(C)-\log_{1+\epsilon}(c))=O(\log{(C/c)}/\epsilon)$
decision algorithms has $O(m+n\log{n})$ amortized update time, the amortized
time of the approximate algorithm is $O((m+n\log{n})\log{(C/c)}/\epsilon)$.

The same bound can be achieved even if $G$ has non-positive edges (without,
however, changing the definition of $c$ and $C$) by extending each threshold
data structure as described in Section 3.1. Apart from the data structures for
thresholds $\mu=(1+\epsilon)^{k}$, we also need two more threshold cycle
detection data structures: one for $\mu=0$ to detect a negative cycle, and one
for $\mu=c$ to detect whether $\phi(G)=0$. We have thus proved Theorem 1.

See 1

##  5 Dynamic algorithms for cycles, cuts and flows in planar graphs

In this section we argue that the fully dynamic threshold cycle detection
algorithm can be implemented on planar directed graphs using the known dynamic
distance oracles on planar graphs. Since the reduction in Section 4 uses the
threshold data structure in a black-box way, this will imply an
$(1+\epsilon)$-approximate minimum weight cycle algorithm.

Using known reductions based on plane duality, this will yield fully dynamic
$(1+\epsilon)$-approximate algorithms for maintaining (1) the capacity of a
global min-cut in a plane digraph, (2) the value of maximum $s,t$-flow in a
plane digraph.

The algorithms in this section handle _edge updates_ , as opposed to more
general vertex updates as was the case in the previous sections. Observe that
achieving sublinear update time for vertex updates is not possible in general
since a vertex update may need up to $\Theta(n)$ space to be described. More
concretely, we will allow a single update to either insert or remove a single
edge $uv$, provided that this update preserves planarity of $G$. In the
cut/flow applications we will additionally need to assume that the edge
insertions are _embedding preserving_ , i.e., $u$ and $v$ lie on a single face
of the current embedding of $G$.

Kaplan et al. [32], based on earlier work [22, 36], showed a dynamic distance
oracle for real-weighted plane graphs undergoing edge weight updates. As
argued in [12], their bound also holds if arbitrary, not necessarily
embedding-preserving, edge updates are allowed.

######  Theorem 16 (see [12, 22, 32, 36]).

Let $G$ be a real-weighted planar digraph. There exists a fully dynamic
algorithm supporting edge insertions and deletions in $\widetilde{O}(n^{2/3})$
worst-case time, such that for any query vertices $s,t$, the shortest $s\to t$
path in $G$ can be computed in $\widetilde{O}(n^{2/3})$ time. If an edge
insertion creates a negative cycle in $G$, the update algorithm reports it and
refuses to perform that insertion. Edge insertions are not required to be
embedding preserving.

#### Fully dynamic threshold- and minimum weight cycles.

Consider using the fully dynamic threshold cycle detection algorithm of
Section 3 in the edge update scenario. Suppose that that algorithm attempts to
moves edges from $E_{1}$ to $E_{0}$ single edge at a time. This does not
influence correctness; the efficiency of processing a _node update_ could
deteriorate though (which we do not mind). Then, the _amortized_ update time
to process the update involving an edge $uv$ can be actually bounded by the
sum of times needed to:

  1. 1.

update the set $E_{1}(u)$ to reflect the graph update,

  2. 2.

if $uv$ is deleted, remove $uv$ from $G_{0}$,

  3. 3.

for some $xy\in E$, find the minimum weight of a cycle going through $xy$ in
$G_{0}+xy$,

  4. 4.

if $\phi(G_{0}+xy)\geq\mu$, insert the edge $xy$ into $G_{0}$.

Clearly, item 1 takes constant time. If we store the (planar) graph $G_{0}$ in
the data structure of Theorem 16, items 2-4 above all require
$\widetilde{O}(n^{2/3})$ time. Indeed, items 2 and 4 translated to a single
edge update to that data structure, whereas item 3 amounts to computing
$\delta_{G_{0}}(y,x)+w_{G}(xy)$ using a single query. We thus obtain the
following analogue of Theorem 7.

######  Theorem 17.

Let $G$ be a real-weighted planar digraph and let $\mu\geq 0$. There exist a
fully dynamic algorithm maintaining whether $\phi(G)<\mu$ and supporting
planarity-preserving edge insertions and deletions in $\widetilde{O}(n^{2/3})$
amortized time.

Since Theorem 1 uses the threshold data structure in a black-box way, we
obtain:

######  Theorem 18.

Let $G$ be a fully dynamic real-weighted planar digraph $G$ such that the
weight of any positive cycle in $G$ always lies in the interval $[c,C]$.

There exists an algorithm maintaining the minimum weight cycle in $G$ under
planarity preserving edge insertions and deletions with amortized update time
$\widetilde{O}(n^{2/3}\log{(C/c)}/\epsilon)$.

Note that Theorem 18 immediately implies Theorem 2.

#### Fully dynamic directed cuts and flows.

Let $G$ be a _plane embedded_ digraph with real edge capacities in
$\\{0\\}\cup[1,W]$. Assume that every edge $e$ in $G$ has its reverse $e^{R}$
of capacity $0$ embedded into the same curve. We can then think of any edge as
traversable in both directions, but the cost of such a traversal is $0$ if the
edge is traversed in the reverse direction. This assumption clearly does not
influence values of max-flows or min-cuts in $G$, but makes the dual graph
$G^{*}$ possess certain useful properties. We call a cycle in $G^{*}$ _non-
trivial_ if it is not of the form $ee^{R}$ for some edge $e\in E(G^{*})$ and
its reverse $e^{R}$.

We now state well-known properties relating flows/cuts in $G$ to cycles in the
dual $G^{*}$.

######  Lemma 19 (see e.g. [37]).

The global minimum cut in a plane graph $G$ corresponds to the minimum weight
non-trivial cycle in $G^{*}$.

######  Lemma 20 (see [20, 31, 41]).

Let $G$ be a plane digraph with some fixed source $s$ and sink $t$. For $f\geq
0$, let $G_{P,f}$ be a plane graph obtained from $G$ adding an embedded $s\to
t$ path $P$ such that for each edge $e$ of $P$, the capacity of $e$ is $f$,
whereas the capacity of $e^{R}$ is $-f$.

There exists an $s,t$-flow of value $f$ in $G$ if and only if the dual
$G_{P,f}^{*}$ of $G_{P,f}$ does not contain negative cycles.

By Lemma 19, maintaining the (approximate) global min-cut dynamically under
edge _embedding preserving_ insertions/deletions can be reduced to maintaining
the (approximate) minimum weight non-trivial cycle in the dual under vertex
splits and edge contractions.

Let us now explain how such operations can be simulated using $O(1)$ updates
to the data structure of Theorem 18 maintained on a certain augmented version
$G^{*}_{1}$ of $G^{*}$, so that the minimum weights of a non-trivial cycle in
$G^{*}$ and $G^{*}_{1}$ are equal. A similar reduction has been previously
described in [29, 37]. Each vertex $v$ of the dual $G^{*}$ corresponds in
$G^{*}_{1}$ to a path $P_{v}$ of $\deg_{G^{*}}(v)$ vertices connected using
$0$-weight edges traversable in both directions. For an edge $vu\in E(G^{*})$
that is the $i$-th in (some) clockwise edge ring of $v$, and $j$-th in (some)
clockwise edge ring of $u$, the $i$-th vertex of $P_{v}$ is connected by an
edge of weight $w_{G^{*}}(vu)$ with the $j$-th vertex of $P_{u}$. This way,
(1) each vertex of $G_{1}^{*}$ has constant degree, (2) each non-trivial cycle
in $G^{*}$ has a corresponding non-trivial cycle of the same weight in
$G^{*}_{1}$, (3) no additional (with respect to $G^{*}$) non-trivial cycles
are introduced in $G^{*}_{1}$.

It is not hard to verify that each edge contraction or vertex split in $G^{*}$
can be reflected using $O(1)$ edge insertions or deletions issued to
$G_{1}^{*}$.

Observe that the additional constraint that the minimum weight cycle is non-
trivial does not introduce any serious difficulties: in the data structure of
Theorem 17 we compute the minimum weight cycle through some edge $e$ by
issuing a distance query to a graph that _does not contain_ that edge.
However, since a minimum weight non-trivial cycle through $e$ in $G_{0}+e$ can
traverse $e$ in any of the two directions, we need to issue two distance
queries instead of one. Similarly, if the minimum weight of a non-trivial
cycle in $G_{0}+e$ is at least $\mu$, we add both edges $e$ and $e^{R}$ (with
appropriate weights) to the distance oracle maintaining $G_{0}$.

We thus obtain the following theorem.

######  Theorem 21.

Let $G$ be a plane digraph with real capacities in $\\{0\\}\cup[1,W]$. There
is an algorithm maintaining a $(1+\epsilon)$-approximate estimate of the
capacity of the global min-cut of $G$ under _embedding preserving_ edge
updates with $\widetilde{O}(n^{2/3}\log{W}/\epsilon)$ amortized update time.

To obtain a dynamic max $s,t$-flow algorithm, we use Lemma 20. We keep track
of whether there exists a negative cycle (i.e., we set $\mu=0$) in the dual of
a graph a $G_{P,f}$, where $f=(1+\epsilon)^{k}$, for each
$k=0,\ldots,\lceil\log_{1+\epsilon}{(nW)}\rceil$. Similarly as was the case
for global min-cut, one can simulate the effect that an embedding preserving
edge update in $G$ has on the negative cycles of the dual of $G_{P,f}$ using
$O(1)$ updates to the data structure of Theorem 17 maintained on an analogous
augmentation $(G_{P,f})^{*}_{1}$ of $G_{P,f}^{*}$.

There is one subtle detail about how $G_{P,f}$ is updated when $G$ is subject
to embedding preserving edge insertions and deletions. Note that Lemma 20
requires us to embed any additional simple $s\to t$ path $P$ into $G$.
Embedding $P$ into $G$ subdivides some of the original faces of $G$. As a
result, an edge $uv$ to be inserted inside some face $F$ of $G$ may cross some
edges of the currently used path $P$ in $G_{P,f}$. We deal with this problem
as follows. We maintain an additional invariant that (the embedding of) the
simple path $P$ crosses each face of the plane graph $G$ at most once.

Now, when a new edge $uv$ is inserted inside $F$, and $P$ has an edge $e=xy$
inside $F$ that would cross $uv$, we first remove $e$ from $G_{P,f}$ to allow
the insertion of $uv$. This insertion splits $F$ into two faces $F_{1},F_{2}$
such that $x$ lies on $F_{1}$ and $y$ lies on $F_{2}$. We now reconnect the
path $P$ by embedding two edges $xu$, $uy$ with appropriate capacities as
required by Lemma 20.

On the other hand, when an edge $uv$ is removed, two faces $F_{1}$ of $F_{2}$
of $G$ are merged into a single face $F$. If at most one of them $F_{1},F_{2}$
contained an edge of $P$, we do not have to do anything. Otherwise, suppose
wlog. that $F_{1}$ contains an edge $xy=e_{1}\in P$, and $F_{2}$ contains an
edge $ab=e_{2}\in P$, such that $e_{1}$ appears before $e_{2}$ on $P$. Then,
we remove $e_{1}$, $e_{2}$, and all edges between $e_{1}$ and $e_{2}$ on $P$
from $G_{P,f}$, and replace them with a single edge $xb$ embedded in $F$.
Afterwards, the invariant is satisfied and $P$ remains a simple path.

Finally, observe that each update to $G$ adds $O(1)$ new edges to $P$ in the
_worst case_. An edge deletion may remove a superconstant number of edges from
$P$, but these removals can be charged to the corresponding additions of new
edges to $P$. To conclude, an edge update to $G$ translates to $O(1)$
amortized edge updates to $G_{P,f}$, and as a result, to $O(1)$ amortized
operations on the data structure of Theorem 17 run on the augmented dual
$(G_{P,f})^{*}_{1}$. We have thus proved: See 3

##  6 Exact fully dynamic algorithm for minimum weight cycle

In this section we argue that using a variant of the fully dynamic APSP
algorithm of Abraham et al. [2] one can achieve subquadratic update bounds for
exact dynamic minimum weight cycle.

We will in fact first solve a slightly more general problem that we call the
_fully dynamic multiple-pairs shortest paths_ (fully dynamic MPSP for short).
Our goal is to have a data structure that maintains distances
$\delta_{G}(s_{i},t_{i})$ for some _fixed_ (throughout the course of the
algorithm) $k$ source-target pairs $(s_{1},t_{1}),\ldots,(s_{k},t_{k})$
subject to fully dynamic vertex updates. Obviously, the classical fully
dynamic APSP corresponds to the case $k=n^{2}$.

In the following we sketch the approach of [2] to fully dynamic APSP. The
presentation is however directed towards our goal of obtaining an MPSP data
structure. Some details and proofs can be found only in [2]; we focus on the
details of our adjustments.

#### Reduction to batch-deletion MPSP data structure.

The first step is to reduce the fully dynamic problem to a certain decremental
problem, called the _batch-deletion MPSP_. In this problem, we want to
preprocess the input digraph $G$, so that one can efficiently compute MPSP in
$G\setminus D$ for a subset $D\subseteq V$ that constitutes the query
parameter. We assume that if $G\setminus D$ has a negative cycle, the data
structure has to report its existence instead.

######  Lemma 22.

Suppose we have a batch-deletion MPSP data structure with preprocessing
time$T_{\mathrm{pre}}(n,m,k)$ and worst-case query time
$T_{\mathrm{q}}(n,m,k,d)$, where $d=|D|$ is the size of the removed vertex
set. Then, for any integer $\Delta>0$, there exists a fully dynamic MPSP
algorithm with worst-case update time
$O(T_{\mathrm{pre}}(n,m,k)/\Delta+T_{\mathrm{q}}(n,m,k,\Delta)+\Delta(m+k+n\log{n}))$.

###### Proof sketch..

To obtain an amortized (as opposed to worst-case) bound from the statement, we
split the timeline into phases of $\Delta$ updates. When a new phase starts,
we rebuild the batch-deletion data structure from scratch on the graph $G_{0}$
at the start of the phase; this clearly incurs
$O(T_{\mathrm{pre}}(n,m_{0},k)/\Delta)$ amortized time cost per update, where
$m_{0}=|E(G_{0})|$. At some point of a phase, let $D\subseteq V$,
$|D|\leq\Delta$, be the vertices touched by updates in this phase. To compute
MPSP at that point, we first compute MPSP in $G_{0}\setminus D=G\setminus D$
in $O(T_{\mathrm{q}}(n,m_{0},k,|D|))=O(T_{\mathrm{q}}(n,m_{0},k,\Delta))$
time. To obtain MPSP in $G$, we need to check if paths going through $D$ in
$G$ improve upon those in $G\setminus D$, i.e., we compute MPSP in $G$
according to the equation
$\delta_{G}(s_{i},t_{i})=\min\left(\delta_{G_{0}\setminus
D}(s_{i},t_{i}),\min_{v\in
D}\\{\delta_{G}(s_{i},v)+\delta_{G}(v,t_{i})\\}\right).$

Observe that all distances of the form $\delta_{G}(\cdot,v)$ or
$\delta_{G}(v,\cdot)$ for $v\in D$ can be obtained by running Dijkstra‘s
algorithm to/from each such $v$, in $O(\Delta(m+n\log{n}))$ total time, as
long as a feasible price function of $G$ is given. A feasible price function
can be maintained in $O(m+n\log{n})$ worst-case time after a vertex update
using the following theorem proved later in Section 6.3.

######  Theorem 23.

Let $G$ be an initially empty real-weighted digraph. There exists an algorithm
maintaining the information whether $G$ has a negative cycle and supporting
vertex updates in $O(m+n\log{n})$ _worst-case_ time. Additionally, whenever
$\phi(G)\geq 0$, the algorithm maintains a feasible price function $p$ of $G$.

Theorem 23 is also used to keep track of whether the current $G$ has a
negative cycle. Once the distances from/to $v$ in $G$ are available, the
distances $\delta_{G}(s_{i},t_{i})$ can be computed in $O(\Delta\cdot k)$
time.

Unfortunately, the above argument is fully valid only if either the number of
edges $m$ is of the same order throughout, i.e., $m_{0}=O(m)$, or it cannot
drop by more than a constant factor during a single phase, e.g.,
$m=\Omega(n\Delta)$. If, say, $T_{\mathrm{pre}}(n,m,k)=\Theta(nm)$,
$\Delta=n^{1/3}$ and $m=n^{5/4}=m_{0}$ at the beginning of the phase, and
during $n^{1/4}$ first updates in that phase $m$ gets decreased to $O(n)$,
then the total update cost coming from the preprocessing in this phase is
$\Theta(nm_{0})=\Theta(n^{9/4})$. If the amortized update time coming from the
preprocessing was indeed $O(T_{\mathrm{pre}}(n,m,k)/\Delta)$, the the total
update cost coming from these terms in that phase would be $O(n^{1/4}\cdot
nm_{0}/\Delta+\Delta\cdot n^{2}/\Delta)=O(n^{13/6})$, which is less by a
polynomial factor..

We circumvent this problem444This problem does not arise in [2], since there
$m$ is assumed to be $\Theta(n^{2})$ throughout. as follows. We build the
batch-deletion MPSP data structure on the graph $G^{\prime}_{0}=G_{0}\setminus
D^{*}$ instead of $G_{0}$, where $D^{*}$ is the set of $\Delta$ vertices of
$G_{0}$ with highest degrees. Then, Dijkstra‘s algorithm is used to separately
compute shortest paths through $D\cup D^{*}$ in $G$, as opposed to only
through $D$. Clearly, the cost of such computation remains
$O(\Delta(m+k+n\log{n}))$. However, the update cost coming from the batch-
deletion MPSP data structure is decreased to
$O(T_{\mathrm{pre}}(n,m_{0}^{\prime},k)/\Delta+T_{\mathrm{q}}(n,m_{0}^{\prime},k,\Delta))$,
where $m_{0}^{\prime}$ is the number of edges in $G_{0}^{\prime}$. It is hence
enough to observe that $m^{\prime}_{0}\leq m$ throughout this phase. Indeed,
the updates centered at vertices $D$ cannot remove more than $\sum_{v\in
D}\deg_{G_{0}}(v)$ edges out of those originally contained in $G_{0}$. As a
result, $m\geq m_{0}-\sum_{v\in D}\deg_{G_{0}}(v)$. On the other hand, by
removing $D^{*}$ from $G_{0}$ we remove at least $\frac{1}{2}\sum_{v\in
D^{*}}\deg_{G_{0}}(v)$ edges from $G_{0}$, i.e, $m_{0}^{\prime}\leq
m_{0}-\frac{1}{2}\sum_{v\in D^{*}}\deg_{G_{0}}(v)$. We obtain
$m_{0}^{\prime}\leq m$ as follows:

$m_{0}^{\prime}\leq m_{0}-\frac{1}{2}\sum_{v\in D^{*}}\deg_{G_{0}}(v)\leq
m_{0}-\frac{1}{2}\sum_{v\in D}\deg_{G_{0}}(v)\leq
m_{0}+\frac{1}{2}(m-m_{0})=\frac{1}{2}m_{0}^{\prime}+\frac{1}{2}m.$

Since the amortization comes only from a (costly) rebuilding step after every
$\Delta$ updates, turning the amortized bound into a worst-case one is
standard, see e.g., [2, Section 2]. ∎

#### The batch-deletion data structure.

Abraham et al. [2] showed a batch-deletion APSP data structure with
$\widetilde{O}(n^{3})$ preprocessing time and $\widetilde{O}(n^{2}\sqrt{nd})$
query time which, by Lemma 22, implies $\widetilde{O}(n^{2+2/3})$ worst-case
update time for fully dynamic APSP. Their batch-deletion data structure is
Monte Carlo randomized and produces answers correct with high probability. We
generalize this data structure to MPSP and non-dense graphs.

######  Theorem 24.

There exists a Monte Carlo randomized batch-deletion MPSP data structure with
$O((m+k)n\log^{2}{n})$ preprocessing and $O((m+n\log{n}+k)\sqrt{nd}\log{n})$
query time. The answers produced are correct with high probability.

Before we prove Theorem 24, let us show how it can be used to obtain fully
dynamic MPSP and minimum weight cycle algorithms.

By choosing $\Delta=n^{1/3}\log^{2/3}n$, and applying Lemma 22, we obtain:

See 5 Now consider the fully dynamic minimum weight cycle problem. The minimum
weight of a cycle in $G$ is given by $\phi(G)=\min_{uv\in
E(G)}\\{\delta_{G}(v,u)+w_{G}(uv)\\}$. As a result, after each update it is
enough to recompute distances $\delta_{G}(s_{l},t_{l})$ in $G$ for $k=m$ pairs
$(s_{l},t_{l})$ such that $t_{l}s_{l}\in E(G)$. If the edge set of $G$ was
fixed (and, for example, the updates were only allowed to change edge
weights), so would be the set of source-target pairs of our interest. Hence,
we could simply use the fully dynamic MPSP data structure of Theorem 5 in a
black-box way. However, in general, $E(G)$ is not fixed and we need to be more
careful.

We proceed as follows. In the reduction of Lemma 22, we will always build a
batch-deletion MPSP data structure with the set of source-target pairs equal
to the edge set used to build that data structure reversed. This means that at
any point of the phase, we can compute the minimum weight cycle in
$G\setminus(D^{*}\cup D)=G_{0}\setminus(D^{*}\cup D)$ in

$O(T_{\mathrm{pre}}(n,m,m)/\Delta+T_{\mathrm{q}}(n,m,m,\Delta))=O((m+n\log{n})n^{2/3}\log^{4/3}n)$

worst-case time. Since $G_{0}\setminus(D^{*}\cup D)$ contains only a subset of
edges of $G_{0}$, reading the subset of entries of the distance matrix of
$G_{0}\setminus(D^{*}\cup D)$ corresponding to reversed edges of $E(G_{0})$ is
enough to this end. In order to find the minimum weight cycle going through
some vertex of $D^{*}\cup D$ in $G$, we just run the algorithm of Observation
6 (or, more generally, in presence of negative edges – the algorithm of Lemma
14 with a feasible price function maintained by the algorithm of Theorem 23)
$|D^{*}\cup D|=O(\Delta)$ times. This costs
$O(\Delta(m+n\log{n}))=\widetilde{O}(mn^{1/3})$ time.

See 4

###  6.1 Overview of the batch-deletion MPSP data structure

Let us now sketch the idea behind our generalization of the batch-deletion
data structure of [2]. The details are given in Section 6.2.

We first need to refer to some details of the construction of Abraham et al.
[2]. The batch-deletion data structure separately handles recomputing shortest
paths of hop-length at least $\sqrt{n/d}$ (’’long‘‘ paths), and separately
’’short‘‘ shortest paths – with hop-lengths in the intervals of the form
$[h/2,h)$ for $O(\log{n})$ values $h=2^{1},2^{2},\ldots,\sqrt{n/d}$.

The main difficulty lies in handling short paths, whereas handling long paths
is an easier task. The key idea (which dates back to Thorup [48]) is to
compute an ordered subset $\\{v_{1},\ldots,v_{\ell}\\}\subseteq V$ with the
following properties. Let $G_{i}=G\setminus\\{v_{1},\ldots,v_{i-1}\\}$. Let
$\mathcal{P}_{i}$ be the set of shortest $\leq h$-hop paths from/to $v_{i}$ in
$G_{i}$. Then:

  1. (1)

For any $s,t\in V$, an $s\to t$ path not longer than the shortest $\leq h$-hop
$s\to t$ path in $G$ can be obtained by stitching, for some
$i\in\\{1,\ldots,\ell\\}$, the $s\to v_{i}$ and $v_{i}\to t$ paths from
$\mathcal{P}_{i}$.

  2. (2)

For any $x\in V$, $x$ lies on at most $\widetilde{O}(hn)$ paths from
$\bigcup_{i=1}^{\ell}\mathcal{P}_{i}$.

Such an ordering, along with the paths $\mathcal{P}_{i}$, can be computed in
$\widetilde{O}(nmh)$ time deterministically (then we have $\ell=n$), or in
$\widetilde{O}(nm)$ time using randomization (then we can achieve
$\ell=\widetilde{O}(n/h)$). Each subsequent vertex $v_{i}$ in the ordering is
picked to be, roughly speaking, the ’’most congested‘‘ one out of
$V\setminus\\{v_{1},\ldots,v_{i-1}\\}$, i.e., the one that has not been picked
yet and appears most often on the previously constructed paths
$\bigcup_{j=1}^{i-1}\mathcal{P}_{j}$.

Given the above, Abraham et al. [2] show that after removing any $D\subseteq
V$ from $G$, the ’’short‘‘ paths in $G$ can be recomputed by:

  1. (1)

constructing a number of _sketch graphs_ $H_{1},\ldots,H_{\ell}$, where
$H_{i}\subseteq G_{i}\setminus D$,

  2. (2)

rebuilding destroyed (by the removal of $D$) paths from $\mathcal{P}_{i}$ by
running Dijkstra‘s algorithm from/to $v_{i}$ on $H_{i}$,

  3. (3)

stitching the reconstructed paths back to obtain paths at leas as good as the
actual shortest $\leq h$-hop paths in $G$.

Abraham et al. [2] prove that if we denote by $U_{i}$ the set of vertices $u$
such that either of the paths $u\to v_{i}$ or $v_{i}\to u$ from
$\mathcal{P}_{i}$ has been destroyed by removing $D$, $d=|D|$, then we have
$\sum_{i=1}^{\ell}|U_{i}|=\widetilde{O}(hnd)$, and the total number of edges
$M$ in the sketch graphs is

$M=O\left(\sum_{i=1}^{\ell}\left(n+\sum_{u\in
U_{i}}\deg_{G}(u)\right)\right).$

It is easy to see that $M=\Omega(n\ell)$, and $M=\tilde{O}(hn^{2}d)$.
Moreover, for each rebuilt path $u\to v_{i}$ or $v_{i}\to u$, stitching takes
additional $\Theta(n)$ time – as one needs to traverse through $\Theta(n)$
source-target pairs that might benefit from this – for a total of
$\widetilde{O}(hn^{2}d)$ time. Since $h$ ranges from $O(1)$ to
$\Theta\left(\sqrt{n/d}\right)$, rebuilding short paths takes $\Omega(n^{2})$
and $\widetilde{O}(n^{2}\sqrt{nd})$ time as claimed.

Now, to obtain our improved $\widetilde{O}((m+k)\sqrt{nd})$ bound on batch
deletion for sparse graphs and small number $k$ of source-target paths
$(s_{i},t_{i})$ of interest, we make two main adjustments.

First of all, we show that even smaller sketch graphs $H_{i}$ – with
$O\left(\sum_{i}^{\ell}\sum_{u\in U_{i}}\deg_{G}(u)\right)$ edges in total –
can be used, thus eliminating the $\Omega(n\ell)$ term, which for small $h$ is
$\Omega(n^{2})$.

More importantly, we use a different _weighted_ scheme for picking the ordered
subset $\\{v_{1},\ldots,v_{\ell}\\}$. Let us denote by $K$ the undirected
graph on $V$ whose edges correspond to the source-target pairs $(s_{i},t_{i})$
of interest. In our scheme, the congestion that a previously computed $\leq
h$-hop path $P=v_{i}\to u$ (or $P=u\to v_{i}$) incurs upon some vertex $x$
with $x\in V(P)$ is $\deg_{G}(u)+\log{n}+\deg_{K}(u)$, as opposed to $1$ in
[2]. This makes the total congestion of each vertex $x$ in the process
possibly increase to $\tilde{\Theta}(h(m+n\log{n}+k))$, as opposed to
$\widetilde{O}(hn)$ in [2]. However, we show that the total cost of running
Dijkstra‘s algorithm on our (more compact) sketch graphs
$H_{1},\ldots,H_{\ell}$ can be charged to the part of the total congestion of
removed vertices $D$ coming from the $[\deg_{G}(u)+\log{n}]$ terms, which is
$\widetilde{O}(dh(m+n\log{n}))$. A similar argument applies to the cost of
restitching, which we prove to be $\widetilde{O}(dhk)$.

###  6.2 Batch-deletion MPSP data structure

In this section we provide a proof of Theorem 24. As our adjustments to the
data structure of Abraham et al. [2] are somewhat low-level, this section also
contains a presentation of this data structure using our notation, with some
unaltered proofs deferred to [2].

Let us first assume that $G$ has non-negative edge weights. We remove this
assumption later on.

For a path $P\subseteq G$, let $|P|$ denote the hop-length or $P$. Moreover,
denote by $\delta_{G}^{k}(s,t)$ the length of the shortest $\leq k$-hop $s\to
t$ path in $G$. Clearly, we have $\delta_{G}(s,t)=\delta_{G}^{n-1}(s,t)$.

Denote by $P_{G}(s,t)$ the shortest $s\to t$ path in $G$. We may consider
$P_{G}(s,t)$ uniquely defined by imposing any fixed (e.g., lexicographical)
order on the shortest $s\to t$ paths in $G$ and defining $P_{G}(s,t)$ more
precisely as the smallest shortest $s\to t$ path in $G$ according to that
order. We will use the following well-known fact.

######  Fact 25.

Let $h$ be an integer, $1\leq h\leq n$. With high probability555Depending on
the constant hidden in the $\Theta$ notation., a random subset $C\subseteq V$
of size $\Theta((n/h)\log{n})$ hits all the paths $P_{G}(s,t)$ for $s,t\in V$
with $|P_{G}(s,t)|\geq h/2$.

Let $h=2^{\ell}$, $1\leq h\leq n$, be an integral parameter to be set later.
Let $h_{i}=2^{i}$ for $i=1,\ldots,\ell$. For $i=1,\ldots,\ell$, let $C_{i}$ be
a random subset of $V$ of size $\Theta((n/h_{i})\log{n})$. The general idea is
to leverage the set $C_{i}$ to efficiently recompute shortest paths with hop-
lengths in $[h_{i}/2,h_{i})$. Additionally, we will also use the last set
$C_{\ell}$ to recompute paths with at least $h=h_{\ell}$ hops. By Fact 25, for
all $i$, $C_{i}$ hits shortest paths with $h_{i}$ or more hops in $G$ whp.

What is more important, $C_{i}$ hits all $\geq h_{i}/2$-hop shortest paths in
graphs $G\setminus D_{j}$ for polynomially many different sets $D_{j}\subseteq
V$, provided that the choice of these subsets is independent of $C_{i}$, i.e.,
if the adversary does not know $C_{i}$. As a result, we can sample the sets
$C_{i}$ just once during the preprocessing stage and use them to process
$O(\operatorname{poly}{n})$ different batch-deletion queries $D$, while
remaining almost certain that $C_{i}$ hits the $\geq h_{i}/2$-hop shortest
paths of $G\setminus D$.

For technical reasons that will become clear later, we will need to slightly
augment the sampled sets $C_{i}$ and subsequently impose an order on them. So,
suppose ${\overline{C}}_{i}$ is such that $C_{i}\subseteq{\overline{C}}_{i}$,
and $|{\overline{C}}_{i}|=\Theta((n/h_{i})\log{n})$. Moreover, let
${\overline{C}}_{i}=\\{c_{i,1},\ldots,c_{i,|{\overline{C}}_{i}|}\\}$. For
$j=1,\ldots,|{\overline{C}}_{i}|$, let
${\overline{C}}_{i,j}=\\{c_{i,1},\ldots,c_{i,j-1}\\}$. Clearly,
$\emptyset={\overline{C}}_{i,1}\subset{\overline{C}}_{i,2}\subset\ldots\subset{\overline{C}}_{i,|{\overline{C}}_{i}|}\subset{\overline{C}}_{i}$.

Let $H\subseteq G$ be any subgraph of $G$. For $i=0,\ldots,\ell$, $s,t\in V$,
and $j=1,\ldots,|{\overline{C}}_{i}|$, define

$d_{H}^{i,j}(s,t)=\delta_{H\setminus{\overline{C}}_{i,j}}^{h_{i}}(s,c_{i,j})+\delta_{H\setminus{\overline{C}}_{i,j}}^{h_{i}}(c_{i,j},t).$
(1)

In words, $d_{H}^{i,j}$ is the minimal length of a $s\to t$ path in $H$ that:

  1. 1.

avoids all vertices ${\overline{C}}_{i,j}$,

  2. 2.

goes through a vertex $c_{i,j}$ and this vertex is no more than $h_{i}$ hops
apart from both endpoints on that path.

Let $d^{\mathrm{long}}_{H}(s,t)$ be the minimal length of an $s\to t$ path in
$G$ that goes through $C_{\ell}$:

$d^{\mathrm{long}}_{H}(s,t)=\min_{v\in
C_{\ell}}\left\\{\delta_{H}(s_{i},v)+\delta_{H}(v,t_{i})\right\\}.$ (2)

######  Lemma 26.

For any $H\subseteq G$, and $s,t\in V$, with high probability we have:

$\delta_{H}(s,t)=\min\left(d^{\mathrm{long}}_{H}(s,t),\min_{i,j}\left\\{d_{H}^{i,j}(s,t)\right\\}\right).$

###### Proof.

Let
$Q=\left\\{d^{\mathrm{long}}_{H}(s,t)\right\\}\cup\bigcup_{i,j}\left\\{d_{H}^{i,j}(s,t)\right\\}$.
We have to prove $\delta_{H}(s,t)=\min Q$. Note that each element constitutes
a length of some $s\to t$ path in $H$, so $\delta_{H}(s,t)\leq\min Q$. As a
result, it is sufficient to prove $\delta_{H}(s,t)\geq\min Q$.

If $|P_{H}(s,t)|\geq h$, then by Fact 25, $P_{H}(s,t)$ is (whp.) hit by a
vertex in $C_{\ell}$. As a result,
$\delta_{H}(s,t)=\delta_{H}(s,v)+\delta_{H}(v,t)$ for some $v\in C_{\ell}$.
This implies $\delta_{H}(s,t)\geq d^{\mathrm{long}}_{H}(s,t)\geq\min Q$.

Otherwise, let $i\in\\{1,\ldots,\ell\\}$ be such that
$|P_{H}(s,t)|\in[h_{i}/2,h_{i})$. By Fact 25, and since
$C_{i}\subseteq{\overline{C}}_{i}$, $P_{H}(s,t)$ contains a vertex of
${\overline{C}}_{i}$ whp. Let $j$ be minimal such that
$c_{i,j}\in{\overline{C}}_{i}$ lies on $P_{H}(s,t)$. Then,
$P_{H}(s,t)\subseteq H\setminus{\overline{C}}_{i,j}$. Since $P_{H}(s,t)$ has
no more than $h_{i}$ hops, $c_{i,j}$ is no more than $h_{i}$ hops apart from
both endpoints $s,t$. As a result, we have:

$\delta_{H}(s,t)\geq\delta^{h}_{H\setminus{\overline{C}}_{i,j}}(s,c_{i,j})+\delta^{h}_{H\setminus{\overline{C}}_{i,j}}(c_{i,j},t)=d_{H}^{i,j}(s,t)\in
Q.$

We conclude $\delta_{H}(s,t)\geq\min Q$. ∎

Given a query set $D\subseteq V$, the data structure will compute for all
pairs $(s_{l},t_{k})$, $l=1,\ldots,k$: (1) $d^{\mathrm{long}}_{G\setminus
D}(s_{l},t_{l})$, and (2) for all $i=1,\ldots,\ell$, an _estimate_
$\tilde{d}^{i}_{G\setminus D}(s_{l},t_{l})$ such that

$\delta_{G\setminus D}(s_{l},t_{l})\leq\tilde{d}^{i}_{G\setminus
D}(s_{l},t_{l})\leq\min_{j}\left\\{d^{i,j}_{G\setminus
D}(s_{l},t_{l})\right\\}.$ (3)

The former values handle ’’long paths‘‘, whereas the latter – ’’short paths‘‘.
By Lemma 26, computing these values is enough to obtain $\delta_{G\setminus
D}(s_{l},t_{l})$ with high probability, since we have:

$\displaystyle\delta_{G\setminus D}(s_{l},t_{l})$
$\displaystyle\leq\min\left(d^{\mathrm{long}}_{G\setminus
D}(s,t),\min_{i}\left\\{\tilde{d}^{i}_{G\setminus D}(s,t)\right\\}\right)$
$\displaystyle\leq\min\left(d^{\mathrm{long}}_{G\setminus
D}(s,t),\min_{i,j}\left\\{d_{G\setminus D}^{i,j}(s,t)\right\\}\right)$
$\displaystyle=\delta_{G\setminus D}(s_{l},t_{l}).$

#### Long paths.

Handling long paths requires no preprocessing apart from sampling $C_{\ell}$.
In order to recompute $d^{\mathrm{long}}_{G\setminus D}(s_{l},t_{l})$ for all
pairs $(s_{l},t_{l})$ we simply run Dijkstra‘s algorithm on $G\setminus D$
from/to all $v\in C_{\ell}$. This takes $O((m+n\log{n})\cdot(n/h)\log{n})$
time. Afterwards, computing each $d^{\mathrm{long}}_{G\setminus
D}(s_{l},t_{l})$ takes $O(|C_{\ell}|)=O((n/h)\log{n})$ additional time. Thus,
we obtain:

######  Lemma 27.

Recomputing all $d^{\mathrm{long}}_{G\setminus D}(s_{l},t_{l})$ takes
$O((m+n\log{n}+k)\cdot(n/h)\log{n})$ time.

#### Preprocessing for rebuilding short paths.

Recomputing shorter paths efficiently is a much more involved task and
involves heavy preprocessing of $G$ described below.

For each $i=1,\ldots,\ell$, we proceed as follows. We start by initializing
the _congestion_ $\alpha(v)$ of each $v\in V$ to $0$. We also initialize
${\overline{C}}_{i}$ to $\emptyset$. While
$C_{i}\setminus{\overline{C}}_{i}\neq\emptyset$, we extend
${\overline{C}}_{i}$ by a single vertex $c_{i,j}$ at a time. More precisely,
suppose that when such an extension is about to happen, the current size of
${\overline{C}}_{i}$ is $z$ and
${\overline{C}}_{i}=\\{c_{i,1},\ldots,c_{i,z}\\}$. If the most recently added
to ${\overline{C}}_{i}$ vertex was in $C_{i}$, i.e., $c_{i,z}\in C_{i}$, we
pick $c_{i,z+1}$ to be the most congested vertex $u\in
V\setminus({\overline{C}}_{i}\cup C_{i})$, i.e., the one such that $\alpha(u)$
is maximum. Otherwise, if $z=0$ or $c_{i,z}\notin C_{i}$, we pick $c_{i,z+1}$
to be an arbitrary vertex of $C_{i}\setminus{\overline{C}}_{i}$. After picking
$c_{i,z}$ and before the subsequent picks happen, we will adjust the vertices‘
congestions. Observe that such a selection process indeed guarantees that
$C_{i}\subseteq{\overline{C}}_{i}$ and $|{\overline{C}}_{i}|\leq
2|C_{i}|=O((n/h_{i})\log{n})$.

We now describe the preprocessing for each subsequent $c_{i,j}$ and how the
congestions of individual vertices are adjusted. Recall that when $c_{i,j}$ is
known, ${\overline{C}}_{i,j}$ is defined as well.

The first step is to compute $\leq h_{i}$-hop shortest paths in
$G\setminus{\overline{C}}_{i,j}$ from/to $c_{i,j}$. Some shortest $\leq
h_{i}$-hop path (if it exists) to each $v\in V\setminus{\overline{C}}_{i,j}$
from $c_{i,j}$ is stored as $\pi^{\mathrm{to}}_{i,j}(v)$. Similarly, some
shortest $\leq h_{i}$-hop from each $v\in V\setminus{\overline{C}}_{i,j}$ to
$c_{i,j}$ is stored as $\pi^{\mathrm{from}}_{i,j}(v)$. Computing these paths
requires running a variant of Bellman-Ford algorithm up to depth $h_{i}$
from/to $c_{i,j}$ and thus takes $O(mh_{i})$ time. Since
$|{\overline{C}}_{i}|=O((n/h_{i})\log{n})$, the total time cost of this step
through all $c_{i,j}\in{\overline{C}}_{i}$ is $O(mn\log{n})$.

Let us now define an undirected graph $K$ on the vertex set $V$ that
represents pairs $(s_{l},t_{l})$, $l=1,\ldots,k$ or our interest. For each
such pair, there is a corresponding edge $s_{l}t_{l}$ in $K$.

For each of the paths $\pi^{\mathrm{from}}_{i,j}(v)$ or
$\pi^{\mathrm{to}}_{i,j}(v)$, we add $\deg_{G}(v)+\deg_{K}(v)+\log{n}$ to the
congestion $\alpha(x)$ of each vertex $x$ lying on these paths. Since these
paths contain $O(h_{i})$ vertices, the total congestion introduced by these
paths is $O((\deg_{G}(v)+\deg_{K}(v)+\log{n})\cdot h_{i})$. Consequently, the
total congestion added through all $v\in V$ when processing $c_{i,j}$ is:666In
[2], a single unit of congestion is added to each vertex on a path. As a
result, the total congestion added is only $O(h_{i}n)$. Weighting the path
congestions by the degree of the source/target is crucial to obtaining a
better bound on the time needed to rebuild these paths when processing a
query.

$O\left(h_{i}\sum_{v\in
V}\left(\deg_{G}(v)+\deg_{K}(v)+\log{n}\right)\right)=O(h_{i}(m+k+n\log{n})).$

Recall that the paths are computed in $G\setminus{\overline{C}}_{i,j}$, so the
congestions of vertices from ${\overline{C}}_{i,j}$ are not increased.

######  Lemma 28.

After all vertices $c_{i,j}\in{\overline{C}}_{i}$ are processed, for all $v\in
V$ we have$\alpha(v)=O(h_{i}(m+n\log{n}+k)\log{n})$.

###### Proof sketch..

Abraham et al. [2] argue that alternating between picking the most-congested
vertex and an arbitrary vertex as the next $c_{i,j}$ is enough to guarantee
that all the congestions at the end are of order $O(L\log{n})$, where $L$ is
the total congestion added for a single $c_{i,j}$. In particular, it does not
matter how the added congestion is distributed among the vertices. The lemma
follows since $L=O((m+n\log{n}+k)h_{i})$ in our case. ∎

For each vertex $u$ we also store a list $\Pi^{i}_{u}$ of pointers to paths of
the form $\pi^{\mathrm{from}}_{i,j}(v)$ or $\pi^{\mathrm{to}}_{i,j}(v)$
containing $u$. Observe that the total size of the lists $\Pi^{i}_{u}$ is
$O(|{\overline{C}}_{i}|\cdot n\cdot h_{i})=O(n^{2}\log{n})$.

Finally, for each source-target pair $(s_{l},t_{l})$ the pairs
$(d^{i,j}_{G}(s_{l},t_{l}),j)$, $j=1,\ldots,|{\overline{C}}_{i}|$, are stored
in a sorted array $S_{i}(s_{l},t_{l})$. Since computing shortest $\leq
h_{i}$-hop paths from/to $c_{i,j}$ also gives the lengths
$\delta_{G\setminus{\overline{C}}_{i,j}}^{h_{i}}(c_{i,j},\cdot)$ and
$\delta_{G\setminus{\overline{C}}_{i,j}}^{h_{i}}(\cdot,c_{i,j})$, we can also
easily compute $d^{i,j}_{G}(s_{l},t_{l})$ for each pair $(s_{l},t_{l})$ in
$O(|{\overline{C}}_{i}|)$ time. Therefore, computing all the required sets
$S_{i}(s_{l},t_{l})$ and sorting them takes $O(|{\overline{C}}_{i}|\cdot
k\log{n}))=O((n/h_{i})k\log^{2}{n})$ time.

######  Lemma 29.

The described preprocessing (through all $i$) takes $O((m+k)n\log^{2}{n})$
time.

###### Proof.

The total running time of the described preprocessing is:

$O\left(\sum_{i=1}^{\ell}mn\log{n}+(n/h_{i})k\log^{2}{n}\right)=O\left(mn\ell\log{n}+nk\log^{2}{n}\cdot\sum_{i=1}^{\infty}\frac{1}{2^{i}}\right),$

which yields the desired bound since $\ell=O(\log{h})=O(\log{n})$. ∎

#### Rebuilding short paths upon query.

Recall that upon query $D$, $|D|=d$, our goal is to compute estimates
$\tilde{d}^{i}_{G\setminus D}(s_{l},t_{l})$ satisfying (3).

For a fixed $i$, let $X_{i}(s_{l},t_{l})$ be the set of those $j$ such that
$D$ intersects either of the paths $\pi^{\mathrm{from}}_{i,j}(s_{l})$ or
$\pi^{\mathrm{to}}_{i,j}(t_{l})$.

######  Lemma 30.

We have $\sum_{l=1}^{k}|X_{i}(s_{l},t_{l})|=O(dh_{i}(m+n\log{n}+k)\log{n})$.
Moreover, all the sets $X_{i}(s_{l},t_{l})$ for $l=1,\ldots,k$ can be computed
in $O(dh_{i}(m+n\log{n}+k)\log{n})$ time.

###### Proof.

For each $v\in D$, we iterate through all the paths $\pi$ of the list
$\Pi^{i}_{v}$. If $\pi=\pi^{\mathrm{from}}_{i,j}(s_{l})$ for some $i,j,l$, we
go through all the neighbors $t^{\prime}$ of $s_{l}$ in $K$. If
$s_{l}t^{\prime}$ corresponds to some pair $(s_{l^{\prime}},t_{l^{\prime}})$,
we add $j$ to $X_{i}(s_{l^{\prime}},t_{l^{\prime}})$. Similarly, if
$\pi=\pi^{\mathrm{to}}_{i,j}(t_{l})$, we go through all the neighbors
$s^{\prime}$ of $t_{l}$ in $K$. If $s^{\prime}t_{l}$ corresponds to some pair
$(s_{l^{\prime}},t_{l^{\prime}})$, we add $j$ to
$X_{i}(s_{l^{\prime}},t_{l^{\prime}})$.

Let us analyze the running time of this algorithm limited to handling paths of
the form $\pi=\pi^{\mathrm{from}}_{i,j}(s_{l})$. The analysis in the other
case is analogous. For a fixed $v\in D$, and each
$\pi^{\mathrm{from}}_{i,j}(s_{l})$ with $v\in
V(\pi^{\mathrm{from}}_{i,j}(s_{l}))$, we spend $O(\deg_{K}(s_{l}))$ time
iterating through the neighbors of $s_{l}$ in the graph $K$. We charge this
cost to the $\deg_{K}(s_{l})$ contribution of the path
$\pi^{\mathrm{from}}_{i,j}(s_{l})$ to the congestion $\alpha(v)$. Note that
some of the costs – in case $\pi^{\mathrm{from}}_{i,j}(s_{l})$ has many
vertices from $D$ – can be charged to multiple vertices of $D$; however, what
matters is that no part of any $\alpha(v)$ is used to ’’pay‘‘ for two distinct
neighbors iterations. As a result, the total time can be bounded as
$O\left(\sum_{v\in D}\alpha(v)\right)=O(dh_{i}(m+n\log{n}+k)\log{n})$.

Since the total size of all the sets $X_{i}(s_{l},t_{l})$ cannot be larger
than the time needed to construct these sets, the above asymptotic expression
also bounds $\sum_{l=1}^{k}|X_{i}(s_{l},t_{l})|$. ∎

Recall that our goal is to compute, for each $i$ and $l$, such an estimate
$\tilde{d}^{i}_{G\setminus D}(s_{l},t_{l})$, that:

$\displaystyle\delta_{G\setminus D}(s_{l},t_{l})\leq\tilde{d}^{i}_{G\setminus
D}(s_{l},t_{l})$ $\displaystyle\leq\min_{j}\left\\{d^{i,j}_{G\setminus
D}(s_{l},t_{l})\right\\}$ $\displaystyle=\min\left(\min_{j\in
X_{i}(s_{l},t_{l})}\left\\{d^{i,j}_{G\setminus
D}(s_{l},t_{l})\right\\},\min_{j\notin
X_{i}(s_{l},t_{l})}\left\\{d^{i,j}_{G\setminus
D}(s_{l},t_{l})\right\\}\right).$

Therefore, for each $l$ we will separately compute:

  1. (1)

the value $\min_{j\notin X_{i}(s_{l},t_{l})}\left\\{d^{i,j}_{G\setminus
D}(s_{l},t_{l})\right\\}$,

  2. (2)

the length of some $s_{l}\to t_{l}$ path in $G\setminus D$ not longer than
$\min_{j\in X_{i}(s_{l},t_{l})}\left\\{d^{i,j}_{G\setminus
D}(s_{l},t_{l})\right\\}$.

We will then use the minimum of the former and the latter as
$\tilde{d}^{i}_{G\setminus D}(s_{l},t_{l})$.

Consider item (1). Observe that $j\notin X_{i}(s_{l},t_{l})$ implies that an
$s_{l}\to t_{l}$ path
$\pi^{\mathrm{from}}_{i,j}(s_{l})\cdot\pi^{\mathrm{to}}_{i,j}(t_{l})\subseteq
G$ exists also in $G\setminus D$. Hence,
$d^{i,j}_{G}(s_{l},t_{l})=d^{i,j}_{G\setminus D}(s_{l},t_{l})$, and thus
$(d^{i,j}_{G\setminus D}(s_{l},t_{l}),j)\in S_{i}(s_{l},t_{l})$. As a result,
the minimum $\min_{j\notin
X_{i}(s_{l},t_{l})}\left\\{d^{i,j}_{G}(s_{l},t_{l})\right\\}$ can be computed
in $O(|X_{i}(s_{l},t_{l})|)$ time by inspecting at most
$|X_{i}(s_{l},t_{l})|+1$ leading elements of the sorted array
$S_{i}(s_{l},t_{l})$: for the first encountered element $(x,j)$ with $j\notin
X_{i}(s_{l},t_{l})$, $x$ is the sought minimum. Note that, by Lemma 30,
computing such minima through all $l$ takes time

$O\left(\sum_{l=1}^{k}|X_{i}(s_{l},t_{l})|\right)=O(dh_{i}(m+n\log{n}+k)\log{n}).$

Now consider item (2). For each $c_{i,j}\in{\overline{C}}_{i}$, we construct
two auxiliary graphs $H^{\mathrm{to}}_{i,j}$, $H^{\mathrm{from}}_{i,j}$. Let
us define the former; the latter is defined completely symmetrically.

The vertices of $H^{\mathrm{to}}_{i,j}$ are precisely those $z\in V$
satisfying $D\cap V(\pi^{\mathrm{to}}_{i,j}(z))\neq\emptyset$, and the vertex
$c_{i,j}$. For each edge $vz\in E(G\setminus D)$ with $v,z\in
V(H^{\mathrm{to}}_{i,j})$, we add that edge $vz$ to $H^{\mathrm{to}}_{i,j}$.
Otherwise, if $v\notin V(H^{\mathrm{to}}_{i,j})$ but $z\in
V(H^{\mathrm{to}}_{i,j})$, we add an edge $c_{i,j}z$ with weight
$\delta^{h_{i}}_{G\setminus{\overline{C}}_{i,j}}(c_{i,j},v)+w_{G\setminus
D}(vz)$. Recall that the value
$\delta^{h_{i}}_{G\setminus{\overline{C}}_{i,j}}(c_{i,j},v)=\ell(\pi^{\mathrm{to}}_{i,j}(v))=\delta^{h_{i}}_{G\setminus{\overline{C}}_{i,j}\setminus
D}(c_{i,j},v)$ was computed during preprocessing.

######  Lemma 31.

For any $l$ such that $j\in X_{i}(s_{l},t_{l})$:

  * •

If $D\cap V(\pi^{\mathrm{to}}_{i,j}(t_{l}))\neq\emptyset$, then
$\delta_{G\setminus
D}(c_{i,j},t_{l})\leq\delta_{H^{\mathrm{to}}_{i,j}}(c_{i,j},t_{l})\leq\delta_{G\setminus{\overline{C}}_{i,j}\setminus
D}^{h_{i}}(c_{i,j},t_{l})$.

  * •

If $D\cap V(\pi^{\mathrm{from}}_{i,j}(s_{l}))\neq\emptyset$ then,
$\delta_{G\setminus
D}(s_{l},c_{i,j})\leq\delta_{H^{\mathrm{from}}_{i,j}}(s_{l},c_{i,j})\leq\delta_{G\setminus{\overline{C}}_{i,j}\setminus
D}^{h_{i}}(s_{l},c_{i,j})$.

###### Proof.

We only prove the former claim; one can prove the latter by proceeding
symmetrically. If $c_{i,j}\in D$, the claim is trivial, so assume
$c_{i,j}\notin D$. First of all, $t_{l}$ is a vertex of
$H^{\mathrm{to}}_{i,j}$ by construction and the assumption $D\cap
V(\pi^{\mathrm{to}}_{i,j}(t_{l}))\neq\emptyset$. The desired lower bound on
$\delta_{H^{\mathrm{to}}_{i,j}}(c_{i,j},t_{l})$ holds since all edges of
$H^{\mathrm{to}}_{i,j}$ are either also edges of $G\setminus D$, or encode
lengths of paths that exist in $G\setminus D$.

To obtain the upper bound, let path $P$ be some shortest among $\leq
h_{i}$-hop $c_{i,j}\to t_{l}$ paths in
$G\setminus{\overline{C}}_{i,j}\setminus D$. Let $v$ be the last vertex on $P$
such that $D\cap V(\pi^{\mathrm{to}}_{i,j}(v))=\emptyset$. Note that $v\neq
t_{l}$ exists since $\pi^{\mathrm{to}}_{i,j}(c_{i,j})$ is a zero-hop path and
$c_{i,j}\notin D$. Let $y$ be the vertex following $v$ on $P$. Split
$P=P_{1}P_{2}$ so that $P_{2}$ is a $y\to t_{l}$ path. Note that
$V(P_{2})\subseteq V(H^{\mathrm{to}}_{i,j})$. Since all edges between the
subset $V(H^{\mathrm{to}}_{i,j})$ in $G\setminus D$ are preserved in
$H^{\mathrm{to}}_{i,j}$, we have $P_{2}\subseteq H^{\mathrm{to}}_{i,j}$.
Moreover, since $D\cap V(\pi^{\mathrm{to}}_{i,j}(v))=\emptyset$ and $v$ is a
neighbor of a vertex $y\in V(H^{\mathrm{to}}_{i,j})$, there is an edge
$c_{i,j}y$ in $H^{\mathrm{to}}_{i,j}$ of weight
$\delta^{h}_{G\setminus{\overline{C}}_{i,j}}(c_{i,j},v)+w_{G\setminus
D}(vy)=\delta^{h}_{G\setminus{\overline{C}}_{i,j}\setminus
D}(c_{i,j},v)+w_{P_{1}}(vy)\leq\ell(P_{1})$. As a result, we have
$\delta_{H^{\mathrm{to}}_{i,j}}(c_{i,j},t_{l})\leq\ell((c_{i,j}w)\cdot
P_{2})\leq\ell(P)=\delta_{G\setminus{\overline{C}}_{i,j}\setminus
D}^{h_{i}}(c_{i,j},t_{l})$. ∎

For a fixed $i$, in order to find – for all $l$ – a path of length no more
than$\min_{j\in X_{i}(s_{l},t_{l})}\left\\{d^{i,j}_{G\setminus
D}(s_{l},t_{l})\right\\}$, we proceed as follows. For each $j$, we build the
graphs $H^{\mathrm{to}}_{i,j}$ and $H^{\mathrm{from}}_{i,j}$. We run
Dijkstra‘s algorithm from $c_{i,j}$ in $H^{\mathrm{to}}_{i,j}$, and Dijktra‘s
algorithm from $c_{i,j}$ in the reverse of $H^{\mathrm{from}}_{i,j}$. This
way, for all $v\in V(H^{\mathrm{to}}_{i,j})$, we obtain
$\delta_{H^{\mathrm{to}}_{i,j}}(c_{i,j},v)$, and for each $v\in
V(H^{\mathrm{from}}_{i,j})$, we obtain
$\delta_{H^{\mathrm{from}}_{i,j}}(v,c_{i,j})$. Finally, for each $l$ we
iterate through all $j\in X_{i}(s_{l},t_{l})$ in order to find the shortest
among the candidate $s_{l}\to t_{l}$ paths through some $c_{i,j}$. The length
of such a candidate path through $c_{i,j}$ is $\lambda_{i,j}(s_{l},t_{l})$,
defined as:

$\lambda_{i,j}(s_{l},t_{l})=\begin{cases}\delta_{H^{\mathrm{from}}_{i,j}}(s_{l},c_{i,j})+\delta_{H^{\mathrm{to}}_{i,j}}(c_{i,j},t_{l})&\text{
if }D\cap\pi^{\mathrm{from}}_{i,j}(s_{l})\neq\emptyset\text{ and
}D\cap\pi^{\mathrm{to}}_{i,j}(t_{l})\neq\emptyset,\\\
\delta_{G\setminus{\overline{C}}_{i,j}}^{h_{i}}(s_{l},c_{i,j})+\delta_{H^{\mathrm{to}}_{i,j}}(c_{i,j},t_{l})&\text{
if }D\cap\pi^{\mathrm{from}}_{i,j}(s_{l})=\emptyset\text{ and
}D\cap\pi^{\mathrm{to}}_{i,j}(t_{l})\neq\emptyset,\\\
\delta_{H^{\mathrm{from}}_{i,j}}(s_{l},c_{i,j})+\delta_{G\setminus{\overline{C}}_{i,j}}^{h_{i}}(c_{i,j},t_{l})&\text{
if }D\cap\pi^{\mathrm{from}}_{i,j}(s_{l})\neq\emptyset\text{ and
}D\cap\pi^{\mathrm{to}}_{i,j}(t_{l})=\emptyset.\\\ \end{cases}$

Recall that one of these three cases apply by $j\in X_{i}(s_{l},t_{l})$. By
Lemma 31, we easily obtain:

$\lambda_{i,j}(s_{l},t_{l})\leq\delta_{G\setminus{\overline{C}}_{i,j}\setminus
D}^{h_{i}}(s_{l},c_{i,j})+\delta_{G\setminus{\overline{C}}_{i,j}\setminus
D}^{h_{i}}(c_{i,j},t_{l})=d^{i,j}_{G\setminus D}(s_{l},t_{l}),$

and consequently $\min_{j\in
X_{i}(s_{l},t_{l})}\\{\lambda_{i,j}(s_{l},t_{l})\\}\leq\min_{j\in
X_{i}(s_{l},t_{l})}\\{d^{i,j}_{G\setminus D}(s_{l},t_{l})\\}$ as desired.

Let us now bound the running time of rebuilding short paths. For a given $i$,
given distances from/to $c_{i,j}$ in $H^{\mathrm{to}}_{i,j}$ and
$H^{\mathrm{from}}_{i,j}$ for all $j$, computing all the values
$\lambda_{i,j}(s_{l},t_{l})$ clearly takes
$O\left(\sum_{l=1}^{k}|X_{i}(s_{l},t_{l})|\right)$ time, i.e.,
$O(dh_{i}(m+n\log{n}+k)\log{n})$ time by Lemma 30. It remains to bound the
total time needed to computing those distances in $H^{\mathrm{to}}_{i,j}$ and
$H^{\mathrm{from}}_{i,j}$.

######  Lemma 32.

Computing single source/target distances
$\delta_{H^{\mathrm{to}}_{i,j}}(c_{i,j},\cdot)$ and
$\delta_{H^{\mathrm{from}}_{i,j}}(\cdot,c_{i,j})$ for all
$j=1,\ldots,|{\overline{C}}_{i}|$ takes $O(dh_{i}(m+n\log{n}+k)\log{n})$ time.

###### Proof.

We only consider computing single-source distances in graphs
$H^{\mathrm{to}}_{i,j}$; finding distances in graphs $H^{\mathrm{from}}_{i,j}$
is analyzed analogously. The cost of running Dijkstra‘s algorithm on
$H^{\mathrm{to}}_{i,j}$ is:

$O(|E(H^{\mathrm{to}}_{i,j})|+|V(H^{\mathrm{to}}_{i,j})|\log{n})=O\left(\sum_{v\in
V(H^{\mathrm{to}}_{i,j})}\left(\deg_{G}(v)+\log{n}\right)\right).$

Recall that we have $v\in V(H^{\mathrm{to}}_{i,j})$ if and only if $D\cap
V(\pi^{\mathrm{to}}_{i,j}(v))\neq\emptyset$. We can thus charge the cost
$O(\deg_{G}(v)+\log{n})$ of processing $v$ in the corresponding Dijkstra run
to the $\deg_{G}(v)+\log{n}$ (out of $\deg_{G}(v)+\deg_{K}(v)+\log{n}$; recall
that $\deg_{K}(v)$ part was already charged in Lemma 30) contribution of
$\pi^{\mathrm{to}}_{i,j}(v)$ to $\alpha(x)$ for an arbitrary vertex $x\in
D\cap V(\pi^{\mathrm{to}}_{i,j}(v))$. The total amount of congestion charged
is again $O\left(\sum_{x\in
D}\alpha(x)\right)=O(dh_{i}(m+n\log{n}+k)\log{n})$. ∎

By combining Lemmas 29, 30 and 32, we obtain:

######  Corollary 33.

After $O((m+k)n\log^{2}{n})$ preprocessing, computing estimates
$\tilde{d}_{G\setminus D}^{i}(s_{l},t_{l})$ as specified in (3) for any
$D\subseteq V$, $d=|D|$, takes $O(dh(m+n\log{n}+k)\log{n})$ time.

And finally, by combining the above corollary with Lemma 27, and choosing
$h=\sqrt{n/d}$, we obtain:

######  Lemma 34.

After $O((m+k)n\log^{2}{n})$ preprocessing, for any $D\subseteq V$, $d=|D|$,
one can recompute distances $\delta_{G\setminus D}(s_{l},t_{l})$ for all
$l=1,\ldots,k$ in $O\left(\sqrt{nd}\left(m+n\log{n}+k\right)\log{n}\right)$
time.

#### Dealing with negative edges and cycles.

Note that the preprocessing computes limited-hop shortest paths using the
Bellman-Ford algorithm. As a result, negative edges or cycles have no effect
on the preprocessing. However, when handling a query, we repeatedly run
Dijkstra‘s algorithm. In general, it needs a feasible price function on
$G\setminus D$ to work. To obtain such a feasible price function at query
time, during preprocessing we set up a fully dynamic negative cycle detection
data structure of Theorem 23 (see Section 6.3) and issue $n$ vertex updates to
that data structure so that after the preprocessing finishes, that data
structure stores the graph $G$. Upon query, we remove the vertices $D$ from
that data structure, so that in $O(d(m+n\log{n}))$ worst-case time we either
declare that $G\setminus D$ contains a negative cycle (and thus we do not have
to compute MPSP), or obtain a feasible price function $p$ on $G\setminus D$.
After obtaining $p$, we revert these removals, again in $O(d(m+n\log{n}))$
worst-case time, so that the data structure again stores the graph $G$. Note
that the extra overhead needed to handle negative edges and cycles is
negligible since $d\leq\sqrt{nd}$.

###  6.3 Maintaining a negative cycle in $O(m+n\log{n})$ worst-case time

In this section we prove the following theorem.

See 23

Consider the graph $G^{\prime}$ where each vertex $v$ is split into two
vertices $v_{\textrm{in}},v_{\textrm{out}}$, so that:

  1. 1.

for each $v$, there is an edge $v_{\textrm{in}}v_{\textrm{out}}$ of weight $0$
in $G^{\prime}$,

  2. 2.

for each edge $uv\in E(G)$, there is an edge $u_{\textrm{out}}v_{\textrm{in}}$
of weight $w_{G}(uv)$ in $G^{\prime}$.

Clearly, $G$ has a negative cycle iff $G^{\prime}$ has a negative cycle.
Moreover, a vertex update to $G$ corresponds to at most two vertex updates to
$G^{\prime}$.

The key idea is to view $G^{\prime}$ as a unit-capacitated flow network with
edge costs given by the edge weights. For some flow $f$ in this network (i.e.,
any function $f:E(G)\to\mathbb{R}_{\geq 0}$ such that for all $e\in E(G)$,
$f(e)\leq w_{G}(e)$), denote by $c(f)$ its cost. Recall that a flow $f$ is
called a circulation if for all $v\in V$ we have $\sum_{xv\in
E(G)}f(xv)=\sum_{vy\in E(G)}f(vy)$.

######  Lemma 35.

Let $f^{*}$ be the minimum cost circulation in $G^{\prime}$. Then
$c(f^{*})\leq 0$. Moreover, $G^{\prime}$ has a negative cycle if and only if
$c(f^{*})<0$.

###### Proof.

Clearly, since there are no demands at vertices, a zero circulation (i.e.,
where the flow on each edge is $0$) is a valid circulation of cost $0$. As a
result, we always have $c(f^{*})\leq 0$.

Suppose $G^{\prime}$ has a negative cycle. Then, by sending a unit of flow
through that cycle, we obtain a valid circulation of negative cost, i.e., we
conclude $c(f^{*})<0$.

Now suppose that $c(f^{*})<0$. It is well-known (see e.g. [3]) that any
circulation – in particular $f^{*}$ – can be decomposed into edge-disjoint
cycles in $G^{\prime}$ of positive flow. Since the sum of costs of these
cycles is negative, at least one of them has to have a negative cost. ∎

Let $G^{\prime}_{f}$ be the residual network corresponding to flow $f$. Recall
that in $G^{\prime}_{f}$, for each edge $e=uv\in E(G^{\prime})$, we have an
edge $uv$ of cost $c(uv)=w_{G^{\prime}}(uv)$ in $G^{\prime}_{f}$ if $f(e)<1$,
and we have an edge $vu$ of cost $c(vu)=-w_{G^{\prime}}(uv)$ in
$G^{\prime}_{f}$ if $f(e)>0$. When working with unit capacities, we can safely
operate on integer flows, i.e., the flow $f(e)$ on each edge $e\in
E(G^{\prime})$ is always either $0$ or $1$. The following characterization of
a minimum cost flow is well known (see e.g. [3]):

######  Fact 36.

A flow $f$ in $G^{\prime}$ has minimum cost if there exists such a potential
function $\pi:V(G^{\prime})\to\mathbb{R}$ that for each edge $e=uv\in
E(G^{\prime}_{f})$ we have $c(e)-\pi(u)+\pi(v)\geq 0$.

Our algorithm will maintain a minimum cost circulation $f^{*}$ in
$G^{\prime}$, along with a potential function $\pi$ as described in Fact 36
that certifies the optimality of $f^{*}$. Initially, when $G$ is empty, we use
a zero circulation and a zero potential function which clearly works since the
graph $G^{\prime}$ contains only edges $v_{\textrm{in}}v_{\textrm{out}}$ of
zero cost.

Suppose a vertex update to $G$ centered at $v$ happens. First, we cancel any
flow that goes through edges incident to either $v_{\textrm{in}}$ or
$v_{\textrm{out}}$ in $f^{*}$. This may create an excess of $1$ on some vertex
$u_{\textrm{out}}$ such that we had $f^{*}(u_{\textrm{out}}v_{\textrm{in}})=1$
before, and a deficit of $1$ on some vertex $z_{\textrm{in}}$ such that we had
$f^{*}(v_{\textrm{out}}z_{\textrm{in}})=1$ before. We then reflect the vertex
update to $G$ in $G^{\prime}$. Note that afterwards, $\pi$ is still a an
_almost_ valid potential function (as in Fact 36) – perhaps except on the
edges of $G_{f^{*}}^{\prime}$ incident to either $v_{\textrm{in}}$ or
$v_{\textrm{out}}$. To fix this, we set $\pi(v_{\textrm{in}})$ to a
sufficiently large value so that for all edges
$u_{\textrm{out}}v_{\textrm{in}}$ (which do not carry flow at this point) we
have
$w_{G^{\prime}}(u_{\textrm{out}}v_{\textrm{in}})-\pi(u_{\textrm{out}})+\pi(v_{\textrm{in}})\geq
0$. Similarly, we set $\pi(v_{\textrm{out}})$ to a sufficiently small value so
that for all edges $v_{\textrm{out}}z_{\textrm{in}}$ we have
$w_{G^{\prime}}(v_{\textrm{out}}z_{\textrm{in}})-\pi(v_{\textrm{out}})+\pi(z_{\textrm{in}})\geq
0$. At this point, $v_{\textrm{in}}v_{\textrm{out}}$ is the only edge in
$G_{f^{*}}^{\prime}$ that can potentially have
$w_{G^{\prime}}(v_{\textrm{in}}v_{\textrm{out}})-\pi(v_{\textrm{in}})+\pi(v_{\textrm{out}})<0$.
If this is the case, we send flow through the edge
$v_{\textrm{in}}v_{\textrm{out}}$. At this point, by Fact 36, $f^{*}$ is a
minimum cost flow, albeit it might have at most two excess and at most two
deficit vertices.

It is well-known (see e.g. [33] for a detailed description) that one can
convert any minimum-cost flow into a minimum cost circulation by gradually
pushing flow from the excess to deficit vertices in the residual network
through shortest (in terms of cost in the residual network) such paths. The
potential function certifying the optimality of the flow allows to find
shortest paths in the residual network using Dijkstra‘s algorithm. Moreover,
the _distances to_ the deficit vertices computed by Dijstra‘s algorithm can be
used as the new potential function after eliminating a single unit of excess.
Since each such step removes a single unit of excess, in our case we need at
most two such steps.

As a result, after a vertex update we can compute a new minimum cost
circulation and the corresponding potential function $\pi$ using $O(1)$
Dijkstra‘s algorithm runs. This takes $O(m+n\log{n})$ worst-case time.

Finally, we show how to obtain, based on $f^{*}$ and $\pi$, a feasible price
function $p$ of $G$ if $G$ has no negative cycles.

######  Lemma 37.

Suppose $G$ has no negative cycles. Let $f^{*}$ be the minimum cost
circulation in $G^{\prime}$ and let $\pi$ be the potential function certifying
the optimality of $f^{*}$. Let $p$ be such that $p(v)=-\pi(v_{\textrm{in}})$
for all $v\in V$. Then, $p$ is a feasible price function of $G$.

###### Proof.

First of all, we have $c(f^{*})=0$ by Lemma 35. As a result, $f^{*}$ can be
decomposed into a collection of $j\geq 0$ edge-disjoint cycles
$C_{1},\ldots,C_{j}$, of positive flow. In fact, each of these cycles has to
have $0$ cost, as otherwise at least one of them would have negative cost.

Consider some of the cycles $C_{i}$. Consider any edge $uv\in C_{i}$. Clearly,
since $f^{*}(uv)=1$, $vu\in G_{f^{*}}^{\prime}$ and thus
$-w_{G^{\prime}}(uv)-\pi(v)+\pi(u)\geq 0$ by the optimality of $f^{*}$.
Equivalently, ${w_{G^{\prime}}(uv)-\pi(u)+\pi(v)\leq 0}$. Now suppose we have
$w_{G^{\prime}}(xy)-\pi(x)+\pi(y)<0$ for some edge $xy\in C_{i}$. Then the sum

$\sum_{uv\in C_{i}}(w_{G^{\prime}}(uv)-\pi(v)+\pi(u))$

has non-positive terms, and at least one negative term, so in fact it is
negative. But since $C_{i}$ is cycle, the potentials $\pi(\cdot)$ in the above
sum cancel out, so we actually obtain $\sum_{uv\in C_{i}}w_{G^{\prime}}(uv)<0$
which contradicts that $C_{i}$ has zero cost. Therefore, we conclude that for
any edge $uv\in C_{i}$ we have:

$w_{G^{\prime}}(uv)-\pi(u)+\pi(v)=0.$ (4)

Suppose that for some $v$ we have $f^{*}(v_{\textrm{in}}v_{\textrm{out}})=1$.
Then $v_{\textrm{in}}v_{\textrm{out}}$ lies on some cycle $C_{i}$ of the
decomposition and thus by (4) we have:

$w_{G^{\prime}}(v_{\textrm{in}}v_{\textrm{out}})-\pi(v_{\textrm{in}})+\pi(v_{\textrm{out}})=-\pi(v_{\textrm{in}})+\pi(v_{\textrm{out}})=0.$

As a result $\pi(v_{\textrm{in}})=\pi(v_{\textrm{out}})$ in this case.

If $f^{*}(v_{\textrm{in}}v_{\textrm{out}})=0$, then
$v_{\textrm{in}}v_{\textrm{out}}\in G_{f^{*}}^{\prime}$, so we easily conclude
$\pi(v_{\textrm{out}})\geq\pi(v_{\textrm{in}})$ from the optimality of
$f^{*}$.

Now consider some original edge $uv$ of $G$. There are two cases. If
$f^{*}(u_{\textrm{out}}v_{\textrm{in}})=1$, then
$u_{\textrm{out}}v_{\textrm{in}}$ lies on some cycle $C_{i}$ and therefore by
(4) we know that

$w_{G^{\prime}}(u_{\textrm{out}}v_{\textrm{in}})-\pi(u_{\textrm{out}})+\pi(v_{\textrm{in}})=0.$

Observe that $u_{\textrm{in}}u_{\textrm{out}}$ also necessarily lies on that
cycle, so $\pi(u_{\textrm{out}})=\pi(u_{\textrm{in}})$ and we in fact have:

$w_{G}(uv)+p(u)-p(v)=w_{G^{\prime}}(u_{\textrm{out}}v_{\textrm{in}})-\pi(u_{\textrm{in}})+\pi(v_{\textrm{in}})=0,$

so in particular $w_{G}(uv)+p(u)-p(v)\geq 0$ as desired.

Now assume $f^{*}(u_{\textrm{out}}v_{\textrm{in}})=0$. Then
$u_{\textrm{out}}v_{\textrm{in}}\in G_{f^{*}}^{\prime}$ and by
$\pi(v_{\textrm{out}})\geq\pi(v_{\textrm{in}})$ we have:

$w_{G}(uv)+p(u)-p(v)=w_{G^{\prime}}(u_{\textrm{out}}v_{\textrm{in}})-\pi(u_{\textrm{in}})+\pi(v_{\textrm{in}})\geq
w_{G^{\prime}}(u_{\textrm{out}}v_{\textrm{in}})-\pi(u_{\textrm{out}})+\pi(v_{\textrm{in}})\geq
0.$

This concludes the proof that $p(v)=-\pi(v_{\textrm{in}})$ is a feasible price
function of $G$. ∎

## References

  * [1] Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang.  Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs.  In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 377–391. SIAM, 2016.  doi:10.1137/1.9781611974331.ch28.
  * [2] Ittai Abraham, Shiri Chechik, and Sebastian Krinninger.  Fully dynamic all-pairs shortest paths with worst-case update-time revisited.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 440–452, 2017.  doi:10.1137/1.9781611974782.28.
  * [3] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.  Network flows - theory, algorithms and applications.  Prentice Hall, 1993.
  * [4] Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, and Nicole Wein.  Algorithms and hardness for diameter in dynamic graphs.  In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 13:1–13:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.ICALP.2019.13.
  * [5] Giorgio Ausiello, Giuseppe F. Italiano, Alberto Marchetti-Spaccamela, and Umberto Nanni.  Incremental algorithms for minimal length paths.  J. Algorithms, 12(4):615–638, 1991.  doi:10.1016/0196-6774(91)90036-X.
  * [6] 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.
  * [7] Aaron Bernstein.  Fully dynamic (2 + epsilon) approximate all-pairs shortest paths with fast query and close to linear update time.  In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 693–702. IEEE Computer Society, 2009.  doi:10.1109/FOCS.2009.16.
  * [8] Aaron Bernstein.  Maintaining shortest paths under deletions in weighted directed graphs.  SIAM J. Comput., 45(2):548–574, 2016.  doi:10.1137/130938670.
  * [9] Aaron Bernstein and Liam Roditty.  Improved dynamic algorithms for maintaining approximate shortest paths under deletions.  In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1355–1365. SIAM, 2011.  doi:10.1137/1.9781611973082.104.
  * [10] Glencora Borradaile and Philip N. Klein.  An _O_(_n_ log _n_) algorithm for maximum _st_ -flow in a directed planar graph.  J. ACM, 56(2):9:1–9:30, 2009.  doi:10.1145/1502793.1502798.
  * [11] Karl Bringmann, Marvin Künnemann, and Karol Wegrzycki.  Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 943–954. ACM, 2019.  doi:10.1145/3313276.3316373.
  * [12] Panagiotis Charalampopoulos and Adam Karczmarz.  Single-source shortest paths and strong connectivity in dynamic planar graphs.  In 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 31:1–31:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.ESA.2020.31.
  * [13] Shiri Chechik.  Near-optimal approximate decremental all pairs shortest paths.  In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pages 170–181. IEEE Computer Society, 2018.  doi:10.1109/FOCS.2018.00025.
  * [14] Shiri Chechik and Gur Lifshitz.  Optimal girth approximation for dense directed graphs.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 290–300. SIAM, 2021.  doi:10.1137/1.9781611976465.19.
  * [15] Shiri Chechik, Yang P. Liu, Omer Rotem, and Aaron Sidford.  Constant girth approximation for directed graphs in subquadratic time.  In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1010–1023. ACM, 2020.  doi:10.1145/3357713.3384330.
  * [16] Julia Chuzhoy and Thatchaphol Saranurak.  Deterministic algorithms for decremental shortest paths via layered core decomposition.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2478–2496. SIAM, 2021.  doi:10.1137/1.9781611976465.147.
  * [17] Marek Cygan, Harold N. Gabow, and Piotr Sankowski.  Algorithmic applications of baur-strassen‘s theorem: Shortest cycles, diameter, and matchings.  J. ACM, 62(4):28:1–28:30, 2015.  doi:10.1145/2736283.
  * [18] Mina Dalirrooyfard and Virginia Vassilevska Williams.  Conditionally optimal approximation algorithms for the girth of a directed graph.  In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 35:1–35:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.ICALP.2020.35.
  * [19] Camil Demetrescu and Giuseppe F. Italiano.  A new approach to dynamic all pairs shortest paths.  J. ACM, 51(6):968–992, 2004.  doi:10.1145/1039488.1039492.
  * [20] Jeff Erickson.  Maximum flows and parametric shortest paths in planar graphs.  In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 794–804. SIAM, 2010.  doi:10.1137/1.9781611973075.65.
  * [21] Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, and Christian Wulff-Nilsen.  Decremental APSP in directed graphs versus an adaptive adversary.  CoRR, abs/2010.00937, 2020.  URL: https://arxiv.org/abs/2010.00937, arXiv:2010.00937.
  * [22] 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.
  * [23] Harold N. Gabow.  Scaling algorithms for network problems.  J. Comput. Syst. Sci., 31(2):148–168, 1985.  doi:10.1016/0022-0000(85)90039-X.
  * [24] Maximilian Probst Gutenberg and Christian Wulff-Nilsen.  Deterministic algorithms for decremental approximate shortest paths: Faster and simpler.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 2522–2541. SIAM, 2020.  doi:10.1137/1.9781611975994.154.
  * [25] Maximilian Probst Gutenberg and Christian Wulff-Nilsen.  Fully-dynamic all-pairs shortest paths: Improved worst-case time and space bounds.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 2562–2574. SIAM, 2020.  doi:10.1137/1.9781611975994.156.
  * [26] Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai.  Dynamic approximate all-pairs shortest paths: Breaking the ${O}(mn)$ barrier and derandomization.  SIAM J. Comput., 45(3):947–1006, 2016.  doi:10.1137/140957299.
  * [27] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane.  Which problems have strongly exponential complexity?  J. Comput. Syst. Sci., 63(4):512–530, 2001.  doi:10.1006/jcss.2001.1774.
  * [28] Alon Itai and Michael Rodeh.  Finding a minimum circuit in a graph.  SIAM J. Comput., 7(4):413–423, 1978.  doi:10.1137/0207033.
  * [29] Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen.  Improved algorithms for min cut and max flow in undirected planar graphs.  In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, pages 313–322, 2011.  doi:10.1145/1993636.1993679.
  * [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] Donald B. Johnson.  Parallel algorithms for minimum cuts and maximum flows in planar networks.  J. ACM, 34(4):950–967, 1987.  doi:10.1145/31846.31849.
  * [32] 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.
  * [33] Adam Karczmarz and Piotr Sankowski.  Min-cost flow in unit-capacity planar graphs.  In 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 66:1–66:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019\.  doi:10.4230/LIPIcs.ESA.2019.66.
  * [34] 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.
  * [35] Adam Karczmarz and Jakub Łącki.  Simple label-correcting algorithms for partially dynamic approximate shortest paths in directed graphs.  In 3rd Symposium on Simplicity in Algorithms, SOSA@SODA 2020, pages 106–120. SIAM, 2020.  doi:10.1137/1.9781611976014.15.
  * [36] 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.  URL: http://dl.acm.org/citation.cfm?id=1070432.1070454.
  * [37] Hung-Chun Liang and Hsueh-I Lu.  Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths.  SIAM J. Discret. Math., 31(1):454–476, 2017.  doi:10.1137/16M1057152.
  * [38] Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams.  Tight hardness for shortest cycles and paths in sparse graphs.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1236–1252. SIAM, 2018.  doi:10.1137/1.9781611975031.80.
  * [39] Jakub Łącki and Piotr Sankowski.  Min-cuts and shortest cycles in planar graphs in o(n loglogn) time.  In Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings, volume 6942 of Lecture Notes in Computer Science, pages 155–166. Springer, 2011.  doi:10.1007/978-3-642-23719-5“˙14.
  * [40] Shay Mozes, Kirill Nikolaev, Yahav Nussbaum, and Oren Weimann.  Minimum cut of directed planar graphs in _O_(_n_ log log _n_) time.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 477–494. SIAM, 2018.  doi:10.1137/1.9781611975031.32.
  * [41] Yahav Nussbaum.  Network flow problems in planar graphs.  PhD thesis, Tel Aviv University, 2014.
  * [42] James B. Orlin and Antonio Sedeño-Noda.  An _O_(_nm_) time algorithm for finding the min length directed cycle in a graph.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1866–1879. SIAM, 2017.  doi:10.1137/1.9781611974782.122.
  * [43] 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.
  * [44] Liam Roditty and Virginia Vassilevska Williams.  Minimum weight cycles and triangles: Equivalences and algorithms.  In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 180–189. IEEE Computer Society, 2011.  doi:10.1109/FOCS.2011.27.
  * [45] Liam Roditty and Uri Zwick.  On dynamic shortest paths problems.  Algorithmica, 61(2):389–401, 2011.  doi:10.1007/s00453-010-9401-5.
  * [46] Liam Roditty and Uri Zwick.  Dynamic approximate all-pairs shortest paths in undirected graphs.  SIAM J. Comput., 41(3):670–683, 2012.  doi:10.1137/090776573.
  * [47] Mikkel Thorup.  Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles.  In Algorithm Theory - SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory, Proceedings, pages 384–396, 2004.  doi:10.1007/978-3-540-27810-8“˙33.
  * [48] Mikkel Thorup.  Worst-case update times for fully-dynamic all-pairs shortest paths.  In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, STOC 2005, pages 112–119, 2005.  doi:10.1145/1060590.1060607.
  * [49] 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.
  * [50] 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.