path in $G$ is bounded by $d_{X_{j}}\cdot\frac{\Lambda}{64d\log m}$.

We let $P^{\prime}$ be the path obtained by concatenating
$e_{1},Q_{2},e_{2},\ldots,Q_{k-1},e_{k-1}$. It is easy to see that
$P^{\prime}$ is an $s$-$t$ path in the current graph $G$. Next, we bound its
length. Recall that the length of the original path $P$ was at most
$1.5\Lambda$. For convenience, for $1<j<k$, if $|X_{j}|=1$, then we denote
$d_{X_{j}}=0$. The total lengths of all paths in
$\left\\{Q_{2},\ldots,Q_{k-1}\right\\}$ can be bounded by:

$\begin{split}\frac{\Lambda}{64d\log
m}\cdot\sum_{j=2}^{k-1}d_{X_{j}}&\leq\frac{\Lambda}{64d\log
m}\cdot\sum_{X_{0}\in{\mathcal{X}}^{*}}d_{X_{0}}\\\
&\leq\frac{\Lambda}{64d\log m}\cdot\sum_{i=0}^{\left\lfloor\log
n\right\rfloor}\sum_{X_{0}\in{\mathcal{X}}_{i}}d_{X_{0}}\\\
&=\frac{\Lambda}{64d\log m}\cdot\sum_{i=0}^{\left\lfloor\log
n\right\rfloor}\sum_{X_{0}\in{\mathcal{X}}_{i}}\frac{|X_{0}|}{n}\cdot d\\\
&\leq\frac{\Lambda}{64d\log m}\cdot d\log n\\\
&\leq\frac{\Lambda}{64},\end{split}$

since for all $X_{0}\in{\mathcal{X}}$, $d_{X_{0}}=\frac{|X_{0}|}{n}\cdot d$,
and for all $0\leq i\leq\left\lfloor\log n\right\rfloor$,
$\sum_{X_{0}\in{\mathcal{X}}_{i}}|X_{0}|\leq n$. Altogether, the length of the
final path $P^{\prime}$ is bounded by $2\Lambda$ as required. Note that the
initial path $P$, returned by the algorithm from Theorem 5.1 is a simple path.
From the definition of the $\mathsf{MaintainCluster}$ problem, each of the
paths $Q_{2},\ldots,Q_{k-1}$ are also simple paths. Moreover, since all
clusters in ${\mathcal{X}}$ are disjoint, and since path $P$ is simple, it is
easy to verify that the final path $P^{\prime}$ is simple as well.

After our algorithm returns a path $Q$, the edges of $Q$ are deleted from $G$.
We then update the $\mathsf{MaintainCluster}$ algorithms for clusters
$X\in{\mathcal{X}}$ with the edges that were deleted from $\hat{G}[X]$, and
then update graph $H=G_{|{\mathcal{X}}}$ with edge deletions and any vertex
splits that may have resulted from splitting of clusters of ${\mathcal{X}}$.

Let $q$ denote the number of iterations in the algorithm, and recall that
$q\leq\Delta$. In each iteration $i$, the time required to compute the initial
path $P_{i}$ in graph $H$ is bounded by $O(|E(P_{i})|)$. The time that is
required to respond to short-path queries within the clusters $X_{j}$ is
already accounted for as part of total running time of the
$\mathsf{MaintainCluster}$ algorithm on $\hat{G}[X_{j}]$. Let $P^{\prime}_{i}$
denote the final path that the algorithm returns in iteration $i$, so
$E(P_{i})\subseteq E(P^{\prime}_{i})$. Then the additional time required to
respond to queries is bounded by $\sum_{i=1}^{q}O(|E(P_{i})|)$. Since, for all
$1\leq i\leq q$, the edges of $P^{\prime}_{i}$ are deleted from $G$ at the end
of iteration $i$, the edges of $P_{i}$ are also deleted from $G$ at the end of
iteration $i$. Therefore, we get that
$\sum_{i=1}^{q}O(|E(P_{i})|)\leq\widetilde{O}(|E(G)|)\leq\widetilde{O}(n^{2})$.
Since $\Delta\leq n$, the total running time of the algorithm is then bounded
by
$\widetilde{O}\left(\frac{n^{2.5}}{\sqrt{\Delta}}\right)+\widetilde{O}(n^{2})\leq{\widetilde{O}\left(\frac{n^{2.5}}{\sqrt{\Delta}}\right)}$.

##  8 Algorithm for the $\mathsf{MaintainCluster}$ Problem – Proof of Theorem
6.2

We will use the following theorem as a subroutine. The theorem provides an
efficient algorithm that either embeds a large expander into the input graph
$H$, or computes a sparse cut in $H$, with both sides of the cut being
sufficiently large. The proof of the theorem uses standard techniques (namely
the Cut-Matching Game), though we provide a simpler algorithm for one of the
ingredients (algorithm for the Cut Player), and an algorithm achieving
slightly better parameters for another ingredient (algorithm for the Matching
Player). The theorem uses parameter $\alpha_{0}$ from Theorem 2.1; its proof
is deferred to Section 8.1.

######  Theorem 8.1.

There is a deterministic algorithm, whose input consists of a directed
$n$-vertex bipartite graph $G=(L,R,E)$ with $|E|=m$, such that every vertex in
$R$ has out-degree at most $1$ and every vertex in $L$ has in-degree at most
$1$, and a parameter $4\leq d^{\prime}\leq 2n$. The algorithm returns one of
the following:

  * •

Either a cut $(X,Y)$ in $G$ with $|E_{G}(X,Y)|\leq\frac{2n}{d^{\prime}}+1$ and
$|X|,|Y|\geq\Omega\left(\frac{n}{\log^{3}n}\right)$; or

  * •

A directed graph $W^{*}$ with $|V(W^{*})|\geq n/8$ and maximum vertex degree
at most $18$, such that $W^{*}$ is an $\alpha_{0}$-expander, together with a
subset $F\subseteq E(W^{*})$ of at most $\frac{\alpha_{0}\cdot n}{500}$ edges
of $W^{*}$, and an embedding ${\mathcal{P}}^{*}$ of $W^{*}\setminus F$ into
$G$ via paths of length at most $O(d^{\prime}\log^{2}n)$, that cause
congestion at most $O(d^{\prime}\log^{4}n)$, such that every path in
${\mathcal{P}}^{*}$ is simple.

The running time of the algorithm is $\widetilde{O}(md^{\prime}+n^{2})$.

Note that in the above theorem we assume that all edge lengths in the input
graph $G$ are unit.

We will also use the following simple observation that uses the standard ball-
growing technique. The proof is deferred to Section D of Appendix.

######  Observation 8.2.

There is a deterministic algorithm, that receives as input a directed
bipartite $n$-vertex graph $H=(L,R,E)$, where the edges in $E_{H}(L,R)$ are
called regular and the edges in $E_{H}(R,L)$ are called special. Every vertex
of $H$ may be incident to at most one special edge. Additionally, the
algorithm is given a set $X\subseteq V(H)$ of at least $\frac{n}{32}$
vertices, and a vertex $v$, such that $\mbox{\sf dist}_{H}(v,X)\geq d$, for
some given parameter ${d\geq 2^{11}\log n}$. The algorithm computes a well-
structured cut $(A,B)$ in $H$, with $v\in A$, $X\subseteq B$, and
$|E_{H}(A,B)|\leq\varphi\cdot\min\left\\{|A|,|B|\right\\}$, for
${\varphi=\frac{2^{11}\log n}{d}}$. The running time of the algorithm is
$O(\operatorname{Vol}_{H}(A))$.

We are now ready to complete the proof of Theorem 6.2. Recall that we are
given as input a simple bipartite $n$-vertex graph $H=(L,R,E)$ with $|E|=m$,
such that every vertex in $R$ has out-degree at most $1$ and every vertex in
$L$ has in-degree at most $1$, together with integral parameters
$c^{*}\log^{6}n\leq d^{*}\leq n$, where $c^{*}$ is a large enough constant and
$1\leq\Delta\leq n$. Recall that we refer to the edges of $E_{H}(R,L)$ as
_special_ , and the edges of $E_{H}(L,R)$ as _regular_. Recall also that a cut
$(X,Y)$ in $H$ is _well-structured_ iff all edges in $E_{H}(X,Y)$ are special.

The algorithm is required to respond to at most $\Delta$ short-path queries:
given a pair $x,y\in V(H)$ of vertices, it must return a simple path $P$
connecting $x$ to $y$ in $H$, whose length is at most $d^{*}$. Once the
algorithm responds to a query, it receives a set of edges that need to be
deleted from $H$, with all the deleted edges lying on path $P$. At any time,
the algorithm may provide a well-structured cut $(X,Y)$ of $H$, whose sparsity
is at most $O\left(\frac{\log^{6}n}{d^{*}}\right)$. If $|X|\leq|Y|$, then the
cut must be provided by listing the vertices of $X$, and otherwise it must be
provided by listing the vertices of $Y$. After that the vertices of the
smaller side of the cut are deleted from $H$.

Note that, over the course of the algorithm, vertices may be deleted from $H$.
We denote by $n$ the initial number of vertices in $H$. Once $|V(H)|$ falls
below $n/2$, the algorithm terminates, even if fewer than $\Delta$ queries
were asked.

Throughout, we use a parameter ${d=\frac{d^{*}}{c^{\prime}\log^{3}n}}$, where
$c^{\prime}$ is some large enough constant, whose value we will set later.
Since $d^{*}\geq c^{*}\cdot\log^{6}n$ for a large enough constant $c^{*}$, we
can ensure that $d\geq 2^{11}\log n$.

Our algorithm consists of a number of phases. Let
$N=\frac{\alpha_{0}n}{2^{20}(d^{*})^{2}\log n}$, where $\alpha_{0}$ is the
constant from Theorem 2.1, and let $\hat{c}$ be a large enough contant whose
value we choose later. A phase terminates whenever one of the following two
conditions are met: either (i) the number of vertices in $H$ decreased by the
factor of at least ${\left(1-\frac{1}{\hat{c}\log^{5}n}\right)}$ over the
course of the current phase (in which case we say that the phase is of _type
1_); or (ii) at least $N$ short-path queries were responded to during the
current phase (in which case the phase is of _type 2_). Clearly, at most
$O(\log^{5}n)$ phases may be of type 1, and the number of type-2 phases is
bounded by
$\max\left\\{1,\frac{\Delta}{N}\right\\}\leq\max\left\\{1,O\left(\frac{\Delta\cdot(d^{*})^{2}\log
n}{n}\right)\right\\}$. Overall, the number of phases in the algorithm is
bounded by
$O\left(\max\left\\{\log^{5}n,\frac{\Delta\cdot(d^{*})^{2}\cdot\log^{6}n}{n}\right\\}\right)$.
At a high level, we follow a scheme that is by now quite standard: we embed a
large $\Omega(1)$-expander $W^{*}$ into graph $H$, and then maintain two ES-
Tree data structures in $H$, both of which are rooted at the vertices of
$W^{*}$; in the first tree all edges are directed away from the root, while in
the second tree the edges are directed towards the root. Given a query
$(x,y)$, we use the ES-Tree data structures in order to connect $x$ to some
vertex $x^{\prime}\in V(W^{*})$, and to connect some vertex $y^{\prime}\in
V(W^{*})$ to $y$, via short paths. Lastly, we compute a short path connecting
$x^{\prime}$ to $y^{\prime}$ in $W^{*}$ by performing a BFS, which is then
transformed into an $x^{\prime}$-$y^{\prime}$ path in $H$ by exploiting the
embedding of $W^{*}$ into $H$. At a high level, we can view each phase as
consisting of two steps. In the first step, we embed an expander $W^{*}$ into
$H$, and the second step contains the remainder of the algorithm that allows
us to support short-path queries. We now describe each of the two steps in
turn.

### Step 1: Embedding an Expander

During the first step of the phase, we will attempt to embed a large expander
into the current graph $H$ via Theorem 8.1. Specifically, we perform a number
of iterations. In every iteration, we apply the algorithm from Theorem 8.1 to
the current graph $H$ with parameter $d^{\prime}=d$.

Assume first that the algorithm returned a cut $(X,Y)$ in $H$ with
$|E_{H}(X,Y)|\leq\frac{2n}{d}+1$ and
$|X|,|Y|\geq\Omega\left(\frac{n}{\log^{3}n}\right)$. In this case, we say that
the current iteration is a _bad_ iteration. Clearly,
$|E_{H}(X,Y)|\leq\frac{2n}{d}+1\leq\frac{4n}{d}\leq
O\left(\frac{\log^{3}n}{d}\right)\cdot\min\left\\{|X|,|Y|\right\\}$. In other
words, the sparsity of the cut $(X,Y)$ is at most
$O\left(\frac{\log^{3}n}{d}\right)=O\left(\frac{\log^{6}n}{d^{*}}\right)$.
Since $d^{*}\geq c^{*}\log^{6}n$, where $c^{*}$ is a large enough constant, we
can ensure that the sparsity of the cut, that we denote by $\varphi$, is
bounded by $1/4$. Using the algorithm from 6.1, we compute, in time
$O(|E(H)|)$, a well-structured cut $(X^{\prime},Y^{\prime})$ in $H$, whose
sparsity remains at most $O\left(\frac{\log^{6}n}{d^{*}}\right)$.

Denote the sets $X$ and $Y$ by $Z$ and $Z^{\prime}$, so that $Z$ is the
smaller set of the two, breaking the tie arbitrarily. Notice that the
algorithm from 6.1 ensures that
$|Z|\geq(1-\varphi)\cdot\min\left\\{|X|,|Y|\right\\}\geq\Omega\left(\frac{n}{\log^{3}n}\right)$.
We output the cut $(X,Y)$ and delete the vertices of $Z$ from graph $H$. If
the number of vertices in $H$ falls below $n/2$, then we terminate the
algorithm. Otherwise, we continue to the next iteration.

Assume now that the algorithm from Theorem 8.1 returned a directed graph
$W^{*}$ with $|V(W^{*})|\geq|V(H)|/8$ and maximum vertex degree at most $18$,
such that $W^{*}$ is an $\alpha_{0}$-expander, together with a subset
$F\subseteq E(W^{*})$ of at most $\frac{\alpha_{0}\cdot|V(H)|}{500}$ edges of
$W^{*}$, and an embedding ${\mathcal{P}}^{*}$ of $W^{*}\setminus F$ into $H$
via simple paths of length at most $O(d\log^{2}n)$ each, that cause congestion
at most $O(d\log^{4}n)$. In this case, we say that the current iteration is a
_good_ iteration. We then terminate the first step of the current phase and
continue to the second step.

Since in every bad iteration at least $\Omega\left(\frac{n}{\log^{3}n}\right)$
vertices are deleted from $H$, the total number of iterations in the first
step is bounded by $O(\log^{3}n)$. In every iteration we apply the algorithm
from Theorem 8.1, whose running time is $\widetilde{O}(|E(H)|d+n^{2})$ to the
current graph $H$, and then possibly use the algorithm from 6.1, whose running
time is at most $O(|E(H)|)$. Overall, the running time of Step 1 of a single
phase is $\widetilde{O}(|E(H)|\cdot d+n^{2})$.

### Step 2: Even-Shiloach Trees and Supporting Short-Path Queries

We denote by $n^{\prime}$ the number of vertices in $H$ at the beginning of
Step 2. The purpose of Step 2 is to support short-path queries. Over the
course of Step 2, the number of vertices in $H$ may decrease. Whenever this
number falls below $n^{\prime}\cdot\left(1-\frac{1}{\hat{c}\log^{5}n}\right)$,
for a large enough constant $\hat{c}$ whose value we choose later, we
terminate the algorithm for Step 2 and the current phase. We start by defining
additional data structures that we maintain.

Recall that, at the beginning of Step 2, we are given an $\alpha_{0}$-expander
graph $W^{*}$ with $|V(W^{*})|\geq n^{\prime}/8$ and maximum vertex degree at
most $18$, together with a subset $F\subseteq E(W^{*})$ of at most
$\frac{\alpha_{0}\cdot n^{\prime}}{500}$ edges of $W^{*}$, and an embedding
${\mathcal{P}}^{*}$ of $W^{*}\setminus F$ into $H$ via simple paths of length
at most $O(d\log^{2}n)$, that cause congestion at most $O(d\log^{4}n)$.

We denote the number of vertices in $W^{*}$ at the beginning of the phase by
$n^{\prime\prime}$, so $n^{\prime\prime}\geq n^{\prime}/8\geq n/16$. Over the
course of Step 2, some vertices may be deleted from $W^{*}$, but we will
ensure that throughout the algorithm for Step 2, $|V(W^{*})|\geq
n^{\prime\prime}/4\geq|V(H)|/32$ holds. We also use a parameter
$\hat{d}=\frac{2^{30}\log n}{\alpha_{0}}$, and we will ensure that at all
times, for every pair $x,y$ of vertices of $W^{*}$, $\mbox{\sf
dist}_{W^{*}\setminus F}(x,y),\mbox{\sf dist}_{W^{*}\setminus
F}(y,x)\leq\hat{d}$.

We maintain two additional graphs: graph $H^{\prime}$ that is obtained from
$H$ by adding a source vertex $s^{\prime}$, and connecting it to every vertex
in $V(W^{*})$ with an edge of length $1$, and graph $H^{\prime\prime}$ that is
obtained from $H$ by adding a vertex $s^{\prime\prime}$, connecting every
vertex in $V(W^{*})$ to it with an edge of length $1$, and then reversing the
directions of all edges. Whenever a vertex $v$ leaves the set $V(W^{*})$ of
vertices, we delete the edge $(s^{\prime},v)$ from $H^{\prime}$, and we also
delete the edge $(s^{\prime\prime},v)$ from $H^{\prime\prime}$. Additionally,
whenever an edge is deleted from graph $H$ due to an update operation, we
delete the corresponding edge from both $H^{\prime}$ and $H^{\prime\prime}$.
When vertices are deleted from graph $H$ (after sparse cuts are returned by
the algorithm), we also update both $H^{\prime}$ and $H^{\prime\prime}$ with
the deletions of these vertices.

We initialize the ES-Tree data structure from Theorem 2.4 for graph
$H^{\prime}$, with source vertex $s^{\prime}$ and distance parameter $d+1$,
and we similarly initialize ES-Tree data structure for $H^{\prime\prime}$ with
source vertex $s^{\prime\prime}$ and distance parameter $d+1$. We denote the
corresponding trees by $T^{\prime}$ and $T^{\prime\prime}$, respectively.

We will ensure that, throughout the algorithm, every vertex $v$ of $H$ lies in
both $T^{\prime}$ and $T^{\prime\prime}$, so that $\mbox{\sf
dist}_{H}(V(W^{*}),v),\mbox{\sf dist}_{H}(v,V(W^{*}))\leq d$ always holds. In
order to ensure this, we use the ES-Tree data structures to identify vertices
$v$ for which this no longer holds. Whenever we identify a vertex $v$ with
$\mbox{\sf dist}_{H}(v,V(W^{*}))>d$, we use the algorithm from 8.2 in order to
compute a well-structured cut $(A,B)$ in $H$ with $v\in A$, $V(W^{*})\subseteq
B$, and $|E_{H}(A,B)|\leq\frac{2^{11}\log
n}{d}\cdot\min\left\\{|A|,|B|\right\\}\leq
O\left(\frac{\log^{6}n}{d^{*}}\right)\cdot\min\left\\{|A|,|B|\right\\}$. If
$|A|\leq|B|$, then we delete the vertices of $A$ from $H$, (which includes
deleting these vertices and their incident edges from graphs $H,H^{\prime}$,
and $H^{\prime\prime}$, and both ES-Tree data structures $T^{\prime}$ and
$T^{\prime\prime}$), and then continue the algorithm. If $|V(H)|$ falls below
$n^{\prime}\left(1-\frac{1}{\hat{c}\log^{5}n}\right)$, then the algorithm is
terminated. Alternatively, if $|A|>|B|$, then we delete the vertices of $B$
from $H$, and terminate the current phase. Notice that in this case, at least
$|V(W^{*})|\geq n^{\prime\prime}/4\geq n/64$ vertices have been deleted from
$H$ in the current phase.

Similarly, whenever we identify a vertex $v$ with $\mbox{\sf
dist}_{H}(V(W^{*}),v)>d$, we use the algorithm from 8.2 (but with reversed
directions of edges) in order to compute a well-structured cut $(A,B)$ in $H$
with $V(W^{*})\subseteq A$, $v\in B$, and $|E_{H}(A,B)|\leq\frac{2^{11}\log
n}{d}\cdot\min\left\\{|A|,|B|\right\\}\leq
O\left(\frac{\log^{6}n}{d^{*}}\right)\cdot\min\left\\{|A|,|B|\right\\}$. As
before, if $|B|\leq|A|$, then we delete the vertices of $B$ from $H$, and from
both ES-Tree data structures. If $|V(H)|$ falls below
$n^{\prime}\left(1-\frac{1}{\hat{c}\log^{5}n}\right)$, then the algorithm is
terminated, and otherwise we continue the algorithm as before. Alternatively,
if $|B|>|A|$, then we delete the vertices of $A$ from $H$, and terminate the
current phase. In the latter case, at least $n/64$ vertices have been deleted
from $H$ in the current phase.

In either case, if the set of vertices that was deleted from $H$ is denoted by
$Z$, then the running time of the algorithm from 8.2 is bounded by
$O(\operatorname{Vol}_{H}(Z))$. Therefore, the total time that the algorithm
ever spends over the course of Step 2 to cut sparse cuts off from $H$ via 8.2
is bounded by $O(m)$. Additionally, the algorithms for maintaining the two ES-
Tree data structures have total update time $O(m\cdot d)$. Therefore, the
total update time of Step 2 of a single phase is so far bounded by $O(m\cdot
d)\leq\widetilde{O}(m\cdot d^{*})$.

For every edge $e\in E(H)$, we maintain a set $S(e)$ of all edges
$e^{\prime}\in E(W^{*})\setminus F$ whose embedding path
$P(e^{\prime})\in{\mathcal{P}}^{*}$ contains $e$. We can initialize the sets
$S(e)$ of edges for all $e\in E(H)$ by scanning every edge $e^{\prime}\in
E(W^{*})\setminus F$ and considering all edges on path $P(e^{\prime})$.
Clearly, the total time required to initialize the sets $S(e)$ of edges for
all $e\in E(H)$ is subsumed by the time spent on constructing the embedding
${\mathcal{P}}^{*}$ of $W^{*}\setminus F$ into $H$ in Step 1.

### A Cleanup Procedure

The purpose of the cleanup procedure is to ensure that every vertex of $H$
lies in both the trees $T^{\prime}$ and $T^{\prime\prime}$, and additionally,
that for every pair $x,y$ of vertices of $W^{*}$, $\mbox{\sf
dist}_{W^{*}\setminus F}(x,y),\mbox{\sf dist}_{W^{*}\setminus
F}(y,x)\leq\hat{d}$ holds. The cleanup procedure is executed before each
query. In other words, we execute the procedure once at the beginning of Phase
2, before responding to any queries. Then, after every query, once graph $H$
is updated with the relevant edge deletions, we execute the procedure again.

Consider for example a short-path query, and suppose the algorithm returned a
path $P^{*}$ in response to the query. Recall that some edges of $P^{*}$ may
be deleted from $H$. As a result, it is possible that some vertices of $H$ no
longer belong to one or both of the trees $T^{\prime},T^{\prime\prime}$. As
described already, we will compute a sparse cut in $H$ in order to fix this
issue, but this may in turn affect the expander $W^{*}$. Additionally, the
deletion of the edges from $H$ may lead to the deletion of some edges from the
expander $W^{*}$. As a result, it is possible that the diameter of
$W^{*}\setminus F$ grows beyond $\hat{d}$. In such a case, we will compute a
sparse cut in graph $W^{*}\setminus F$, but this may in turn affect the trees
$T^{\prime},T^{\prime\prime}$, since, whenever a vertex $x$ leaves the set
$V(W^{*})$ of vertices, we delete edge $(s^{\prime},x)$ from $T^{\prime}$ and
we delete edge $(s^{\prime\prime},x)$ from $T^{\prime\prime}$. Similarly, it
is possible that, at the beginning of Phase 2, not all vertices of $H$ lie in
the trees $T^{\prime},T^{\prime\prime}$, or that the diameter of
$W^{*}\setminus F$ is greater than $\hat{d}$. Fixing each of these issues may
in turn create new issues as described above. We now formally describe the
cleanup procedure.

At the beginning of the cleanup procedure, we select an arbitrary vertex $v\in
V(W^{*})$, and compute two shortest-paths trees $\hat{T}^{\prime}$ and
$\hat{T}^{\prime\prime}$ rooted at $v$ in graph $W^{*}\setminus F$, where the
edges in $\hat{T}^{\prime}$ are directed away from $v$, and the edges in
$\hat{T}^{\prime\prime}$ are directed towards $v$. In other words, for every
vertex $a\in V(W^{*})$, the unique $v$-$a$ path in $\hat{T}^{\prime}$ is a
shortest $v$-$a$ path in $W^{*}\setminus F$, and the unique $a$-$v$ path in
$\hat{T}^{\prime\prime}$ is a shortest $a$-$v$ path in $W^{*}\setminus F$.
Note that both trees can be computed in time $O(n)$. We then perform a number
of iterations. At the beginning of every iteration, we assume that we are
given some vertex $v\in V(W^{*})$, and two shortest-paths trees
$\hat{T}^{\prime}$ and $\hat{T}^{\prime\prime}$ in $W^{*}\setminus F$ that are
both rooted at $v$, with the edges of $\hat{T}^{\prime}$ directed away from
$v$, and the edges of $\hat{T}^{\prime}$ directed towards $v$. The iterations
are executed as long as at least one of the following two conditions hold: (i)
some vertex $u\in V(H)$ does not lie in $T^{\prime}$ or in $T^{\prime\prime}$;
or (ii) the depth of at least one of the trees
$\hat{T}^{\prime},\hat{T}^{\prime\prime}$ is greater than $\hat{d}$. We now
describe the execution of a single iteration.

Assume first that some vertex $u\in V(H)$ no longer lies in either
$T^{\prime}$ or $T^{\prime\prime}$. In this case, we say that the current
iteration is a _type-1_ iteration. Assume first that $u\not\in
T^{\prime\prime}$, in other words, $\mbox{\sf dist}_{H}(u,V(W^{*}))>d$ holds.
As we described already, we use the algorithm from 8.2 in order to compute a
well-structured cut $(A,B)$ in $H$ with $u\in A$, $V(W^{*})\subseteq B$, and
$|E_{H}(A,B)|\leq\frac{2^{11}\log n}{d}\cdot\min\left\\{|A|,|B|\right\\}\leq
O\left(\frac{\log^{6}n}{d^{*}}\right)\cdot\min\left\\{|A|,|B|\right\\}$. If
$|A|\leq|B|$, then we delete the vertices of $A$ from $H$, (which includes
deleting these vertices and their incident edges from graphs $H,H^{\prime}$,
and $H^{\prime\prime}$, and both ES-Tree data structures $T^{\prime}$ and
$T^{\prime\prime}$). If $|V(H)|$ falls below
$n^{\prime}\left(1-\frac{1}{\hat{c}\log^{5}n}\right)$, then the algorithm is
terminated, and otherwise we continue the algorithm. Alternatively, if
$|A|>|B|$, then we delete the vertices of $B$ from $H$, and terminate the
current phase. Similarly, if some vertex $u\in V(H)$ no longer lies in
$T^{\prime}$, then, as desribed above, we use the algorithm from 8.2 (but with
reversed directions of edges) in order to compute a well-structured cut
$(A,B)$ in $H$ with $V(W^{*})\subseteq A$, $u\in B$, and
$|E_{H}(A,B)|\leq\frac{2^{11}\log n}{d}\cdot\min\left\\{|A|,|B|\right\\}\leq
O\left(\frac{\log^{6}n}{d^{*}}\right)\cdot\min\left\\{|A|,|B|\right\\}$. As
before, if $|B|\leq|A|$, then we delete the vertices of $B$ from $H$, and from
both ES-Tree data structures. If $|V(H)|$ falls below
$n^{\prime}\left(1-\frac{1}{\hat{c}\log^{5}n}\right)$, then the algorithm is
terminated, and otherwise we continue the algorithm. Alternatively, if
$|B|>|A|$, then we delete the vertices of $A$ from $H$, and terminate the
current phase. In the latter case, at least $n/64$ vertices have been deleted
from $H$ in the current phase. Let $Z$ be the set of all vertices that were
deleted from $H$ in the current iteration, and let $\hat{E}=\bigcup_{e\in
E_{H}(A,B)}S(e)$, that is, these are all edges $e^{\prime}\in
E(W^{*})\setminus F$ whose embedding path contains an edge of $E_{H}(A,B)$.
Since the embedding of $W^{*}\setminus F$ into $H$ causes congestion at most
$O(d\log^{4}n)$, we get that $|\hat{E}|\leq O(d\log^{4}n)\cdot|E_{H}(A,B)|\leq
O(|Z|\cdot\log^{6}n)$. We delete the edges of $\hat{E}$ from graph $W^{*}$. If
$Z\cap V(W^{*})=\emptyset$, then we say that the current iteration is a
_type-(1a) iteration_ , and we continue to the next iteration. Notice that in
this case, the running time of the current iteration is
$\widetilde{O}(\operatorname{Vol}_{H}(Z)\cdot d^{*})$, and we _charge_ the
running time of the current iteration to the set $Z$ of vertices.

Assume now that $Z\cap V(W^{*})\neq\emptyset$. In this case, we say that the
current iteration is a _type-(1b) iteration_. Let $X=Z\cap V(W^{*})$. So far
the total running time of the iteration is
$\tilde{O}(\operatorname{Vol}_{H}(Z)\cdot d^{*})$, and it is charged to the
set $Z$ of vertices. Next, we delete the vertices of $X$ from $W^{*}$. The
remainder of the running time of the current iteration will be charged to set
$X$. Notice that, if $Z=A$, and we denote $Z^{\prime}=B$, then graph
$W^{*}\setminus F$ no longer contains any edges connecting vertices of $Z\cap
V(W^{*})$ to vertices of $Z^{\prime}\cap V(W^{*})$. In other words, $(Z\cap
V(W^{*}),Z^{\prime}\cap V(W^{*}))$ is a cut of sparsity $0$ in $W^{*}\setminus
F$. Similarly, if $Z=B$, and we denote $Z^{\prime}=A$, then cut
$(Z^{\prime}\cap V(W^{*}),Z\cap V(W^{*}))$ is a cut of sparsity $0$ in
$W^{*}\setminus F$. Once the vertices of $X$ are deleted from $W^{*}$, we
select an arbitrary vertex $v\in V(W^{*})$, and compute two shortest-paths
trees $\hat{T}^{\prime}$ and $\hat{T}^{\prime\prime}$ rooted at $v$ in graph
$W^{*}\setminus F$, where the edges in $\hat{T}^{\prime}$ are directed away
from $v$, and the edges in $\hat{T}^{\prime\prime}$ are directed towards $v$.
It is easy to verify that the total running time of a type-(1b) iteration is
bounded by $\widetilde{O}(\operatorname{Vol}_{H}(Z)\cdot d^{*})+O(n)$. We
charge time $\widetilde{O}(\operatorname{Vol}_{H}(Z)\cdot d^{*})$ to the set
$Z$ of vertices that is deleted from $H$ in the current iteration, and we
charge time $O(n)$ to the set $X$ of vertices that is deleted from $W^{*}$ in
the current iteration. Lastly, graphs $H^{\prime}$ and $H^{\prime\prime}$ need
to be updated to reflect the deletion of the vertices of $X$ from $W^{*}$:
namely, for all $u\in X$, we delete the edge $(s^{\prime},u)$ from
$H^{\prime}$, and we delete the edge $(s^{\prime\prime},u)$ from
$H^{\prime\prime}$. This, in turn, may require updating the ES-Tree data
structures $T^{\prime}$ and $T^{\prime\prime}$. The time required to update
the two trees is counted as part of the total update time of these data
structures, and not as part of the running time of the current cleanup
procedure. This completes the description of a type-(1b) iteration.

If the depth of either of the trees $\hat{T}^{\prime},\hat{T}^{\prime\prime}$
is greater than $\hat{d}$, then we say that the current iteration is a type-2
iteration. In this case, we can compute, in time $O(1)$, a pair $a,b\in
V(W^{*})$ of vertices with $\mbox{\sf dist}_{W^{*}\setminus F}(a,b)>\hat{d}$.
Recall that $\hat{d}=\frac{2^{30}\log n}{\alpha_{0}}$, and the maximum vertex
degree in $W^{*}$ is bounded by $D=18$. We can now use the algorithm from 2.2
to compute, in time $O(n)$, a cut $(A,B)$ in $W^{*}\setminus F$ of sparsity at
most $\varphi=\frac{32D\log n}{\hat{d}}\leq\frac{\alpha_{0}}{2^{20}}$. If
$|A|\leq|B|$, then we delete from $W^{*}$ the vertices of $A$, and otherwise
we delete from $W^{*}$ the vertices of $B$. If we denote by $X$ the set of
vertices deleted from $W^{*}$ in the current iteration, then graphs
$H^{\prime}$ and $H^{\prime\prime}$ need to be updated accordingly (namely,
for all $u\in X$, we delete the edge $(s^{\prime},u)$ from $H^{\prime}$ and we
delete the edge $(s^{\prime\prime},u)$ from $H^{\prime\prime}$). This, in
turn, may require updating the ES-Tree data structures $T^{\prime}$ and
$T^{\prime\prime}$. The time required to update the two trees is counted as
part of the total update time of these data structures, and not as part of the
running time of the current cleanup procedure. We then select an arbitrary
vertex $v\in V(W^{*})$, and compute two shortest-paths trees
$\hat{T}^{\prime}$ and $\hat{T}^{\prime\prime}$ rooted at $v$ in graph
$W^{*}\setminus F$, where the edges in $\hat{T}^{\prime}$ are directed away
from $v$, and the edges in $\hat{T}^{\prime\prime}$ are directed towards $v$.
Clearly, the running time of a type-2 iteration is $O(n)$, and we charge it to
the set of vertices (either $A$ or $B$) that was deleted from $W^{*}$ over the
course of the current iteration.

The algorithm for the cleanup procedure terminates once every vertex of $H$
lies in both $T^{\prime}$ and $T^{\prime\prime}$, and the depths of the trees
$\hat{T}^{\prime}$ and $\hat{T}^{\prime\prime}$ are both bounded by $\hat{d}$.

We now bound the total time required to perform the cleanup procedure over the
course of the entire Step 2. Since we only need to respond to at most
$N=O\left(\frac{n}{(d^{*})^{2}\log n}\right)$ queries, the number of times
that the cleanup procedure is called is bounded by $N$. The time that is
required in order to compute the shortest-path trees
$\hat{T}^{\prime},\hat{T}^{\prime\prime}$ in $W^{*}\setminus F$ for the first
time at the beginning of each cleanup procedure is then bounded by $O(n\cdot
N)\leq\widetilde{O}(n^{2})$.

If we denote by $Z$ the set of all vertices that are deleted over the course
of the phase from graph $H$, and by ${\mathcal{X}}$ the collection of all
subsets of vertices that were deleted from $V(W^{*})$ over the course of the
phase, then, from our charging scheme, the remaining running time that is
spent on the repeated executions of the cleanup procedure can be bounded by
$\widetilde{O}(\operatorname{Vol}_{H}(Z)\cdot d^{*})+O(|{\mathcal{X}}|\cdot
n)\leq\widetilde{O}(md^{*}+n^{2})$. Therefore, the total time spent over the
course of a single phase on executing the cleanup procedure is bounded by
$\widetilde{O}(md^{*}+n^{2})$.

### Updates to the Expander $W^{*}$

Recall that, at the beginning of Step 2, we are given an $\alpha_{0}$-expander
$W^{*}$, with $|V(W^{*})|=n^{\prime\prime}\geq n^{\prime}/8$ and maximum
vertex degree at most $18$, together with a subset $F\subseteq E(W^{*})$ of at
most $\frac{\alpha_{0}\cdot n^{\prime}}{500}$ edges of $W^{*}$, and an
embedding ${\mathcal{P}}^{*}$ of $W^{*}\setminus F$ into $H$ via paths of
length at most $O(d\log^{2}n)$, that cause congestion at most $O(d\log^{4}n)$.

Over the course of the algorithm, we may delete some edges from $W^{*}$, and
we may also compute sparse cuts in $W^{*}$ that decompose $W^{*}$ into smaller
subgraphs. For convenience, we will maintain a collection ${\mathcal{X}}$ of
subsets of vertices of $W^{*}$ that partition the original set $V(W^{*})$. At
the beginning of the algorithm, ${\mathcal{X}}$ contains a single set
$V(W^{*})$ of vertices. Over the course of the algorithm, if we identify a
sparse cut $(X,Y)$ in the current graph $W^{*}\setminus F$, we replace
$V(W^{*})$ with $X$ and $Y$ in ${\mathcal{X}}$, and we delete the vertices of
the smaller of the two sets from $W^{*}$. The key is to ensure that, since the
cuts that we compute are sparse, and since the number of edges deleted from
$W^{*}$ over the course of the second step is relatively small,
$|V(W^{*})|\geq n^{\prime\prime}/4$ continues to hold throughout Step 2 of the
phase.

There are three types of updates that expander $W^{*}$ may undergo over the
course of the algorithm, that we describe next.

#### First Type of Updates.

Suppose some edge $e$ was deleted from $H$, as part of the update sequence
that graph $H$ undergoes. In this case, we delete every edge $e^{\prime}\in
S(e)$ from $W^{*}$. For each such edge $e^{\prime}$, we also delete
$e^{\prime}$ from the set $S(e^{\prime\prime})$ of every edge
$e^{\prime\prime}\in E(H)$ that lies on the embedding path
$P(e^{\prime})\in{\mathcal{P}}^{*}$. Recall that, over the course of the
current phase, our algorithm will need to respond to at most $N$ short-path
queries. If $Q$ is a path that is returned in response to such a query, then
$Q$ may contain at most $d^{*}$ edges, and the only edges that may be deleted
from $H$ over the course of the current phase as part of the update sequence
are edges that lie on such paths. Therefore, the total number of edges that
may be deleted from $H$ as part of the update sequence during a single phase
is at most $N\cdot d^{*}$. Since the embedding of $W^{*}\setminus F$ causes
congestion at most $O(d\log^{4}n)$ in $H$, the number of corresponding edge
deletions from $W^{*}$ is bounded by:

$O(N\cdot d^{*}\cdot d\log^{4}n)\leq N\cdot(d^{*})^{2}\cdot\log
n\leq\frac{\alpha_{0}n}{2^{20}},$

since $d=\frac{d^{*}}{c^{\prime}\log^{3}n}$, where $c^{\prime}$ can be chosen
as a large enough constant and $N=\frac{\alpha_{0}n}{2^{20}(d^{*})^{2}\log
n}$. Throughout, we denote by $E^{\prime}$ the set of edges that were deleted
from $W^{*}$ as the result of this type of updates to $W^{*}$, so
$|E^{\prime}|\leq\frac{\alpha_{0}n}{2^{20}}$ always holds. The time that is
required to update graph $W^{*}$ with this type of updates is subsumed by the
time spent in Step 1 of the algorithm.

#### Second Type of Updates.

The second type of update happens when the algorithm for Step 2 identifies a
well-structured cut $(A,B)$ in $H$ with $|E_{H}(A,B)|\leq\frac{2^{11}\log
n}{d}\cdot\min\left\\{|A|,|B|\right\\}$. Denote sets $A$ and $B$ by $Z$ and
$Z^{\prime}$, so that $Z$ is the smaller of the two sets, breaking ties
arbitrarily. Recall that our algorithm then deletes the vertices of $Z$ from
$H$. If, as the result of this deletion, the number of vertices in $H$ falls
below $\left(1-\frac{1}{\hat{c}\log^{5}n}\right)n^{\prime}$, then the current
phase terminates. If this did not happen, then we update graph $W^{*}$ as
follows. Let $\hat{E}=\bigcup_{e\in E_{H}(A,B)}S(e)$, that is, these are all
edges $e^{\prime}\in E(W^{*})\setminus F$ whose embedding path contains an
edge of $E_{H}(A,B)$. Since the embedding of $W^{*}\setminus F$ into $H$
causes congestion at most $O(d\log^{4}n)$ in $H$, we get that $|\hat{E}|\leq
O(d\log^{4}n)\cdot|E_{H}(A,B)|\leq O(|Z|\cdot\log^{5}n)$.

We start by deleting the edges of $\hat{E}$ from $W^{*}$. Note that, if $Z=A$
and $Z^{\prime}=B$, then graph $W^{*}\setminus F$ no longer contains any edges
connecting vertices of $Z\cap V(W^{*})$ to vertices of $Z^{\prime}\cap
V(W^{*})$. In other words, $(Z\cap V(W^{*}),Z^{\prime}\cap V(W^{*}))$ is a cut
of sparsity $0$ in $W^{*}\setminus F$. We replace the set $V(W^{*})$ of
vertices in ${\mathcal{X}}$ by two sets: $Z\cap V(W^{*})$ and $Z^{\prime}\cap
V(W^{*})$. We also delete the vertices of $Z$ from $W^{*}$. Similarly, if
$Z=B$ and $Z^{\prime}=A$, then $(Z^{\prime}\cap V(W^{*}),Z\cap V(W^{*}))$ is a
cut of sparsity $0$ in $W^{*}\setminus F$. We replace the set $V(W^{*})$ of
vertices in ${\mathcal{X}}$ by two sets: $Z\cap V(W^{*})$ and $Z^{\prime}\cap
V(W^{*})$, and we delete the vertices of $Z$ from $W^{*}$.

We denote by $E^{\prime\prime}$ the set of edges that were deleted from
$W^{*}$ as the result of this type of transformation: in other words, for each
sparse cut $(A,B)$ of $H$ that our algorithm computes, we add all edges of
$\bigcup_{e\in E_{H}(A,B)}S(e)$ to $E^{\prime\prime}$. Recall that the number
of edges added to $E^{\prime\prime}$ due to such cut $(A,B)$ is bounded by
$O(\log^{5}n)\cdot\min\left\\{|A|,|B|\right\\}$, and that the vertices of $A$
or the vertices of $B$ are deleted from $H$. Since the total number of
vertices that may be deleted from $H$ before the phase terminates is bounded
by $\frac{n^{\prime}}{\hat{c}\log^{5}n}$, where $\hat{c}$ can be chosen to be
a large enough constant, we can ensure that throughout the phase
$|E^{\prime\prime}|\leq\frac{\alpha_{0}n}{2^{20}}$ holds.

#### Third Type of Updates.

Recall that the cleanup procedure may sometimes identify cuts $(A,B)$ in
$W^{*}\setminus F$, with $|E_{W^{*}\setminus
F}(A,B)|\leq\frac{\alpha_{0}}{2^{20}}\cdot\min\left\\{|A|,|B|\right\\}$.
Whenever this happens, it replaces the set $V(W^{*})$ of vertices in
${\mathcal{X}}$ with $V(A)$ and $V(B)$. Denote $A$ and $B$ by $Z$ and
$Z^{\prime}$, where $Z$ is the smaller of the two sets, breaking ties
arbitrarily. We then delete the vertices of $Z$ from graph $W^{*}$. Notice
that $|E_{W^{*}\setminus F}(A,B)|\leq\frac{\alpha_{0}}{2^{20}}\cdot|Z|$.

Let $E^{\prime\prime\prime}$ denote the collection of all edges that
participate in such cuts. In other words, for each such sparse cut $(A,B)$ of
$W^{*}\setminus F$, we include the edges of $E_{W^{*}\setminus F}(A,B)$ in
$E^{\prime\prime\prime}$. From the above discussion, throughout the algorithm,
$|E^{\prime\prime\prime}|\leq\frac{\alpha_{0}}{2^{20}}\cdot
n^{\prime\prime}\leq\frac{\alpha_{0}}{2^{20}}\cdot n$ holds.

Lastly, we denote $E^{*}=F\cup E^{\prime}\cup E^{\prime\prime}\cup
E^{\prime\prime\prime}$. Recall that $|F|\leq\frac{\alpha_{0}\cdot
n^{\prime}}{500}\leq\frac{\alpha_{0}\cdot n^{\prime\prime}}{62}$, since
$n^{\prime\prime}\geq n^{\prime}/8$. The cardinality of each of the three sets
$E^{\prime},E^{\prime\prime}$ and $E^{\prime\prime\prime}$ is bounded by
$\frac{\alpha_{0}\cdot n}{2^{20}}\leq\frac{\alpha_{0}\cdot
n^{\prime}}{2^{19}}\leq\frac{\alpha_{0}\cdot n^{\prime\prime}}{2^{14}}$.
Overall, we get that $|E^{*}|\leq\frac{\alpha_{0}\cdot n^{\prime\prime}}{32}$
holds throughout the algorithm. We now show that, throughout the algorithm,
$|V(W^{*})|\geq n^{\prime\prime}/4$ holds.

######  Claim 8.3.

Throughout the algorithm, $|V(W^{*})|\geq n^{\prime\prime}/4$.

###### Proof.

Assume otherwise. Consider some time $\tau$ at which
$|V(W^{*})|<n^{\prime\prime}/4$ holds. For convenience, we denote by $W$ the
original graph $W^{*}$, which is an $\alpha_{0}$-expander, with
$n^{\prime\prime}$ vertices and we denote by $W^{\prime}$ the graph
$W\setminus E^{*}$, with respect to the set $E^{*}$ of edges at time $\tau$.
We also consider the set ${\mathcal{X}}$ of vertex subsets at time $\tau$. We
denote the sets of ${\mathcal{X}}$ by $X_{1},X_{2},\ldots,X_{r}$, where
$X_{r}=V(W^{*})$ at time $\tau$, and the remaining sets are indexed in the
order in which they were added to ${\mathcal{X}}$. For all $1\leq j<r$, let
$X^{\prime}_{j}=X_{j+1}\cup\cdots\cup X_{r}$. At the time when $X_{j}$ was
added to ${\mathcal{X}}$, it defined a sparse cut in graph $W^{*}\setminus F$.
In other words, either
$|E_{W^{\prime}}(X_{j},X^{\prime}_{j})|\leq\frac{\alpha_{0}}{2^{20}}|X_{j}|$,
or
$|E_{W^{\prime}}(X^{\prime}_{j},X_{j})|\leq\frac{\alpha_{0}}{2^{20}}|X_{j}|$
holds. Let $\alpha$ be such that
$\max_{X_{j}\in{\mathcal{X}}}|X_{j}|=\alpha\cdot n^{\prime\prime}$. Then it is
easy to verify that $\alpha\leq 1/2$ must hold. From 2.3, there is a cut
$(A,B)$ in $W^{\prime}$ with $|A|,|B|\geq n^{\prime\prime}/4$, and
$|E_{W^{\prime}}(A,B)|\leq\frac{\alpha_{0}\cdot n^{\prime\prime}}{2^{20}}$.

Observe that $|E_{W}(A,B)|\leq|E^{*}|+\frac{\alpha_{0}\cdot
n^{\prime\prime}}{2^{20}}\leq\frac{\alpha_{0}\cdot n^{\prime\prime}}{16}$.
Since $|A|,|B|\geq n^{\prime\prime}/4$, we obtain a cut $(A,B)$ in $W$, whose
sparsity is below $\alpha_{0}$, contradicting the fact that $W$ is an
$\alpha_{0}$-expander.

This completes the description of the data structures that we maintain over
the course of Step 2. Next, we describe an algorithm for responding to a
short-path queries.

### Responding to short-path queries

In a short-path query, we are given a pair $x,y$ of vertices of $H$, and our
goal is to compute a simple path connecting $x$ to $y$ in $H$ of length at
most $d^{*}$.

In order to respond to the query, we use ES-Tree $T^{\prime\prime}$ to compute
a path $P^{\prime}$ in graph $H$ of length at most $d$, connecting $x$ to some
vertex $x^{\prime}\in V(W^{*})$, in time $O(d)$. Similarly, we use ES-Tree
$T^{\prime}$ in order to compute a path $P^{\prime\prime}$ of length at most
$d$, connecting some vertex $y^{\prime}\in V(W^{*})$ to $y$, in time $O(d)$.
Next, we perform a BFS in graph $W^{*}\setminus F$, from vertex $x^{\prime}$,
in order to compute the shortest $x^{\prime}$-$y^{\prime}$ path $Q$ in
$W^{*}\setminus F$. Recall that we are guaranteed that the length of $Q$ in
$W^{*}\setminus F$ is bounded by $\hat{d}=\frac{2^{30}\log n}{\alpha_{0}}$. We
then use the embedding of $W^{*}\setminus F$ into $H$ via paths of lengths at
most $O(d\log^{2}n)$ in order to obtain a path $\hat{P}$ connecting
$x^{\prime}$ to $y^{\prime}$ in $H$, whose length is at most $O(d\log^{3}n)$.
Let $P^{*}$ be the path that is obtained by concatenating $P^{\prime},\hat{P}$
and $P^{\prime\prime}$. Path $P^{*}$ connects $x$ to $y$ in graph $H$, and its
length is bounded by $2d+O(d\log^{3}n)$. Since we have set
$d=\frac{d^{*}}{c^{\prime}\log^{3}n}$, where $c^{\prime}$ is a large enough
constant, the length of $P^{*}$ is bounded by $d^{*}$. We transform $P^{*}$
into a simple path in time $O(d^{*})$ and return the resulting path. This
finishes the algorithm for responding to the query. Notice that its running
time is bounded by $O(n+d^{*})$, since a BFS search in $W^{*}$ can be
performed in time $O(n)$, and the time required to compute paths $P^{\prime}$
and $P^{\prime\prime}$ and to transform $Q$ into path $\hat{P}$ is bounded by
$O(d^{*})$. Since the number of short-path queries that we need to process in
a single phase is bounded by $N=\tilde{O}(n/(d^{*})^{2})$, the total time that
is required in order to respond to short-path queries over the course of a
single phase is bounded by $\tilde{O}(n^{2})$.

### Final Analysis of the Running Time.

We now bound the total running time of a single phase. Recall that the running
time of Step 1 is bounded by $O(m\cdot
d+n^{2})\leq\widetilde{O}(md^{*}+n^{2})$. The total time spent on executing
the cleanup procedure over the course of the phase is bounded by
$\widetilde{O}(md^{*}+n^{2})$, and the total time spent on responding to
queries is bounded by $\tilde{O}(n^{2})$. Lastly, and the time spent on
maintaining ES-Tree data strucures $T^{\prime}$ and $T^{\prime\prime}$ is
bounded by $\tilde{O}(md)\leq\widetilde{O}(md^{*})$. Additional time that is
required to maintain the expander $W^{*}$ is bounded by the above running
times, and so the running time of a single phase is bounded by
$\tilde{O}(m\cdot d^{*}+n^{2})$.

Since the number of phases is bounded by
$\tilde{O}\left(\max\left\\{1,\frac{\Delta\cdot(d^{*})^{2}}{n}\right\\}\right)$,
we get that the total running time of the algorithm is bounded by:

$\widetilde{O}(m\cdot
d^{*}+n^{2})\cdot\max\left\\{1,\frac{\Delta\cdot(d^{*})^{2}}{n}\right\\}.$

###  8.1 Algorithm $\operatorname{AlgEmbedOrCut}$: Proof of Theorem 8.1

We use the Cut-Matching Game – a framework that was first proposed by [KRV09].
The specific variant of the game is due to [KKOV07]. Its slight modification,
that we also use, was proposed in [CGL+19], and later adapted to directed
graphs in [BGS20]. We also note that [Lou10] extended the original cut-
matching game of [KRV09] to directed graphs, though we do not use this
variation here. We now define the variant of the game that we use.

The game is played between two players: the Cut Player and the Matching
Player. The game starts with a directed graph $W$ that contains $n$ vertices
and no edges, where $n$ is an even integer, and proceeds in iterations. In the
$i$th iteration, the Cut Player chooses a cut $(A_{i},B_{i})$ in $W$ with
$|A_{i}|,|B_{i}|\geq n/10$, and $|E_{W}(A_{i},B_{i})|\leq n/100$. It then
computes two arbitrary equal-cardinality sets $A_{i}^{\prime},B_{i}^{\prime}$
of vertices with $|A^{\prime}_{i}|\geq n/4$, such that either $A_{i}\subseteq
A^{\prime}_{i}$, or $B_{i}\subseteq B^{\prime}_{i}$. The matching player then
needs to return two perfect matchings: a matching $M_{i}\subseteq
A^{\prime}_{i}\times B^{\prime}_{i}$, and a matching $M^{\prime}_{i}\subseteq
B^{\prime}_{i}\times A^{\prime}_{i}$, both of cardinality $|A^{\prime}_{i}|$.
The edges of $M_{i}\cup M^{\prime}_{i}$ are added to $W$, and the iteration
terminates. The following bound on the number of iterations in this variant of
the Cut-Matching Game was shown in [BGS20], extending a similar result of
[KKOV07] for undirected graphs.

######  Theorem 8.4 (Lemma 7.4 in [BGS20]; see also Theorem 7.3 and the
following discussion).

The number of iterations in the above Cut-Matching Game is bounded by $O(\log
n)$.

From the above theorem, there is an absolute constant $c_{\mathsf{CMG}}>0$,
such that, after $c_{\mathsf{CMG}}\log n$ iterations of the game, for every
cut $(A,B)$ in $W$ with $|A|,|B|\geq n/10$, $|E_{W}(A,B)|>n/100$ must hold.
Notice that the maximum vertex degree in the final graph $W$ is bounded by
$2c_{\mathsf{CMG}}\log n$.

In order to implement the Cut-Matching Game, we design two algorithms: an
algorithm for the Cut Player, and an algorithm for the Matching Player. We
note that previous work, such as, e.g. [BGS20] also designed similar
algorithms, but since we focus here on a more specific setting, we believe
that our algorithm for the cut player is significally simpler, while the
algorithm for the Matching Player achieves better parameters.

The algorithm for the Cut Player is summarized in the following theorem, whose
proof is deferred to Section 8.2. The theorem uses the constant $\alpha_{0}$
from Theorem 2.1.

######  Theorem 8.5.

There is a deterministic algorithm, that, given an $n$-vertex directed graph
$W$ with maximum vertex degree at most $O(\log n)$, returns one of the
following:

  * •

Either a cut $(A,B)$ in $W$ with $|E_{W}(A,B)|\leq n/100$ and $|A|,|B|\geq
n/10$; or

  * •

another directed graph $W^{\prime}$ with $|V(W^{\prime})|\geq n/4$ and maximum
vertex degree at most $18$, such that $W^{\prime}$ is an
$\alpha_{0}$-expander, together with a subset $F\subseteq E(W^{\prime})$ of at
most $\frac{\alpha_{0}\cdot n}{1000}$ edges of $W^{\prime}$, and an embedding
${\mathcal{P}}$ of $W^{\prime}\setminus F$ into $W$ via paths of length at
most $\tilde{d}=O(\log^{2}n)$, that cause congestion at most
$\eta=O(\log^{2}n)$.

The running time of the algorithm is $\widetilde{O}(n^{2})$.

We note that [BGS20], generalizing the results of [CGL+19] to directed graphs,
provided an algorithm for the cut player with faster running time
$\widehat{O}(n)$ (see Theorem 7.3 in [BGS20]). We could have used their
algorithm as a blackbox instead of the algorithm from Theorem 8.5. However,
the proof of Theorem 8.5 is significantly simpler than that of [BGS20] and
[CGL+19], and we can afford this slower running time since other components of
our algorithm have slower running time.

The algorithm for the Matching Player is summarized in the following theorem,
whose proof is deferred to Section 8.3.

######  Theorem 8.6.

There is a deterministic algorithm, whose input consists of a directed
$n$-vertex bipartite graph $G=(L,R,E)$ with $|E|=m$, where $n$ is an even
integer, such that every vertex in $R$ has out-degree at most $1$ and every
vertex in $L$ has in-degree at most $1$, together with two disjoint sets $A,B$
of vertices of $G$ of cardinality $n/2$ each, and two parameters $4\leq
d^{\prime}\leq 2n$ and $z\geq 1$. The algorithm returns one of the following:

  * •

either a cut $(X,Y)$ in $G$ with $|E_{G}(X,Y)|\leq\frac{2n}{d^{\prime}}$ and
$|X|,|Y|\geq z$; or

  * •

a collection ${\mathcal{Q}}$ of at least $(n/2-z)$ paths in graph $G$, with
every path $Q\in{\mathcal{Q}}$ connecting some vertex of $A$ to some vertex of
$B$, such that the length of every path in ${\mathcal{Q}}$ is at most
$2d^{\prime}+1$, the paths cause congestion at most $O(d^{\prime}\log n)$, and
the endpoints of all paths are distinct.

The running time of the algorithm is $\widetilde{O}(md^{\prime})$.

Note that in the above theorem we assume that all edge lengths in the input
graph $G$ are unit.

We are now ready to complete the algorithm for Theorem 8.1. We will assume
that $n=|V(G)|$ is an even integer; otherwise, we temporarily delete an
arbitrary vertex $v_{0}$ from $G$. We let $c$ be a large enough constant, so
that, in Theorem 8.5 the parameter $\eta\leq c\log^{2}n$.

We start with a graph $W$ that contains $n$ vertices and no edges, and then
run the Cut-Matching game on it. Recall that the number of iterations in the
game is bounded by $c_{\mathsf{CMG}}\cdot\log n$. This ensures that the graph
$W$ that is maintained over the course of the game has maximum vertex degree
$O(\log n)$. We now describe the execution of the $i$th iteration.

First, we apply the algorithm from Theorem 8.5 to the current graph $W$. We
say that the current iteration is a type-1 iteration, if the algorithm returns
a cut $(A_{i},B_{i})$ in $W$ with $|E_{W}(A_{i},B_{i})|\leq n/100$ and
$|A_{i}|,|B_{i}|\geq n/10$, and otherwise we say that it is a type-2
iteration. Assume first that the current iteration is a type-1 iteration. Then
we compute an arbitrary partition $(A^{\prime}_{i},B^{\prime}_{i})$ of $V(W)$
into two subsets of cardinality $n/2$ each, such that either $A_{i}\subseteq
A^{\prime}_{i}$ or $B_{i}\subseteq B^{\prime}_{i}$, and we treat
$(A^{\prime}_{i},B^{\prime}_{i})$ as the move of the cut player.

Next, we twice apply the algorithm from Theorem 8.6 to graph $G$, with
parameter $d^{\prime}$ that remains unchanged, and parameter
${z=\frac{\alpha_{0}}{2000c\cdot c_{\mathsf{CMG}}\cdot\log^{3}n}\cdot n}$:
once for the ordered pair of sets $(A^{\prime}_{i},B^{\prime}_{i})$, and once
for the ordered pair of sets $(B^{\prime}_{i},A^{\prime}_{i})$.

Assume first that in any of the two applications of the algorithm, it returns
a cut $(X,Y)$ in $G$ with $|E_{G}(X,Y)|\leq\frac{2n}{d^{\prime}}$ and
$|X|,|Y|\geq z\geq\Omega(n/\log^{3}n)$. In this case, we terminate the
algorithm and return the cut $(X,Y)$ as its outcome. If the initial value
$|V(G)|$ was odd, then we add vertex $v_{0}$ to $X$ if $v_{0}\in R$, and to
$Y$ otherwise. In either case, the only newly added edge to $E_{G}(X,Y)$ is
the special edge incident to $v_{0}$ (if such an edge exists), and so
$|E_{G}(X,Y)|\leq\frac{2n}{d^{\prime}}+1$ holds. We also say that the current
iteration is of _type (1a)_.

Otherwise, the algorithm computes a collection ${\mathcal{Q}}^{\prime}_{i}$ of
at least $(n/2-z)$ paths in graph $G$, with every path $Q\in{\mathcal{Q}}_{i}$
connecting a distinct vertex of $A^{\prime}_{i}$ to a distinct vertex of
$B^{\prime}_{i}$, and a collection ${\mathcal{Q}}^{\prime\prime}_{i}$ of at
least $(n/2-z)$ paths in $G$, with every path
$Q^{\prime}\in{\mathcal{Q}}^{\prime}_{i}$ connecting a distinct vertex of
$B^{\prime}_{i}$ to a distinct vertex of $A^{\prime}_{i}$. The paths in
${\mathcal{Q}}^{\prime}_{i}\cup{\mathcal{Q}}^{\prime\prime}_{i}$ have lengths
at most $2d^{\prime}+1$ each, and they cause congestion at most
$O(d^{\prime}\log n)$. In this case, we say that the current iteration is of
_type (1b)_. The set ${\mathcal{Q}}^{\prime}_{i}$ of paths naturally defines a
matching $M^{\prime}_{i}\subseteq A^{\prime}_{i}\times B^{\prime}_{i}$, where
for every path $Q\in{\mathcal{Q}}_{i}$ whose endpoints are $a\in
A^{\prime}_{i},b\in B^{\prime}_{i}$, we add an edge $e=(a,b)$ to the matching.
We also let $P(e)=Q$ be its embedding into $G$. Similarly, the set
${\mathcal{Q}}^{\prime\prime}_{i}$ of paths defines a matching
$M^{\prime\prime}_{i}\subseteq B^{\prime}_{i}\times A^{\prime}_{i}$, together
with an embedding $P(e)\in{\mathcal{Q}}^{\prime\prime}_{i}$ of each edge $e\in
M^{\prime\prime}$. Recall that matching $M^{\prime}_{i}$ has cardinality at
least $n/2-z$, while $|A^{\prime}|=|B^{\prime}|=n/2$. Therefore, by adding a
set $F^{\prime}_{i}$ of at most $z$ additional edges (that we refer to as
_fake edges_), we can turn matching $M^{\prime}_{i}$ into a perfect one.
Similarly, we add a collection $F^{\prime\prime}_{i}$ of at most $z$ fake
edges to $M^{\prime\prime}_{i}$ in order to turn it into a perfect matching.
The edges of $M^{\prime}_{i}\cup M^{\prime\prime}_{i}$ are then added to graph
$W$, and the current iteration terminates.

Finally, assume that the current iteration $i$ is of type 2. In this case, the
algorithm for the Cut Player from Theorem 8.5 computed a graph $W^{\prime}$
with $|V(W^{\prime})|\geq n/4$ and maximum vertex degree at most $18$, such
that $W^{\prime}$ is an $\alpha_{0}$-expander, together with a subset
$\hat{F}\subseteq E(W^{\prime})$ of at most $\frac{\alpha_{0}\cdot n}{1000}$
edges of $W^{\prime}$, and an embedding ${\mathcal{P}}$ of
$W^{\prime}\setminus\hat{F}$ into $W$ via paths of length at most
$O(\log^{2}n)$, that cause congestion at most $c\log^{2}n$.

Consider the current graph $W$. Denote
$F^{*}=\bigcup_{i^{\prime}=1}^{i-1}(F^{\prime}_{i^{\prime}}\cup
F^{\prime\prime}_{i^{\prime}})$ – the collection of the fake edges that we
have computed so far. Since for all $1\leq i^{\prime}<i$,
$|F^{\prime}_{i^{\prime}}\cup F^{\prime\prime}_{i^{\prime}}|\leq 2z$ and
$i\leq c_{\mathsf{CMG}}\log n$, we get that $|F^{*}|\leq
2c_{\mathsf{CMG}}z\log n$. We also denote
${\mathcal{Q}}^{*}=\bigcup_{i^{\prime}=1}^{i-1}({\mathcal{Q}}^{\prime}_{i}\cup{\mathcal{Q}}^{\prime\prime}_{i})$.
Note that ${\mathcal{Q}}^{*}$ defines an embedding of $W\setminus F^{*}$ into
$G$. All paths in ${\mathcal{Q}}^{*}$ have lengths at most $2d^{\prime}+1$.
Each set ${\mathcal{Q}}^{\prime}_{i}\cup{\mathcal{Q}}^{\prime\prime}_{i}$
causes congestion at most $O(d^{\prime}\log n)$, and so the total congestion
caused by the paths in ${\mathcal{Q}}^{*}$ is bounded by
$\eta^{*}=O(d^{\prime}\log^{2}n)$.

Next, we will construct a set $F\subseteq E(W^{\prime})$ of fake edges, and an
embedding of the remaining edges of $W^{\prime}$ into $G$, by combining the
embedding ${\mathcal{P}}$ of $W^{\prime}\setminus\hat{F}$ into $W$ with the
embedding ${\mathcal{Q}}^{*}$ of $W\setminus F$ into $G$. We start with
$F=\hat{F}$. Next, we process every edge $e\in E(W^{\prime})\setminus\hat{F}$
one by one. When an edge $e=(u,v)$ is processed, we consider the path
$P(e)\in{\mathcal{P}}$, that serves as an embedding of $e$ into graph $W$.
Recall that the length of the path is at most $O(\log^{2}n)$. Let
$P(e)=(e_{1},e_{2},\ldots,e_{r})$, where $r\leq O(\log^{2}n)$. If path $P(e)$
contains any edges of $F^{*}$, then we add $e$ to the set $F$ of fake edges.
Otherwise, for all $1\leq j\leq r$, we consider the path
$Q(e_{j})\in{\mathcal{Q}}^{*}$, that serves as the embedding of the edge
$e_{j}$ into graph $G$. Recall that the length of $Q$ is at most
$O(d^{\prime})$. By concatenating the paths $Q(e_{1}),\ldots,Q(e_{r})$, we
obtain a path $P^{\prime}(e)$ connecting $u$ to $v$ in $G$, whose length is at
most $O(d^{\prime}\log^{2}n)$. We turn $P^{\prime}(e)$ into a simple path in
time $O(d^{\prime}\log^{2}n)$, obtaining the final path $P^{*}(e)$, that will
serve as an embedding of the edge $e$.

Once every edge of $E(W^{\prime})\setminus\hat{F}$ is processed, we obtain a
final set $F$ of fake edges, and, for every remaining edge $e\in
E(W^{\prime})\setminus F$, a simple path $P^{*}(e)$ of length
$O(d^{\prime}\log^{2}n)$, that serves as the embedding of $e$ in $G$. Recall
that $|V(W^{\prime})|\geq n/4$. If the original value $|V(G)|$ was odd, then
$|V(W^{\prime})|\geq(|V(G)|-1)/4\geq|V(G)|/8$ holds. As required, graph
$W^{\prime}$ is an $\alpha_{0}$-expander with maximum vertex degree at most
$18$. It remains to bound the congestion caused by the paths in set
${\mathcal{P}}^{*}=\left\\{P^{*}(e)\mid e\in E(W^{\prime})\setminus
F\right\\}$, and the cardinality of the set $F$.

Consider any edge $e\in E(G)$. Recall that $e$ may participate in at most
$\eta^{*}=O(d^{\prime}\log^{2}n)$ paths in set
${\mathcal{Q}}^{*}=\left\\{Q(e^{\prime})\mid e^{\prime}\in E(W)\setminus
F^{*}\right\\}$. Every edge $e^{\prime}\in E(W)\setminus F^{*}$, whose
corresponding path $Q(e^{\prime})$ contains the edge $e$, may in turn
participate in at most $O(\log^{2}n)$ paths of ${\mathcal{P}}$. Therefore,
overall, every edge $e$ of $G$ participates in at most
$O(d^{\prime}\log^{4}n)$ paths of ${\mathcal{P}}^{*}$.

In order to bound the final number of the fake edges in $W^{\prime}$, recall
that $|F^{*}|\leq 2c_{\mathsf{CMG}}z\log n$. Since the paths in
${\mathcal{P}}$ cause congestion at most $c\log^{2}n$, we get that every edge
of $F^{*}$ may participate in at most $c\log^{2}n$ paths of ${\mathcal{P}}$.
Therefore, $|F\setminus\hat{F}|\leq(2c_{\mathsf{CMG}}z\log
n)\cdot(c\log^{2}n)\leq 2c\cdot c_{\mathsf{CMG}}\cdot
z\cdot\log^{3}n\leq\frac{\alpha_{0}\cdot n}{1000}$, since
$z=\frac{\alpha_{0}}{2000c\cdot c_{\mathsf{CMG}}\cdot\log^{3}n}\cdot n$. Since
$|\hat{F}|\leq\frac{\alpha_{0}\cdot n}{1000}$, we get that
$|F|\leq\frac{\alpha_{0}\cdot n}{500}$.

It now remains to bound the running time of the algorithm. The algorithm has
$O(\log n)$ iterations. In every iteration we use the algorithm for the Cut
Player from Theorem 8.5, whose running time is $\widetilde{O}(n^{2})$, and an
algorithm for the Matching Player from Theorem 8.6, whose running time is
$\widetilde{O}(md^{\prime})$.

Additionally, when computing the embedding of $W^{\prime}\setminus F$ into
$G$, we spend time at most $\tilde{O}(d^{\prime})$ per edge of $W^{\prime}$,
and, since $|E(W^{\prime})|\leq O(n)$, the computation of the embedding takes
time $\tilde{O}(nd^{\prime})$. Overall, the running time of the algorithm is
$\widetilde{O}(md^{\prime}+n^{2})$.

###  8.2 Algorithm for the Cut Player – Proof of Theorem 8.5

The proof of Theorem 8.5 easily follows from the following slightly weaker
theorem.

######  Theorem 8.7.

There is a deterministic algorithm, that, given an $n$-vertex directed graph
$W$ with maximum vertex degree at most $O(\log n)$, returns one of the
following:

  * •

either a cut $(A,B)$ in $W$ with
$|E_{W}(A,B)|\leq\frac{\min\left\\{|A|,|B|\right\\}}{128}$ and
$|A|,|B|\geq\frac{\alpha_{0}}{2^{14}}\cdot n$; or

  * •

another directed $n$-vertex graph $W^{\prime}$ with maximum vertex degree at
most $18$, such that $W^{\prime}$ is an $\alpha_{0}$-expander, together with a
subset $F\subseteq E(W^{\prime})$ of at most $k=\frac{\alpha_{0}\cdot
n}{1000}$ edges of $W^{\prime}$, and an embedding ${\mathcal{P}}$ of
$W^{\prime}\setminus F$ into $W$ via paths of length at most
$\tilde{d}=O(\log^{2}n)$, that cause congestion at most $\eta=O(\log^{2}n)$.

The running time of the algorithm is $\widetilde{O}(n^{2})$.

We prove Theorem 8.7 below, after we complete the proof of Theorem 8.5 using
it. We start with the graph $\hat{W}=W$, and then perform iterations, as long
as $|V(\hat{W})|\geq n/4$. We will also construct a collection ${\mathcal{X}}$
of subsets of vertices of $\hat{W}$, that is initialized to $\emptyset$. In
every iteration, we may add a single set $X$ to ${\mathcal{X}}$ (that defines
a sparse cut in the current graph $\hat{W}$), and then delete the vertices of
$X$ from $\hat{W}$.

In order to execute a single iteration, we apply the algorithm from Theorem
8.7 to the current graph $\hat{W}$. Let $n^{\prime}\geq n/4$ denote the number
of vertices that currently belong to $\hat{W}$. If the algorithm returned a
directed $n^{\prime}$-vertex $\alpha_{0}$-expander graph $W^{\prime}$ with
maximum vertex degree at most $18$, together with a subset $F\subseteq
E(W^{\prime})$ of at most $k=\frac{\alpha_{0}\cdot
n^{\prime}}{1000}\leq\frac{\alpha_{0}n}{1000}$ edges of $W^{\prime}$, and an
embedding ${\mathcal{P}}$ of $W^{\prime}\setminus F$ into $\hat{W}$ via paths
of length at most $\tilde{d}$, that cause congestion at most $\eta$, then we
terminate the algorithm and return $W^{\prime}$, $F$ and ${\mathcal{P}}$.

Assume now that the algorithm from Theorem 8.7 returned a cut
$(A^{\prime},B^{\prime})$ in $\hat{W}$ with
$|E_{\hat{W}}(A^{\prime},B^{\prime})|\leq\frac{\min\left\\{|A^{\prime}|,|B^{\prime}|\right\\}}{128}$
and $|A^{\prime}|,|B^{\prime}|\geq\frac{\alpha_{0}}{2^{14}}\cdot
n^{\prime}\geq\frac{\alpha_{0}}{2^{16}}n$. Denote the sets
$A^{\prime},B^{\prime}$ by $X$ and $Y$ respectively, where $X$ is the set
among $\left\\{A^{\prime},B^{\prime}\right\\}$ that is of smaller cardinality,
and $Y$ is the other set (if the cardinalities of the two sets are equal,
break the tie arbitrarily). We then add $X$ to ${\mathcal{X}}$, delete the
vertices of $X$ from $\hat{W}$, and continue to the next iteration.

If the above algorithm does not terminate with an expander $W^{\prime}$ that
is embedded into $W$, then it must terminate once $|V(\hat{W})|\leq n/4$
holds. Let ${\mathcal{X}}=\left\\{X_{1},X_{2},\ldots,X_{r}\right\\}$ be the
final collection of vertex subsets, where the sets are indexed in the order in
which they were added to ${\mathcal{X}}$. We also denote by $X_{r+1}$ the set
$V(\hat{W})$ obtained at the end of the algorithm, and we add $X_{r+1}$ to
${\mathcal{X}}$ as well. For all $1\leq j\leq r$, denote
$X^{\prime}_{j}=X_{j+1}\cup\cdots\cup X_{r+1}$. From our algorithm, for each
such index $j$, either $|E_{W}(X_{j},X^{\prime}_{j})|\leq|X_{j}|/128$, or
$|E_{W}(X^{\prime}_{j},X_{j})|\leq|X_{j}|/128$. Moreover, for all $1\leq j\leq
r+1$, $|X_{j}|\leq n/2$, while $|X_{r+1}|\geq\frac{n}{8}$. Therefore, if we
let $\alpha$ be such that
$\max_{X_{j}\in{\mathcal{X}}}\left\\{|X_{j}|\right\\}=\alpha\cdot n$, then
$\frac{1}{8}\leq\alpha\leq\frac{1}{2}$.

We can now use the algorithm from 2.3 to compute, in time
$O(|E(W)|)\leq\widetilde{O}(n)$, a cut $(A,B)$ in $W$, with $|E_{W}(A,B)|\leq
n/128$, and $|A|,|B|\geq\min\left\\{\frac{1-\alpha}{2}\cdot
n,\frac{n}{4}\right\\}\geq\frac{n}{10}$.

The running time of every iteration of the algorithm is
$\widetilde{O}(n^{2})$, and the number of iterations is bounded by a constant.
The running time of the algorithm from 2.3 is bounded by $\widetilde{O}(n)$,
and so the total running time of our algorithm is $\widetilde{O}(n^{2})$.

In order to complete the proof of theorem 8.5, it is now enough to prove
Theorem 8.7.

Proof of Theorem 8.7. Since we can afford a running time that is as high as
$\widetilde{O}(n^{2})$, we can use a straightforward algorithm, that is
significantly simpler than other current deterministic algorithms for the cut
player (see e.g. Theorem 7.3 in [BGS20], that generalizes the results of
[CGL+19] to directed graphs).

We let $c$ be a sufficiently large constant, and we set the parameters
$\tilde{d}=c\log^{2}n$ and $\eta=c^{2}\log^{2}n$.

We start by using the algorithm from Theorem 2.1 to construct, in time $O(n)$,
a directed $n$-vertex graph $W^{\prime}$ that is an $\alpha_{0}$-expander,
with maximum vertex degree at most $18$.

Next, we start with a graph $\hat{W}=W$, and then perform $|E(W^{\prime})|$
iterations. In every iteration we will attempt to embed some edge $e\in
E(W^{\prime})$ into $\hat{W}$, and we will delete from $\hat{W}$ edges that
participate in too many of the embedding paths. We will maintain a partition
$(E^{\prime},E^{\prime\prime},F)$ of the edges of $E(W^{\prime})$, where set
$E^{\prime}$ contains all edges $e\in E^{\prime}$ for which an embedding path
$P(e)$ was already computed by the algorithm; set $F$ contains all edges $e\in
E^{\prime}$ for which the algorithm failed to compute an embedding path; and
$E^{\prime\prime}$ contains all edges of $W^{\prime}$ that were not considered
by the algorithm yet. We also maintain a set ${\mathcal{P}}=\left\\{P(e)\mid
e\in E^{\prime}\right\\}$ of all embedding paths that the algorithm computed
so far. For every edge $e\in E(W)$ we will maintain a counter $\mu(e)$ that
counts the number of paths in ${\mathcal{P}}$ containing $e$.

Initially, we set $E^{\prime}=F=\emptyset$, $E^{\prime\prime}=E(W^{\prime})$,
and ${\mathcal{P}}=\emptyset$. We also set $\hat{W}=W$, and perform iterations
as long as $E^{\prime\prime}\neq\emptyset$.

In order to perform an iteration, we consider any edge $e=(u,v)\in
E^{\prime\prime}$. We compute the shortest path $P$ in the current graph
$\hat{W}$ connecting $u$ to $v$, by peforming a BFS from vertex $u$, in time
$O(|E(\hat{W})|)\leq\widetilde{O}(n)$. If the length of $P$ is greater than
$\tilde{d}$, then we move edge $e$ from $E^{\prime\prime}$ to $F$. Otherwise,
we set $P(e)=P$, move $e$ from $E^{\prime\prime}$ to $E^{\prime}$, and add
path $P(e)$ to set ${\mathcal{P}}$. Additionally, for every edge
$e^{\prime}\in E(P)$ we increase the counter $\mu(e^{\prime})$ by $1$, and if
the counter reaches $\eta$, we delete $e^{\prime}$ from $\hat{W}$.

Once $E^{\prime\prime}=\emptyset$ holds, the algorithm terminates. Notice
that, since the algorithm spends at most $\widetilde{O}(n)$ time on processing
every edge of $W^{\prime}$, its running time so far is $\widetilde{O}(n^{2})$.

We now consider two cases. Assume first that, at the end of the above
procedure, $|F|\leq k$ holds. In this case, we terminate the algorithm, and
return the $\alpha_{0}$-expander $W^{\prime}$, the set $F$ of its edges, and
the embedding ${\mathcal{P}}$ of $W^{\prime}\setminus F$ into $W$ that our
algorithm has computed. It is easy to verify that every path in
${\mathcal{P}}$ has length at most $\tilde{d}$, and ${\mathcal{P}}$ causes
congestion at most $\eta$ in $W$.

From now on we assume that $|F|>k$. We now show an algorithm to compute a cut
$(A,B)$ in $W$ of sparsity at most $\frac{1}{128}$, such that
$|A|,|B|\geq\frac{\alpha_{0}}{2^{14}}\cdot n$.

Let $E^{*}=E(W)\setminus E(\hat{W})$. Equivalently, set $E^{*}$ contains all
edges that participate in $\eta$ paths in ${\mathcal{P}}$. Recall that
$|{\mathcal{P}}|\leq|E(W^{\prime})|\leq 9n$, and the length of every path in
${\mathcal{P}}$ is at most $\tilde{d}$. Therefore,
$\sum_{P\in{\mathcal{P}}}|E(P)|\leq 9\tilde{d}n$, and
$|E^{*}|\leq\frac{\sum_{P\in{\mathcal{P}}}|E(P)|}{\eta}\leq\frac{9\tilde{d}n}{\eta}$.

In the remainder of the algorithm, we will iteratively cut off sparse cuts
(that may be quite small) from graph $\hat{W}$. We maintain a set
${\mathcal{X}}$ of subsets of vertices of $\hat{W}$, that is initially empty.
The algorithm is iterative, and in every iteration a single set $Z$ is added
to ${\mathcal{X}}$, with the vertices of $Z$ deleted from $\hat{W}$. The
algorithm continues as long as $|V(\hat{W})|\geq n-k/2$ holds. We now describe
the execution of a single iteration.

Since $|V(\hat{W})|\geq n-k/2$, there exists an edge $e=(x,y)\in F$ with
$x,y\in\hat{W}$. Moreover, since we were unable to embed $e$ into $\hat{W}$
when it was considered, and since we only deleted edges and vertices from
$\hat{W}$ since then, it must be the case that $\mbox{\sf
dist}_{\hat{W}}(x,y)>\tilde{d}$ holds right now. Let $\Delta=O(\log n)$ denote
the maximum vertex degree in $\hat{W}$. Since $\tilde{d}=c\log^{2}n$, where
$c$ is a large enough constant, we can ensure that $\tilde{d}\geq 64\Delta\log
n$ holds. We now use the algorithm from 2.2 to compute a cut $(Z,Z^{\prime})$
in the current graph $\hat{W}$, whose sparsity is at most
$\varphi^{\prime}=\frac{32\Delta\log
n}{\tilde{d}}\leq\frac{O(\log^{2}n)}{\tilde{d}}$. Since
$\tilde{d}=c\log^{2}n$, and we can set $c$ to be a large enough constant, we
can ensure that $\varphi^{\prime}\leq\frac{\alpha_{0}}{2^{22}}$. Denote the
sets $Z,Z^{\prime}$ by $X$ and $Y$, such that $X$ is the set of smaller
cardinality, and $Y$ is the other set (if the cardinalities of the two sets
are equal, break the tie arbitrarily). We then add $X$ to ${\mathcal{X}}$,
delete the vertices of $X$ from $\hat{W}$, and continue to the next iteration.
Note that, if $X$ is the set of vertices that was added to ${\mathcal{X}}$
during the current iteration, then from 2.2, the running time of the iteration
is bounded by $\tilde{O}(|X|)$.

When the above algorithm terminates, we let
${\mathcal{X}}=\left\\{X_{1},X_{2},\ldots,X_{r}\right\\}$ be the final
collection of vertex subsets, where the sets are indexed in the order in which
they were added to ${\mathcal{X}}$. We also denote by $X_{r+1}$ the set
$V(\hat{W})$ obtained at the end of the algorithm, and we add $X_{r+1}$ to
${\mathcal{X}}$ as well. For all $1\leq j\leq r$, denote
$X^{\prime}_{j}=X_{j+1}\cup\cdots\cup X_{r+1}$. From our algorithm, for each
such index $j$, either
$|E_{\hat{W}}(X_{j},X^{\prime}_{j})|\leq\varphi^{\prime}\cdot|X_{j}|$, or
$|E_{\hat{W}}(X^{\prime}_{j},X_{j})|\leq\varphi^{\prime}\cdot|X_{j}|$, where
$\varphi^{\prime}\leq\frac{\alpha_{0}}{2^{22}}$. From our discussion, the
total time that the algorithm spent on constructing the sets of vertices in
${\mathcal{X}}$ is bounded by
$\sum_{j=1}^{r}\tilde{O}(|X_{j}|)\leq\tilde{O}(n)$. Let $\alpha$ be chosen
such that the cardinality of largest set of vertices in ${\mathcal{X}}$ is
$\alpha\cdot n$. From our algorithm, $\alpha\leq 1-\frac{k}{2n}\leq
1-\frac{\alpha_{0}}{2000}$, since $k=\frac{\alpha_{0}\cdot n}{1000}$.

We can now use the algorithm from 2.3 to compute, in time
$O(|E(\hat{W})|)\leq\widetilde{O}(n)$, a cut $(A,B)$ in $\hat{W}$, with
$|E_{\hat{W}}(A,B)|\leq\varphi^{\prime}\cdot\sum_{i=1}^{r}|X_{i}|$, and
$|A|,|B|\geq\min\left\\{\frac{1-\alpha}{2}\cdot
n,\frac{n}{4}\right\\}\geq\frac{\alpha_{0}n}{4000}$.

Recall that graph $\hat{W}$ was obtained from $W$ by deleting the edges of
$E^{*}$ from it, and that $|E^{*}|\leq\frac{9\tilde{d}n}{\eta}$. Subtituting
$\tilde{d}=c\log^{2}n$ and $\eta=c^{2}\log^{2}n$, where $c$ is a sufficiently
large constant, we get that: $|E^{*}|\leq\frac{\alpha_{0}n}{2^{22}}$.

Overall:

$|E_{W}(A,B)|\leq|E_{\hat{W}}(A,B)|+|E^{*}|\leq\varphi^{\prime}n+\frac{\alpha_{0}n}{2^{22}}\leq\frac{\alpha_{0}n}{2^{21}}.$

(we have used the fact that $\varphi^{\prime}\leq\frac{\alpha_{0}}{2^{22}}$).
Lastly, since
$|A|,|B|\geq\frac{\alpha_{0}n}{4000}\geq\frac{\alpha_{0}n}{2^{14}}$, we get
that $|E_{W}(A,B)|\leq\frac{\min\left\\{|A|,|B|\right\\}}{128}$, as required.

From our discussion, the running time of the entire algorithm is bounded by
$\widetilde{O}(n^{2})$.

###  8.3 Algorithm for the Matching Player – Proof of Theorem 8.6

As before, we call the edges of $E_{G}(R,L)$ _special edges_ , and the edges
of $E_{G}(L,R)$ _regular edges_. Notice that every vertex of $G$ may be
incident to at most one special edge.

As a preprocessing step, we construct a maximal set ${\mathcal{Q}}_{1}$ of
disjoint paths, where every path connects a distinct vertex of $A$ to a
distinct vertex of $B$, and consists of a single regular edge. We do so by
employing a simple greedy algorithm. We start with
${\mathcal{Q}}_{1}=\emptyset$. While there is a regular edge $e=(a,b)$ with
$a\in A$ and $b\in B$, we add a path $Q=(e)$ to ${\mathcal{Q}}_{1}$, and we
delete $a$ and $b$ from $A$ and $B$, respectively. Clearly, this preprocessing
step can be executed in time $O(|E(G)|)$, and at the end of this step there is
no regular edge in $G$ connecting a vertex of $A$ to a vertex of $B$.

Let $\hat{G}$ be the graph that is obtained from $G$ by replacing every edge
$e$ with $d^{\prime}$ parallel copies. Edges that are copies of special edges
in $G$ are called special edges of $\hat{G}$, and similarly copies of regular
edges in $G$ are called regular edges of $\hat{G}$.

At the beginning of the algorithm, every special edge $e\in E(\hat{G})$ is
assigned a length $\ell(e)=1/d^{\prime}$, while every regular edge $e\in
E(\hat{G})$ is assigned length $0$. Clearly, at the beginning of the
algorithm, $\sum_{e\in E(\hat{G})}\ell(e)\leq n$ holds, as there are at most
$nd^{\prime}$ special edges in $\hat{G}$, each of which has length
$1/d^{\prime}$.

Over the course of the algorithm, the lengths of special edges may grow, while
the lengths of regular edges remain $0$. Additionally, vertices may be deleted
from sets $A$ and $B$. We will gradually construct a collection
${\mathcal{Q}}_{2}$ of paths in graph $\hat{G}$, where every path connects a
distinct vertex of $A$ to a distinct vertex of $B$; the number of special
edges on every path is at most $d^{\prime}$; and the paths cause edge-
congestion at most $O(\log n)$ in $\hat{G}$. Initially, we set
${\mathcal{Q}}_{2}=\emptyset$.

We assume for now that we are given an oracle, that, when prompted, either
returns a simple path $Q$ in the current graph $\hat{G}$ connecting some
vertex of $A$ to some vertex of $B$, such that the length $\sum_{e\in
E(Q)}\ell(e)$ of the path is at most $1$; or correctly establishes that such a
path does not exist.

The algorithm proceeds in iterations. In every iteration, the oracle is asked
to return a simple path $Q$ in the current graph $\hat{G}$ connecting some
vertex of $A$ to some vertex of $B$, such that the length $\sum_{e\in
E(Q)}\ell(e)$ of the path is at most $1$. If it successfully does so, then we
add $Q$ to ${\mathcal{Q}}_{2}$, double the length of every special edge on
path $Q$, remove the endpoints of the path from sets $A$ and $B$,
respectively, and continue to the next iteration. Notice that in this case,
$|{\mathcal{Q}}_{2}|$ grows by $1$, while $\sum_{e\in E(\hat{G})}\ell(e)$
increases by at most $1$. If the oracle establishes that no such path $Q$
exists, then we terminate the algorithm.

At the end of the algorithm, we set
${\mathcal{Q}}={\mathcal{Q}}_{1}\cup{\mathcal{Q}}_{2}$. If
$|{\mathcal{Q}}|\geq n/2-z$, then we return the collection ${\mathcal{Q}}$ of
paths. It is immediate to verify that the paths in ${\mathcal{Q}}$ connect
vertices of $A$ to vertices of $B$, and that their endpoints are disjoint.
Moreover, since the length of every special edge in $\hat{G}$ is at least
$\frac{1}{d^{\prime}}$, while the length of every path $Q\in{\mathcal{Q}}$ is
at most $1$, each path in ${\mathcal{Q}}$ contains at most $d^{\prime}$
special edges, and at most $2d^{\prime}+1$ edges overall, since special and
regular edges must alternate on every path. Lastly, due to the doubling of
edge lengths on the paths that we add to ${\mathcal{Q}}$, every special edge
of $\hat{G}$ may participate in at most $\log d^{\prime}=O(\log n)$ paths in
${\mathcal{Q}}$, and so in total every special edge of $G$ may participate in
at most $O(d^{\prime}\log n)$ paths in ${\mathcal{Q}}$. Moreover, if $e=(u,v)$
is a regular edge, then every path $Q\in{\mathcal{Q}}_{2}$ that contains $e$
must also contain either the unique special edge incident to $u$, or the
unique special edge incident to $v$, while the paths in ${\mathcal{Q}}_{1}$
are disjoint. We conclude that the paths in ${\mathcal{Q}}$ cause congestion
at most $O(d^{\prime}\log n)$ in $G$.

From now on we assume that, when the algorithm terminates,
$|{\mathcal{Q}}|<n/2-z$ holds. Let $A^{\prime}\subseteq A$,
$B^{\prime}\subseteq B$ be the sets of vertices that remain in $A$ and $B$,
respectively at the end of the algorithm. Since the algorithm terminated, in
the current graph $\hat{G}$, the length of the shortest path connecting a
vertex of $A^{\prime}$ to a vertex of $B^{\prime}$ is at least $1$. Since
$|{\mathcal{Q}}|<n/2-z$ and $|A^{\prime}|,|B^{\prime}|=n/2-|{\mathcal{Q}}|$,
we get that $|A^{\prime}|,|B^{\prime}|\geq z$.

Recall that, at the beginning of the algorithm, $\sum_{e\in
E(\hat{G})}\ell(e)\leq n$ held. Over the course of the algorithm, in every
iteration, $\sum_{e\in E(\hat{G})}\ell(e)$ grew by at most $1$, and the number
of iterations is bounded by $|A|\leq n$. Therefore, at the end of the
algorithm, $\sum_{e\in E(\hat{G})}\ell(e)\leq 2n$ holds.

Let $e$ be any edge of graph $G$, and let $S(e)$ be the collection of $d$
parallel edges representing $e$ in graph $\hat{G}$. Let $e^{\prime}\in S(e)$
be the copy of $e$ with smallest current length $\ell(e^{\prime})$. Notice
that, if we set the lengths of all edges in $S(e)$ to $\ell(e^{\prime})$, then
the length of the shortest path connecting a vertex of $A^{\prime}$ to a
vertex of $B^{\prime}$ in $\hat{G}$ will remain at least $1$. Therefore, we
can assume without loss of generality, that, for every edge $e\in E(G)$, the
lengths of all edges in set $S(e)$ are identical; we denote this length by
$\ell^{\prime}(e)$. Notice that $\sum_{e\in E(\hat{G})}\ell(e)\leq 2n$
continues to hold after this transformation.

Consider now the graph $G^{\prime}$ that is obtained from $G$ by setting the
length of every edge $e\in E(G)$ to $\ell^{\prime}(e)$, unifying all vertices
of $A^{\prime}$ into a source vertex $s$ and all vertices of $B^{\prime}$ into
a destination vertex $t$. Since graph $\hat{G}$ contained $d^{\prime}$
parallel copies of every edge $e\in E(G)$, that all had the same length equal
to $\ell^{\prime}(e)$, we now have that $\sum_{e\in
E(G)}\ell^{\prime}(e)\leq\frac{\sum_{e\in
E(\hat{G})}\ell(e)}{d^{\prime}}\leq\frac{2n}{d^{\prime}}$. At the same time,
since $\hat{G}$ did not contain an $A^{\prime}$-$B^{\prime}$ path of length at
most $1$, we get that $\mbox{\sf dist}_{G^{\prime}}(s,t)\geq 1$.

Consider the following thought experiment: we choose a threshold
$\rho\in(0,1)$ uniformly at random, and then define two sets $S=\left\\{v\in
V(G^{\prime})\mid\mbox{\sf dist}_{G^{\prime}}(s,v)\leq\rho\right\\}$ and
$T=V(G^{\prime})\setminus S$ of vertices. Clearly, $s\in S$ and $t\in T$ must
hold. By replacing $s$ with the vertices of $A^{\prime}$ in $S$ and replacing
$t$ with the vertices of $B^{\prime}$ in $T$, we obtain a cut
$(S^{\prime},T^{\prime})$ in graph $G$ with
$|E_{G}(S^{\prime},T^{\prime})|=|E_{G^{\prime}}(S,T)|$. It is easy to verify
that, for every edge $e=(u,v)\in E(G^{\prime})$, the probability that $u\in S$
and $v\in T$ is bounded by $\ell^{\prime}(e)$. Therefore, the expected value
of $|E_{G^{\prime}}(S,T)|$ is bounded by $\sum_{e\in
E(G)}\ell^{\prime}(e)\leq\frac{2n}{d^{\prime}}$. By performing a BFS search
from vertex $s$, we can then compute a cut $(S^{\prime},T^{\prime})$ in
$G^{\prime}$ with
$|E_{G^{\prime}}(S^{\prime},T^{\prime})|\leq\frac{2n}{d^{\prime}}$. Using the
procedure outlined above, we can convert this cut into a cut $(S,T)$ in $G$
with $|E_{G}(S,T)|\leq\frac{2n}{d^{\prime}}$. Since $A^{\prime}\subseteq S$
and $B^{\prime}\subseteq T$, we are guaranteed that $|S|,|T|\geq z$. We return
the cut $(S,T)$ and terminate the algorithm. In order to analyze the algorithm
we need to provide an implementation of the oracle, which we do next.

Notice that the paths in ${\mathcal{Q}}$ cause congestion at most
$O(d^{\prime}\log n)$ in $G$, so
$\sum_{Q\in{\mathcal{Q}}}|E(Q)|)\leq\tilde{O}(md^{\prime})$. We will use this
fact later.

#### Implementing the Oracle.

In order to implement the oracle efficiently, we construct a new graph $H$, as
follows. Initially, $H$ is obtained from $G$ by adding a source vertex $s$
that connects with an edge to every vertex of $A$, and a destination vertex
$t$, to which every vertex of $B$ connects. The edges that leave $s$ or enter
$t$ are called regular edges.

Let $q=\left\lceil\log d^{\prime}\right\rceil$. Consider any special edge
$e=(u,v)\in E(G)$. We replace $e$ with $q$ parallel edges
$e_{1},\ldots,e_{q}$, whose lengths are $1,2,4,\ldots,2^{q}$, respectively.
Additionally, for every regular edge $e^{\prime}=(x,u)$ that enters $u$, we
replace $e^{\prime}$ with $q$ parallel edges
$e^{\prime}_{1},\ldots,e^{\prime}_{q}$, whose lengths are
$1,2,4,\ldots,2^{q}$, respectively (the latter transformation is also applied
to the regular edge $(s,u)$, if such an edge is present). The latter step is
done in order to ensure that the length of every edge in $G$ is greater than
$0$, since this is a requirement in Theorem 2.4 that we will use. If $(x,y)$
is a regular edge with $y\neq t$, such that no special edge leaves $y$, then
we set $\ell(y)=1$. So far we have assigned lengths to all edges of $H$,
except for some edges that leave $s$, and all edges that enter $t$. Initially,
for every edge $e$ that leaves $s$, we set the length of $e$ to be $0$. If
$e=(v,t)$ is an edge that enters $t$, then we set its length to be $1$ if
$v\in L$ and to $0$ otherwise. We then increase the length of every edge that
is incident to $s$ or $t$ by $1$, thus obtaining the final lengths of all
edges in $H$.

Over the course of the algorithm, for every special edge $e=(u,v)\in E(G)$,
for every index $1\leq j\leq q$, we monitor the number of copies of $e$ in
graph $\hat{G}$, whose length is $\frac{2^{j}}{d^{\prime}}$. Once this number
becomes $0$, the corresponding copy $e_{j}$ of $e$ is deleted from graph $H$.
Additionally, for every regular edge $e^{\prime}=(x,u)$, we also delete the
corresponding copy $e^{\prime}_{j}$ from $H$. Lastly, whenever a vertex $a$ is
deleted from set $A$, we delete edge $(s,a)$ from $H$, and whenever a vertex
$b$ is deleted from set $B$, we delete edge $(b,t)$ from $H$. Therefore, the
only types of updates that graph $H$ undergoes is the deletion of edges.

Throughout the algorithm, we will ensure that, if $Q$ is an $s$-$t$ path that
the oracle returns, then exactly one vertex of $Q$ lies in $B$ – the
penultimate vertex on the path. This ensures that, throughout the algorithm,
for every vertex $v$ that currently lies in $B$, for every edge $e\in E(G)$
that enters $v$, a copy of $e$ whose length is $1$ is present in $H$.

Consider now an $s$-$t$ path $Q$ in $H$ at any time during the algorithm. From
the definition of $H$, the penultimate vertex on $Q$ must lie in $B$; we
denote that vertex by $b$. We assume that $Q$ is a simple path, that $b$ is
the only vertex of $Q$ that lies in $B$, and that, for every edge $e\in E(Q)$,
$e$ is the shortest-length edge among its parallel edges in $H$. Note that the
first edge on $Q$ must be regular, while the second edge may be either regular
or special. Similarly, the last edge on $Q$ must be regular, while the
penultimate edge may be regular or special. We partition $Q$ into three
subpaths, $Q_{1},Q_{2}$, and $Q_{3}$, as follows. Path $Q_{1}$ is the longest
subpath of $Q$ that starts with $s$ and only contains regular edges. Since no
regular edge connects a vertex of $A$ to a vertex of $B$, it is easy to verify
that $Q_{1}$ contains either one or two edges. Similarly, we let $Q_{3}$ be
the longest subpath of $Q$ that terminates at $t$ and only contains regular
edges. As before, path $Q_{3}$ contains either one or two edges. We let
$Q_{2}$ be the subpath of $Q$ that starts at the last endpoint of $Q_{1}$, and
terminates at the first endpoint of $Q_{3}$. From our definition, the first
and the last edges on $Q_{2}$ must be special edges, and, from the properties
of graph $G$, special and regular edges alternate on $Q_{2}$. Therefore, we
can denote the sequence of the edges on path $Q_{2}$ by
$(e_{1},e^{\prime}_{2},e_{2},\ldots,e^{\prime}_{z},e_{z})$, where
$e_{1},e_{2},\ldots,e_{z}$ are special edges, and
$e^{\prime}_{2},e^{\prime}_{3},\ldots,e^{\prime}_{z}$ are regular edges. For
all $1\leq i\leq z$, let $e^{*}_{i}$ denote the edge of $\hat{G}$
corresponding to $e_{i}$. Then for all $1<i\leq z$, the lengths of the edges
$e^{\prime}_{i}$ and $e_{i}$ in $H$ are both equal to $\ell(e^{*}_{i})\cdot
d^{\prime}$, where $\ell(e^{*}_{i})$ is the length of $e^{*}_{i}$ in
$\hat{G}$. Therefore, the length of $Q_{2}$ in $H$ is $\ell(e^{*}_{1})\cdot
d^{\prime}+\sum_{i=2}^{z}2\ell(e^{*}_{i})\cdot d^{\prime}$. Consider now the
path $Q_{1}$. If this path consists of a single edge (that must be incident to
$s$), then, from our construction, the length of that edge is
$\ell(e^{*}_{1})\cdot d^{\prime}+1$. Otherwise, the first edge on $Q_{1}$ has
length $1$, and the second has length $\ell(e^{*}_{1})\cdot d^{\prime}$. In
either case, the length of $Q_{1}$ in $H$ is $\ell(e^{*}_{1})\cdot
d^{\prime}+1$. Lastly, consider the path $Q_{3}$. Notice that the first
endpoint of $Q_{3}$, that we denote by $v$, has a special edge entering it,
and so $v$ lies in the set $L$ of the bipartition. If path $Q_{3}$ consists of
a single edge, then that edge connects a vertex of $L$ to $t$, so, from our
construction, its length is $2$. Assume now that path $Q_{3}$ consists of two
edges, and denote the sequence of the vertices on $Q_{3}$ by $(v,b,t)$. Then
$b\in R$ must hold, and so the length of the edge $(b,t)$ is $1$.
Additionally, since $b\in B$, the length of the edge $(v,b)$ is $1$ as well.
Therefore, in either case, the length of $Q_{3}$ is $2$. Altogether, we get
that the length of $Q$ is $2d^{\prime}\cdot\sum_{i=1}^{z}\ell(e^{*}_{i})+3$.

It is now easy to verify that, throughout the algorithm, if $Q$ is an $s$-$t$
path in $H$, whose length is $\delta+3$, and exactly one vertex of $Q$ lies in
$B$, then the length of the corresponding path $Q^{\prime}$ in $\hat{G}$
(where for every edge $e\in E(Q)$, we choose its cheapest copy in $\hat{G}$ to
participate in the path) is at most $\frac{\delta}{2d^{\prime}}$. Similarly,
if $Q^{\prime}$ is an $s$-$t$ path in graph $\hat{G}$, that contains exactly
one vertex of $B$, whose length is $\delta^{\prime}$, then the length of the
corresponding $s$-$t$ path in graph $H$ (where again for every edge $e\in
E(Q^{\prime})$ we use its cheapest copy available in $H$) is at most
$2\delta^{\prime}\cdot d^{\prime}+3$.

It is now enough to design an algorithm for the following problem. We are
given a graph $H$, with two special vertices $s$ and $t$, and integral
positive edge lengths, together with a parameter $d^{\prime}>0$. The algorithm
consists of a number of iterations. In every iteration, we need to either
return the shortest $s$-$t$ path in the current graph $H$, provided that its
length is at most $2d^{\prime}+2$; or correctly establish that the length of
the shortest $s$-$t$ path in $H$ is greater than $2d^{\prime}+2$. In the
latter case, the algorithm terminates, while in the former case, the algorithm
is given a batch of edge deletions from graph $H$, together with the deletion
of the penultimate vertex on $Q$ from $B$, and we proceed to the next
iteration. It is easy to verify that, if $Q$ is the shortest $s$-$t$ path in
$H$, then it may contain at most one vertex that lies in $B$ – the penultimate
vertex on $Q$. Otherwise, if another vertex $b^{\prime}\in B$ lies in $Q$,
then the subpath of $Q$ between $s$ and $b^{\prime}$, combined with the edge
$(b^{\prime},t)$, provides a shorter $s$-$t$ path in $H$.

We apply the algorithm from Theorem 2.4 to graph $H$ and parameter
$2d^{\prime}+3$. Recall that the algorithm maintains an ES-Tree for $H$,
rooted in $s$, up to depth $2d^{\prime}+3$. We denote the corresponding tree
by $T$. In every iteration, we check whether vertex $t$ lies in the tree $T$,
and if so, whether $\mbox{\sf dist}_{H}(s,t)\leq 2d^{\prime}+3$. If this is
not the case, then we terminate the algorithm. Otherwise, we use the tree $T$
to compute a shortest $s$-$t$ path $P$ in $H$, whose length must be at most
$2d^{\prime}+3$, in time $O(|E(P)|)$, by simply retracing the unique $s$-$t$
path in the tree $T$. By deleting the first and the last vertices from $P$, we
obtain a path connecting a vertex of $A$ to a vertex of $B$ in $\hat{G}$,
whose length is at most $1$.

It is easy to verify that the total time needed to implement the oracle is
$O(|E(H)|\cdot d^{\prime}+\sum_{Q\in{\mathcal{Q}}}|E(Q)|)$, where
${\mathcal{Q}}$ is the set containing all paths that the algorithm ever
returned. As shown already,
$\sum_{Q\in{\mathcal{Q}}}|E(Q)|)\leq\tilde{O}(md^{\prime})$, while it is easy
to see that $|E(H)|\leq\widetilde{O}(m)$. The total running time of the oracle
is then bounded by $\widetilde{O}(md^{\prime})$.

We note that in general, the algorithm for Theorem 8.6 does not need to
compute and maintain the graph $\hat{G}$ explicitly, this graph is only used
for the sake of analysis. Instead, for every special edge $e\in E(G)$, for
every integer $0\leq j\leq\left\lceil\log d^{\prime}\right\rceil$, we only
need to keep track of the number of copies of $e$ that lie in graph $\hat{G}$
and have length $2^{j}/d^{\prime}$. Therefore, the total running time of the
remainder of the algorithm is bounded by
$O(m+\sum_{Q\in{\mathcal{Q}}}|E(Q)|)\leq\widetilde{O}(md^{\prime})$. This
includes the time required to perform a BFS in $G^{\prime}$, in order to
compute a spase cut $(S,T)$ if needed. The total running time of the whole
algorithm for Theorem 8.6 is then bounded by $\widetilde{O}(md^{\prime})$.

##  Appendix A Proof of 2.2

For all integers $i\geq 0$, let $S_{i}=B_{G}(x,i)$ be the set of all vertices
$u\in V(G)$ with $\mbox{\sf dist}_{G}(x,u)\leq i$.

Let $L=d/4$. We claim that, if $|S_{L}|<n/2$, then there is some index $1\leq
i<L$ for which $|E_{G}(S_{i},V\setminus S_{i})|\leq\varphi\cdot|S_{i}|$ holds.

Indeed, assume otherwise. Then for all $1\leq i<L$, $|E_{G}(S_{i},V\setminus
S_{i})|\geq\varphi\cdot|S_{i}|$. Denote $R_{i}=S_{i+1}\setminus S_{i}$. Since
every edge in $E_{G}(S_{i},V\setminus S_{i})$ must enter a vertex of $R_{i}$,
and the degree of every vertex in $G$ is at most
$\delta_{\mbox{{\footnotesize{max}}}}$, we get that
$|R_{i}|\geq\frac{|E_{G}(S_{i},V\setminus
S_{i})|}{\delta_{\mbox{{\footnotesize{max}}}}}\geq\frac{\varphi\cdot|S_{i}|}{\delta_{\mbox{{\footnotesize{max}}}}}$
must hold.

Therefore, for all $1\leq i<L$,
$|S_{i+1}|\geq\left(1+\frac{\varphi}{\delta_{\mbox{{\footnotesize{max}}}}}\right)|S_{i}|$,
and
$|S_{L}|\geq\left(1+\frac{\varphi}{\delta_{\mbox{{\footnotesize{max}}}}}\right)^{L}\geq\left(1+\frac{\varphi}{\delta_{\mbox{{\footnotesize{max}}}}}\right)^{d/4}$.

Since $d=\frac{32\delta_{\mbox{{\footnotesize{max}}}}\log n}{\varphi}$, we get
that $|S_{L}|>n$, a contradiction.

For all integers $i\geq 0$, we also let $S^{\prime}_{i}=\left\\{u\in
V(G)\mid\mbox{\sf dist}(u,y)\leq i\right\\}$. Using the same reasoning, if
$|S^{\prime}_{L}|\leq n/2$, then there is some index $1\leq i<L$ for which
$|E_{G}(V\setminus
S^{\prime}_{i},S^{\prime}_{i})|\leq\varphi\cdot|S^{\prime}_{i}|$.

We are now ready to describe our algorithm. We run in parallel two processes.
The first process simply performs a BFS from vertex $x$, while the second
process performs a reversed BFS from vertex $y$. The first process, whenever
it computes a set $S_{i}$, checks whether $|E_{G}(S_{i},V\setminus
S_{i})|\leq\varphi\cdot|S_{i}|$. If so, we terminate both processes and return
the cut $(A,B)=(S_{i},V\setminus S_{i})$. Similarly, the second process,
whenever it computes a set $S^{\prime}_{j}$, checks whether $|E_{G}(V\setminus
S^{\prime}_{j},S^{\prime}_{j})|\leq\varphi\cdot|S^{\prime}_{j}|$ holds. If so,
we terminate both processes and return the cut $(A,B)=(V\setminus
S^{\prime}_{j},S^{\prime}_{j})$. Since we set $L=d/4$, it must be the case
that either $|S_{L}|\leq n/2$ or $|S^{\prime}_{L}|\leq n/2$, so one of the two
processes must terminate with a sparse cut. Since we run the two processes in
parallel, it is easy to verify that the running time is bounded by the number
of edges that the process that successfully terminated explored. Therefore,
the running time of the algorithm is at most
$O(\delta_{\mbox{{\footnotesize{max}}}}\cdot\min\left\\{|A|,|B|\right\\})$.

##  Appendix B Proof of Corollary 3.2

We start by applying the algorithm from Theorem 3.1 to graph $H$, to obtain a
collection ${\mathcal{P}}$ of $\Omega(\Delta/\operatorname{poly}\log n)$
$s$-$t$ paths in $H$, that cause edge-congestion at most $O(\log n)$. We
construct a directed graph $H^{\prime}\subseteq H$, that consists of all
vertices and edges that participate in the paths of ${\mathcal{P}}$. The
capacity of every edge in $H^{\prime}$ remains unit – the same as its capacity
in $H$.

Since the paths in ${\mathcal{P}}$ cause edge-congestion $\eta=O(\log n)$, due
to the special structure of graph $H$, they also cause vertex-congestion
$\eta$. Therefore, $|E(H^{\prime})|\leq O(n\log n)$. Additionally, by sending
$1/\eta=\Omega(1/\log n)$ flow units on every path in ${\mathcal{P}}$, we can
obtain a valid $s$-$t$ flow in $H^{\prime}$, that obeys edge capacities, whose
value is $\Omega(|{\mathcal{P}}|/\log n)$.

Next, we compute an integral maximum $s$-$t$ flow in $H^{\prime}$ that obeys
edge capacities in $H^{\prime}$, using the standard Ford-Fulkerson algorithm.
We start by setting the flow $f(e)$ on every edge $e\in E(H^{\prime})$ to $0$,
and then perform iterations. In every iteration, we use the current flow $f$
in $H^{\prime}$ in order to compute a residual flow network
$H^{\prime\prime}=H^{\prime}_{f}$. If there is no $s$-$t$ path in
$H^{\prime\prime}$, then the algorithm terminates. We are then guaranteed that
the value of the current flow $f$ is optimal, so
$\operatorname{val}(f)\geq\Omega(|{\mathcal{P}}|/\log n)$. Otherwise, we
compute an arbitrary $s$-$t$ path $P$ in $H^{\prime\prime}$, and we augment
the flow $f$ along the path $P$. Notice that every iteration of the algorithm
can be implemented in time $O(|E(H^{\prime\prime})|)=\widetilde{O}(n)$, and
the number of iterations is bounded by $n$. Therefore, the total running time
of this algorithm is $\widetilde{O}(n^{2})$. The final integral flow $f$ can
be decomposed, in time $O(|E(H^{\prime})|)=\widetilde{O}(n)$, into a
collection ${\mathcal{P}}^{\prime}$ of $\Omega(|{\mathcal{P}}|/\log
n)\geq\Omega(\Delta/\operatorname{poly}\log n)$ edge-disjoint paths connecting
$s$ to $t$ in $H^{\prime}$. Due to the special structure of the graph $H$, the
paths in ${\mathcal{P}}^{\prime}$ are also internally vertex-disjoint. It now
remains to analyze the running time of the algorithm. The running time of the
algorithm from Theorem 3.1 is
$\widetilde{O}\left(\frac{n^{2.5}}{\sqrt{\Delta}}\right)$; the running time of
the Ford-Fulkerson algorithm in graph $H^{\prime}$ is $\widetilde{O}(n^{2})$,
and the time required to decompose the resulting flow into a collection
${\mathcal{P}}^{\prime}$ of paths is bounded by $\widetilde{O}(n)$, as
discussed above. Since $\Delta\leq n$, the overall running time of the
algorithm is bounded by
$\widetilde{O}\left(\frac{n^{2.5}}{\sqrt{\Delta}}\right)$.

We note that we could have used the blocking flow idea used in Hopcroft-Karp
algorithm to compute the set ${\mathcal{P}}^{\prime}$ of paths in $H^{\prime}$
in time $\widetilde{O}(n^{1.5})$. Alternatively, we could also directly round
the initial fractional $s$-$t$ flow in $H^{\prime}$, in expected time
$\widetilde{O}(|E(H)|)=\widetilde{O}(n)$, e.g. by using the algorithm from
Theorem 5 in [LRS13], that builds on the results of [GKK10]. The latter would
however result in a randomized algorithm, and since the bottlenecks in the
running time of our algorithm lie elsewhere we use this simpler albeit
somewhat slower method.

##  Appendix C Proof of Theorem 5.1

#### Initial Transformation of Edge Lengths.

We start by performing a simple transformation of the lengths of edges, whose
goal is to ensure that $\Gamma\cdot\log n\leq
d\leq\max\left\\{4n/\epsilon,4\Gamma\cdot\log n\right\\}$.

We perform the transformation in two steps. The first step is only performed
if $d>\left\lceil n/\epsilon\right\rceil$. For every edge $e\in E(G)$, we let
the new length $\tilde{\ell}(e)$ be obtained by rounding the length $\ell(e)$
up to the next integral multiple of $\left\lceil\epsilon d/n\right\rceil$, and
we set $\tilde{d}=(1+2\epsilon)d$. Consider any simple $s$-$t$ path $P$ in
$G$. Since $|E(P)|\leq n$, we get that $\sum_{e\in E(P)}\ell(e)\leq\sum_{e\in
E(P)}\tilde{\ell}(e)\leq 2\epsilon d+\sum_{e\in E(P)}\ell(e)$. Notice that, if
$P$ is a simple $s$-$t$ path in $G$, with $\sum_{e\in
E(P)}\tilde{\ell}(e)\leq(1+6\epsilon)\tilde{d}$, then $\sum_{e\in
E(P)}\ell(e)\leq(1+10\epsilon)d$. Moreover, if $G^{\prime}$ is a subgraph that
is obtained from $G$ by deleting some edges from it, and $G^{\prime}$ does not
contain an $s$-$t$ path $P$ with $\sum_{e\in
E(P)}\tilde{\ell}(e)\leq\tilde{d}$, and $\sum_{e\in E(P)}w(e)\leq\Gamma$, then
$G$ may not contain an $s$-$t$ path $P$ with $\sum_{e\in E(P)}\ell(e)\leq d$,
and $\sum_{e\in E(P)}w(e)\leq\Gamma$. Therefore, we can now replace the
lengths $\ell(e)$ of edges $e\in E(G)$ with new lengths $\tilde{\ell}(e)$. The
problem remains unchanged, except that now, in response to path-query, the
algorithm needs to return a simple $s$-$t$ path $P$ of length at most
$(1+6\epsilon)\tilde{d}$.

Since all edge lengths are now integral multiples of
$\left\lceil\frac{\epsilon d}{n}\right\rceil$, we can divide the length of
every edge $e$ by $\left\lceil\frac{\epsilon d}{n}\right\rceil$, obtaining a
new length, that we still denote by $\ell(e)$, which remains an integer. We
also update $\tilde{d}$ by dividing its value by $\left\lceil\frac{\epsilon
d}{n}\right\rceil$. This scaling of the lengths of edges and of parameter $d$
do not change the problem, but now we are guaranteed that $\tilde{d}\leq
4n/\epsilon$. For convenience, we will call $\tilde{d}$ by $d$ from now on.

If $d\geq\Gamma\cdot\log n$ now holds, no further transformations are
necessary, since we are now guaranteed that $\Gamma\cdot\log n\leq
d\leq\max\left\\{4n/\epsilon,4\Gamma\cdot\log n\right\\}$. Assume now that
$d<\Gamma\cdot\log n$. Then we multiply the lengths of all edges by factor
$\left\lceil\frac{\Gamma\log n}{d}\right\rceil$, and replace $d$ with value
$d\cdot\left\lceil\frac{\Gamma\log n}{d}\right\rceil$; this transformation
does not change the problem, but it ensures that $\Gamma\cdot\log n\leq d\leq
4\Gamma\cdot\log n$. From now on we assume that $\Gamma\cdot\log n\leq
d\leq\max\left\\{4n/\epsilon,4\Gamma\cdot\log n\right\\}$ holds. The problem
remains the same, except that now, in response to path-query, the algorithm
needs to return a simple $s$-$t$ path $P$ of length at most $(1+6\epsilon)d$.

#### Modified Edge Lengths.

We define, for every edge $e\in E(G)$, a _modified edge length_
$\ell^{\prime}(e)$, as follows:
${\ell^{\prime}(e)=\ell(e)+\epsilon\cdot\left\lceil\frac{d}{\Gamma\cdot\log
n}\cdot w(e)\right\rceil}$. Notice that, since $1/\epsilon$ is an integer, for
every edge $e\in E(G)$, its modified length $\ell^{\prime}(e)$ is an integral
multiple of $\epsilon$. Throughout, for a pair of vertices $u,v$ in $G$, we
denote by $\mbox{\sf dist}^{\prime}(u,v)$ the distance from $u$ to $v$ in the
current graph $G$, with respect to edge lengths $\ell^{\prime}(\cdot)$. We
need the following simple observation.

######  Observation C.1.

Assume that at time $\tau\in{\mathcal{T}}$, there is an $s$-$t$ path $P$ in
$G$ with $\sum_{e\in E(P)}\ell(e)\leq d$, and $\sum_{e\in
E(P)}w(e)\leq\Gamma$. Then at time $\tau$, $\mbox{\sf
dist}^{\prime}(s,t)\leq(1+3\epsilon)\cdot d$.

###### Proof.

For all $0\leq i\leq\left\lceil\log n\right\rceil$, let $E_{i}$ be the set of
all edges $e\in E(P)$ with $w(e)=2^{i}$. Since $\sum_{e\in
E(P)}w(e)\leq\Gamma$, for all such $i$, $|E_{i}|\leq\frac{\Gamma}{2^{i}}$. We
now get that:

$\begin{split}\sum_{e\in E(P)}\ell^{\prime}(e)&\leq\sum_{e\in
E(P)}\left(\ell(e)+\frac{\epsilon\cdot d}{\Gamma\cdot\log n}\cdot
w(e)+\epsilon\right)\\\ &\leq\sum_{e\in
E(P)}(1+\epsilon)\ell(e)+\sum_{i=0}^{\left\lceil\log n\right\rceil}\sum_{e\in
E_{i}}\frac{\epsilon\cdot d}{\Gamma\cdot\log n}\cdot 2^{i}\\\
&\leq(1+\epsilon)d+\sum_{i=0}^{\left\lceil\log
n\right\rceil}|E_{i}|\cdot\frac{\epsilon\cdot d}{\Gamma\cdot\log n}\cdot
2^{i}\\\ &\leq(1+\epsilon)\cdot d+\sum_{i=0}^{\left\lceil\log
n\right\rceil}\frac{\Gamma}{2^{i}}\cdot\frac{\epsilon\cdot d}{\Gamma\cdot\log
n}\cdot 2^{i}\\\ &\leq(1+3\epsilon)d.\end{split}$

(we have used the fact that $\ell(e)\geq 1$ for every edge $e\in E(G)$).

Throughout the algorithm, we maintain, for every vertex $v\in V(G)$, an
estimate $\widetilde{\mathsf{dist}}(v)$ on $\mbox{\sf dist}^{\prime}(s,v)$. If
$\widetilde{\mathsf{dist}}(v)>2d$ holds, we replace
$\widetilde{\mathsf{dist}}(v)$ with $\infty$. Additionally, for every edge
$e=(v,u)$, vertex $u$ is given an estimate $\widetilde{\mathsf{dist}}_{u}(v)$
on $\mbox{\sf dist}^{\prime}(s,v)$ (that may be outdated). More specifically,
if $w(e)=2^{i}$, then vertex $v$ only communicates its estimate
$\widetilde{\mathsf{dist}}(v)$ to $u$ in increments of
${\epsilon^{2}\cdot\left\lceil\frac{d\cdot 2^{i}}{\Gamma\cdot\log
n}\right\rceil}$ (it is this modification of the standard Even-Shiloach tree
algorithm that leads to the faster total update time). In other words, every
time $\widetilde{\mathsf{dist}}(v)$ passes a threshold of
${z\cdot\epsilon^{2}\cdot\left\lceil\frac{d\cdot 2^{i}}{\Gamma\cdot\log
n}\right\rceil}$ for some integer $z$, vertex $v$ communicates its current
estimate $\widetilde{\mathsf{dist}}(v)$ to $u$, and
$\widetilde{\mathsf{dist}}_{u}(v)$ is replaced with this amount. Additionally,
we maintain a directed tree $T\subseteq G$, that is rooted at vertex $s$, with
all edges directed away from the root. The tree contains all vertices $v\in
V(G)$ with $\widetilde{\mathsf{dist}}(v)\neq\infty$. Whenever we refer to
lengths of paths or distances in the tree $T$, it is with respect to edge
lengths $\ell^{\prime}(e)$ for $e\in E(T)$.

#### Additional Data Structures.

In addition to the tree $T$, the estimates $\widetilde{\mathsf{dist}}(v)$ for
vertices $v\in V$, and estimates $\widetilde{\mathsf{dist}}_{u}(v)$ for edges
$(v,u)\in E$, we maintain the following data structures. For every vertex
$v\in V$, we maintain a heap $H(v)$ that contains all vertices of
$\left\\{u\in V\mid(u,v)\in E\right\\}$, with the key associated with each
such vertex $u$ being $\widetilde{\mathsf{dist}}_{v}(u)+\ell^{\prime}(u,v)$.
Additionally, for all $0\leq i\leq\left\lceil\log n\right\rceil$, we maintain
a set $U_{i}(v)$ of vertices, that contains every vertex $u\in V(G)$, such
that there is an edge $e=(v,u)$ with $w(e)=2^{i}$ in $G$.

#### Invariants.

We ensure that, throughout the algorithm, the following invariants hold.

  1. I1.

For every vertex $v$, the value $\widetilde{\mathsf{dist}}(v)$ is an integral
multiple of $\epsilon$, and it may only grow over the course of the algorithm;
the same holds for values $\widetilde{\mathsf{dist}}_{u}(v)$ for all edges
$e=(v,u)$;

  2. I2.

If $e=(x,y)$ is an edge in the tree $T$, then vertex $x$ is the vertex with
the lowest key $\widetilde{\mathsf{dist}}_{y}(x)+\ell^{\prime}(x,y)$ in
$H(y)$, and moreover
$\widetilde{\mathsf{dist}}(y)=\widetilde{\mathsf{dist}}_{y}(x)+\ell^{\prime}(x,y)$;

  3. I3.

For every edge $e=(u,v)$, if $w(e)=2^{i}$, then
$\widetilde{\mathsf{dist}}(u)-\epsilon^{2}\cdot\left\lceil\frac{d\cdot
2^{i}}{\Gamma\cdot\log
n}\right\rceil\leq\widetilde{\mathsf{dist}}_{v}(u)\leq\widetilde{\mathsf{dist}}(u)$;

  4. I4.

For all $v\in V(G)$, if $\mbox{\sf dist}^{\prime}_{G}(s,v)\leq 2d$, then
$\widetilde{\mathsf{dist}}(v)\neq\infty$ and
$\widetilde{\mathsf{dist}}(v)\leq\mbox{\sf dist}^{\prime}(s,v)$; and

  5. I5.

For all $v\in V(G)$,
$\widetilde{\mathsf{dist}}(v)\geq(1-\epsilon)\cdot\mbox{\sf
dist}^{\prime}(s,v)$ holds at all times; moreover, if $v\in V(T)$, then the
length of the $s$-$v$ path in the current tree $T$ is at most
$\frac{\widetilde{\mathsf{dist}}(v)}{1-\epsilon}$.

#### Initialization.

At the beginning of the algorithm, we compute a shortest-path out-tree $T$
rooted at vertex $s$, with respect to edge lengths $\ell^{\prime}(\cdot)$. For
every vertex $v\in V$, we then set $\widetilde{\mathsf{dist}}(v)=\mbox{\sf
dist}^{\prime}(s,v)$ – the distance from $s$ to $v$ in the tree $T$. Next, we
scan all vertices in the bottom-up order in the tree $T$. For each such vertex
$v$, if $\widetilde{\mathsf{dist}}(v)>2d$, then we set
$\widetilde{\mathsf{dist}}(v)=\infty$, and delete $v$ from the tree. For every
edge $e=(v,u)\in E$, we set
$\widetilde{\mathsf{dist}}_{u}(v)=\widetilde{\mathsf{dist}}(v)$. Lastly, for
every vertex $v\in V$, we initialize the heap $H(v)$ with the vertices of
$\left\\{u\in V\mid(u,v)\in E\right\\}$, and the sets
$\left\\{U_{i}(v)\right\\}_{0\leq i\leq\left\lceil\log n\right\rceil}$ of its
out-neighbors. It is easy to verify that the initialization can be performed
in time $O(m\log m)$, and that all invariants hold at the end of
initialization.

Next we describe the algorithms for handling vertex-splits and edge deletions.

#### Algorithm for Handling Vertex Splits.

Consider a vertex split operation, in which we are given a vertex $v\in V$,
and a collection $U=\left\\{u_{1},\ldots,u_{k}\right\\}$ of new vertices that
need to be inserted into $G$. Recall that we are also given a collection
$E^{\prime}$ of new edges that must be inserted into $G$, and for every edge
$e\in E^{\prime}$, we are given a length $\ell(e)$ and a weight $w(e)$. For
each such edge $e\in E^{\prime}$, either both its endpoints lie in
$\left\\{u_{1},\ldots,u_{k},v\right\\}$; or one endpoint lies in
$\left\\{u_{1},\ldots,u_{k}\right\\}$, and the other in
$V(G)\setminus\left\\{v,u_{1},\ldots,u_{k}\right\\}$. In the latter case, if
$e=(u_{i},x)$, then edge $e^{\prime}=(v,x)$ must currently lie in $G$, and
both $w(e^{\prime})=w(e)$ and $\ell(e^{\prime})=\ell(e)$ must hold, so
$\ell^{\prime}(e^{\prime})=\ell^{\prime}(e)$. Similarly, if $e=(x,u_{i})$,
then edge $e^{\prime}=(x,v)$ must currently lie in $G$, and both
$w(e^{\prime})=w(e)$ and $\ell(e^{\prime})=\ell(e)$ must hold, so
$\ell^{\prime}(e^{\prime})=\ell^{\prime}(e)$.

If $\widetilde{\mathsf{dist}}(v)\neq\infty$, then let $e=(x,v)$ be the unique
edge that is incoming into $v$ in the tree $T$. We _temporarily_ insert, into
set $E^{\prime}$, edges $e_{i}=(x,u_{i})$ with
$\ell^{\prime}(e_{i})=\ell^{\prime}(e)$ and $w(e_{i})=w(e)$ for all $u_{i}\in
U$.

Our algorithm consists of two steps. In the first step, we set, for every
vertex $u_{i}\in U$,
$\widetilde{\mathsf{dist}}(u_{i})=\widetilde{\mathsf{dist}}(v)$. We then
inspect the edges of $E^{\prime}$ one by one. Consider any such edge
$e=(a,b)$.

  * •

If both endpoints of $e$ lie in $U\cup\left\\{v\right\\}$, then we set
$\widetilde{\mathsf{dist}}_{b}(a)=\widetilde{\mathsf{dist}}(a)$, and update
the corresponding heap $H(b)$ by inserting $a$ into it.

  * •

If the second endpoint $b$ of $e$ lies in $U$ and the first endpoint $a$ lies
in $V(G)\setminus(U\cup\left\\{v\right\\})$, then edge $e^{\prime}=(a,v)$ with
$\ell^{\prime}(e^{\prime})=\ell^{\prime}(e)$ must be present in $G$. In this
case, we set
$\widetilde{\mathsf{dist}}_{b}(a)=\widetilde{\mathsf{dist}}_{v}(a)$, and
update heap $H(b)$ by inserting $a$ into it.

  * •

Similarly, if the first endpoint $a$ of $e$ lies in $U$, and the second
endpoint $b$ lies in $V(G)\setminus(U\cup\left\\{v\right\\})$, then edge
$e^{\prime}=(v,b)$ with $\ell^{\prime}(e^{\prime})=\ell^{\prime}(e)$ must be
present in $G$. In this case, we set
$\widetilde{\mathsf{dist}}_{b}(a)=\widetilde{\mathsf{dist}}_{b}(v)$, and
update heap $H(b)$ by inserting $a$ into it.

Lastly, if $w(e)=2^{i}$, and $b\not\in U_{i}(a)$, then we insert $b$ into
$U_{i}(a)$. We also update the graph $G$ with the insertion of the vertices of
$U$ and edges of $E^{\prime}$. Notice that all these updates can be done in
time $O((|U|+|E^{\prime}|)\cdot\log m)$.

The second step only needs to be executed if
$\widetilde{\mathsf{dist}}(v)\neq\infty$. In this step we delete from $G$ the
edges $e_{1},\ldots,e_{k}$ that were temporarily inserted. Our data structure
is then updated using the algorithm that we describe below, for handling edge-
deletion updates.

We now establish that all invariants hold after the first step. Invariant I1
continues to hold, as we did not update any $\widetilde{\mathsf{dist}}(a)$ or
$\widetilde{\mathsf{dist}}_{b}(a)$ estimates except for the newly inserted
vertices.

In order to establish Invariant I2, assume that
$\widetilde{\mathsf{dist}}(v)\neq\infty$, and so edge $(x,v)$ lies in tree
$T$. Observe that for every vertex $u_{i}\in U$, all vertices in $H(u_{i})$
lie in $H(v)$, except possibly for the vertices of $\left(U\cup
v\right)\setminus\left\\{u_{i}\right\\}$. But for every vertex
$a\in\left(U\cup v\right)\setminus\left\\{u_{i}\right\\}$,
$\widetilde{\mathsf{dist}}(a)=\widetilde{\mathsf{dist}}(v)>\widetilde{\mathsf{dist}}(x)$
currently holds, so the key of such a vertex $a$ in the heap $H(u_{i})$ is
greater than or equal to
$\widetilde{\mathsf{dist}}_{u_{i}}(v)=\widetilde{\mathsf{dist}}(v)=\widetilde{\mathsf{dist}}_{v}(x)+\ell^{\prime}(x,v)=\widetilde{\mathsf{dist}}_{u_{i}}(x)+\ell^{\prime}(x,u_{i})$.
Since $u_{i}$ is connected to $x$ in the tree $T$, we get that Invariant I2
holds for $u_{i}$. Consider now any vertex $a\not\in U$, and assume that some
edge $(b,a)$ lies in tree $T$. It is possible that we have inserted new
vertices into $H(a)$: if an edge $e=(u_{i},a)$ for some $u_{i}\in U$ lies in
$E^{\prime}$, then $u_{i}$ was inserted into $H(a)$. However, in this case,
edge $e^{\prime}=(v,a)$ with $\ell^{\prime}(e^{\prime})=\ell^{\prime}(e)$
belonged to $G$ before the current update, and so $v$ already lied in $H(a)$.
Since $\ell^{\prime}(e)=\ell^{\prime}(e^{\prime})$, and
$\widetilde{\mathsf{dist}}_{a}(u_{i})=\widetilde{\mathsf{dist}}_{a}(v)$, the
key of $u_{i}$ in heap $H(a)$ is equal to the key of $v$, that remained
unchanged. Therefore, Invariant I2 continues to hold.

We now turn to prove that Invariants I4 and I5 continue to hold. Consider any
vertex $a\in V(G)$. If $a\not\in U$, then it is easy to see that $\mbox{\sf
dist}^{\prime}(s,a)$ did not change after the current update. This is because
for any path $P$ connecting $s$ to $a$ in the current graph $G$, we can obtain
a path $P^{\prime}$ connecting $s$ to $a$ in the original graph $G$, whose
length with respect to the modified edge lengths $\ell^{\prime}(\cdot)$ is no
higher than that of $P$, by replacing every vertex of $U$ on $P$ with the
vertex $v$. Moreover, path $P^{\prime}$ still belongs to the current graph
since we did not delete any vertices or edges during the current update. Since
$\widetilde{\mathsf{dist}}(a)$ did not change, and the path connecting $s$ to
$a$ in $T$ did not undergo any changes either, both invariants continue to
hold for $a$.

Assume now that $a\in U$. Let $P$ be the path connecting $s$ to $v$ in the
current tree $T$. Since path $P$ did not change during the current update,
from Invariant I5 , the length of this path is at most
$\frac{\widetilde{\mathsf{dist}}(v)}{1-\epsilon}$. Notice that the last edge
on this path is $e=(x,v)$, and recall that we have inserted an edge
$e^{\prime}=(x,a)$ into $G$, with
$\ell^{\prime}(e^{\prime})=\ell^{\prime}(e)$. By replacing edge $e$ with
$e^{\prime}$ on path $P$, we obtain a path $P^{\prime}$, connecting $s$ to
$a$, which is the unique $s$–$a$ path in tree $T$. Moreover, the length of
$P^{\prime}$ is equal to the length of $P$, which, in turn, is at most
$\frac{\widetilde{\mathsf{dist}}(v)}{1-\epsilon}=\frac{\widetilde{\mathsf{dist}}(a)}{1-\epsilon}$.
We conclude that $\mbox{\sf
dist}^{\prime}(s,a)\leq\frac{\widetilde{\mathsf{dist}}(a)}{1-\epsilon}$,
establishing Invariant I5 for vertex $a$.

In order to establish Invariant I4 for vertex $a$, let $Q$ be the shortest
$s$-$a$ path in graph $G$, with respect to edge lengths
$\ell^{\prime}(\cdot)$. By replacing every vertex of $U$ on this path with
vertex $v$, and removing loops, we obtain an $s$-$v$ path $Q^{\prime}$ in $G$,
whose length is no higher than the length of $Q$. Therefore, $\mbox{\sf
dist}^{\prime}(s,v)\leq\mbox{\sf dist}^{\prime}(s,a)$. Since we set
$\widetilde{\mathsf{dist}}(a)=\widetilde{\mathsf{dist}}(v)$, we get that, if
$\mbox{\sf dist}^{\prime}(s,a)\neq\infty$, then $\mbox{\sf
dist}^{\prime}(s,v)\neq\infty$, and
$\widetilde{\mathsf{dist}}(a)=\widetilde{\mathsf{dist}}(v)\leq\mbox{\sf
dist}^{\prime}(s,v)\leq\mbox{\sf dist}^{\prime}(s,a)$. We conclude that
Invariants I4 and I5 continue to hold.

It now remains to establish Invariant I3. Consider any edge $e=(a,b)$. Notice
that none of the values $\widetilde{\mathsf{dist}}(a)$ of vertices $a\in V$
changed, except for the vertices of $U$ that were inserted into $G$.
Similarly, value $\widetilde{\mathsf{dist}}_{b}(a)$ remained unchanged, except
if $a$ or $b$ (or both) are vertices that were newly inserted into $G$. In
other words, we only need to consider edges $e=(a,b)\in E^{\prime}$.

Let $e=(a,b)$ be any such edge. As before, we need to consider three cases.
The first case happens if both $a,b\in U\cup\left\\{v\right\\}$. In this case,
we set
$\widetilde{\mathsf{dist}}(a)=\widetilde{\mathsf{dist}}(b)=\widetilde{\mathsf{dist}}(v)$
and $\widetilde{\mathsf{dist}}_{b}(a)=\widetilde{\mathsf{dist}}(v)$, so the
invariant clearly holds. Assume now that $a\in U$ and $b\not\in
U\cup\left\\{v\right\\}$. In this case, edge $e^{\prime}=(v,b)$ was present in
$G$ before the current update, and we set
$\widetilde{\mathsf{dist}}(a)=\widetilde{\mathsf{dist}}(v)$ and
$\widetilde{\mathsf{dist}}_{b}(a)=\widetilde{\mathsf{dist}}_{b}(v)$. Since the
invariant held for edge $(v,b)$ before the current update, and since
$w(a,b)=w(v,b)$, the invariant holds for edge $(a,b)$ at the end of the
current update. Lastly, assume that $a\not\in U\cup\left\\{v\right\\}$ and
$b\in U$. In this case, edge $(a,v)$ was present in $G$ before the current
update, we set
$\widetilde{\mathsf{dist}}_{b}(a)=\widetilde{\mathsf{dist}}_{v}(a)$ and
$\widetilde{\mathsf{dist}}(a)$ remains unchanged. Since Invariant I3 held for
edge $(a,v)$ at the beginning of the current update, it now holds for edge
$(a,b)$ at the end of the update.

#### Algorithm for Handling Edge Deletions.

We now provide an algorithm for updating the data structure with the deletion
of some edge $e=(x,y)$. First, we may need to update the heap $H(y)$ (by
either deleting $x$ from it, or changing the key of $x$ in the heap, if
another $(x,y)$ edge is present in $G$). We may also need to delete $y$ from
the appropriate set $U_{i}(x)$; all this can be done in time $O(\log n)$. If
$e\not\in T$, then no further updates are needed. We assume from now on that
$e\in E(T)$. We start by deleting the edge $e$ from the tree $T$.

Throughout the algorithm, we let $S$ be the set of vertices that are not
currently connected to the tree $T$. We will not maintain the set $S$
explicitly, but it will be useful for the analysis. At the beginning of the
algorithm, the set $S$ contains all vertices that lied in the original subtree
of $T$ rooted at $y$.

Our algorithm maintains a heap $Q$ that contains a subset of vertices of $S$
that need to be examined. The key associated with each vertex $v$ in $Q$ is
$\widetilde{\mathsf{dist}}(v)$. We will ensure that the following invariant
holds throughout the update:

  1. J1.

If $a$ is the vertex with minimum value $\widetilde{\mathsf{dist}}(a)$ in $S$,
then $a\in Q$ holds.

We start with the heap $Q$ containing only the vertex $y$. Then we perform
iterations, as long as $Q\neq\emptyset$. In order to execute a single
iteration, we let $a$ be the vertex with smallest key
$\widetilde{\mathsf{dist}}(a)$ in the heap $Q$, and we let $b$ be the vertex
in heap $H(a)$ with smallest key. If $\widetilde{\mathsf{dist}}(a)>2d$, then
we set $\widetilde{\mathsf{dist}}(a)$ to $\infty$ and remove it from $Q$. We
then set value $\widetilde{\mathsf{dist}}(x)$ of every vertex that is
currently not connected to the tree $T$ to $\infty$ and terminate the update
algorithm. We assume from now on that $\widetilde{\mathsf{dist}}(a)\leq 2d$.
We then consider two cases.

The first case happens if
$\widetilde{\mathsf{dist}}_{a}(b)+\ell^{\prime}(b,a)\leq\widetilde{\mathsf{dist}}(a)$.
Note that from Invariant J1, vertex $b$ is currently attached to the tree $T$.
In this case, we remove $a$ from $Q$ and attach it to the tree $T$ as a child
of vertex $b$, via the edge $(b,a)$. Every vertex that is currently a
descendant of $a$ also becomes automatically attached to the tree $T$ and
removed from the set $S$; vertex $a$ itself is removed from $S$ as well.

Consider now the second case, where
$\widetilde{\mathsf{dist}}_{a}(b)+\ell^{\prime}(b,a)>\widetilde{\mathsf{dist}}(a)$.
In this case, we increase $\widetilde{\mathsf{dist}}(a)$ by (additive)
$\epsilon$, and keep vertex $a$ in the heap $Q$. Additionally, for every
integer $0\leq i\leq\left\lceil\log n\right\rceil$, such that, for some
integer $q$, threshold $q\cdot\epsilon^{2}\cdot\left\lceil\frac{d\cdot
2^{i}}{\Gamma\cdot\log n}\right\rceil$ lies between the old and the new value
$\widetilde{\mathsf{dist}}(a)$, we consider every vertex $z\in U_{i}(a)$. We
set $\widetilde{\mathsf{dist}}_{z}(a)=\widetilde{\mathsf{dist}}(a)$ and update
the key of vertex $a$ in the heap $H(z)$. Additionally, if $z$ is currently a
child-vertex of $a$, then we disconnect $z$ from $a$ (so it stops being a
child of $a$), and add $z$ to the heap $Q$. This finishes the algorithm for
handling edge-deletion updates.

We start by showing that Invariant J1 holds throughout the algorithm.

######  Claim C.2.

Invariant J1 holds throughout the algorithm.

###### Proof.

Consider any time during the execution of the update procedure, and let $a$ be
the vertex of $S$ with smallest value $\widetilde{\mathsf{dist}}(a)$. Assume
for contradiction that $a\not\in Q$. Observe first that, whenever the value
$\widetilde{\mathsf{dist}}(v)$ changes for any vertex of $S$, we add $v$ to
$Q$. Vertex $v$ can only leave the heap $Q$ when it is connected to the tree
$T$, or if we set $\widetilde{\mathsf{dist}}(v)$ to $\infty$. Therefore, if
$\widetilde{\mathsf{dist}}(a)$ ever changed over the course of the current
update operation, then $a\in Q$ must hold. We assume from now on that value
$\widetilde{\mathsf{dist}}(a)$ did not change over the course of the current
update operation. Let $b$ be the parent-vertex of $a$ at the beginning of the
current update. From our algorithm, if value
$\widetilde{\mathsf{dist}}_{b}(a)$ ever changed over the course of the current
update operation, then vertex $a$ was immediately added to heap $Q$.
Therefore, value $\widetilde{\mathsf{dist}}_{b}(a)$ remained unchanged
throughout the current update.

Denote the weight of edge $(b,a)$ by $2^{i}$. In the next observation, we show
that, at the beginning of the current update procedure,
$\widetilde{\mathsf{dist}}(b)$ was significantly lower than
$\widetilde{\mathsf{dist}}(a)$. We will then conclude that
$\widetilde{\mathsf{dist}}(b)$ must have grown significantly over the course
of the current update procedure, and so $\widetilde{\mathsf{dist}}_{b}(a)$
must have grown as well, leading to a contradiction.

######  Observation C.3.

At the beginning of the current update procedure,
$\widetilde{\mathsf{dist}}(b)\leq\widetilde{\mathsf{dist}}(a)-\frac{\epsilon\cdot
d}{\Gamma\cdot\log n}\cdot 2^{i-1}$ held.

###### Proof.

From Invariant I2, at the beginning of the current update procedure,
$\widetilde{\mathsf{dist}}(a)=\widetilde{\mathsf{dist}}_{a}(b)+\ell^{\prime}(b,a)$
held. Recall that
$\ell^{\prime}(b,a)=\ell(b,a)+\epsilon\cdot\left\lceil\frac{d}{\Gamma\cdot\log
n}\cdot 2^{i}\right\rceil$. Moreover, from Invariant I3,
$\widetilde{\mathsf{dist}}_{a}(b)\geq\widetilde{\mathsf{dist}}(b)-\epsilon^{2}\cdot\left\lceil\frac{d\cdot
2^{i}}{\Gamma\cdot\log n}\right\rceil$ held at the beginning of the procedure
for processing the update. Altogether, we get that, at the beginning of the
current update procedure:

$\begin{split}\widetilde{\mathsf{dist}}(a)&=\widetilde{\mathsf{dist}}_{a}(b)+\ell^{\prime}(b,a)\\\
&\geq\widetilde{\mathsf{dist}}(b)-\epsilon^{2}\cdot\left\lceil\frac{d\cdot
2^{i}}{\Gamma\cdot\log
n}\right\rceil+\ell(b,a)+\epsilon\cdot\left\lceil\frac{d}{\Gamma\cdot\log
n}\cdot 2^{i}\right\rceil\\\
&\geq\widetilde{\mathsf{dist}}(b)+\frac{\epsilon\cdot d}{\Gamma\cdot\log
n}\cdot 2^{i-1}.\end{split}$

Since vertex $a$ is the vertex of $S$ with smallest value
$\widetilde{\mathsf{dist}}(a)$, either vertex $b$ is currently connected to
the tree $T$, or the value $\widetilde{\mathsf{dist}}(b)$ has grown to become
at least $\widetilde{\mathsf{dist}}(a)$ over the course of the current update
procedure.

If vertex $b$ remained attached to the tree $T$ over the course of the entire
update procedure, then $a=y$ must hold; in other words, the edge that was
deleted from $G$ is $(b,a)$. In this case, $a$ must have been added to $Q$
immediately at the beginning of the update procedure. Otherwise, if vertex $b$
became attached to tree $T$ at any time during the update procedure, then each
of its children was either attached to tree $T$ together with it, or added to
$Q$. Since $a$ was never added to $Q$, it must be the case that $b$ was never
attached to $T$, and so $\widetilde{\mathsf{dist}}(b)$ increased over the
course of the current update procedure to become at least
$\widetilde{\mathsf{dist}}(a)$. We claim that in this case, value
$\widetilde{\mathsf{dist}}_{b}(a)$ must have been updated, leading to a
contradiction.

Indeed, from the above calculations, over the course of the current update
operation, value $\widetilde{\mathsf{dist}}(b)$ must have increased by at
least $\frac{\epsilon\cdot d}{\Gamma\cdot\log n}\cdot
2^{i-1}>\epsilon^{2}\cdot\left\lceil\frac{d\cdot 2^{i}}{\Gamma\cdot\log
n}\right\rceil$ units, (since $d\geq\Gamma\log n$ and $\epsilon\leq 1/8$), and
so value $\widetilde{\mathsf{dist}}_{a}(b)$ must have been updated, with
vertex $a$ added to $Q$, a contradiction.

We now verify that Invariants I1–I3 continue to hold at the end of the update
procedure, assuming that they held before the procedure started.

First, it is immediate to verify that values $\widetilde{\mathsf{dist}}(v)$
for vertices $v\in V$ and values $\widetilde{\mathsf{dist}}_{u}(v)$ for edges
$(v,u)$ are never decreased, and they only increase by intergral multiples of
$\epsilon$, so Invariant I1 continues to hold.

Consider now some edge $e=(v,u)$ with $w(e)=2^{i}$. Notice that our algorithm
updates $\widetilde{\mathsf{dist}}_{u}(v)$ to the current value
$\widetilde{\mathsf{dist}}(v)$ whenever the latter passes a threshold that is
an integral multiple of $\epsilon^{2}\cdot\left\lceil\frac{d\cdot
2^{i}}{\Gamma\cdot\log n}\right\rceil$. This ensures that
$\widetilde{\mathsf{dist}}(u)-\epsilon^{2}\left\lceil\frac{d\cdot
2^{i}}{\Gamma\cdot\log
n}\right\rceil\leq\widetilde{\mathsf{dist}}_{v}(u)\leq\widetilde{\mathsf{dist}}(u)$
holds at all times and establishes Invariant I3.

In order to establish Invariant I2, we consider the time when some vertex
$v\in S$ reconnects to the tree $T$ via an edge $(u,v)$. Notice that at this
time, if $z$ is a descendant of $v$, and no vertex on the $v$–$z$ path in $T$
was ever added to $Q$, then $z$ becomes connected to the tree $T$ as well. If
$z^{\prime}$ is the parent of $z$, then
$\widetilde{\mathsf{dist}}_{z}(z^{\prime})$ and $\widetilde{\mathsf{dist}}(z)$
remained unchanged over the course of the current update procedure, so
$\widetilde{\mathsf{dist}}(z)=\widetilde{\mathsf{dist}}_{z}(z^{\prime})+\ell^{\prime}(z^{\prime},z)$
continues to hold, and $z^{\prime}$ is the vertex with the lowest key
$\widetilde{\mathsf{dist}}_{z}(z^{\prime})+\ell^{\prime}(z^{\prime},z)$ in the
heap $H(z)$. Consider now vertex $v$ itself, and recall that it reconnects to
the tree $T$ via the edge $(u,v)$. From our algorithm, it must be the case
that $u$ is the vertex with the smallest key
$\widetilde{\mathsf{dist}}_{v}(u)+\ell^{\prime}(u,v)$ in $H(v)$, and moreover,
$\widetilde{\mathsf{dist}}_{v}(u)+\ell^{\prime}(u,v)\leq\widetilde{\mathsf{dist}}(v)$.
It now remains to show that
$\widetilde{\mathsf{dist}}_{v}(u)+\ell^{\prime}(u,v)=\widetilde{\mathsf{dist}}(v)$.
If the value $\widetilde{\mathsf{dist}}(v)$ never increased over the course of
the current update procedure, then, since Invariant I2 held at the beginning
of the update procedure, and since value $\widetilde{\mathsf{dist}}_{v}(u)$
may only grow, it is impossible that
$\widetilde{\mathsf{dist}}_{v}(u)+\ell^{\prime}(u,v)<\widetilde{\mathsf{dist}}(v)$.
Therefore, in this case,
$\widetilde{\mathsf{dist}}_{v}(u)+\ell^{\prime}(u,v)=\widetilde{\mathsf{dist}}(v)$
must hold at the end of the update procedure. Assume now that the value
$\widetilde{\mathsf{dist}}(v)$ grew over the course of the current update
procedure, and let $\tau$ be the time when it was increased last (recall that
each increase is by exactly $\epsilon$ units). Then, at time $\tau$,
$\widetilde{\mathsf{dist}}_{v}(u)+\ell^{\prime}(u,v)>\widetilde{\mathsf{dist}}(v)$
held. Since value $\widetilde{\mathsf{dist}}_{v}(u)$ may not decrease, and
since $\widetilde{\mathsf{dist}}_{v}(u)+\ell^{\prime}(u,v)$ is an integral
multiple of $\epsilon$, it must be the case that
$\widetilde{\mathsf{dist}}_{v}(u)+\ell^{\prime}(u,v)=\widetilde{\mathsf{dist}}(v)$
at the end of the procedure.

In order to establish Invariant I5, it is enough to show that, if $v\in V(T)$,
then the length of the $s$-$v$ path in the current tree $T$ is at most
$\frac{\widetilde{\mathsf{dist}}(v)}{1-\epsilon}$. The proof is by induction
on the number of edges on the path. The claim clearly holds for the root
vertex $s$. Let $j>0$ be any integer. We assume that the claim holds for all
vertices $v\in V(T)$ for which the $s$-$v$ path in $T$ contains at most $j-1$
edges, and prove the claim for the case where the path contains $j$ edges.
Consider now some vertex $v\in V(T)$, and let $P$ be the $s$-$v$ path in tree
$T$, that contains $j$ edges. Let $u$ be the penultimate vertex on the path,
and let $P^{\prime}$ be the subpath of $P$ from $s$ to $u$. Then
$\ell^{\prime}(P)=\ell^{\prime}(P^{\prime})+\ell^{\prime}(u,v)$. Let $i$ be
the integer for which $w(u,v)=2^{i}$. From the induction hypothesis:

$\ell^{\prime}(P^{\prime})\leq\frac{\widetilde{\mathsf{dist}}(u)}{1-\epsilon}.$

From Invariant I2,
$\widetilde{\mathsf{dist}}(v)=\widetilde{\mathsf{dist}}_{v}(u)+\ell^{\prime}(u,v)$,
and from Invariant I3,
$\widetilde{\mathsf{dist}}_{v}(u)\geq\widetilde{\mathsf{dist}}(u)-\epsilon^{2}\cdot\left\lceil\frac{d\cdot
2^{i}}{\Gamma\cdot\log n}\right\rceil$. Altogether, we get that:

$\widetilde{\mathsf{dist}}(v)=\widetilde{\mathsf{dist}}_{v}(u)+\ell^{\prime}(u,v)\geq\widetilde{\mathsf{dist}}(u)-\epsilon^{2}\cdot\left\lceil\frac{d\cdot
2^{i}}{\Gamma\cdot\log
n}\right\rceil+\ell^{\prime}(u,v)\geq(1-\epsilon)\cdot\ell^{\prime}(P^{\prime})-\epsilon^{2}\cdot\left\lceil\frac{d\cdot
2^{i}}{\Gamma\cdot\log n}\right\rceil+\ell^{\prime}(u,v).$

Since $\ell^{\prime}(u,v)=\ell(u,v)+\epsilon\cdot\left\lceil\frac{d\cdot
2^{i}}{\Gamma\cdot\log n}\right\rceil$, we get that
$\epsilon^{2}\cdot\left\lceil\frac{d\cdot 2^{i}}{\Gamma\cdot\log
n}\right\rceil\leq\epsilon\cdot\ell^{\prime}(u,v)$. Altogether, we get that:

$\widetilde{\mathsf{dist}}(v)\geq(1-\epsilon)\cdot\ell^{\prime}(P^{\prime})+(1-\epsilon)\ell^{\prime}(u,v)=(1-\epsilon)\ell^{\prime}(P),$

as required.

Lastly, it remains to establish Invariant I4. We first prove that, for every
vertex $v$ that lies in the tree $T$,
$\widetilde{\mathsf{dist}}(v)\leq\mbox{\sf dist}^{\prime}(s,v)$ holds. The
proof is by induction on the number of edges on the shortest path (with
respect to edge lengths $\ell^{\prime}(\cdot)$) connecting $s$ to $v$.
Induction base is when the path consists of a single vertex and no edges, so
$v=s$, in which case the claim clearly holds. Assume now that for some integer
$j>0$, the claim holds for all vertices $v^{\prime}$, for which there exists a
shortest $s$-$v^{\prime}$ path that contains fewer than $j$ edges. Consider
some vertex $v$, such that there exists a shortest $s$-$v$ path $P^{*}$ (with
respect to edge lengths $\ell^{\prime}(\cdot)$), containing exactly $j$ edges.
Let $u$ be the penultimate vertex on this path. From the induction hypothesis,
$\widetilde{\mathsf{dist}}(u)\leq\mbox{\sf dist}^{\prime}(s,u)$. From
Invariant I3,
$\widetilde{\mathsf{dist}}_{v}(u)\leq\widetilde{\mathsf{dist}}(u)$ holds, and,
from Invariant I2,
$\widetilde{\mathsf{dist}}(v)\leq\widetilde{\mathsf{dist}}_{v}(u)+\ell^{\prime}(u,v)$.
Altogether, we get that
$\widetilde{\mathsf{dist}}(v)\leq\widetilde{\mathsf{dist}}(u)+\ell^{\prime}(u,v)\leq\mbox{\sf
dist}^{\prime}(s,u)+\ell^{\prime}(u,v)=\mbox{\sf dist}^{\prime}(s,v)$. From
the analysis of the algorithm it is easy to verify that, once
$\widetilde{\mathsf{dist}}(v)$ reaches $2d$, it must be the case that