Recall that $\tilde{d}_{j-1}=2^{c(j-1)/\epsilon^{4}}$, while
$d^{\prime}<\frac{1}{4}\cdot 2^{c/\epsilon^{4}}$ from Inequality 5. Therefore,
we get that the length of every path in ${\mathcal{P}}^{\prime\prime}$ is at
most:

$3\tilde{d}_{j-1}\cdot d^{\prime}\leq 2^{c(j-1)/\epsilon^{4}}\cdot
2^{c/\epsilon^{4}}=2^{cj/\epsilon^{4}}=\tilde{d}_{j}.$

The total congestion caused by the paths in ${\mathcal{P}}^{\prime\prime}$ is
bounded by:

$4N^{6}+8\eta_{j-1}\cdot N^{128\epsilon^{2}}=4N^{6}+8\cdot
N^{6+256(j-1)\epsilon^{2}}\cdot
N^{128\epsilon^{2}}\leq\frac{N^{6+256j\epsilon^{2}}}{2}=\frac{\eta_{j}}{2},$

since $\eta_{j-1}=N^{6+256(j-1)\epsilon^{2}}$, and $N$ is sufficiently large.

This completes the proof of Lemma 6.7

##  7 APSP in Well-Connected Graphs – Proof of Theorem 2.3

The goal of this section is to prove Theorem 2.3. We do so using the following
theorem.

######  Theorem 7.1.

There are large enough constants $c^{\prime},c^{\prime\prime}$, and a
deterministic algorithm, whose input consists of:

  * •

a parameter $0<\epsilon<1/400$;

  * •

a pair $N$, $1\leq j\leq\left\lceil 1/\epsilon\right\rceil$ of integers, such
that $N$ is sufficiently large, so that $\frac{N^{\epsilon^{4}}}{\log N}\geq
2^{128/\epsilon^{6}}$ holds;

  * •

a graph $H$ with $|V(H)|=N^{j}$; and

  * •

a level-$j$ Hierarchical Support Structure for graph $H$, such that graph $H$
is $(\eta_{j},\tilde{d}_{j})$-well-connected with respect to the set $S(H)$ of
vertices defined by the Hierarchical Support Structure.

Further, we assume that graph $H$ undergoes an online sequence of less than
$\Lambda_{j}=N^{j-8-300j\epsilon^{2}}$ edge deletions. The algorithm maintains
a set $S^{\prime}(H)\subseteq S(H)$ of vertices of $H$, called _supported
vertices_ , such that, at the beginning of the algorithm,
$S^{\prime}(H)=S(H)$, and over the course of the algorithm, vertices can leave
$S^{\prime}(H)$ but they may not join it. The algorithm ensures that
$|S^{\prime}(H)|\geq\frac{N^{j}}{16^{j}}$ holds over the course of the
algorithm, and it supports short-path queries between supported vertices:
given a pair $x,y\in S^{\prime}(H)$ of vertices, return a path $P$ connecting
$x$ to $y$ in the current graph $H$, whose length is at most
$d^{*}_{j}=2^{c^{\prime}j/\epsilon^{5}}$, in time $O(|E(P)|)$. The total
update time of the algorithm is bounded by $2c^{\prime\prime}jN^{j+3}\cdot
2^{4c^{\prime}/\epsilon^{6}}+c^{\prime\prime}m\cdot N^{2}\cdot
2^{4c^{\prime}/\epsilon^{6}}$, where $m$ is the number of edges in graph $H$
at the beginning of the algorithm. (If $\Lambda_{j}\leq 1$, then the algorithm
only needs to support short-path queries until the first edge deletion).

It is immediate to verify that Theorem 2.3 follows from Theorem 7.1, by
substituting $j=1/\epsilon$. In the remainder of this section we prove Theorem
7.1. The proof is by induction on $j$.

###  7.1 Base Case: $j\leq 8$

We first consider the base case, where $j\leq 8$. In this case,
$\Lambda_{j}\leq 1$ holds, and so we only need to support short-path queries
until the first edge deletion.

In this case, the level-$j$ Hierarchical Support Structure for graph $H$
defines a set $S(H)$ of vertices, and, from 5.1, $|V(H)\setminus
S(H)|\leq|V(H)|\cdot\frac{4j}{N^{\epsilon^{4}}}$. Since $j\leq\left\lceil
1/\epsilon\right\rceil$, and $N^{\epsilon^{4}}\geq 2^{128/\epsilon^{5}}$ from
the statement of Theorem 7.1, we get that $|S(H)|\geq|V(H)|/2=N^{j}/2$. We set
$S^{\prime}(H)=S(H)$, and this set remains unchanged throughout the algorithm.

Recall that are guaranteed that graph $H$ is $(\eta_{j},\tilde{d}_{j})$-well-
connected with respect to $S(H)$, where
$\tilde{d}_{j}=2^{cj/\epsilon^{4}}\leq\frac{2^{c^{\prime}j/\epsilon^{5}}}{2}=\frac{d^{*}_{j}}{2}$
(if $c^{\prime}>c$), and $\eta_{j}=N^{6+256j\epsilon^{2}}$. In particular, for
every pair $x,y\in S^{\prime}(H)$ of supported vertices, there is a path of
length at most $d^{*}_{j}/2$ connecting $x$ to $y$ in $H$. We let $s\in S(H)$
be an arbitrary vertex, and we construct a BFS tree $\tau$ rooted at vertex
$s$, whose depth is bounded by $d^{*}_{j}/2$. Computing the tree takes time
$O(|E(H)|)$. In order to respond to a short-path query between a pair $x,y$ of
vertices of $H$, we simply compute the unique simple path $P$ connecting $x$
to $y$ in the tree $\tau$, which can be done in time $O(|E(P)|)$. Since the
depth of the tree is bounded by $d^{*}_{j}/2$, the length of the path is at
most $d^{*}_{j}$.

###  7.2 Step: $j>8$

We assume that we are given a graph $H$ with $|V(H)|=N^{j}$, together
level-$j$ hierarchical support structure for graph $H$, whose associated
collection of graphs is ${\mathcal{H}}=\left\\{H_{1},\ldots,H_{r}\right\\}$.
Recall that $r=N-\left\lceil 2N^{1-\epsilon^{4}}\right\rceil$, and we are
guaranteed that graph $H$ is $(\eta_{j},\tilde{d}_{j})$-well-connected with
respect to the set $S(H)=\bigcup_{H_{i}\in{\mathcal{H}}}S(H_{i})$ of vertices.
Additionally, the hierarchical support structure contains an embedding
${\mathcal{P}}$ of the graph $H^{\prime}=\bigcup_{i=1}^{r}H_{i}$ into graph
$H$ via paths of length at most $2^{64/\epsilon^{4}}$, that causes congestion
at most $N^{128\epsilon^{2}}$. For every edge $e\in E(H^{\prime})$, we denote
by $P(e)\in{\mathcal{P}}$ the unique path that serves as the embedding of $e$
in $G$.

Our algorithm will maintain a set $S^{\prime}(H)\subseteq S(H)$ of supported
vertices, where initially $S^{\prime}(H)=S(H)$. While vertices may leave set
$S^{\prime}(H)$ over the course of the algorithm, set $S(H)$ remains
unchanged.

Our algorithm recursively applies the algorithm from Theorem 7.1 to each of
the graphs in ${\mathcal{H}}$. When an edge $e\in E(H)$ is deleted, then for
all $1\leq i\leq r$, for every edge $e^{\prime}\in E(H_{i})$ whose
corresponding embedding path $P(e^{\prime})$ contains $e$, we delete edge
$e^{\prime}$ from graph $H_{i}$. Since the paths in ${\mathcal{P}}$ cause
congestion at most $N^{128\epsilon^{2}}$, the deletion of a single edge from
graph $H$ may trigger the deletion of up to $N^{128\epsilon^{2}}$ edges from
graphs $H_{1},\ldots,H_{r}$ overall. As the result of these edge deletions,
the supported sets of vertices $S^{\prime}(H_{i})$ that the algorithm from
Theorem 7.1 maintains recursively for each of the graphs
$H_{i}\in{\mathcal{H}}$ may need to be updated. Once a graph
$H_{i}\in{\mathcal{H}}$ undergoes $\left\lceil\Lambda_{j-1}\right\rceil$ edge
deletions, we say that it is _destroyed_. Once graph $H_{i}$ is destroyed, the
corresponding set $S^{\prime}(H_{i})$ of vertices is set to $\emptyset$.

Our algorithm maintains a partition of the set ${\mathcal{H}}$ of graphs into
three subsets: set ${\mathcal{H}}^{D}$ of _destroyed graphs_ , set
${\mathcal{H}}^{I}$ of _inactive graphs_ , and set ${\mathcal{H}}^{A}$ of
active graphs. Set ${\mathcal{H}}^{D}$ contains all graphs that have been
destroyed so far. Once a graph joins set ${\mathcal{H}}^{D}$, it remains in
${\mathcal{H}}^{D}$ for the remainder of the algorithm. We define the sets
${\mathcal{H}}^{I}$ and ${\mathcal{H}}^{A}$ of graphs later. We will ensure
that the set ${\mathcal{H}}^{A}$ of active graphs is decremental, and we will
set $S^{\prime}(H)=\bigcup_{H_{i}\in{\mathcal{H}}^{A}}S^{\prime}(H_{i})$
throughout the algorithm. Intuitively, we will maintain, for every active
graph $H_{i}\in{\mathcal{H}}^{A}$, an ES-Tree data structure that is rooted at
the vertices of $S^{\prime}(H_{i})$. We need the following simple observation
bounding the number of graphs in ${\mathcal{H}}^{D}$.

######  Observation 7.2.

Over the course of the algorithm, $|{\mathcal{H}}^{D}|<N/32$ always holds.

###### Proof.

Assume otherwise, and consider the first time $t$ during the algorithm when
$|{\mathcal{H}}^{D}|\geq N/32$ held. Recall that a graph
$H_{i}\in{\mathcal{H}}$ is destroyed once it undergoes
$\left\lceil\Lambda_{j-1}\right\rceil$ edge deletions. Therefore, at least
$\frac{N}{32}\cdot\left\lceil\Lambda_{j-1}\right\rceil$ edges have been
deleted from $\bigcup_{H_{i}\in{\mathcal{H}}}E(H_{i})$ by time $t$. On the
other hand, the deletion of a single edge from $H$ may trigger the deletion of
at most $N^{128\epsilon^{2}}$ edges from graphs $H_{1},\ldots,H_{r}$.
Therefore, the number of edges that have been deleted from $H$ by time $t$ is
at least:

$\frac{N}{32N^{128\epsilon^{2}}}\cdot\left\lceil\Lambda_{j-1}\right\rceil=\frac{N^{1-128\epsilon^{2}}}{32}\cdot\left\lceil
N^{j-9-300(j-1)\epsilon^{2}}\right\rceil>N^{j-8-300j\epsilon^{2}}=\Lambda_{j},$

a contradiction.

Consider now a graph $H_{i}\in{\mathcal{H}}\setminus{\mathcal{H}}^{D}$ at some
time during the algorithm’s execution. For every vertex $s\in
S^{\prime}(H_{i})$, we denote by ${\mathcal{G}}(s)$ the set of all graphs
$H_{i^{\prime}}\in{\mathcal{H}}\setminus{\mathcal{H}}^{D}$, such that
$S^{\prime}(H_{i^{\prime}})\cap B_{H}(s,d^{*}_{j}/32)\neq\emptyset$. In other
words, set ${\mathcal{G}}(s)$ contains all graphs $H_{i^{\prime}}$ that have
not been destroyed yet, such that some vertex in the current set
$S^{\prime}(H_{i^{\prime}})$ of supported vertices is sufficiently close to
$s$ in the current graph $H$. Recall that the set $S^{\prime}(H_{i})$ of
vertices is decremental. The following observation will be useful for us.

######  Observation 7.3.

Consider any time $t$ during the algorithm’s execution. Let
$H_{i}\in{\mathcal{H}}\setminus{\mathcal{H}}^{D}$ be a graph that has not been
destroyed by time $t$, and let $s\in S^{\prime}(H_{i})$ be any vertex in the
current set of supported vertices for $H_{i}$. Then, since the beginning of
the algorithm and until time $t$, the collection ${\mathcal{G}}(s)$ of graphs
has been decremental: that is, graphs may have left it, but no graph may have
joined it since the beginning of the algorithm.

###### Proof.

Assume for contradiction that $H_{i^{\prime}}\in{\mathcal{H}}$ is some graph
that did not belong to set ${\mathcal{G}}(s)$ at time $t^{\prime}$, but
belongs to set ${\mathcal{G}}(s)$ at time $t^{\prime\prime}$, where
$t^{\prime}<t^{\prime\prime}\leq t$.

From the definition, at time $t^{\prime\prime}$,
$H_{i^{\prime}}\in{\mathcal{H}}\setminus{\mathcal{H}}^{D}$ held. Since graphs
may leave set ${\mathcal{H}}\setminus{\mathcal{H}}^{D}$ (when they are
destroyed) but they may never join ${\mathcal{H}}\setminus{\mathcal{H}}^{D}$
over the course of the algorithm, we get that at time $t^{\prime}$,
$H_{i^{\prime}}\in{\mathcal{H}}\setminus{\mathcal{H}}^{D}$ held. Furthermore,
from the definition, at time $t^{\prime\prime}$, some vertex $x\in
S^{\prime}(H_{i^{\prime}})$ belonged to $B_{H}(s,d^{*}_{j}/32)$. Since set
$S^{\prime}(H_{i^{\prime}})$ of vertices is decremental, $x\in
S^{\prime}(H_{i^{\prime}})$ held at time $t^{\prime}$. Since distances in
graph $H$ may only grow over time, $x\in B_{H}(s,d^{*}_{j}/32)$ held at time
$t^{\prime}$. Therefore, $S^{\prime}(H_{i^{\prime}})\cap
B_{H}(s,d^{*}_{j}/32)\neq\emptyset$ must have held at time $t^{\prime}$, and
graph $H_{i^{\prime}}$ must have belonged to ${\mathcal{G}}(s)$ at time
$t^{\prime}$, a contradiction.

Throughout the algorithm, the set ${\mathcal{H}}^{I}$ of inactive graphs will
only contain graphs $H_{i}\in{\mathcal{H}}$ that have not been destroyed yet,
for which the following property holds:

  1. P1.

For every vertex $s\in S^{\prime}(H_{i})$, $|{\mathcal{G}}(s)|\leq 7N/8$.

We note that it is possible that some graph
$H_{i}\in{\mathcal{H}}\setminus{\mathcal{H}}^{D}$ has Property P1 but is not
added to ${\mathcal{H}}^{I}$.

The following observation shows that once property P1 holds for some graph
$H_{i}$, it will continue to hold until the algorithm terminates or the graph
is destroyed.

######  Observation 7.4.

Let $H_{i}\in{\mathcal{H}}$ be any graph, and assume that Property P1 holds
for $H_{i}$ at some time $t$ during the algorithm’s execution. Then Property
P1 holds for $H_{i}$ from time $t$ and until the algorithm terminates or until
$H_{i}$ is destroyed.

###### Proof.

Assume that Property P1 holds for graph $H_{i}\in{\mathcal{H}}$ at some time
$t$ during the algorithm’s execution, and consider some time $t^{\prime}>t$
during the algorithm’s execution. We assume that graph $H_{i}$ is not
destroyed at time $t^{\prime}$, and prove that Property P1 continues to hold
for $H_{i}$ at time $t^{\prime}$. Indeed, consider any vertex $s$ that lies in
set $S^{\prime}(H_{i})$ at time $t^{\prime}$. Since set $S^{\prime}(H_{i})$ is
decremental, vertex $s$ lied in $S^{\prime}(H_{i})$ at time $t$. Since
Property P1 held for graph $H_{i}$ at time $t$, $|{\mathcal{G}}(s)|\leq 7N/8$
held at time $t$. From 7.3, set ${\mathcal{G}}(s)$ is decremental, so
$|{\mathcal{G}}(s)|$ may not grow between time $t$ and time $t^{\prime}$.
Therefore, $|{\mathcal{G}}(s)|\leq 7N/8$ holds at time $t^{\prime}$. We
conclude that Property P1 continues to hold for $H_{i}$ at time $t^{\prime}$.

To summarize, over the course of the algorithm, we maintain a partition of the
collection ${\mathcal{H}}$ of graphs into three subsets: the set
${\mathcal{H}}^{D}$ of destroyed graphs; the set ${\mathcal{H}}^{I}$ of
inactive graphs; and the set ${\mathcal{H}}^{A}$ of all remaining graphs, that
are called _active graphs_. We ensure that every graph in ${\mathcal{H}}^{I}$
has Property P1. We also ensure that the set ${\mathcal{H}}^{A}$ of active
graphs is decremental – graphs may leave it but they may not join it over
time. The following claim bounds the cardinality of the collection
${\mathcal{H}}^{I}$ of graphs.

######  Claim 7.5.

Over the course of the algorithm, $|{\mathcal{H}}^{I}|\leq N/32$ always holds.

###### Proof.

Assume otherwise, and consider the first time $t$ during the algorithm when
$|{\mathcal{H}}^{I}|>N/32$ held. We will construct two large sets
$T_{1},T_{2}$ of vertices, so that the distance between the vertices of
$T_{1}$ and the vertices of $T_{2}$ is large in the current graph $H$. We will
then reach a contradiction by using the facts that, at the beginning of the
algorithm, graph $H$ was well-connected with respect to $S(H)$, and that the
number of edges that were deleted from $H$ is relatively small.

Recall that $|{\mathcal{H}}|=r=N-\left\lceil
2N^{1-\epsilon^{4}}\right\rceil\geq 63N/64$, since $N^{\epsilon^{4}}\geq
2^{128/\epsilon^{5}}$ from the statement of Theorem 7.1. Additionally, from
7.2, $|{\mathcal{H}}^{D}|<N/32$ holds at time $t$. Therefore, at time $t$,
$|{\mathcal{H}}\setminus{\mathcal{H}}^{D}|\geq\frac{63N}{64}-\frac{N}{32}\geq\frac{61N}{64}$.
Let $\tilde{\mathcal{H}}\subseteq{\mathcal{H}}\setminus{\mathcal{H}}^{D}$ be a
collection of graphs that is obtained as follows. We start with
$\tilde{\mathcal{H}}={\mathcal{H}}\setminus{\mathcal{H}}^{D}$. We then
consider the graphs of $\tilde{\mathcal{H}}$ one by one, starting with the
graphs of ${\mathcal{H}}^{A}$. If, when graph $H_{i}$ is considered,
$|\tilde{\mathcal{H}}|>\left\lceil\frac{61N}{64}\right\rceil$ holds, then we
discard $H_{i}$ from set $\tilde{\mathcal{H}}$. Otherwise, we terminate the
algorithm with the final collection $\tilde{\mathcal{H}}$ of graphs, whose
cardinality must be $\left\lceil\frac{61N}{64}\right\rceil$. Notice that, if
any graph of ${\mathcal{H}}^{A}$ lies in $\tilde{\mathcal{H}}$, then
${\mathcal{H}}^{I}\subseteq\tilde{\mathcal{H}}$. Recall that, from the
induction hypothesis, for every graph
$H_{i}\in{\mathcal{H}}\setminus{\mathcal{H}}^{D}$,
$|S^{\prime}(H_{i})|\geq\frac{N^{j-1}}{16^{j-1}}$ holds throughout the
algorithm. We construct a set $T$ of vertices as follows. For every graph
$H_{i}\in\tilde{\mathcal{H}}$, we let $S^{\prime\prime}(H_{i})$ be an
arbitrary collection of $\left\lceil\frac{N^{j-1}}{16^{j-1}}\right\rceil$
vertices that lie in set $S^{\prime}(H_{i})$ at time $t$. We then let
$T=\bigcup_{H_{i}\in\tilde{\mathcal{H}}}S^{\prime\prime}(H_{i})$. Clearly:

$|T|=\left\lceil\frac{61N}{64}\right\rceil\cdot\left\lceil\frac{N^{j-1}}{16^{j-1}}\right\rceil.$

Intuitively, we would like to apply Procedure $\mathsf{ProcSeparate}$ from
Lemma 3.10 to graph $H$, set $T$ of terminals, and distance parameters
$\Delta=64/\epsilon^{2}$ and $d=\frac{d^{*}_{j}}{64\Delta}$, in order to
compute two large subsets $T_{1},T_{2}\subseteq T$ of vertices with $\mbox{\sf
dist}_{H}(T_{1},T_{2})\geq d$. However, the procedure may instead return a
single vertex $s\in T$, for which the ball $B_{H}(s,d^{*}_{j}/64)$ contains
many vertices of $T$. In the next observation we show that this is impossible,
that is, for every vertex $s\in T$, $|B_{H}(s,d^{*}_{j}/64)\cap T|$ is
sufficiently small.

######  Observation 7.6.

At time $t$, for every vertex $s\in T$, $|B_{H}(s,d^{*}_{j}/64)\cap
T|<|T|\cdot\left(1-\frac{1}{256}\right)$ holds.

###### Proof.

Consider some vertex $s\in T$, and denote $B=B_{H}(s,d^{*}_{j}/64)$. Let
$T^{\prime}=\bigcup_{H_{i}\in{\mathcal{H}}^{I}\cap\tilde{\mathcal{H}}}S^{\prime\prime}(H_{i})$.
Assume first that $B$ does not contain any vertex of $T^{\prime}$. Notice that
in this case, at least one graph of ${\mathcal{H}}^{A}$ lies in
$\tilde{\mathcal{H}}$, and so ${\mathcal{H}}^{I}\subseteq\tilde{\mathcal{H}}$.
Since we have assumed that $|{\mathcal{H}}^{I}|>\frac{N}{32}$, we get that:

$|\tilde{\mathcal{H}}\setminus{\mathcal{H}}^{I}|\leq|\tilde{\mathcal{H}}|-|{\mathcal{H}}^{I}|\leq\left\lceil\frac{61N}{64}\right\rceil-\frac{N}{32}\leq\left\lceil\frac{61N}{64}\right\rceil\cdot\left(1-\frac{1}{61}\right)\leq\left\lceil\frac{61N}{64}\right\rceil\cdot\left(1-\frac{1}{256}\right).$

Therefore:

$|B\cap
T|\leq|T|-|T^{\prime}|\leq|\tilde{\mathcal{H}}\setminus{\mathcal{H}}^{I}|\cdot\left\lceil\frac{N^{j-1}}{16^{j-1}}\right\rceil\leq\left\lceil\frac{61N}{64}\right\rceil\cdot\left(1-\frac{1}{256}\right)\cdot\left\lceil\frac{N^{j-1}}{16^{j-1}}\right\rceil\leq|T|\cdot\left(1-\frac{1}{256}\right).$

Assume now that $B$ contains at least one vertex of $T^{\prime}$, and let
$s^{\prime}$ be any such vertex. Note that $B=B_{H}(s,d^{*}_{j}/64)\subseteq
B_{H}(s^{\prime},d^{*}_{j}/32)$. Observe that $s^{\prime}$ must lie in the
current set $S^{\prime}(H_{i})$ of supported vertices of some graph $H_{i}$
that currently lies in ${\mathcal{H}}^{I}$. From Property P1,
$|{\mathcal{G}}(s^{\prime})|\leq\frac{7N}{8}$. Let
${\mathcal{G}}^{\prime}(s^{\prime})={\mathcal{H}}\setminus{\mathcal{G}}(s^{\prime})$,
so $|{\mathcal{G}}^{\prime}(s^{\prime})|\geq\frac{N}{8}$.

From our definitions, for every graph
$H_{i^{\prime}}\in{\mathcal{G}}^{\prime}(s^{\prime})$,
$S^{\prime}(H_{i^{\prime}})\cap B_{H}(s^{\prime},d^{*}_{j}/32)=\emptyset$, and
therefore, $S^{\prime}(H_{i^{\prime}})\cap B=\emptyset$.

Let
$\tilde{\mathcal{H}}^{\prime}=\tilde{\mathcal{H}}\cap{\mathcal{G}}^{\prime}(s^{\prime})$.
On the one hand, since
$|\tilde{\mathcal{H}}|=\left\lceil\frac{61N}{64}\right\rceil$, and
$|{\mathcal{G}}^{\prime}(s^{\prime})|\geq\frac{N}{8}$, while
$|{\mathcal{H}}|=N$, we get that
$|\tilde{\mathcal{H}}^{\prime}|\geq\frac{5N}{64}\geq\left\lceil\frac{61N}{64}\right\rceil\cdot\frac{1}{256}$.
On the other hand, the vertices of
$\bigcup_{H_{i}\in\tilde{\mathcal{H}}^{\prime}}S^{\prime\prime}(H_{i})$ may
not lie in set $B$. Therefore:

$|B\cap
T|\leq\left(|\tilde{\mathcal{H}}|-|\tilde{\mathcal{H}}^{\prime}|\right)\cdot\left\lceil\frac{N^{j-1}}{16^{j-1}}\right\rceil\leq\left\lceil\frac{61N}{64}\right\rceil\cdot\left(1-\frac{1}{256}\right)\cdot\left\lceil\frac{N^{j-1}}{16^{j-1}}\right\rceil\leq|T|\cdot\left(1-\frac{1}{256}\right).$

We apply Algorithm $\mathsf{ProcSeparate}$ from Lemma 3.10 to graph $H$, set
$T$ of terminals, distance parameters $\Delta=64/\epsilon^{2}$, and
$d=\frac{d^{*}_{j}}{64\Delta}$, and parameter
$\alpha=\left(1-\frac{1}{256}\right)$. From 7.6, the algorithm may not return
a vertex $s\in T$ with $|B_{H}(s,\Delta\cdot d)\cap
T|=|B_{H}(s,d^{*}_{j}/64)\cap T|>\alpha\cdot|T|$. Therefore, it must compute
two subsets $T_{1},T_{2}$ of vertices with $|T_{1}|=|T_{2}|$, such that
$|T_{1}|\geq\frac{|T|^{1-64/\Delta}}{256}$, and for every pair $s\in
T_{1},s^{\prime}\in T_{2}$ of terminals, $\mbox{\sf
dist}_{H}(s,s^{\prime})\geq d$. We will now exploit the facts that graph $H$
was well-connected with respect to set $S(H)$ of vertices at the beginning of
the algorithm, and that relatively few edges were deleted from $H$, in order
to reach a contradiction.

Observe first that:

$|T_{1}|\geq\frac{|T|^{1-\epsilon^{2}}}{256}\geq\frac{1}{256}\cdot\left(\frac{61\cdot
N^{j}}{4\cdot
16^{j}}\right)^{1-\epsilon^{2}}\geq\frac{N^{j(1-\epsilon^{2})}}{1024\cdot
16^{j}}.$

On the other hand:

$d=\frac{d^{*}_{j}}{64\Delta}=\frac{2^{c^{\prime}j/\epsilon^{5}}\cdot\epsilon^{2}}{2^{12}}>2^{cj/\epsilon^{4}}=\tilde{d}_{j}.$

Let $H^{(0)}$ denote the graph $H$ at the beginning of the algorithm, and let
$H^{(t)}$ denote graph $H$ at time $t$. Recall that, at the beginning of the
algorithm, graph $H^{(0)}$ was $(\eta_{j},\tilde{d}_{j})$-well-connected with
respect to the set $S(H)=\bigcup_{H_{i}\in{\mathcal{H}}}S(H_{i})$ of vertices.
Since the sets $S^{\prime}(H_{i})$ of vertices for graphs
$H_{i}\in{\mathcal{H}}$ are decremental, and since
$S^{\prime}(H_{i})=S(H_{i})$ at the beginning of the algorithm for each such
graph, we get that $T\subseteq S(H)$ held at the beginning of the algorithm.
Therefore, there was a collection ${\mathcal{P}}(T_{1},T_{2})$ of paths in
graph $H^{(0)}$, routing every vertex of $T_{1}$ to a distinct vertex of
$T_{2}$, such that the paths in ${\mathcal{P}}(T_{1},T_{2})$ cause congestion
at most $\eta_{j}=N^{6+256j\epsilon^{2}}$, and the length of every path is at
most $\tilde{d}_{j}$.

Let $E^{\prime}$ be the set of edges that have been deleted from graph $H$ by
time $t$. Note that, in graph $H^{(t)}$, no path of length at most
$\tilde{d}_{j}$ connecting a vertex of $T_{1}$ to a vertex of $T_{2}$ exists.
Therefore, set $E^{\prime}$ must contain at least one edge from every path in
${\mathcal{P}}(T_{1},T_{2})$. We conclude that:

$|E^{\prime}|\geq\frac{|T_{1}|}{\eta_{j}}\geq\frac{N^{j(1-\epsilon^{2})}}{1024\cdot
16^{j}\cdot N^{6+256j\epsilon^{2}}}=\frac{N^{j-257j\epsilon^{2}-6}}{1024\cdot
16^{j}}>N^{j-8-257j\epsilon^{2}}\geq\Lambda_{j},$

since $j\leq\left\lceil 1/\epsilon\right\rceil$, $\epsilon\leq 1/400$, and
$N^{\epsilon}>2^{8/\epsilon}$ from the statement of Theorem 7.1. This is a
contradiction, since fewer than $\Lambda_{j}$ edges may be deleted from $H$.

From 7.2 and 7.5, throughout the algorithm,
$|{\mathcal{H}}^{I}|+|{\mathcal{H}}^{D}|\leq N/16$ holds. Since
$|{\mathcal{H}}|=r=N-\left\lceil 2N^{1-\epsilon^{4}}\right\rceil\geq 63N/64$,
we get that, throughout the algorithm:

$|{\mathcal{H}}^{A}|\geq|{\mathcal{H}}|-|{\mathcal{H}}^{I}|-|{\mathcal{H}}^{D}|\geq\frac{63N}{64}-\frac{N}{16}\geq\frac{59N}{64}.$
(10)

The set $S^{\prime}(H)$ that we maintain throughout the algorithm is defined
to be: $S^{\prime}(H)=\bigcup_{H_{i}\in{\mathcal{H}}^{A}}S^{\prime}(H_{i})$.
Since, for every graph $H_{i}$, set $S^{\prime}(H_{i})$ of vertices is
decremental, and since the collection ${\mathcal{H}}^{A}$ of graphs is
decremental, we get that the set $S^{\prime}(H)$ of vertices is decremental as
well. It is also easy to see that
$S^{\prime}(H)=S(H)=\bigcup_{H_{i}\in{\mathcal{H}}}S(H)$ hods at the beginning
of the algorithm. Since, from Inequality 10,
$|{\mathcal{H}}^{A}|\geq\frac{59N}{64}$ holds throughout the algorithm, and
since, from the induction hypothesis, for every graph
$H_{i}\in{\mathcal{H}}^{A}$, $|S^{\prime}(H_{i})|\geq\frac{N^{j-1}}{16^{j-1}}$
holds, we get that, throughout the algorithm:

$|S^{\prime}(H)|\geq|{\mathcal{H}}^{A}|\cdot\frac{N^{j-1}}{16^{j-1}}\geq\frac{59N}{64}\cdot\frac{N^{j-1}}{16^{j-1}}\geq\frac{N^{j}}{16^{j}},$

as required.

####  7.2.1 Data Structures and Initialization

Consider a graph $H_{i}\in{\mathcal{H}}$. Note that, as part of the level-$j$
hierarchical support structure for $H$, we are given a level-$(j-1)$
hierarchical support structure for $H_{i}$, and we are guaranteed that $H_{i}$
is $(\eta_{j-1},\tilde{d}_{j-1})$-well-connected with respect to $S(H_{i})$.
Therefore, from the induction hypothesis, we can apply the algorithm from
Theorem 7.1 with parameter $(j-1)$ to graph $H_{i}$, and the corresponding
level-$(j-1)$ hierarchical support structure. Parameters $N$ and $\epsilon$
remain unchanged. We denote the corresponding data structure by
${\mathcal{D}}_{j-1}(H_{i})$.

As part of the initialization procedure, for every graph
$H_{i}\in{\mathcal{H}}$, we initialize the corresponding data structure
${\mathcal{D}}_{j-1}(H_{i})$.

Our algorithm also maintains, for every edge $e\in E(H)$, a list $L(e)$ of
edges $e^{\prime}\in\bigcup_{H_{i}\in{\mathcal{H}}}E(H_{i})$, such that the
path $P(e^{\prime})$, contains $e$. Here, $P(e^{\prime})$ is the path in the
embedding ${\mathcal{P}}$ of $\bigcup_{H\in{\mathcal{H}}}H^{\prime}$ into $H$,
that serves as the embedding of edge $e^{\prime}$. Together with this list, we
maintain a pointer from $e$ to each such edge $e^{\prime}$ in its
corresponding graph $H_{i}$, and a pointer in the opposite direction. We
initialize the lists $L(e)$ for edges $e\in E(H)$ at the beginning of the
algorithm.

We also initialize ${\mathcal{H}}^{A}={\mathcal{H}}$,
${\mathcal{H}}^{I}={\mathcal{H}}^{D}=\emptyset$, and $S^{\prime}(H)=S(H)$.

Lastly, for every graph $H_{i}\in{\mathcal{H}}$, we initialize an ES-Tree data
structure, whose corresponding tree is denoted by $\tau_{i}$, that,
intuitively, is rooted at the set $S^{\prime}(H_{i})$ of vertices.
Specifically, in order to construct data structure $\tau_{i}$, we let
$\tilde{G}_{i}$ be a graph that is obtained from $H$, after we add a source
vertex $s_{i}$ to it, which connects to every vertex in $S^{\prime}(H_{i})$
with an edge. We then let $\tau_{i}$ be an ES-Tree data structure in graph
$\tilde{G}_{i}$, rooted at vertex $s_{i}$, with depth bound $d^{*}_{j}/8+1$.
When an edge is deleted from $H$, we will also delete it from $\tilde{G}_{i}$,
and update the ES-Tree data structure $\tau_{i}$ accordingly. When a vertex
$s$ is deleted from set $S^{\prime}(H_{i})$, we will delete the edge
$(s_{i},s)$ from graph $\tilde{G}_{i}$, and update $\tau_{i}$ accordingly.

We maintain, for every pair of graphs $H_{i}\in{\mathcal{H}}^{A}$ and
$H_{i^{\prime}}\in{\mathcal{H}}\setminus{\mathcal{H}}^{D}$, a counter
$n_{i,i^{\prime}}$, that counts the number of vertices of
$S^{\prime}(H_{i^{\prime}})$ that lie at distance at most $d^{*}_{j}/32+1$
from $s_{i}$ in tree $\tau_{i}$. Note that, if $n_{i,i^{\prime}}=0$, then for
every vertex $s\in S^{\prime}(H_{i})$, $S^{\prime}(H_{i^{\prime}})\cap
B_{H}(s,d^{*}_{j}/32)=\emptyset$. In other words,
$H_{i^{\prime}}\not\in{\mathcal{G}}(s)$ holds for all $s\in
S^{\prime}(H_{i})$. We also maintain a counter $\tilde{n}_{i}$, whose value is
the number of graphs
$H_{i^{\prime}}\in{\mathcal{H}}\setminus{\mathcal{H}}^{D}$, with
$n_{i,i^{\prime}}>0$. We can initialize the values $n_{i,i^{\prime}}$ for
every pair $H_{i},H_{i^{\prime}}\in{\mathcal{H}}$ of graphs, and the counters
in $\left\\{\tilde{n}_{i}\right\\}_{H_{i}\in{\mathcal{H}}}$ at the beginning
of the algorithm. The time that is required in order to do so is subsumed by
the time required to initialize the ES-Tree data structures. We need the
following simple observation.

######  Observation 7.7.

Let $H_{i}\in{\mathcal{H}}$ be a graph. Assume that at some time $t$ in the
algorithm’s execution, $H_{i}\not\in{\mathcal{H}}^{D}$ holds, and
$\tilde{n}_{i}\leq 7N/8$. Then graph $H_{i}$ has Property P1 at time $t$.

###### Proof.

Assume otherwise. Then at time $t$, there is some vertex $s\in
S^{\prime}(H_{i})$ with $|{\mathcal{G}}(s)|>7N/8$. If $H_{i^{\prime}}$ is a
graph that lies in ${\mathcal{G}}(s)$ at time $t$, then at least one vertex of
$S^{\prime}(H_{i^{\prime}})$ must lie in $B_{H}(s,d^{*}_{j}/32)$ at time $t$,
and so $n_{i,i^{\prime}}>0$ must hold. But then $\tilde{n}_{i}>7N/8$ must hold
at time $t$, a contradiction.

Throughout the algorithm’s execution, whenever, for some graph
$H_{i}\in{\mathcal{H}}^{A}$, the value of counter $\tilde{n}_{i}$ becomes at
most $7N/8$, we move graph $H_{i}$ from ${\mathcal{H}}^{A}$ to
${\mathcal{H}}^{I}$. Lastly, we need the following simple observation.

######  Observation 7.8.

Let $H_{i},H_{i^{\prime}}$ be any pair of graphs that lie in set
${\mathcal{H}}^{A}$ at some time $t$ during the algorithm’s execution. Let $s$
be any vertex that lies in $S^{\prime}(H_{i})$ at time $t$, and let
$s^{\prime}$ be any vertex that lies in $S^{\prime}(H_{i^{\prime}})$ at time
$t$. Then $\mbox{\sf dist}_{H}(s,s^{\prime})\leq d^{*}_{j}/8$ at time $t$.

###### Proof.

Let ${\mathcal{G}}_{i}$ be the set of all graphs
$H_{i^{\prime\prime}}\in{\mathcal{H}}\setminus{\mathcal{H}}^{D}$ with
$n_{i,i^{\prime\prime}}>0$ at time $t$. Since $H_{i}\in{\mathcal{H}}^{A}$ at
time $t$, $|{\mathcal{G}}_{i}|\geq 7N/8$ must hold. Similarly, let
${\mathcal{G}}_{i^{\prime}}$ be the set of all graphs
$H_{i^{\prime\prime}}\in{\mathcal{H}}\setminus{\mathcal{H}}^{D}$ with
$n_{i^{\prime},i^{\prime\prime}}>0$ at time $t$. As before,
$|{\mathcal{G}}_{i^{\prime}}|\geq 7N/8$. Therefore, there is some graph
$H_{i^{\prime\prime}}\in{\mathcal{G}}_{i}\cap{\mathcal{G}}_{i^{\prime}}$.

In the remainder of this proof, whenever we refer to vertex sets
$S^{\prime}(H_{i}),S^{\prime}(H_{i^{\prime}}),S^{\prime}(H_{i^{\prime\prime}})$,
or to graphs $H_{i},H_{i^{\prime}},H_{i^{\prime\prime}},H$, we mean the
corresponding sets of vertices or the corresponding graphs at time $t$.

Since, at time $t$, $n_{i,i^{\prime\prime}}>0$, there is some vertex $x\in
S^{\prime}(H_{i^{\prime\prime}})$, such that the distance from $s_{i}$ to $x$
in tree $\tau_{i}$ is at most $d^{*}_{j}/32+1$. Therefore, there is some
vertex $x^{\prime}\in S^{\prime}(H_{i})$, such that $\mbox{\sf
dist}_{H}(x,x^{\prime})\leq d^{*}_{j}/32$. Let $Q$ be a path of length at most
$d^{*}_{j}/32$ connecting $x$ to $x^{\prime}$ in $H$. From a similar
reasoning, there is a pair of vertices $y\in S^{\prime}(H_{i^{\prime\prime}})$
and $y^{\prime}\in S^{\prime}(H_{i^{\prime}})$, such that $\mbox{\sf
dist}_{H}(y,y^{\prime})\leq d^{*}_{j}/32$. Let $Q^{\prime}$ be a path of
length at most $d^{*}_{j}/32$ connecting $y$ to $y^{\prime}$ in $H$.

From the induction hypothesis, there is a path $P_{1}$ of length at most
$d^{*}_{j-1}$ connecting $s$ to $x^{\prime}$ in graph $H_{i}$. Recall that we
are given an embedding ${\mathcal{P}}$ of the edges of
$\bigcup_{H_{a}\in{\mathcal{H}}}E(H_{a})$ into $H$, where the length of every
path in ${\mathcal{P}}$ is at most $2^{64/\epsilon^{4}}$. From 3.1, there is a
path $P_{1}^{\prime}$ in graph $H$, connecting $s$ to $x^{\prime}$, whose
length is at most $2^{64/\epsilon^{4}}\cdot d^{*}_{j-1}$.

Using similar reasonings, there is a path $P_{2}^{\prime}$ in graph $H$
connecting $x$ to $y$ of length at most $2^{64/\epsilon^{4}}\cdot
d^{*}_{j-1}$, and a path $P_{3}^{\prime}$ in graph $H$ connecting $y^{\prime}$
to $s^{\prime}$, of length at most $2^{64/\epsilon^{4}}\cdot d^{*}_{j-1}$. By
concatenating the paths
$P_{1}^{\prime},Q,P_{2}^{\prime},Q^{\prime},P_{3}^{\prime}$, we obtain a path
in graph $H$, connecting $s$ to $s^{\prime}$, whose length is bounded by:

$\frac{d^{*}_{j}}{16}+3\cdot 2^{64/\epsilon^{4}}\cdot
d^{*}_{j-1}=\frac{d^{*}_{j}}{16}+3\cdot 2^{64/\epsilon^{4}}\cdot
2^{c^{\prime}(j-1)/\epsilon^{5}}\leq\frac{d^{*}_{j}}{16}+\frac{2^{c^{\prime}j/\epsilon^{5}}}{16}\leq\frac{d^{*}_{j}}{8}$

(since $d^{*}_{j}=2^{c^{\prime}j/\epsilon^{5}}$).

Next, we describe an algorithm for updating the data structures after each
edge deletion, followed by the analysis of the total update time of the
algorithm. We then conclude with an algorithm for responding to queries.

####  7.2.2 Maintaining the Data Structures

For each graph $H_{i}\in{\mathcal{H}}$, our algorithm will only maintain ES-
Tree data structure $\tau_{i}$, together with the corresponding counters
$\tilde{n}_{i}$ and $n_{i,i^{\prime}}$ for all
$H_{i^{\prime}}\in{\mathcal{H}}\setminus{\mathcal{H}}^{D}$, as long as graph
$H_{i}$ lies in ${\mathcal{H}}^{A}$. Once graph $H_{i}$ is removed from
${\mathcal{H}}^{A}$, we no longer maintain these data structures.

We now describe an algorithm for updating the data structures following the
deletion of an edge $e$ from graph $H$. The algorithm, called
$\operatorname{DeleteEdge}(e)$, is straightforward and it is summarized in
Figure 1.

When an edge $e$ is deleted from graph $H$, we consider every edge
$e^{\prime}\in L(e)$ (that is, edges
$e^{\prime}\in\bigcup_{H_{i}\in{\mathcal{H}}}E(H_{i})$, whose embedding path
$P(e^{\prime})$ contains edge $e$). We assume that $e^{\prime}\in E(H_{i})$,
and that $H_{i}\in{\mathcal{H}}\setminus{\mathcal{H}}^{D}$ (if
$H_{i}\in{\mathcal{H}}^{D}$, no further action is required for processing edge
$e^{\prime}$). We then delete edge $e^{\prime}$ from graph $H_{i}$ and update
the corresponding data structure ${\mathcal{D}}_{j-1}(H_{i})$. As a result, we
obtain a set $X_{i}$ (that may be empty) of vertices that have been deleted
from $S^{\prime}(H_{i})$. We also update lists $L(e^{\prime\prime})$ of edges
$e^{\prime\prime}\in E(H)$ that contain $e^{\prime}$, to remove $e^{\prime}$
from these lists.

If the number of edges deleted so far from $H_{i}$ reaches at least
$\left\lceil\Lambda_{j-1}\right\rceil$, then graph $H_{i}$ is destroyed. We
add the graph to set ${\mathcal{H}}^{D}$, and we update all counters
$n_{i^{\prime},i}$ and $\tilde{n}_{i^{\prime}}$ for graphs
$H_{i^{\prime}}\in{\mathcal{H}}^{A}$ as needed. Otherwise, we process every
vertex $s\in X_{i}$ one by one. If $H_{i}\in{\mathcal{H}}^{A}$, then we delete
edge $(s_{i},s)$ from graph $\tilde{G}_{i}$, and the corresponding ES-Tree
data structure $\tau_{i}$. As the result, some distances in tree $\tau_{i}$
may have increased, and we need to update all counters in
$\left\\{n_{i,i^{\prime}}\right\\}_{H_{i^{\prime}}\in{\mathcal{H}}\setminus{\mathcal{H}}^{D}}$,
as well as counter $\tilde{n}_{i}$ accordingly. Additionally, for every graph
$H_{i^{\prime}}\in{\mathcal{H}}^{A}$, if the distance from $s_{i}$ to $s$ in
tree $\tau_{i}$ was bounded by $d^{*}_{j}/32+1$, then we need to decrease
$n_{i^{\prime},i}$ by $1$ (as vertex $s$ no longer lies in
$S^{\prime}(H_{i})$), and if needed, we need to update counter
$\tilde{n}_{i^{\prime}}$.

Once we finish processing every edge $e^{\prime}\in L(e)$, we also need to
delete edge $e$ from every graph $\tilde{G}_{i^{\prime}}$, where
$H_{i^{\prime}}\in{\mathcal{H}}^{A}$, and the corresponding ES-Tree data
structure $\tau_{i^{\prime}}$. As before, this may increase some distances in
tree $\tau_{i^{\prime}}$, and we may need to update counters
$\left\\{n_{i^{\prime},i^{\prime\prime}}\right\\}_{H_{i^{\prime\prime}}\in{\mathcal{H}}\setminus{\mathcal{H}}^{D}},\tilde{n}_{i^{\prime}}$
accordingly. Lastly, we consider every graph
$H_{i^{\prime}}\in{\mathcal{H}}^{A}$ in turn. If $\tilde{n}_{i^{\prime}}\leq
7N/8$ holds for any such graph, then we move it from ${\mathcal{H}}^{A}$ to
${\mathcal{H}}^{I}$.

Algorithm $\operatorname{DeleteEdge}(e)$ 1. For every edge $e^{\prime}\in
L(e)$, such that the graph $H_{i}\in{\mathcal{H}}$ containing $e^{\prime}$
lies in ${\mathcal{H}}\setminus{\mathcal{H}}^{D}$ do: (a) Delete $e^{\prime}$
from $H_{i}$ and update the corresponding data structure
${\mathcal{D}}_{j-1}(H_{i})$. Let $X_{i}$ be the set of vertices that were
deleted from $S^{\prime}(H_{i})$ as the result of this update. (b) For every
edge $e^{\prime\prime}\in E(H)$ with $e^{\prime}\in L(e^{\prime\prime})$,
delete $e^{\prime}$ from $L(e^{\prime\prime})$. (c) If the number of edges
deleted so far from $H_{i}$ becomes at least
$\left\lceil\Lambda_{j-1}\right\rceil$: i. Add graph $H_{i}$ to
${\mathcal{H}}^{D}$ and remove it from the set ${\mathcal{H}}^{A}$ or
${\mathcal{H}}^{I}$ to which it belonged. ii. For every graph
$H_{i^{\prime}}\in{\mathcal{H}}^{A}$, if $n_{i^{\prime},i}>0$, set
$n_{i^{\prime},i}$ to $0$ and decrease $\tilde{n}_{i^{\prime}}$ by $1$. (d)
Otherwise: for every vertex $s\in X_{i}$ do: i. If
$H_{i}\in{\mathcal{H}}^{A}$, delete edge $(s_{i},s)$ from graph
$\tilde{G}_{i}$ and update the ES-Tree $\tau_{i}$, together with counters
$\left\\{n_{i,i^{\prime}}\right\\}_{H_{i^{\prime}}\in{\mathcal{H}}\setminus{\mathcal{H}}^{D}},\tilde{n}_{i}$
accordingly. ii. For every graph $H_{i^{\prime}}\in{\mathcal{H}}^{A}$, if
$\mbox{\sf dist}_{\tau_{i^{\prime}}}(s_{i^{\prime}},s)\leq d^{*}_{j}/32+1$,
decrease $n_{i^{\prime},i}$ by $1$. If $n_{i^{\prime},i}$ decreases from $1$
to $0$, decrease $\tilde{n}_{i^{\prime}}$ by $1$. 2. For every graph
$H_{i^{\prime}}\in{\mathcal{H}}^{A}$, delete edge $e$ from graph
$\tilde{G}_{i^{\prime}}$, and update the ES-Tree $\tau_{i^{\prime}}$, together
with counters
$\left\\{n_{i^{\prime},i^{\prime\prime}}\right\\}_{H_{i^{\prime\prime}}\in{\mathcal{H}}\setminus{\mathcal{H}}^{D}},\tilde{n}_{i^{\prime}}$
accordingly. 3. For every graph $H_{i^{\prime}}\in{\mathcal{H}}^{A}$, if
$\tilde{n}_{i^{\prime}}\leq 7N/8$ holds, move $H_{i^{\prime}}$ from
${\mathcal{H}}^{A}$ to ${\mathcal{H}}^{I}$.

Figure 1: Algorithm $\operatorname{DeleteEdge}(e)$

It is easy to verify that the algoritm maintains all data structures
correctly, and, from 7.7, when graph $H_{i}$ is added to ${\mathcal{H}}^{I}$,
Property P1 holds for it. From 7.4, once $H_{i}$ is added to
${\mathcal{H}}^{I}$, Property P1 continues to hold for it until the end of the
algorithm, or until $H_{i}$ is added to ${\mathcal{H}}^{D}$. From the above
discussion, we are guaranteed that, throughout the algorithm,
$|{\mathcal{H}}^{A}|\neq\emptyset$.

####  7.2.3 Analysis of Total Update Time

Let $m$ denote the number of edges in graph $H$ at the beginning of the
algorithm. Recall that every edge $e\in E(H)$ participates in at most
$N^{128\epsilon^{2}}$ paths in ${\mathcal{P}}$. Therefore, the length of the
list $L(e)$ is bounded by $N^{128\epsilon^{2}}$. Every edge of
$\bigcup_{H_{i}\in{\mathcal{H}}}E(H_{i})$ may be added at most once to list
$L(e)$ when the data structure is initialized, and subsequently it may be
deleted at most once from $L(e)$. Therefore, the total time required to
maintain the lists $L(e)$ for all edges $e\in E(H)$ is at most $O(m\cdot
N^{128\epsilon^{2}})$.

Consider now some graph $H_{i}\in{\mathcal{H}}$, and denote by $m_{i}$ the
number of edges in $H_{i}$ at the beginning of the algorithm. Recall that,
from the definition of the hierarchical support structure, $|E(H_{i})|\leq
N^{j-1+32\epsilon^{2}}$. From the induction hypothesis, maintaining data
structure ${\mathcal{D}}_{j-1}(H_{i})$ recursively takes time at most:

$\begin{split}2c^{\prime\prime}(j-1)N^{j+2}\cdot
2^{4c^{\prime}/\epsilon^{6}}+c^{\prime\prime}|E(H_{i})|\cdot N^{2}\cdot
2^{4c^{\prime}/\epsilon^{6}}&\leq 2c^{\prime\prime}(j-1)N^{j+2}\cdot
2^{4c^{\prime}/\epsilon^{6}}+c^{\prime\prime}N^{j+1+32\epsilon^{2}}\cdot
2^{4c^{\prime}/\epsilon^{6}}\\\ &\leq c^{\prime\prime}(2j-1)N^{j+2}\cdot
2^{4c^{\prime}/\epsilon^{6}}.\end{split}$

Since $|{\mathcal{H}}|=N$, the total update time needed in order to maintain
these data structures for all graphs $H_{i}\in{\mathcal{H}}$ is bounded by
$c^{\prime\prime}(2j-1)N^{j+3}\cdot 2^{4c^{\prime}/\epsilon^{5}}$.

Consider now some graph $H_{i}\in{\mathcal{H}}$. The total update time that is
needed in order to maintain ES-Tree $\tau_{i}$ is bounded by:

$O(jm\cdot d^{*}_{j}\cdot\log N)\leq O(jm\cdot
2^{c^{\prime}j/\epsilon^{5}}\log N)\leq O(m\cdot
2^{4c^{\prime}/\epsilon^{6}}\log N),$

since $d^{*}_{j}=2^{c^{\prime}j/\epsilon^{4}}$ and $j\leq\left\lceil
1/\epsilon\right\rceil$. We can initialize the counters $n_{i,i^{\prime}}$ for
all graphs $H_{i^{\prime}}\in{\mathcal{H}}$ and $\tilde{n}_{i}$ without
increasing this asymptotic running time. We can also perform updates to these
counters in Step 1(d)i within the same asymptotic running time. Since
$|{\mathcal{H}}|=N$, this part of the algorithm takes total update time at
most $O(N\cdot m\cdot 2^{4c^{\prime}/\epsilon^{6}}\log N)$.

Whenever a vertex $s$ is deleted from a set $S^{\prime}(H_{i})$ for any graph
$H_{i}\in{\mathcal{H}}$, we may need to update the counters $n_{i^{\prime},i}$
and $\tilde{n}_{i^{\prime}}$ for some graphs
$H_{i^{\prime}}\in{\mathcal{H}}^{A}$. This can be done in time $O(N)$ per
vertex. Since a vertex may be deleted at most once from
$\bigcup_{H_{i}\in{\mathcal{H}}}S^{\prime}(H_{i})$, these updates can be done
in time $O(N^{j+1})$.

Lastly, every graph $H_{i}\in{\mathcal{H}}$ may be moved to set
${\mathcal{H}}^{D}$ at most once over the course of the algorithm, at which
time we may need to update counters $n_{i^{\prime},i}$ and
$\tilde{n}_{i^{\prime}}$ for graphs $H_{i^{\prime}}\in{\mathcal{H}}_{A}$. This
takes time $O(N)$ per graph $H_{i}\in{\mathcal{H}}$, and $O(N^{2})$ overall.

From the above discussion, the total update time of the algorithm is bounded
by:

$c^{\prime\prime}(2j-1)N^{j+3}\cdot 2^{4c^{\prime}/\epsilon^{6}}+O(N\cdot
m\cdot 2^{4c^{\prime}/\epsilon^{6}}\log N)+O(N^{j+1})\leq
2c^{\prime\prime}jN^{j+3}\cdot
2^{4c^{\prime}/\epsilon^{6}}+c^{\prime\prime}m\cdot N^{2}\cdot
2^{4c^{\prime}/\epsilon^{6}}.$

####  7.2.4 Response to Queries

In this subsection we describe an algorithm for responding to a short-path
query between a pair $x,y\in S^{\prime}(H)$ of vertices. Recall that the goal
is to return a path $P$ of length at most $d^{*}_{j}$ connecting $x$ to $y$ in
$H$, in time $O(|E(P)|)$.

Recall that
$S^{\prime}(H)=\bigcup_{H_{i}\in{\mathcal{H}}^{A}}S^{\prime}(H_{i})$.
Therefore, there is a pair of graphs
$H_{i},H_{i^{\prime}}\in{\mathcal{H}}^{A}$ (where possibly
$H_{i}=H_{i^{\prime}}$), with $x\in S^{\prime}(H_{i})$ and $y\in
S^{\prime}(H_{i^{\prime}})$. From 7.8, $\mbox{\sf dist}_{H}(x,y)\leq
d^{*}_{j}/8$ must hold. In particular, if we consider the ES-Tree data
structure $\tau_{i}$, then $y\in V(\tau_{i})$ must hold, and the distance from
$y$ to $s_{i}$ in the tree must be at most $d^{*}_{j}/8+1$. Let $Q_{1}$ be the
path connecting $y$ to $s_{i}$ in tree $\tau_{i}$. We delete the last vertex
on the path, and let $x^{\prime}\in S^{\prime}(H_{i})$ be the new last vertex
of $Q_{1}$. Using the induction hypothesis, we can compute a path $P^{\prime}$
in graph $H_{i}$ connecting $x$ to $x^{\prime}$, whose length is at most
$d^{*}_{j-1}$. Assume that the sequence of edges on path $Q^{\prime}$ is
$(e_{1},e_{2},\ldots,e_{z})$. For all $1\leq z^{\prime}\leq z$, consider the
path $P(e_{z^{\prime}})\in{\mathcal{P}}$ that serves as the embedding of edge
$z^{\prime}$ into $H$. Recall that the length of the path is bounded by
$2^{64/\epsilon^{4}}$. By concatenating the paths $P(e_{1}),\ldots,P(e_{z})$,
we obtain a path $Q_{2}$ in graph $H$, connecting $x$ to $x^{\prime}$, whose
length is at most $d^{*}_{j-1}\cdot 2^{64/\epsilon^{4}}$. Lastly, by
concatenating paths $Q_{1}$ and $Q_{2}$, we obtain a path $P$ in graph $H$
connecting $x$ to $y$. The length of the path is bounded by:

$d^{*}_{j-1}\cdot 2^{64/\epsilon^{4}}+\frac{d^{*}_{j}}{8}\leq
2^{c^{\prime}(j-1)/\epsilon^{5}}\cdot
2^{64/\epsilon^{4}}+\frac{2^{c^{\prime}j/\epsilon^{5}}}{8}\leq
2^{c^{\prime}j/\epsilon^{5}}=d^{*}_{j}.$

since $d^{*}_{j}=2^{c^{\prime}j/\epsilon^{5}}$. It is easy to see that the
algorithm can be implemented in time $O(|E(P)|)$.

##  8 APSP in Expanders – Proof of Theorem 2.4

This section is dedicated to the proof of Theorem 2.4. We first prove the
following lemma, that can be viewed as a weaker variation of Theorem 2.4, in
the sense that it can only withstand a significantly shorter sequence of edge
deletions.

######  Lemma 8.1.

There is a deterministic algorithm whose input consists of an $n$-vertex graph
$G$ with $|E(G)|=m$ that is a $\varphi^{*}$-expander, for some
$0<\varphi^{*}<1$, with maximum vertex degree at most $\Delta$, and a
parameter $\frac{2}{(\log n)^{1/12}}<\epsilon<\frac{1}{400}$, such that
$1/\epsilon$ is an integer. We assume that graph $G$ undergoes an online
sequence of at most $\frac{n^{1-20\epsilon}(\varphi^{*})^{2}}{\Delta^{2}}$
edge deletions. The algorithm maintains a set $U\subseteq V(G)$ of vertices,
such that, for every integer $t>0$, after $t$ edges are deleted from $G$,
$|U|\leq\frac{4\Delta t}{\varphi^{*}}$ holds. Vertex set $U$ is incremental,
so vertices may join it but they may not leave it. The algorithm also supports
short-path queries: given a pair of vertices $x,y\in V(G)\setminus U$, return
an $x$-$y$ path $P$ in the current graph $G$, of length at most
$\frac{2^{O(1/\epsilon^{6})}\cdot\Delta\cdot\log n}{\varphi^{*}}$, with query
time $O(|E(P)|)$. The total update time of the algorithm is
$O\left(\frac{n^{1+O(\epsilon)}\cdot\Delta^{3}}{(\varphi^{*})^{2}}\right)$.

The proof of Lemma 8.1 is deferred to Section 8.1. We now complete the proof
of Theorem 2.4 using it. We partition the execution of our algorithm into
phases. Let
$k^{\prime}=\left\lfloor\frac{n^{1-20\epsilon}\varphi^{2}}{2^{11}\cdot\Delta^{4}}\right\rfloor$.
The first phase lasts as long as the number of edges deleted from $G$ via the
input update sequence is at most $k^{\prime}$. Once $k^{\prime}$ edges are
deleted from graph $G$, the second phase begins. Each subsequent phase
similarly lasts as long as at most $k^{\prime}$ edges are deleted since the
beginning of the phase, except for the last phase which may be shorter, if the
input update sequence terminates before $k^{\prime}$ edges are deleted from
$G$ since the beginning of the phase. For all $i\geq 1$, we denote by
$\Sigma_{i}$ the sequence of edge deletions that graph $G$ undergoes as part
of the online input sequence of edge deletions in phase $i$, and we denote by
$E_{i}$ the set of edges that belong to $\Sigma_{i}$. Since the total number
of edges in the input sequence of edge deletions is bounded by
$\frac{n\cdot\varphi^{2}}{2^{13}\Delta^{4}}$, we get that the number of phases
is bounded by $\frac{n\cdot\varphi^{2}}{2^{13}\cdot\Delta^{4}\cdot
k^{\prime}}\leq\frac{n^{20\epsilon}}{4}$.

We define another dynamic graph $G^{\prime}$. At the beginning of the
algorithm, we set $G^{\prime}=G$. As the algorithm progresses, we will delete
some edges from $G^{\prime}$. Specifically, at the end of every phase of the
algorithm, we will define a set of edges to be deleted from graph
$G^{\prime}$; we do not delete any edges from $G^{\prime}$ as long as a phase
progresses. We will run the algorithm from Theorem 3.4 (expander pruning) on
graph $G^{\prime}$, and we let $\tilde{U}$ be the set of vertices of
$G^{\prime}$ that it maintains. We will ensure that the number of edges that
are deleted from $G^{\prime}$ over the course of the entire algorithm is
bounded by $k=\frac{\varphi n}{16\Delta}$. Clearly,
$k\leq\frac{\varphi\cdot|E(G)|}{10\Delta}$. From Theorem 3.4, we are
guaranteed that, throughout the algorithm,
$|\tilde{U}|\leq\frac{8k\Delta}{\varphi}\leq\frac{n}{2}$ holds.

In order to execute the first phase, we let $H_{1}=G^{\prime}=G$, and we apply
the algorithm from Lemma 8.1 to graph $H_{1}$, and the online sequence
$\Sigma_{1}$ of edge deletions. Recall that graph $G$ is a $\varphi$-expander,
and that $|\Sigma_{1}|\leq
k^{\prime}=\left\lfloor\frac{n^{1-20\epsilon}\varphi^{2}}{2^{11}\cdot\Delta^{4}}\right\rfloor$.
Recall that the algorithm maintains an incremental set $U\subseteq V(G)$ of
vertices, that we denote by $U_{1}$, such that, for every integer $t>0$, after
$t$ edges are deleted from $G$, $|U_{1}|\leq\frac{4\Delta t}{\varphi}$ holds.
Throughout the first phase, we let the set $U$ of vertices that our algorithm
maintains be $U_{1}$. Recall that the algorithm from Lemma 8.1 supports
queries short-path queries: given a pair of vertices $x,y\in V(G)\setminus
U_{1}$, return an $x$-$y$ path $P$ in the current graph $H_{1}=G$, of length
at most $\frac{2^{O(1/\epsilon^{6})}\cdot\Delta\cdot\log n}{\varphi}$, with
query time $O(|E(P)|)$.

From the above discussion, at the end of the first phase,
$|U_{1}|\leq\frac{4\Delta
k^{\prime}}{\varphi}\leq\frac{n^{1-20\epsilon}\cdot\varphi}{2^{9}\cdot\Delta^{3}}$
holds. We denote by $\tilde{E}_{1}$ the set of all edges that are incident to
the vertices of $U_{1}$ in the current graph $G$. We then update graph
$G^{\prime}$, by deleting the edges of $E_{1}\cup\tilde{E}_{1}$ from it.
Therefore, at the end of the first phase, the number of edges that are deleted
from $G^{\prime}$ is bounded by:

$|E_{1}|+|\tilde{E}_{1}|\leq\frac{n^{1-20\epsilon}\cdot\varphi}{2^{8}\cdot\Delta^{2}}<k.$

We denote by $\tilde{U}_{1}$ the set of vertices that the algorithm from
Theorem 3.4 produces at the end of Phase 1, and the deletion of the edges of
$E_{1}\cup\tilde{E}_{1}$ from $G^{\prime}$. We also denote by
$H_{2}=G^{\prime}\setminus\tilde{U}_{1}$. From Theorem 3.4, graph $H_{2}$ is a
$\varphi/(6\Delta)$-expander. Notice also that, if $U_{1}$ is the set of
vertices that the algorithm from Lemma 8.1 maintains at the end of the phase,
then $U_{1}\subseteq\tilde{U}_{1}$ must hold.

The remaining phases are executed similarly, with several minor differences.
We let $\tilde{U}_{i}$ be the set $\tilde{U}$ that the algorithm from Theorem
3.4 produces at the end of Phase $(i-1)$, and we denote
$H_{i}=G^{\prime}\setminus\tilde{U}_{i}$. We will ensure that the total number
of edges that are deleted from graph $G^{\prime}$ over the course of the first
$(i-1)$ phases is bounded by:

$(i-1)\cdot\frac{n^{1-20\epsilon}\cdot\varphi}{32\cdot\Delta}.$

Since the total number of phases is bounded by $\frac{n^{20\epsilon}}{4}$,
this ensures that the number of edges deleted so far from $G^{\prime}$ is less
than $\frac{n\cdot\varphi}{16\Delta}=k$. Therefore, from Theorem 3.4, graph
$H_{i}$ is a $\varphi/(6\Delta)$-expander, and furthermore,
$|\tilde{U}_{i}|\leq n/2$, so $|V(H_{i})|\geq n/2$. Denote
$\varphi^{*}=\frac{\varphi}{6\Delta}$, and note that:

$k^{\prime}=\left\lfloor\frac{n^{1-20\epsilon}\varphi^{2}}{2^{11}\cdot\Delta^{4}}\right\rfloor\leq\frac{|V(H_{i})|^{1-20\epsilon}(\varphi^{*})^{2}}{\Delta^{2}}$

Therefore, we can apply the algorithm from Lemma 8.1 to graph $H_{i}$ with the
sequence $\Sigma_{i}$ of edge deletions. We denote by $U_{i}$ the incremental
set of vertices of $H_{i}$ that the algorithm maintains. The set $U$ of
vertices of $G$ that our algorithm maintains over the course of the $i$th
phase is defined to be $\tilde{U}_{i}\cup U_{i}$.

Recall that the total number of edges that are deleted over the course of the
first $(i-1)$ phases of the algorithm from graph $G$ is $(i-1)\cdot
k^{\prime}\geq(i-1)\cdot\left\lfloor\frac{n^{1-20\epsilon}\varphi^{2}}{2^{11}\cdot\Delta^{4}}\right\rfloor$.

Since the total number of edges deleted from graph $G^{\prime}$ over the
course of the first $(i-1)$ phases is bounded by
$(i-1)\cdot\frac{n^{1-20\epsilon}\cdot\varphi}{32\cdot\Delta}$, from Theorem
3.4, we get that:

$|\tilde{U}_{i}|\leq\frac{n^{1-20\epsilon}\cdot(i-1)}{4}.$

Consider some integer $0\leq t\leq k^{\prime}$, and the time during the
execution of phase $i$, immediately after the $t$-th edge of $\Sigma_{i}$ is
deleted from graph $G$ in phase $i$. Then at this time, the total number of
edges deleted from graph $G$ since the beginning of the algorithm is at least:

$m^{i}_{t}=(i-1)\cdot\left\lfloor\frac{n^{1-20\epsilon}\varphi^{2}}{2^{11}\cdot\Delta^{4}}\right\rfloor+t.$

At the same time:

$|U|=|\tilde{U}_{i}|+|U_{i}|\leq(i-1)\cdot\frac{n^{1-20\epsilon}}{4}+\frac{4\Delta
t}{\varphi^{*}}=(i-1)\cdot\frac{n^{1-20\epsilon}}{4}+\frac{24\Delta^{2}t}{\varphi}\leq\frac{2^{11}\Delta^{4}}{\varphi^{2}}\cdot
m^{i}_{t}.$

Notice that, over the course of the $i$th phase, $V(H_{i})\setminus
U_{i}=V(G)\setminus(U_{i}\cup\tilde{U}_{i})=V(G)\setminus U$ holds. Therefore,
when short-path query arrives for a pair $x,y\in V(G)\setminus U$ of vertices,
it must be the case that $x,y\in V(H_{i})\setminus U_{i}$. We can then perform
short-path query in the data structure maintained by the algorithm from Lemma
8.1, to obtain a path $P$ in the current graph $H_{i}\subseteq G$, of length
at most $\frac{2^{O(1/\epsilon^{6})}\cdot\Delta\cdot\log
n}{\varphi^{*}}\leq\frac{2^{O(1/\epsilon^{6})}\cdot\Delta^{2}\cdot\log
n}{\varphi}$, in time $O(|E(P)|)$. We return this path as the response to the
query.

From the above discussion, at every time $t$ during the execution of phase
$i$, if $m_{t}^{i}$ is the number of edges deleted so far by the algorithm,
and $U^{(t)}$ is the current set $U$, then:

$|U^{(t)}|\leq\frac{2^{11}\Delta^{2}}{\varphi^{2}}\cdot m^{i}_{t}.$

Once all edges of $\Sigma_{i}$ edges are deleted from graph $G$, we let
$\tilde{E}_{i}$ be the set of all edges that are incident to the vertices in
the current set $U_{i}$. Observe that:

$|\tilde{E}_{i}|\leq\Delta\cdot|U_{i}|\leq\frac{4\Delta^{2}}{\varphi^{*}}\cdot
k^{\prime}\leq\frac{24\Delta^{3}}{\varphi}\cdot\frac{n^{1-20\epsilon}\varphi^{2}}{2^{11}\cdot\Delta^{4}}\leq\frac{n^{1-20\epsilon}\cdot\varphi}{64\cdot\Delta}.$

since $\varphi^{*}=\frac{\varphi}{6\Delta}$ and
$k^{\prime}=\left\lfloor\frac{n^{1-20\epsilon}\varphi^{2}}{2^{11}\cdot\Delta^{4}}\right\rfloor$.

We delete the edges of $E_{i}\cup\tilde{E}_{i}$ from graph $G^{\prime}$, and
update the data structure maintained by the algorithm from Theorem 3.4. Since
$|E_{i}|\leq
k^{\prime}=\left\lfloor\frac{n^{1-20\epsilon}\varphi^{2}}{2^{11}\cdot\Delta^{4}}\right\rfloor$,
we get that
$|E_{i}\cup\tilde{E}_{i}|\leq\frac{n^{1-20\epsilon}\cdot\varphi}{32\cdot\Delta}$.
Recall that we have assumed that, over the course of the first $(i-1)$ phases,
the total number of edges deleted from graph $G^{\prime}$ is bounded by
$(i-1)\cdot\frac{n^{1-20\epsilon}\cdot\varphi}{32\cdot\Delta}$. We then get
that, over the course of the first $i$ phases, the total number of edges
deleted from graph $G^{\prime}$ is bounded by
$i\cdot\frac{n^{1-20\epsilon}\cdot\varphi}{32\cdot\Delta}$. We let
$\tilde{U}_{i+1}$ the set $\tilde{U}$ that the algorithm from Theorem 3.4
maintains after the edges of $E_{i}\cup\tilde{E}_{i}$ are deleted from
$G^{\prime}$. Since the vertices of $U_{i}$ are isolated in graph
$G^{\prime}\setminus\tilde{E}_{i}$, while graph
$G^{\prime}\setminus\tilde{U}_{i+1}$ must be a $\varphi/(6\Delta)$-expander,
we get that $U_{i}\subseteq\tilde{U}_{i+1}$. We then let the set $U$ that the
algorithm maintains be $\tilde{U}_{i+1}$, and we continue to the next phase,
with the graph $H_{i+1}=G^{\prime}\setminus\tilde{U}_{i+1}$.

It is easy to verify that the set $U$ of vertices that the algorithm maintains
is incremental. Indeed, consider some phase $i$ of the algorithm. Throughout
the phase, we let $U=\tilde{U}_{i}\cup U_{i}$, where $\tilde{U}_{i}$ is fixed
over the course of the phase, and $U_{i}$ is incremental. If we denote by
$U_{i}^{\prime}$ the set $U_{i}$ at the end of Phase $i$, then we are
guaranteed that $U^{\prime}_{i}\subseteq\tilde{U}_{i+1}$, and, from Theorem
3.4, $\tilde{U}_{i}\subseteq\tilde{U}_{i+1}$. At the beginning of Phase
$(i+1)$, we set $U=\tilde{U}_{i+1}$, and so $\tilde{U}_{i}\cup
U_{i}^{\prime}\subseteq U$ at this point. Therefore, set $U$ is incremental
throughout the algorithm.

It now only remains to bound the total update time of the algorithm. The
algorithm consists of at most $O(n^{20\epsilon})$ phases. In every phase, we
run the algorithm from Lemma 8.1, whose total update time is
$O\left(\frac{m^{1+O(\epsilon)}\cdot\Delta^{3}}{(\varphi^{*})^{2}}\right)\leq
O\left(\frac{m^{1+O(\epsilon)}\cdot\Delta^{5}}{\varphi^{2}}\right)$.

Additionally, the total update time of the algorithm from Theorem 3.4, over
the course of at most $m$ deletions of edges from $G^{\prime}$, is bounded by
$\widetilde{O}\left(\frac{m\Delta^{2}}{\varphi^{2}}\right)$.

Altogether, the total update time of the algorithm is bounded by:

$O(n^{20\epsilon})\cdot
O\left(\frac{m^{1+O(\epsilon)}\cdot\Delta^{5}}{\varphi^{2}}\right)+\widetilde{O}\left(\frac{m\Delta^{2}}{\varphi^{2}}\right)\leq
O\left(\frac{m^{1+O(\epsilon)}\cdot\Delta^{5}}{\varphi^{2}}\right).$

In order to complete the proof of Theorem 2.4, it now remains to prove Lemma
8.1.

###  8.1 Proof of Lemma 8.1

We start by describing the data structures that the algorithm maintains,
together with their initialization. We then describe an algorithm for
maintaining the data structures under the deletion of edges from $G$. Finally,
we describe an algorithm for responding to short-path query.

Before we do so, we establish some bounds on the parameters that will be
useful for us later. All of these bounds follow from the fact that
$\frac{2}{(\log n)^{1/12}}<\epsilon<\frac{1}{400}$ holds, from the statement
of Lemma 8.1.

First, since $\epsilon>\frac{2}{(\log n)^{1/12}}$, we get that $\log
n\geq(2/\epsilon)^{12}$, and:

$n\geq 2^{(2/\epsilon)^{12}}\geq 2^{800^{12}}.$ (11)

Additionally:

$n^{\epsilon^{8}}>n^{(2/(\log n)^{1/12})^{8}}=n^{256/(\log n)^{2/3}}>2^{(\log
n)^{1/3}}>\log n.$ (12)

####  8.1.1 Data Structures and Initialization

We start by applying the algorithm from Corollary 5.3 to graph $G$, with the
set $T=V(G)$ of terminals, parameter $\epsilon$ given by the statement of
Lemma 8.1, and parameters $d=\frac{64\Delta\log m}{\varphi^{*}}$ and
$\eta=\frac{512\Delta^{2}\log m}{(\varphi^{*})^{2}}$.

We claim that the algorithm may not return a pair $T_{1},T_{2}\subseteq T$ of
disjoint subsets of terminals, and a set $E^{\prime}$ of edges of $G$, with
$|T_{1}|=|T_{2}|$, $|T_{1}|\geq\frac{n^{1-4\epsilon^{3}}}{4}$ and
$|E^{\prime}|\leq\frac{d\cdot|T_{1}|}{\eta}$, such that for every pair $t\in
T_{1},t^{\prime}\in T_{2}$ of terminals, $\mbox{\sf dist}_{G\setminus
E^{\prime}}(t,t^{\prime})>d$. Indeed, assume for contradiction that the
algorithm returns a pair $T_{1},T_{2}$ of disjoint subsets of vertices of $G$
with the above properties. Denote $\varphi=\frac{\varphi^{*}}{\Delta}$, and
note that
$|E^{\prime}|\leq\frac{d\cdot|T_{1}|}{\eta}=\frac{\varphi^{*}\cdot|T_{1}|}{8\Delta}\leq\frac{\varphi\cdot|T_{1}|}{4}$.
Note also that $d=\frac{64\Delta\log m}{\varphi^{*}}\geq\frac{32\log
m}{\varphi}$. Clearly, we can view $(T_{1},T_{2},E^{\prime})$ as a
$(\delta,d)$-distancing in graph $G$, for some parameter $0<\delta<1$. From
Lemma 4.1, there is a cut $(X,Y)$ in graph $G$, with $T_{1}\subseteq X$ and
$T_{2}\subseteq Y$, such that
$|E_{G}(X,Y)|\leq\varphi\cdot\min\left\\{|E(X)|,|E(Y)|\right\\}$. Since the
maximum vertex degree in $G$ is bounded by $\Delta$, $|E(X)|<\Delta\cdot|X|$,
and similarly $|E(Y)|<\Delta\cdot|Y|$. Therefore, we are guaranteed that
$|E(X,Y)|<\varphi\cdot\Delta\cdot\min\left\\{|X|,|Y|\right\\}=\varphi^{*}\cdot\min\left\\{|X|,|Y|\right\\}$,
contradicting the fact that $G$ is a $\varphi^{*}$-expander.

We conclude that the algorithm from Corollary 5.3 must return a graph $H$ with
$V(H)\subseteq V(G)$, $|V(H)|=N^{1/\epsilon}\geq n-n^{1-\epsilon/2}\geq n/2$,
where $N=\left\lfloor n^{\epsilon}\right\rfloor$, so that the maximum vertex
degree in $H$ is at most $n^{32\epsilon^{3}}$. The algorithm also must return
an embedding ${\mathcal{P}}$ of $H$ into $G$ via paths of length at most $d$
that cause congestion at most $\eta\cdot n^{32\epsilon^{3}}$, and a
level-$(1/\epsilon)$ hierarchical support structure for $H$, such that $H$ is
$(\eta^{\prime},\tilde{d})$-well-connected with respect to the set $S(H)$ of
vertices defined by the support structure, where
$\eta^{\prime}=N^{6+256\epsilon}$, and $\tilde{d}=2^{c/\epsilon^{5}}$, with
$c$ being the constant used in the definition of the Hierarchical Support
Structure. Recall that the running time of the algorithm is:

$O\left(n^{1+O(\epsilon)}+|E(G)|\cdot n^{O(\epsilon^{3})}\cdot(\eta+d\log
n)\right)\leq
O\left(n^{1+O(\epsilon)}+n^{1+O(\epsilon^{3})}\cdot\frac{\Delta^{3}\log^{2}n}{(\varphi^{*})^{2}}\right)\leq
O\left(\frac{n^{1+O(\epsilon)}\cdot\Delta^{3}}{(\varphi^{*})^{2}}\right).$

(We have used the fact that $d=\frac{64\Delta\log m}{\varphi^{*}}$,
$\eta=\frac{512\Delta^{2}\log m}{(\varphi^{*})^{2}}$, and Inequality 12). Let
$q=1/\epsilon$.

For every edge $e^{\prime}\in E(H)$, let $P(e^{\prime})\in{\mathcal{P}}$ be
the path embedding edge $e^{\prime}$ into $G$. For every edge $e\in E(G)$, we
will maintain a list $L(e)$ of all edges $e^{\prime}\in E(H)$ with $e\in
E(P(e^{\prime}))$. The list also contains, for each edge $e^{\prime}\in L(e)$,
a pointer to edge $e^{\prime}$ in graph $H$, and each edge $e^{\prime}\in
E(H)$ maintains a pointer to every edge in $E(P(e^{\prime}))$. Whenever an
edge $e\in E(G)$ is deleted from graph $G$, we will delete every edge
$e^{\prime}\in L(e)$ from graph $H$. Since the paths in ${\mathcal{P}}$ cause
congestion at most $\eta\cdot n^{32\epsilon^{3}}=\frac{512\Delta^{2}\cdot
n^{32\epsilon^{3}}\log m}{(\varphi^{*})^{2}}\leq\frac{\Delta^{2}\cdot
n^{33\epsilon^{3}}}{(\varphi^{*})^{2}}$ in $H$, every deletion of an edge in
$G$ may trigger the deletion of at most $\tilde{\eta}=\frac{\Delta^{2}\cdot
n^{33\epsilon^{3}}}{(\varphi^{*})^{2}}$ edges from $H$. Let $q=1/\epsilon$.
Then the total number of edge deletions from graph $H$ over the course of the
algorithm is bounded by:

$\frac{n^{1-20\epsilon}(\varphi^{*})^{2}}{\Delta^{2}}\cdot\tilde{\eta}=n^{1-20\epsilon+33\epsilon^{2}}\leq\frac{n^{1-16\epsilon}}{2}\leq
N^{q-16q\epsilon}<N^{q-8-300q\epsilon^{2}},$

as $q=1/\epsilon$ and $\frac{n}{2}\leq N^{q}$.

Note that $\eta^{\prime}=N^{6+256\epsilon}=N^{6+256q\epsilon^{2}}=\eta_{q}$
and $\tilde{d}=2^{c/\epsilon^{5}}=\tilde{d}_{q}$, where $\eta_{q}$ and
$\tilde{d}_{q}$ are the parameters from the definition of Hierarchical Support
Structure. We will use the algorithm from Theorem 7.1 in graph $H$, with
parameter $j=q$, and parameters $\epsilon,N$ remaining unchanged. In order to
be able to use the theorem, we need to verify that
$\frac{N^{\epsilon^{4}}}{\log N}\geq 2^{128/\epsilon^{6}}$ holds. Since
$N=\left\lfloor n^{\epsilon}\right\rfloor$, we get that:

$\frac{N^{\epsilon^{4}}}{\log N}\geq\frac{n^{\epsilon^{6}}}{\epsilon\cdot\log
n}\geq n^{\epsilon^{6}/2}\geq 2^{128/\epsilon^{6}}.$

(we have used the fact that, from Inequality 12, $\log n<n^{\epsilon^{8}}$,
from Inequality 11, $n\geq 2^{(2/\epsilon)^{12}}$, and $\epsilon<1/400$).

As observed already, the number of edge deletions that graph $H$ undergoes
over the course of the algorithm is bounded less than
$N^{q-8-300q\epsilon^{2}}=\Lambda_{q}$. We will maintain a data structure from
Theorem 7.1 in graph $H$, with parameters $\epsilon,N$ and $q$ as defined
above. We denote this data structure by ${\mathcal{D}}(H)$. At the beginning
of the algorithm, we initialize this data structure. Recall that data
structure ${\mathcal{D}}(H)$ maintains a decremental set
$S^{\prime}(H)\subseteq S(H)$ of vertices of $H$, called supported vertices,
such that, at the beginning of the algorithm, $S^{\prime}(H)=S(H)$. The
algorithm ensures that $|S^{\prime}(H)|\geq\frac{N^{q}}{16^{q}}$ holds over
the course of the algorithm, and it supports short-path queries between
supported vertices: given a pair $x,y\in S^{\prime}(H)$ of vertices, return a
path $P$ connecting $x$ to $y$ in the current graph $H$, whose length is at
most $d^{*}_{q}=2^{O(q/\epsilon^{5})}=2^{O(1/\epsilon^{6})}$, in time
$O(|E(P)|)$. If $m^{\prime}\leq n^{1+32\epsilon^{3}}$ is the number of edges
in $H$ at the beginning of the algorithm, then the total update time needed to
maintain data structure ${\mathcal{D}}(H)$ is bounded by:

$O\left(qN^{q+3}\cdot 2^{O(1/\epsilon^{6})}+m^{\prime}\cdot N^{2}\cdot
2^{O(1/\epsilon^{6})}\right)\leq O\left(n^{1+O(\epsilon)}\cdot
2^{O(1/\epsilon^{5})}\right)\leq O\left(n^{1+O(\epsilon)}\right)$

(We have used the fact that, from Inequality 11, $n^{\epsilon}\geq
2^{(2/\epsilon)^{12}\cdot\epsilon}\geq 2^{O(1/\epsilon^{6})}$).

Lastly, we maintain an ES-Tree data structure $\tau$ in graph $G$, rooted at
the set $S^{\prime}(H)$ of vertices, with depth parameter
$d=\frac{64\Delta\log m}{\varphi^{*}}$. Specifically, we maintain a graph
$G^{\prime}$, that is obtained from graph $G$ by adding a source vertex $s$,
that connects to every vertex that lies in the current set $S^{\prime}(H)$ of
supported vertices with an edge. We then let $\tau$ be an ES-Tree data
structure in graph $G^{\prime}$, rooted at $s$, with depth $d+1$. Whenever a
vertex $x$ is deleted from set $S^{\prime}(H)$, we will delete edge $(s,x)$
from $G^{\prime}$, and update the data structure $\tau$ accordingly. Also,
whenever an edge $e$ is deleted from graph $G$, we will also delete $e$ from
graph $G^{\prime}$, and update the data structure $\tau$ accordingly.
Throughout the algorithm, we let $U$ be the set of all vertices $v\in V(G)$,
such that $v\not\in V(\tau)$. In other words, $\mbox{\sf
dist}_{G}(S^{\prime}(H),v)>d$. Clearly, the set $U$ of vertices is
incremental: vertices can joint it but they cannot leave it. In the next claim
we bound the cardinality of $U$.

######  Claim 8.2.

Let $t$ be any time during the algorithm’s execution, let $E^{\prime}_{t}$ be
the set of edges that were deleted so far from $G$, and let $U_{t}$ be the
current set $U$ of vertices. Then
$|U_{t}|\leq\frac{4\Delta|E^{\prime}_{t}|}{\varphi^{*}}$.

###### Proof.

Assume otherwise, and let $t$ be some time during the algorithm’s execution,
when $|U_{t}|>\frac{4\Delta|E^{\prime}_{t}|}{\varphi^{*}}$ holds. Denote
$\varphi=\frac{\varphi^{*}}{\Delta}$, so that
$|E^{\prime}_{t}|<\varphi\cdot|U_{t}|/4$.

Let $S^{\prime}_{t}$ be the set $S^{\prime}(H)$ of vertices at time $t$.
Recall that we are guaranteed that
$|S^{\prime}(H)|\geq\frac{N^{q}}{16^{q}}\geq\frac{n}{2^{4/\epsilon+1}}$ holds
throughout the algorithm. Since the total number of the edges deleted from $G$
over the course of the algorithm is at most
$\frac{n^{1-20\epsilon}(\varphi^{*})^{2}}{\Delta^{2}}=n^{1-20\epsilon}\varphi^{2}\leq
n^{1-20\epsilon}\cdot\varphi$, we get that $|E^{\prime}_{t}|\leq
n^{1-20\epsilon}\cdot\varphi$. On the other hand, from Inequality 11,
$n^{20\epsilon}\geq 2^{4/\epsilon+4}$, and so:

$|S^{\prime}_{t}|\geq\frac{n}{2^{4/\epsilon+1}}\geq
4n^{1-20\epsilon}\geq\frac{4|E^{\prime}_{t}|}{\varphi}.$

We conclude that
$|E^{\prime}_{t}|\leq\frac{\varphi}{4}\cdot\min\left\\{|S^{\prime}_{t}|,|U_{t}|\right\\}$.
Denote $M=\min\left\\{|S^{\prime}_{t}|,|U_{t}|\right\\}$. Let $X\subseteq
S^{\prime}_{t}$, $Y\subseteq U_{t}$ be arbitrary subsets of vertices of
cardinality $M$ each. Let $G^{0}$ be the graph $G$ at the beginning of the
algorithm. Clearly, $\mbox{\sf dist}_{G^{0}\setminus E^{\prime}_{t}}(X,Y)>d$.
Recall that $d=\frac{64\Delta\log m}{\varphi^{*}}=\frac{64\log m}{\varphi}$.
From Lemma 4.1, there is a cut $(X^{\prime},Y^{\prime})$ in graph $G^{0}$,
with with $X\subseteq X^{\prime}$ and $Y\subseteq Y^{\prime}$, such that
$|E_{G^{0}}(X^{\prime},Y^{\prime})|\leq\varphi\cdot\min\left\\{|E_{G^{0}}(X^{\prime})|,|E_{G^{0}}(Y^{\prime})|\right\\}$.
Since $|E_{G^{0}}(X^{\prime})|<\Delta\cdot|X^{\prime}|$ and
$|E_{G^{0}}(Y^{\prime})|<\Delta\cdot|Y^{\prime}|$, we get that:

$|E_{G^{0}}(X^{\prime},Y^{\prime})|<\varphi\cdot\Delta\cdot\min\left\\{|X^{\prime}|,|Y^{\prime}|\right\\}=\varphi^{*}\cdot\min\left\\{|X^{\prime}|,|Y^{\prime}|\right\\},$

contradicting the fact that graph $G^{0}$ is a $\varphi^{*}$-expander.

At the beginning of the algorithm, we initialize the ES-Tree data structure
$\tau$, and set $U=\emptyset$. The total update time needed in order to
maintain $\tau$ is bounded by $O(md\log m)\leq
O\left(\frac{m\Delta\log^{2}m}{\varphi^{*}}\right)$.

We now bound the running time that is needed to initialize all data
structures, and to maintain data structures ${\mathcal{D}}(H)$, $\tau$, and
$\left\\{L(e)\right\\}_{e\in E(G)}$ over the course of the algorithm. The
running time of the algorithm from Corollary 5.3, from the above discussion,
is bounded by
$O\left(\frac{n^{1+O(\epsilon)}\cdot\Delta^{3}}{(\varphi^{*})^{2}}\right)$.
The time that is needed in order to initialize and maintain the lists $L(e)$
for edges $e\in E(G)$ is subsumed by this running time. Additionally, from the
above discussion, the total update time of data structure ${\mathcal{D}}(H)$
is bounded by $O\left(n^{1+O(\epsilon)}\right)$, and the total update time of
data structure $\tau$ is bounded by
$O\left(\frac{m\Delta\log^{2}m}{\varphi^{*}}\right)$. The set $U$ of vertices
can be maintained within this asymptotic running time. Overall, the total time
needed to initialize all data structures, and to maintain data structures
${\mathcal{D}}(H)$, $\tau$, and $\left\\{L(e)\right\\}_{e\in E(G)}$ over the
course of the algorithm is bounded by:

$O\left(\frac{m\Delta\log^{2}m}{\varphi^{*}}\right)+O\left(\frac{n^{1+O(\epsilon)}\cdot\Delta^{3}}{(\varphi^{*})^{2}}\right)\leq
O\left(\frac{n^{1+O(\epsilon)}\cdot\Delta^{3}}{(\varphi^{*})^{2}}\right).$

####  8.1.2 Maintaining the Data Structures

Maintaining the data structures under the deletion of edges from $G$ is now
straightforward. In Figure 2 we describe algorithm
$\operatorname{DeleteExpanderEdge}(e)$ that is invoked whenever an edge $e$ is
deleted from graph $G$. We start by considering every edge $e^{\prime}\in
E(H)$ whose embedding path $P(e^{\prime})$ contains edge $e$ – in other words,
all edges of $L(e)$. We delete each such edge $e^{\prime}$ from graph $H$, and
update data structure ${\mathcal{D}}(H)$ with this deletion. As a result, it
is possible that some vertices are removed from set $S^{\prime}(H)$. For each
such vertex $x$, we delete edge $(s,x)$ from graph $G^{\prime}$, and update
the data structure $\tau$ accordingly. Finally, we delete edge $e$ from data
structure $\tau$. Whenever a vertex leaves the tree $\tau$, we add it to $U$.

Algorithm $\operatorname{DeleteExpanderEdge}(e)$ 1. For every edge
$e^{\prime}\in L(e)$ do: (a) Delete $e^{\prime}$ from $H$ and update data
structure ${\mathcal{D}}(H)$. Let $X$ be the set of vertices that were deleted
from $S^{\prime}(H)$ as the result of this update. (b) For every edge
$e^{\prime\prime}\in E(G)$ with $e^{\prime}\in L(e^{\prime\prime})$, delete
$e^{\prime}$ from $L(e^{\prime\prime})$. (c) for every vertex $x\in X$, delete
edge $(s,x)$ from graph $G^{\prime}$ and update the ES-Tree $\tau$ with this
deletion. Add every vertex that is removed from $\tau$ to $U$. 2. Delete edge
$e$ from graph $G^{\prime}$ and update data structure $\tau$ accordingly. Add
every vertex that is removed from $\tau$ to $U$.

Figure 2: Algorithm $\operatorname{DeleteExpanderEdge}(e)$

It is easy to verify that the total update time of the algorithm is dominated
by the time needed to initialize the data structures, and to maintain data
structures ${\mathcal{D}}(H)$, $\tau$, and $\left\\{L(e)\right\\}_{e\in
E(G)}$. From the above discussion, the total update time of the algorithm is
bounded by
$O\left(\frac{n^{1+O(\epsilon)}\cdot\Delta^{3}}{(\varphi^{*})^{2}}\right)$.

####  8.1.3 Responding to Short-Path Queries

We assume that we are given a pair of vertices $x,y\in V(G)\setminus U$, and
describe an algorithm for responding to short-path query between $x$ and $y$.
Recall that our goal is to return an $x$-$y$ path $P$ in the current graph
$G$, of length at most $\frac{2^{O(1/\epsilon^{6})}\cdot\Delta\cdot\log
n}{\varphi^{*}}$, with query time $O(|E(P)|)$.

Using the ES-Tree $\tau$, we compute a path $Q$ connecting $x$ to some vertex
$x^{\prime}\in S^{\prime}(H)$, and a path $Q^{\prime}$ connecting vertex $y$
to some vertex $y^{\prime}\in S^{\prime}(H)$, so that the length of each path
is bounded by $d$. Next, we query data structure ${\mathcal{D}}(H)$ with the
pair $x^{\prime},y^{\prime}\in S^{\prime}(H)$ of vertices. The data structure
must return a path $\tilde{Q}$ connecting $x^{\prime}$ to $y^{\prime}$ in $H$,
whose length is at most $2^{O(1/\epsilon^{6})}$, in time $O(|E(\tilde{Q})|)$.
Using the embedding ${\mathcal{P}}$ of $H$ into $G$, in which the length of
every path is bounded by $d$, we can compute a path $Q^{\prime\prime}$ in
graph $G$, connecting $x^{\prime}$ to $y^{\prime}$, whose length is bounded by
$|E(\tilde{Q})|\cdot d\leq 2^{O(1/\epsilon^{6})}\cdot d$. Lastly, by
concatenating the paths $Q,Q^{\prime\prime}$ and $Q^{\prime}$, we obtain a
path $P$ connecting $x$ to $y$ in graph $G$, whose length is at most:

$2^{O(1/\epsilon^{6})}\cdot
d\leq\frac{2^{O(1/\epsilon^{6})}\cdot\Delta\cdot\log
m}{\varphi^{*}}\leq\frac{2^{O(1/\epsilon^{6})}\cdot\Delta\cdot\log
n}{\varphi^{*}}.$

It is easy to see that the running time of the algorithm is $O(|E(P)|)$.

##  9 Advanced Path Peeling – Proof of Theorem 2.5

In this section we prove Theorem 2.5. The main tool in the proof is the
following theorem.

######  Theorem 9.1.

There is a large enough constant $c^{*}$, and a deterministic algorithm, whose
input consists of a connected $n$-vertex $m$-edge graph $G$, a collection
${M}=\left\\{(s_{1},t_{1}),\ldots,(s_{k},t_{k})\right\\}$ of pairs of vertices
of $G$, such that ${M}$ is a matching, and parameters $d,\eta>0$,
$0<\alpha\leq 1/2$ and $\frac{2}{(\log n)^{1/24}}<\epsilon<\frac{1}{400}$,
such that $1/\epsilon$ is an integer and
$256d<\eta\leq\frac{d^{2}}{2^{c^{*}/\epsilon^{6}}\cdot\log m}$ holds. The
algorithm computes one of the following:

  * •

either a cut $(A,B)$ with
$|E_{G}(A,B)|\leq\frac{1024d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}$,
and each of $A$, $B$ contains at least $\frac{\alpha k}{8}$ vertices of set
$T=\left\\{s_{1},t_{1},\ldots,s_{k},t_{k}\right\\}$; or

  * •

a routing ${\mathcal{P}}$ in $G$ of a subset ${M}^{\prime}\subseteq{M}$
containing at least $(1-\alpha)k$ pairs of vertices, such that every path in
${\mathcal{P}}$ has length at most $d$, and the total congestion caused by the
paths in ${\mathcal{P}}$ is at most $\frac{4\eta}{\alpha}$.

The running time of the algorithm is bounded by
$O\left(m^{1+O(\epsilon)}(d^{2}+\eta d)\right)$.

The proof of Theorem 2.5 easily follows from Theorem 9.1. Let
$z=\left\lceil\frac{1}{\epsilon}\right\rceil$, and let
$\epsilon^{\prime}=\frac{1}{z}$. Clearly, $\frac{1}{\epsilon}\leq
z\leq\frac{2}{\epsilon}$, and so
$\frac{\epsilon}{2}\leq\epsilon^{\prime}\leq\epsilon$. Since we have assumed
that $\frac{4}{(\log n)^{1/24}}<\epsilon<\frac{1}{400}$, we get that
$\frac{2}{(\log n)^{1/24}}<\epsilon^{\prime}<\frac{1}{400}$. For convenience,
in the remainder of the proof we will denote $\epsilon^{\prime}$ by
$\epsilon$.

Let $c^{*}$ be the constant from Theorem 9.1. We set
$d=\frac{2^{c^{*}/\epsilon^{6}+10}\cdot\log m}{\varphi}$ and
$\eta=\frac{1024d}{\varphi}=\frac{2^{c^{*}/\epsilon^{6}+20}\cdot\log
m}{\varphi^{2}}$. It is immediate to verify that $\eta>256d$. Observe also
that:

$\frac{d^{2}}{2^{c^{*}/\epsilon^{6}}\cdot\log
m}=\frac{1024d}{\varphi}\geq\eta.$

We start by considering the case where $\frac{1}{\alpha}<\log n$. In this
case, we apply the algorithm from Theorem 9.1 to graph $G$, the set ${M}$ of
pairs of its vertices, and parameters $d,\eta,\alpha$ and $\epsilon$. Assume
first that the outcome of the algorithm is a cut $(A,B)$ with
$|E_{G}(A,B)|\leq\frac{1024d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}=\varphi\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}$,
and $|T\cap A|,|T\cap B|\geq\frac{\alpha k}{8}$. In this case, we return the
cut $(A,B)$ as the outcome of the algorithm. Otherwise, the outcome of the
algorithm from Theorem 9.1 is a routing ${\mathcal{P}}$ in $G$ of a subset
${M}^{\prime}\subseteq{M}$ containing at least $k\cdot(1-\alpha)$ pairs of
vertices, such that every path in ${\mathcal{P}}$ has length at most
$d\leq\frac{2^{O(1/\epsilon^{6})}\cdot\log n}{\varphi}$, and the total
congestion caused by the paths in ${\mathcal{P}}$ is at most
$\frac{4\eta}{\alpha}\leq\frac{2^{O(1/\epsilon^{5})}\cdot\log
n}{\alpha\cdot\varphi^{2}}$. We then return this set of paths as the outcome
of the algorithm.

The running time of the algorithm from Theorem 9.1 is bounded by:

$O\left(m^{1+O(\epsilon)}(d^{2}+\eta d)\right)\leq
O\left(m^{1+O(\epsilon)}\left(\frac{2^{O(1/\epsilon^{6})}\cdot\log^{2}n}{\varphi^{2}}+\frac{2^{O(1/\epsilon^{6})}\cdot\log^{2}n}{\varphi^{3}}\right)\right)\leq
O\left(\frac{m^{1+O(\epsilon)}}{\varphi^{3}}\right).$

Next, we consider the case where $\frac{1}{\alpha}>\log n$. In this case, we
perform at most $\log n$ iterations. At the beginning of iteration $i$, we are
given a collection ${M}_{i}\subseteq{M}$ of pairs of vertices that have been
already routed, together with their routing ${\mathcal{P}}_{i}$ in graph $G$.
At the beginning of the algorithm, ${M}_{1}=\emptyset$ and
${\mathcal{P}}_{1}=\emptyset$. The iterations continue as long as
$|{M}_{i}|<(1-\alpha)k$ holds.

We now describe the execution of the $i$th iteration. Let
${M}^{\prime}_{i}={M}\setminus{M}_{i}$, and recall that
$|{M}^{\prime}_{i}|\geq\alpha k$ must hold. We apply the algorithm from
Theorem 9.1 to graph $G$, the set ${M}^{\prime}_{i}$ of pairs of its vertices,
and parameters $d,\eta,\alpha^{\prime}=1/2$ and $\epsilon$. Assume first that
the outcome of the algorithm is a cut $(A,B)$ with
$|E_{G}(A,B)|\leq\frac{1024d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}=\varphi\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}$,
and $|T\cap A|,|T\cap B|\geq\frac{|{M}^{\prime}_{i}|}{16}\geq\frac{\alpha
k}{16}$. In this case, we terminate the algorithm and return the cut $(A,B)$
as the outcome of the algorithm. Otherwise, the outcome of the algorithm from
Theorem 9.1 is a routing $\tilde{\mathcal{P}}_{i}$ in $G$ of a subset
$\tilde{M}_{i}\subseteq{M}^{\prime}_{i}$ containing at least
$|{M}^{\prime}_{i}|/2$ pairs of vertices, such that every path in
$\tilde{\mathcal{P}}_{i}$ has length at most
$d\leq\frac{2^{O(1/\epsilon^{6})}\cdot\log n}{\varphi}$, and the total
congestion caused by the paths in $\tilde{\mathcal{P}}_{i}$ is at most
$8\eta\leq\frac{2^{O(1/\epsilon^{6})}\cdot\log n}{\varphi^{2}}$. We then set
${M}_{i+1}={M}_{i}\cup\tilde{M}_{i}$,
${\mathcal{P}}_{i+1}={\mathcal{P}}_{i}\cup\tilde{\mathcal{P}}_{i}$, and
continue to the next iteration.

Assume that the last iteration of the algorithm is iteration $i$. If the
algorithm did not terminate with a cut, then $|{M}_{i+1}|\geq(1-\alpha)k$ must
hold. We then return the set ${M}^{\prime}={M}_{i+1}$ of pairs of vertices,
and their routing ${\mathcal{P}}={\mathcal{P}}_{i+1}$. It is easy to verify
that the cardinality of the set ${M}^{\prime}_{i^{\prime}}$ of pairs of
vertices that remains to be routed decreases by at least factor $2$ in every
iteration, and so the number of iterations in the algorithm is bounded by
$\log k$. Since, for every iteration $i^{\prime}$, the congestion caused by
the set $\tilde{\mathcal{P}}_{i^{\prime}}$ of paths is at most
$\frac{2^{O(1/\epsilon^{6})}\cdot\log n}{\varphi^{2}}$, the total congestion
caused by the set ${\mathcal{P}}$ of paths is at most
$\frac{2^{O(1/\epsilon^{6})}\cdot\log^{2}n}{\varphi^{2}}$. The running time of
a single iteration is bounded by
$O\left(\frac{m^{1+O(\epsilon)}}{\varphi^{3}}\right)$ as before, and, since
the number of iterations is $O(\log n)$, the total running time of the
algorithm remains bounded by
$O\left(\frac{m^{1+O(\epsilon)}}{\varphi^{3}}\right)$.

In the remainder of this section we prove Theorem 9.1. Following is a key
lemma that we use in the proof.

######  Lemma 9.2.

There is a large enough constant $c^{*}$, and a deterministic algorithm, whose
input consists of a connected $m$-edge graph $G$ with $|V(G)|\leq n$, a
collection ${M}=\left\\{(s_{1},t_{1}),\ldots,(s_{k},t_{k})\right\\}$ of pairs
of vertices of $G$, such that ${M}$ is a matching, and parameters $d,\eta>0$
and $\frac{2}{(\log n)^{1/24}}<\epsilon<\frac{1}{400}$, such that $1/\epsilon$
is an integer, and $128d<\eta\leq\frac{d^{2}}{2^{c^{*}/\epsilon^{6}}\cdot\log
m}$ holds. The algorithm computes one of the following:

  * •

either a cut $(A,B)$ with
$|E_{G}(A,B)|\leq\frac{64d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}$,
and each of $A$, $B$ contains at least $\frac{k^{1-\epsilon}}{16}$ vertices of
set $T=\left\\{s_{1},t_{1},\ldots,s_{k},t_{k}\right\\}$; or

  * •

a routing ${\mathcal{P}}$ in $G$ of a subset ${M}^{\prime}\subseteq{M}$
containing at least $z=\frac{k^{1-22\epsilon}}{d}$ pairs of vertices, such
that every path in ${\mathcal{P}}$ has length at most $d$, and the total
congestion caused by the paths in ${\mathcal{P}}$ is at most $\eta$.

The running time of the algorithm is bounded by
$O\left(m^{1+O(\epsilon)}(\eta+d\log n)\right)$.

We defer the proof of Lemma 9.2 to Section 9.1, after we complete the proof of
Theorem 9.1 using it. Our algorithm iteratively applies the algorithm from
Lemma 9.2, while gradually constructing both a routing of some pairs from
${M}$, and a low-conductance cut in $G$.

Let $\eta^{\prime}=\frac{4\eta}{\alpha}$. Our algorithm consists of two
stages. In the first stage, we either construct the desired routing
${\mathcal{P}}$ of a large subset ${M}^{\prime}\subseteq{M}$ of pairs of
vertices, or compute a collection ${\mathcal{S}}$ of disjoint subsets of
vertices of $G$ with some useful properties. In the former case, we terminate
the algorithm and return the resulting routing ${\mathcal{P}}$, while in the
latter case we continue to Stage 2, in which we exploit the collection
${\mathcal{S}}$ of vertex subsets, in order to construct the desired low-
conductance cut $(A,B)$. We now describe each of the two stages in turn.

### Stage 1: Constructing a Routing

Let $q^{\prime}=4d\cdot k^{22\epsilon}\cdot\log k$. Our algorithm in Stage 1
consists of at most $q^{\prime}$ iterations. At the beginning of iteration
$q$, we are given a subset ${M}^{\prime}_{q}\subseteq{M}$ of pairs of vertices
with $|{M}^{\prime}_{q}|<(1-\alpha)\cdot k$, and a routing ${\mathcal{P}}_{q}$
of the matching ${M}^{\prime}_{q}$ in graph $G$. Additionally, we are given a
collection ${\mathcal{S}}_{q}$ of disjoint subsets of vertices of $G$, and we
denote $A_{q}=\bigcup_{S\in{\mathcal{S}}_{q}}S$. We will ensure that the
following invariants hold:

  1. I1.

every path in ${\mathcal{P}}_{q}$ has length at most $d$;

  2. I2.

$|{\mathcal{P}}_{q}|<(1-\alpha)k$;

  3. I3.

the paths in ${\mathcal{P}}_{q}$ cause congestion at most $\eta^{\prime}$ in
$G$;

  4. I4.

if we denote by $E^{\prime}_{q}$ the set of all edges that lie on at least
$\eta^{\prime}/2$ paths in ${\mathcal{P}}_{q}$, then
$\left|\left(\bigcup_{S\in{\mathcal{S}}_{q}}\delta_{G}(S)\right)\setminus
E^{\prime}_{q}\right|\leq\frac{64d}{\eta}\sum_{S\in{\mathcal{S}}_{q}}\left|E_{G}(S)\right|$;
and

  5. I5.

$|A_{q}\cap T|<\frac{\alpha k}{2}$.

At the beginning of the algorithm, we set ${\mathcal{P}}_{1}=\emptyset$ and
${\mathcal{S}}_{1}=\emptyset$, so $A_{1}=\emptyset$ holds. Clearly, all
invariants hold for this setting. We now describe the execution of the $q$th
iteration, for some $q\geq 1$. We assume that we are given a set
${M}^{\prime}_{q}\subseteq{M}$ of pairs of vertices, a set ${\mathcal{P}}_{q}$
of paths routing the pairs in ${M}^{\prime}_{q}$ in $G$, and a collection
${\mathcal{S}}_{q}$ of disjoint subsets of vertices of $G$, for which
invariants I1–I5 hold.

We let ${M}_{q}$ be a set of pairs of vertices of $G$, containing all pairs
$(s_{i},t_{i})\in{M}\setminus{M}^{\prime}_{q}$ with $s_{i},t_{i}\in
V(G)\setminus A_{q}$. We also let $G_{q}$ be the graph obtained from $G$,
after we delete from it all vertices of $A_{q}$, and all edges $e\in E(G)$,
such that $e$ that belongs to at least $\eta^{\prime}/2$ paths of
${\mathcal{P}}_{q}$. In other words, $G_{q}=(G\setminus A_{q})\setminus
E^{\prime}_{q}$. Denote $k_{q}=|{M}_{q}|$. Since, from Invariant I5,
$|A_{q}\cap T|<\frac{\alpha k}{2}$, while from Invariant I2,
$|{M}\setminus{M}^{\prime}_{q}|\geq k-|{\mathcal{P}}_{q}|\geq\alpha k$, we get
that $k_{q}>\frac{\alpha k}{2}$ must hold. Notice that graph $G_{q}$ may not
be connected. We assume first that there is some connected component $C_{q}$
of graph $G_{q}$, and a subset $\tilde{M}_{q}\subseteq{M}_{q}$ containing at
least $k_{q}/2$ pairs, such that all vertices participating in the pairs in
$\tilde{M}_{q}$ lie in $C_{q}$.

We apply the algorithm from Lemma 9.2 to graph $C_{q}$, the set
$\tilde{M}_{q}$ of pairs of vertices, and parameters $d,\eta,\epsilon$ that
remain unchanged. We now consider two cases. The first case happens if the
algorithm from Lemma 9.2 returns a cut $(X_{q},Y_{q})$ in graph $C_{q}$, with
$|E_{G_{q}}(X_{q},Y_{q})|\leq\frac{64d}{\eta}\cdot\min\left\\{|E_{G_{q}}(X_{q})|,|E_{G_{q}}(Y_{q})|\right\\}\leq\frac{64d}{\eta}\cdot\min\left\\{|E_{G}(X_{q})|,|E_{G}(Y_{q})|\right\\}$.
Recall that we are also guaranteed that each of $X_{q}$, $Y_{q}$ contains at
least $\frac{k_{q}^{1-\epsilon}}{32}$ vertices of set
$T^{\prime}=\left\\{s_{i},t_{i}\mid(s_{i},t_{i})\in\tilde{M}_{q}\right\\}$. We
say that iteration $q$ is a _type-1 iteration_. We assume w.l.o.g. that
$|X_{q}\cap T^{\prime}|\leq|Y_{q}\cap T^{\prime}|$. We set
${\mathcal{S}}_{q+1}={\mathcal{S}}_{q}\cup\left\\{X_{q}\right\\}$, and we let
${M}^{\prime}_{q+1}={M}^{\prime}_{q}$ and
${\mathcal{P}}_{q+1}={\mathcal{P}}_{q}$. It is immediate to verify that
Invariants I1–I3 continue to hold for ${\mathcal{P}}_{q+1}$. It is also
immediate to verify that $E^{\prime}_{q+1}=E^{\prime}_{q}$. Therefore,
$\left|\left(\bigcup_{S\in{\mathcal{S}}_{q}}\delta_{G}(S)\right)\setminus
E^{\prime}_{q+1}\right|\leq\frac{64d}{\eta}\sum_{S\in{\mathcal{S}}_{q}}\left|E_{G}(S)\right|$.
Let
$E^{*}_{q}=\left(\left(\bigcup_{S\in{\mathcal{S}}_{q+1}}\delta_{G}(S)\right)\setminus\left(\bigcup_{S\in{\mathcal{S}}_{q}}\delta_{G}(S)\right)\right)\setminus
E^{\prime}_{q}$. Then $E^{*}_{q}=E_{G_{q}}(X_{q},Y_{q})$, and we are
guaranteed that $|E^{*}_{q}|\leq\frac{64d}{\eta}\cdot|E_{G}(X_{q})|$.
Therefore, we get that:

$\begin{split}\left|\left(\bigcup_{S\in{\mathcal{S}}_{q+1}}\delta_{G}(S)\right)\setminus
E^{\prime}_{q+1}\right|&\leq\left|\left(\bigcup_{S\in{\mathcal{S}}_{q}}\delta_{G}(S)\right)\setminus
E^{\prime}_{q+1}\right|+|E^{*}_{q}|\\\
&\leq\frac{64d}{\eta}\sum_{S\in{\mathcal{S}}_{q}}|E_{G}(S)|+\frac{64d}{\eta}\cdot|E_{G}(X_{q})|\\\
&\leq\frac{64d}{\eta}\sum_{S\in{\mathcal{S}}_{q+1}}|E_{G}(S)|.\end{split}$

Therefore, Invariant I4 continues to hold for ${\mathcal{S}}_{q+1}$. If
Invariant I5 continues to hold as well, then we continue to the next
iteration. Otherwise, we terminate the first stage, and continue to the second
stage.

Consider now the second case, when the algorithm from Lemma 9.2 returns a
routing ${\mathcal{R}}_{q}$ in $C_{q}$ of a subset
${M}^{*}_{q}\subseteq\tilde{M}_{q}$ containing at least
$\frac{k_{q}^{1-22\epsilon}}{2d}$ pairs of vertices, such that every path in
${\mathcal{R}}_{q}$ has length at most $d$, and the total congestion caused by
the paths in ${\mathcal{R}}_{q}$ is at most $\eta$. In this case, we say that
iteration $q$ is a _type-2 iteration_. We set
${\mathcal{P}}_{q+1}={\mathcal{P}}_{q}\cup{\mathcal{R}}_{q}$ and
${M}^{\prime}_{q+1}={M}^{\prime}_{q}\cup{M}^{*}_{q}$. Clearly,
${\mathcal{P}}_{q+1}$ is a routing of the pairs in ${M}^{\prime}_{q+1}$ in
graph $G$, and every path in ${\mathcal{P}}_{q+1}$ has length at most $d$.
Furthermore, since the edges of $G$ that participate in at least
$\eta^{\prime}/2$ paths in ${\mathcal{P}}_{q}$ do not lie in graph $G_{q}$,
and since $\eta<\eta^{\prime}/2$, we get that the total congestion that the
paths of ${\mathcal{P}}_{q+1}$ cause in graph $G$ is at most $\eta^{\prime}$.
We also set ${\mathcal{S}}_{q+1}={\mathcal{S}}_{q}$. Since
$E^{\prime}_{q}\subseteq E^{\prime}_{q+1}$, it is easy to verify that
Invariant I4 continues to hold for ${\mathcal{S}}_{q+1}$, and it is immediate
to verify that Invariant I5 holds as well. If
$|{\mathcal{P}}_{q+1}|\geq(1-\alpha)k$, then we terminate the algorithm and
return the set ${M}^{\prime}={M}_{q+1}$ of pairs of vertices and the set
${\mathcal{P}}={\mathcal{P}}_{q+1}$ of paths. From the above discussion, the
paths in ${\mathcal{P}}$ are a routing of the pairs in ${M}^{\prime}$; every
path in ${\mathcal{P}}$ has length at most $d$, and the paths in
${\mathcal{P}}$ cause congestion at most $\eta^{\prime}$. Otherwise, if
$|{\mathcal{P}}_{q+1}|<(1-\alpha)k$, then from the above discussion, all
invariants hold for ${\mathcal{P}}_{q+1}$ and ${\mathcal{S}}_{q+1}$, and we
continue to the next iteration.

It remains to consider the case where for every connected component $C$ of
graph $G_{q}$, the number of demand pairs $(s_{i},t_{i})\in{M}_{q}$ with
$s_{i},t_{i}\in V(C)$ is less than $k_{q}/2$. Let ${\mathcal{C}}$ denote the
set of all connected components of $G_{q}$, and let
$T^{\prime}=\left\\{s_{i},t_{i}\mid(s_{i},t_{i})\in{M}_{q}\right\\}$, so
$|T^{\prime}|=2k_{q}$. For each component $C\in{\mathcal{C}}$, let
$n_{C}=|V(C)\cap T^{\prime}|$. Then for all $C\in{\mathcal{C}}$, $n_{C}\leq
1.5k_{q}$ must hold. Let $(A^{\prime},B^{\prime})$ be a partition of
$V(G_{q})$, that is computed as follows. We denote
${\mathcal{C}}=\left\\{C_{1},C_{2},\ldots,C_{r}\right\\}$, where the
components are indexed so that $n_{C_{1}}\geq n_{C_{2}}\geq\cdots\geq
n_{C_{r}}$. We start with $A^{\prime}=B^{\prime}=\emptyset$, and consider the
components of ${\mathcal{C}}$ in the order of their indices. When component
$C_{i}$ is processed, if $|A^{\prime}\cap T^{\prime}|\leq|B^{\prime}\cap
T^{\prime}|$, then we add the vertices of $C_{i}$ to $A^{\prime}$, and
otherwise we add the vertices of $C_{i}$ to $B^{\prime}$. Consider the
partition $(A^{\prime},B^{\prime})$ of the vertices of $V(G_{q})$ that we
obtain at the end of the algorithm, and assume w.l.o.g. that $|A^{\prime}\cap
T^{\prime}|\geq|B^{\prime}\cap T^{\prime}|$. It is easy to verify that
$|A^{\prime}\cap T^{\prime}|-|B^{\prime}\cap
T^{\prime}|\leq\max_{i}\left\\{n_{C_{i}}\right\\}\leq n_{C_{1}}\leq 1.5k_{q}$.
Since $|T^{\prime}|=2k_{q}$, we then get that $|A^{\prime}\cap
T^{\prime}|,|B^{\prime}\cap T^{\prime}|\geq\frac{k_{q}}{4}\geq\frac{\alpha
k}{8}$. We obtain a cut $(A,B)$ in graph $G$ by letting $A=A^{\prime}\cup
A_{q}$ and $B=B^{\prime}$. Clearly, $|A\cap T|,|B\cap T|\geq\frac{\alpha
k}{8}$. Next, we show that
$|E_{G}(A,B)|\leq\frac{1024d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}$.
Indeed, it is immediate to verify that $E_{G}(A,B)\subseteq E^{\prime}_{q}$.
Since the paths in ${\mathcal{P}}_{q}$ have length at most $d$ each, and since
$\eta^{\prime}=\frac{4\eta}{\alpha}$, we get that
$|E^{\prime}_{q}|\leq\frac{2|{\mathcal{P}}_{q}|\cdot
d}{\eta^{\prime}}\leq\frac{\alpha kd}{2\eta}$. On the other hand, since graph
$G$ is connected, and since $|A|\geq\frac{\alpha k}{8}$, we get that
$|E_{G}(A)|+|E_{G}(A,B)|\geq\frac{\alpha k}{16}$. Similarly,
$|E_{G}(B)|+|E_{G}(A,B)|\geq\frac{\alpha k}{16}$. Altogether, we get that:
$|E^{\prime}_{q}|\leq\frac{\alpha
kd}{2\eta}\leq\frac{8d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}+\frac{8d}{\eta}|E_{G}(A,B)|$.
Since $\eta\geq 128d$, we get that:

$|E_{G}(A,B)|\leq|E^{\prime}_{q}|\leq\frac{8d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}+\frac{|E_{G}(A,B)|}{2},$

and so:

$|E_{G}(A,B)|\leq\frac{1024d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}.$

In this case, we terminate the algorithm and return the cut $(A,B)$. We say
that the current iteration is a type-1 iteration.

This completes the description of the first stage of the algorithm. We now
show that the number of iteration in this stage is bounded by $q^{\prime}$,
and bound the running time of the algorithm.

######  Observation 9.3.

The number of iterations in the algorithm is bounded by $q^{\prime}=4d\cdot
k^{22\epsilon}\cdot\log k$.

###### Proof.

We partition the execution of the algorithm into phases. For all $i\geq 1$,
the $i$th phase includes all iterations $q$, for which
$\frac{k}{2^{i}}<|{M}_{q}|\leq\frac{k}{2^{i-1}}$. Clearly, the number of
phases is bounded by $\log k$. Next, we bound the number of iterations in a
single phase.

Consider some integer $i$, and denote by $n_{i}=\frac{k}{2^{i}}$. If iteration
$q$ is a type-2 iteration that belongs to phase $i$, then $k_{q}=|{M}_{q}|\geq
n_{i}$, and, from Lemma 9.2, at least $\frac{n_{i}^{1-22\epsilon}}{2d}$ pairs
of vertices are routed in iteration $q$. Therefore, after $2d\cdot
n_{i}^{22\epsilon}$ type-2 iterations, the number of pairs that remain to be
routed must decrease by at least factor $2$. We conclude that the $i$th phase
may contain at most $2d\cdot n_{i}^{22\epsilon}\leq 2d\cdot k^{22\epsilon}$
type-2 iterations.

If iteration $q$ is a type-2 iteration in phase $i$, then we are guaranteed
that set $X_{q}$ contains at least $\frac{n_{i}^{1-\epsilon}}{32}$ terminals
that participate in pairs in ${M}_{q}$. Therefore, after
$32n_{i}^{\epsilon}\leq 32k^{\epsilon}$ type-1 iterations, the number of
terminals in $V(G)\setminus A_{q}$ that remain to be routed (that is, the
terminals of ${M}_{q}$), must decrease by at least factor $4$. We conclude
that a single phase may contain at most $32k^{\epsilon}$ type-1 iterations.

Overall, a single phase may contain at most $2d\cdot
k^{22\epsilon}+32k^{\epsilon}\leq 3d\cdot k^{22\epsilon}$ iterations, and the
total number of iterations in the algorithm is bounded by
$3dk^{22\epsilon}\log k\leq q^{\prime}$.

Since the running time of the algorithm from Lemma 9.2 is bounded by
$O\left(m^{1+O(\epsilon)}(\eta+d\log n)\right)$, the total running time of the
first stage of the algorithm algorithm is bounded by
$O\left(m^{1+O(\epsilon)}(\eta d+d^{2}\log n)\right)\leq
O\left(m^{1+O(\epsilon)}(\eta d+d^{2})\right)$, since $\epsilon>\frac{2}{(\log
n)^{1/24}}$, so $n^{\epsilon}>n^{2/(\log n)^{1/24}}>2^{(\log n)^{3/24}}>\log
n$.

### Stage 2: Computing the Cut

Assume that the last iteration of the algorithm was iteration $q$. Let
$E^{\prime}$ be the set of all edges $e\in E(G)$, such that $e$ belongs to at
least $\eta^{\prime}/2$ paths of ${\mathcal{P}}_{q}$. Since the paths in
${\mathcal{P}}_{q}$ have length at most $d$ each, and since
$\eta^{\prime}=\frac{4\eta}{\alpha}$, we get that
$|E^{\prime}|\leq\frac{2|{\mathcal{P}}_{q}|\cdot
d}{\eta^{\prime}}\leq\frac{\alpha kd}{2\eta}$. Let $G^{\prime}=G\setminus
E^{\prime}$. In the second stage, we will compute a cut $(A,B)$ in graph
$G^{\prime}$, with
$|E_{G^{\prime}}(A,B)|\leq\frac{512d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}$,
so that each of $A,B$ contains at least $\frac{\alpha k}{8}$ vertices of $T$.
Assume w.l.o.g. that $|E_{G}(A)|\leq|E_{G}(B)|$. Since graph $G$ is connected,
and since $|A|\geq\frac{\alpha k}{8}$, we get that
$|E_{G}(A)|+|E_{G}(A,B)|\geq\frac{\alpha k}{16}$. Therefore,
$|E^{\prime}|\leq\frac{\alpha
kd}{2\eta}\leq\frac{8d}{\eta}\left(|E_{G}(A)|+|E_{G}(A,B)|\right)$. We then
get that:

$\begin{split}|E_{G}(A,B)|&\leq|E_{G^{\prime}}(A,B)|+|E^{\prime}|\\\
&\leq\frac{512d}{\eta}|E_{G}(A)|+\frac{8d}{\eta}\left(|E_{G}(A)|+|E_{G}(A,B)|\right)\\\
&\leq\frac{520d}{\eta}|E_{G}(A)|+\frac{8d}{\eta}|E_{G}(A,B)|.\end{split}$

Since $\eta\geq 256d$, we get that
$|E_{G}(A,B)|\leq\frac{1024d}{\eta}|E_{G}(A)|=\frac{1024d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}$.
In the remainder of the algorithm, it is enough to compute a cut $(A,B)$ in
graph $G^{\prime}$, with
$|E_{G^{\prime}}(A,B)|\leq\frac{512d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}$,
so that each of $A,B$ contains at least $\frac{\alpha k}{8}$ vertices of $T$.

Recall that the last iteration of the algorithm was iteration $q$, and in
iteration $q$ we have computed a cut $(X_{q},Y_{q})$ of the connected
component $C_{q}$ of the corresponding graph $G_{q}$. We denote
$Y^{\prime}_{q}=V(G_{q})\setminus X_{q}$, so $Y_{q}\subseteq Y^{\prime}_{q}$.
We have also defined a set ${\mathcal{S}}_{q+1}$ of disjoint subsets of
vertices, with $X_{q}\in{\mathcal{S}}_{q+1}$. Let
${\mathcal{S}}^{\prime}={\mathcal{S}}_{q+1}\cup\left\\{Y^{\prime}_{q}\right\\}$.
From the description of the algorithm, it is immediate to verify that the
subsets of vertices in ${\mathcal{S}}^{\prime}$ are all disjoint, and they
partition $V(G)$. Since the algorithm terminated at iteration $q$, we are
guaranteed that $|A_{q+1}\cap T|\geq\frac{\alpha k}{2}$. Additionally, if
$T^{\prime}$ denotes the set of all terminals participating in the demand
pairs in $\tilde{M}_{q}$, then at least $k_{q}$ terminals from $T^{\prime}$
lie in $C_{q}$. Since we have assumed that $|X_{q}\cap
T^{\prime}|\leq|Y_{q}\cap T^{\prime}|$, we get that $|Y^{\prime}_{q}\cap
T^{\prime}|\geq\frac{k_{q}}{2}\geq\frac{\alpha k}{4}$.

Let
$E^{\prime\prime}=\bigcup_{S\in{\mathcal{S}}_{q+1}}\delta_{G^{\prime}}(S)=\left(\bigcup_{S\in{\mathcal{S}}_{q+1}}\delta_{G}(S)\right)\setminus
E^{\prime}=\left(\bigcup_{S\in{\mathcal{S}}_{q+1}}\delta_{G}(S)\right)\setminus
E^{\prime}_{q+1}$. Recall that we have established that Invariant I4 holds for
${\mathcal{S}}_{q+1}$, so
$|E^{\prime\prime}|\leq\frac{64d}{\eta}\sum_{S\in{\mathcal{S}}_{q+1}}|E_{G}(S)|$.

We now consider two cases. The first case happens if
$|E_{G}(Y^{\prime}_{q})|\geq\frac{\eta}{256d}|E^{\prime\prime}|$. In this
case, we consider the cut $(A,B)$ in graph $G^{\prime}$, where
$B=Y^{\prime}_{q}$ and $A=V(G)\setminus Y^{\prime}_{q}$. From the above
discussion $|B\cap T|\geq\frac{\alpha k}{4}$, and $|A\cap T|=|A_{q+1}\cap
T|\geq\frac{\alpha k}{2}$. Moreover,
$|E_{G^{\prime}}(A,B)|\leq|E^{\prime\prime}|\leq\frac{64d}{\eta}\sum_{S\in{\mathcal{S}}_{q+1}}|E_{G}(S)|\leq\frac{64d}{\eta}|E_{G}(A)|$.
Altogether, we get that
$|E_{G^{\prime}}(A,B)|\leq|E^{\prime\prime}|\leq\frac{256d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}$,
as required.

From now on we consider the second case, where
$|E_{G}(Y^{\prime}_{q})|<\frac{\eta}{256d}|E^{\prime\prime}|$. We compute a
partition $(A^{\prime},B^{\prime})$ of $V(G)\setminus Y^{\prime}_{q}$ as
follows. Assume w.l.o.g. that
${\mathcal{S}}_{q+1}=\left\\{S_{1},S_{2},\ldots,S_{r}\right\\}$, where the
sets are indexed so that
$|E_{G}(S_{1})|\geq|E_{G}(S_{2})|\geq\cdots\geq|E_{G}(S_{r})|$. We start with
$A^{\prime}=B^{\prime}=\emptyset$, and then consider the sets
$S_{1},\ldots,S_{r}$ in this order. When set $S_{i}$ is considered, if
$|E_{G}(A^{\prime})|\leq|E_{G}(B^{\prime})|$, then we add the vertices of
$S_{i}$ to $A^{\prime}$, and otherwise we add the vertices of $S_{i}$ to
$B^{\prime}$. Consider the partition $(A^{\prime},B^{\prime})$ of
$V(G)\setminus Y^{\prime}_{q}$ that we obtain at the end of this algorithm. If
$|A^{\prime}\cap T|<|B^{\prime}\cap T|$, then we set $A=A^{\prime}\cup
Y^{\prime}_{q}$ and $B=B^{\prime}$. Otherwise, we set $A=A^{\prime}$ and
$B=B^{\prime}\cup Y^{\prime}_{q}$. We now show that cut $(A,B)$ has all
required properties. Assume w.l.o.g. that $|A^{\prime}\cap T|<|B^{\prime}\cap
T|$ (the other case is symmetric). Then $|B\cap T|=|B^{\prime}\cap
T|\geq\frac{|A_{q+1}\cap T|}{2}\geq\frac{\alpha k}{4}$. Also, $|A\cap
T|\geq|Y^{\prime}_{q}\cap T|\geq\frac{\alpha k}{2}$. We next show that
$|E^{\prime\prime}|\leq\frac{512d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}$
in the following claim.

######  Claim 9.4.

$|E^{\prime\prime}|\leq\frac{512d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}.$

###### Proof.

Recall that we have denoted
${\mathcal{S}}_{q+1}=\left\\{S_{1},\ldots,S_{r}\right\\}$, where the sets of
vertices $S_{i}$ are indexed in the non-increasing order of the cardinalities
of the corresponding sets of edges $E_{G}(S_{i})$. We use the following
observation.

######  Observation 9.5.

$\sum_{i=2}^{r}|E_{G}(S_{i})|\geq\frac{\eta}{512d}|E^{\prime\prime}|$.

We prove 9.5 below, after we complete the proof of 9.4 using it. Since
$A^{\prime}\subseteq A$ and $B^{\prime}\subseteq B$, it is enough to prove
that
$|E^{\prime\prime}|\leq\frac{512d}{\eta}\cdot\min\left\\{|E_{G}(A^{\prime})|,|E_{G}(B^{\prime})|\right\\}$.
Denote $M=\frac{\eta}{512d}|E^{\prime\prime}|$. We consider two cases. The
first case happens if $|E_{G}(S_{1})|\geq M$. Our algorithm then adds the
vertices of $S_{1}$ to $A^{\prime}$, and it will keep adding vertices from
sets $S_{i}$ to $B^{\prime}$ until
$|E_{G}(B^{\prime})|\geq|E_{G}(A^{\prime})|\geq M$ holds. Therefore, we are
guaranteed that, at the end of the algorithm,
$|E_{G}(A^{\prime})|,|E_{G}(B^{\prime})|\geq
M=\frac{\eta}{512d}|E^{\prime\prime}|$, and so
$|E^{\prime\prime}|\leq\frac{512d}{\eta}\cdot\min\left\\{|E_{G}(A^{\prime})|,|E_{G}(B^{\prime})|\right\\}$.

Consider now the second case, where $|E_{G}(S_{1})|<M$. Assume for
contradiction that
$|E^{\prime\prime}|>\frac{512d}{\eta}\cdot\min\left\\{|E_{G}(A^{\prime})|,|E_{G}(B^{\prime})|\right\\}$,
and assume w.l.o.g. that $|E_{G}(A^{\prime})|\leq|E_{G}(B^{\prime})|$, so
$|E_{G}(A^{\prime})|<\frac{\eta}{512d}|E^{\prime\prime}|$. Recall that, from
Invariant I4,
$\sum_{S\in{\mathcal{S}}_{q+1}}|E_{G}(S)|\geq\frac{\eta}{64d}|E^{\prime\prime}|$.
Since $|E_{G}(A^{\prime})|<\frac{\eta}{512d}|E^{\prime\prime}|$, it must be
the case that $\sum_{\stackrel{{\scriptstyle
S\in{\mathcal{S}}_{q+1}:}}{{S\subseteq
B^{\prime}}}}|E_{G}(S)|>\frac{\eta}{128d}|E^{\prime\prime}|$. Let
$S_{i}\in{\mathcal{S}}_{q+1}$ be the set whose vertices were added to
$B^{\prime}$ last. Then at the time when the vertices of $S_{i}$ were added to
$B^{\prime}$, $|E_{G}(A^{\prime})|<\frac{\eta}{512d}|E^{\prime\prime}|$ held.
Therefore, from our algorithm, at the same time
$|E_{G}(B^{\prime})|<\frac{\eta}{512d}|E^{\prime\prime}|$ held. Therefore, at
the end of the algorithm, $\sum_{\stackrel{{\scriptstyle
S\in{\mathcal{S}}_{q+1}:}}{{S\subseteq
B^{\prime}}}}|E_{G}(S)|\leq\frac{\eta}{512d}|E^{\prime\prime}|+|E_{G}(S_{i})|$.
But since
$|E_{G}(S_{i})|\leq|E_{G}(S_{1})|<M=\frac{\eta}{512d}|E^{\prime\prime}|$, we
get that $\sum_{\stackrel{{\scriptstyle S\in{\mathcal{S}}_{q+1}:}}{{S\subseteq
B^{\prime}}}}|E_{G}(S)|<\frac{\eta}{256d}|E^{\prime\prime}|$ holds at the end
of the algorithm, a contradiction.

In order to complete the proof of 9.4, it is now enough to prove 9.5.

Proof of 9.5. Let $1\leq i_{1}<i_{2}<\cdots<i_{r}=q$ be the indices of type-2
iterations. Recall that for each $1\leq j\leq r$, in iteration $i_{j}$ we
computed a cut $(X_{i_{j}},Y_{i_{j}})$ of the connected component $C_{i_{j}}$
of graph $G_{i_{j}}$, with
$|E_{G_{i_{j}}}(X_{i_{j}},Y_{i_{j}})|\leq\frac{64d}{\eta}\cdot\min\left\\{|E_{G}(X_{i_{j}})|,|E_{G}(Y_{i_{j}})|\right\\}$.

We can then denote
${\mathcal{S}}_{q+1}=\left\\{X_{i_{1}},X_{i_{2}},\ldots,X_{i_{r}}\right\\}$.
For all $1\leq j\leq r$, we define a subset $E_{j}\subseteq E^{\prime\prime}$
of edges that the set $X_{i_{j}}$ of vertices is responsible for. We let
$E_{1}=\delta_{G^{\prime}}(X_{i_{1}})$, and for $1<j\leq r$, we let
$E_{j}=\delta_{G^{\prime}}(X_{i_{j}})\setminus(E_{1}\cup\cdots\cup E_{j-1})$.
It is easy to verify that $(E_{1},\ldots,E_{r})$ is a partition of
$E^{\prime\prime}$.

Consider now some index $1\leq j\leq r$, and the cut $(X_{i_{j}},Y_{i_{j}})$
that our algorithm computed in iteration $i_{j}$. It is easy to verify that
$Y_{i_{j}}\subseteq X_{i_{j}+1}\cup\cdots\cup X_{i_{r}}\cup Y^{\prime}_{q}$.
Moreover, $E_{j}=E_{G_{i_{j}}}(X_{i_{j}},Y_{i_{j}})\setminus E^{\prime}$, and
so, from the above discussion:

$|E_{j}|\leq\frac{64d}{\eta}\cdot\min\left\\{|E_{G}(X_{i_{j}})|,|E_{G}(Y_{i_{j}})|\right\\}.$

Assume w.l.o.g. that $S_{1}=X_{i_{j^{*}}}$. We partition the edges of
$E^{\prime\prime}$ into three subsets: set $\hat{E}_{1}=\bigcup_{1\leq
j<j^{*}}E_{i_{j}}$; set $\hat{E}_{2}=E_{i_{j^{*}}}$; and set
$\hat{E}_{3}=\bigcup_{j^{*}<j\leq r}E_{i_{j}}$. From the discussion so far, we
get that:

$|\hat{E}_{1}|\leq\frac{64d}{\eta}\cdot\sum_{1\leq
j<j^{*}}|E_{G}(X_{i_{j}})|,$

$|\hat{E}_{3}|\leq\frac{64d}{\eta}\cdot\sum_{j^{*}<j\leq
q}|E_{G}(X_{i_{j}})|,$

and

$|\hat{E}_{2}|\leq\frac{64d}{\eta}\cdot|E_{G}(Y_{i_{j^{*}}})|.$

Recall that $Y_{i_{j^{*}}}\subseteq X_{i_{j^{*}}+1}\cup\cdots\cup
X_{i_{r}}\cup Y^{\prime}_{q}$. Therefore, for every edge $e\in
E_{G}(Y_{i_{j^{*}}})$, either both endpoints of $e$ lie in one of the sets
$X_{i_{j}^{*}+1},\cdots,X_{i^{*}_{r}},Y^{\prime}_{q}$ (in which case $e\in
E_{G}(X_{i_{j^{*}}+1})\cup\cdots\cup E_{G}(X_{i_{r}})\cup
E_{G}(Y^{\prime}_{q})$), or the endpoints of $e$ lie in different sets of
$\left\\{X_{i_{j^{*}}+1},\cdots,X_{i_{r}},Y^{\prime}_{q}\right\\}$. In the
latter case, $e\in E_{i_{j^{*}}+1}\cup\cdots E_{r}\cup
E^{\prime}=\hat{E}_{3}\cup E^{\prime}$ must hold. Altogether, we get that:

$\begin{split}|E_{G}(Y_{i_{j^{*}}})|&\leq\sum_{j^{*}<j\leq
r}|E_{G}(X_{i_{j}})|+|E_{G}(Y^{\prime}_{q})|+|\hat{E}_{3}|+|E^{\prime}|\\\
&\leq\left(1+\frac{64d}{\eta}\right)\cdot\sum_{j^{*}<j\leq
r}|E_{G}(X_{i_{j}})|+|E_{G}(Y^{\prime}_{q})|+|E^{\prime}|\\\
&\leq\frac{5}{4}\cdot\sum_{j^{*}<j\leq
r}|E_{G}(X_{i_{j}})|+|E_{G}(Y^{\prime}_{q})|+|E^{\prime}|.\end{split}$

(since $\eta>256d$).

Recall that $|E^{\prime}|\leq\frac{\alpha kd}{2\eta}\leq\frac{\alpha k}{512}$,
while $|Y_{q}|\geq|T\cap Y_{q}|\geq\frac{\alpha k}{4}$. Since $Y_{q}$ is a set
of vertices of a connected component of $G_{q}$,
$|E_{G_{q}}(Y_{q})|+|E_{G_{q}}(X_{q},Y_{q})|\geq\frac{|Y_{q}|}{2}\geq\frac{\alpha
k}{8}$. Moreover, we are guaranteed that
$|E_{G_{q}}(X_{q},Y_{q})|\leq\frac{64d}{\eta}\cdot|E_{G_{q}}(Y_{q})|\leq\frac{|E_{G_{q}}(Y_{q})|}{4}$.
Therefore,
$|E_{G}(Y^{\prime}_{q})|\geq|E_{G}(Y_{q})|\geq|E_{G_{q}}(Y_{q})|\geq\frac{\alpha
k}{10}$, and so $|E^{\prime}|\leq\frac{\alpha
k}{512}\leq\frac{|E_{G}(Y^{\prime}_{q})|}{50}$. Overall, we get that:

$|E_{G}(Y_{i_{j^{*}}})|\leq\frac{5}{4}\cdot\sum_{j^{*}<j\leq
r}|E_{G}(X_{i_{j}})|+\frac{51|E_{G}(Y^{\prime}_{q})|}{50}.$

Altogether:

$|\hat{E}_{2}|\leq\frac{80d}{\eta}\sum_{j^{*}<j\leq
r}|E_{G}(X_{i_{j}})|+\frac{80d}{\eta}|E_{G}(Y^{\prime}_{q})|,$

and:

$|E^{\prime\prime}|=|\hat{E}_{1}|+|\hat{E}_{2}|+|\hat{E}_{3}|\leq\frac{144d}{\eta}\sum_{a=2}^{r}|E_{G}(S_{a})|+\frac{80d}{\eta}|E_{G}(Y^{\prime}_{q})|.$

Recall that we have assumed that
$|E_{G}(Y^{\prime}_{q})|<\frac{\eta}{256d}|E^{\prime\prime}|$. Therefore, we
get that
$|E^{\prime\prime}|\leq\frac{144d}{\eta}\sum_{a=2}^{r}|E_{G}(S_{a})|+\frac{|E^{\prime\prime}|}{3}$,
and so $\sum_{a=2}^{r}|E_{G}(S_{a})|\geq\frac{\eta}{512d}|E^{\prime\prime}|$.

Since $E_{G^{\prime}}(A,B)\subseteq E^{\prime\prime}$, we get that, in the
second case,
$|E_{G^{\prime}}(A,B)|\leq|E^{\prime\prime}|\leq\frac{512d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}$
holds. To conclude, we have computed a cut $(A,B)$ in graph $G$, with $|A\cap
T|,|B\cap T|\geq\frac{\alpha k}{8}$ and
$|E_{G}(A,B)|\leq\frac{1024d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}$.

Recall that the running time of the first stage of the algorithm is at most
$O\left(m^{1+O(\epsilon)}(d^{2}+\eta d)\right)$, while the running time of the
second stage can be bounded by $O(m)$. Therefore, the total running time of
the algorithm is $O\left(m^{1+O(\epsilon)}(d^{2}+\eta d)\right)$. In order to
prove Theorem 9.1 it now remains to prove Lemma 9.2, which we do next.

###  9.1 Proof of Lemma 9.2

We denote $T=\left\\{s_{1},t_{1},\ldots,s_{k},t_{k}\right\\}$, and for
convenience we denote by $\tilde{k}=|T|=2k$.

The algorithm consists of two stages. In the first stage, we apply the
algorithm from Corollary 5.3 to graph $G$ and the set $T$ of terminals. If the
algorithm returns two subsets $T_{1},T_{2}\subseteq T$ of terminals and a set
$E^{\prime}$ of edges (essentially defining a distancing
$(T_{1},T_{2},E^{\prime})$), then we will use the algorithm from Lemma 4.1 in
order to convert this distancing into a low-conductance cut $(A,B)$ as
required. Otherwise, the algorithm must embed a large graph $H$ into $G$, and
construct a level-$(1/\epsilon)$ hierarchical support structure for $H$, so
that $H$ is $(\eta^{\prime},\tilde{d})$-well-linked with respect to the set
$S(H)$ of vertices defined by the hierarchical support structure. In this
latter case, we continue to Stage 2. In Stage 2, we will initialize an ES-Tree
data structure, rooted at the set $S(H)$ of vertices in graph $G$.
Additionally, we will maintain a data structure from Theorem 7.1 in order to
support approximate short-path queries in graph $H$, as it undergoes edge
deletions. We will use these data structure to iteratively identify pairs
$(s_{i},t_{i})\in{M}$ of vertices, that can be connected via a short path
$P_{i}$ in $G$. The corresponding path $P_{i}$ is then added to the routing
${\mathcal{P}}$ that we are constructing, and every edge of $G$ that currently
appears on $\eta$ paths in ${\mathcal{P}}$ is deleted from $G$. Edges of $H$
whose embedding paths have thus been eliminated will be deleted from $H$. The
algorithm terminates when we can no longer route the remaining paths of
${\mathcal{P}}$ via short paths. If, by that time $|{\mathcal{P}}|\geq z$,
then we return the routing in ${\mathcal{P}}$. Otherwise, we will obtain a
distancing in graph $G$, that can again be converted into a low-conductance
cut. Before we describe each of the two stages, we need to consider an easier
special case where $k\leq n^{\epsilon}$.

####  9.1.1 Special Case: $k\leq n^{\epsilon}$

For all $1\leq i\leq k$, let $A_{i}=\left\\{s_{i}\right\\}$ and
$B_{i}=\left\\{t_{i}\right\\}$. We apply Procedure $\mathsf{ProcPathPeel}$
from Lemma 3.12 to graph $G$ and the collections
$A_{1},B_{1},\ldots,A_{k},B_{k}$ of subsets of its vertices, and parameters
$d$ and $\eta$. Let ${\mathcal{P}}_{1},\ldots,{\mathcal{P}}_{k}$ be the
collection of paths that the algorithm outputs. Then for all $1\leq i\leq k$,
either ${\mathcal{P}}_{i}=\emptyset$, or ${\mathcal{P}}_{i}$ contains a single
path $P_{i}$, connecting $s_{i}$ to $t_{i}$ in $G$. Let
${\mathcal{P}}=\bigcup_{i=1}^{k}{\mathcal{P}}_{i}$, and let
${M}^{\prime}\subseteq{M}$ contain all pairs $(s_{i},t_{i})\in{M}$, such that
some path in ${\mathcal{P}}$ connects $s_{i}$ to $t_{i}$. Clearly,
${\mathcal{P}}$ is a routing of the pairs in ${M}^{\prime}$, and we are
guaranteed that every path in ${\mathcal{P}}$ has length at most $d$, and the
paths in ${\mathcal{P}}$ cause congestion at most $\eta$. Let $E^{\prime}$ be
the set of all edges of $G$ that participate in exactly $\eta$ paths in
${\mathcal{P}}$, and let ${M}^{\prime\prime}={M}\setminus{M}^{\prime}$. From
Property P3, for every pair $(s_{i},t_{i})\in{M}^{\prime\prime}$ of vertices,
$\mbox{\sf dist}_{G\setminus E^{\prime}}(s_{i},t_{i})>d$. Notice also that
$|E^{\prime}|\leq\frac{\sum_{P\in{\mathcal{P}}}|E(P)|}{\eta}\leq\frac{d\cdot|{\mathcal{P}}|}{\eta}$.
Recall that the running time of the algorithm is $O(m\eta+mdk\log n)\leq
O(mn^{O(\epsilon)}d+m\eta)\leq O\left(m^{1+O(\epsilon)}(\eta+d\log n)\right)$.

We now consider two cases. The first case happens if $|{\mathcal{P}}|\geq z$.
In this case, we return the routing ${\mathcal{P}}$ of the set ${M}^{\prime}$
of pairs of vertices.

Consider now the second case, where $|{\mathcal{P}}|<z$. In this case,
$|{M}^{\prime\prime}|\geq k-z\geq k/2$. Let $T^{\prime}\subseteq T$ be the set
of all vertices that participate in the pairs in ${M}^{\prime\prime}$, and let
$\tilde{G}=G\setminus E^{\prime}$. Since, for every pair
$(s_{i},t_{i})\in{M}^{\prime\prime}$ of vertices, $\mbox{\sf
dist}_{\tilde{G}}(s_{i},t_{i})>d$, we get that for every vertex $x\in
T^{\prime}$, $|B_{\tilde{G}}(x,d/2)\cap T^{\prime}|<|T^{\prime}|/2$. Let
$\Delta=\frac{64}{\epsilon}$ and
$\hat{d}=\frac{d}{2\Delta}=\frac{d\epsilon}{128}$. We apply Procedure
$\mathsf{ProcSeparate}$ from Lemma 3.10 to graph $\tilde{G}$, the set
$T^{\prime}$ of terminals, parameters $\Delta$, $\alpha=2/3$, and distance
parameter $\hat{d}$ replacing $d$. Note that the algorithm may not return a
terminal $t\in T^{\prime}$ with $|B_{\tilde{G}}(t,\Delta\cdot\hat{d})\cap
T^{\prime}|=|B_{\tilde{G}}(t,d/2)\cap T^{\prime}|>\alpha|T^{\prime}|$, since,
as observed above, for each such terminal $t$, $|B_{\tilde{G}}(t,d/2)\cap
T^{\prime}|<|T^{\prime}|/2$.

Therefore, the algorithm must return two subsets $T_{1},T_{2}$ of terminals,
with $|T_{1}|=|T_{2}|$, such that
$|T_{1}|\geq\frac{|T^{\prime}|^{1-64/\Delta}}{3}\geq\frac{k^{1-\epsilon}}{16}$.
Moreover, for every pair $t\in T_{1}$, $t^{\prime}\in T_{2}$ of terminals,
$\mbox{\sf dist}_{\tilde{G}}(t,t^{\prime})\geq\hat{d}=\frac{d\epsilon}{128}$.
Recall that the running time of Procedure $\mathsf{ProcSeparate}$ is bounded
by $O(m\cdot|V(G)|^{64/\Delta})\leq O(m^{1+O(\epsilon)})$.

Recall that
$|E^{\prime}|\leq\frac{d|{\mathcal{P}}|}{\eta}\leq\frac{dz}{\eta}=\frac{k^{1-22\epsilon}}{\eta}\leq\frac{16d|T_{1}|}{\eta}$.
Clearly, $(T_{1},T_{2},E^{\prime})$ is a $(\delta,\hat{d})$-distancing in
graph $G$, for some parameter $0<\delta<1$. Let $\varphi=\frac{64d}{\eta}$, so
that $|E^{\prime}|\leq\frac{\varphi|T_{1}|}{4}$. Since $\eta>128d$, we get
that $\varphi<1/2$. Notice also that:

$\hat{d}=\frac{d\epsilon}{256}\geq\frac{\eta\log m}{2d}=\frac{32\log
m}{\varphi},$

since $\eta\leq\frac{d^{2}}{2^{c^{*}/\epsilon^{6}}\cdot\log
m}\leq\frac{d^{2}\epsilon}{256\log m}$ from the statement of Lemma 9.2.

We can now use the algorithm from Lemma 4.1 to compute a cut $(A,B)$ in graph
$G$, with $T_{1}\subseteq A$, $T_{2}\subseteq B$, such that
$|E_{G}(A,B)|\leq\varphi\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}\leq\frac{64d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}$.
We return the cut $(A,B)$ as the outcome of the algorithm. From the above
discussion, $|A\cap T|,|B\cap T|\geq|T_{1}|\geq\frac{k^{1-\epsilon}}{16}$.

The running time of the algorithm from Lemma 4.1 is bounded by $O(m)$, and so
the total running time in Case 1 is bounded by
$O\left(m^{1+O(\epsilon)}(\eta+d\log n)\right)$.

From now on, we assume that $k\geq n^{\epsilon}$. The remainder of the
algorithm consists of two stages, that we now describe.

####  9.1.2 Stage 1: Embedding a Well-Connected Graph

In this stage, we will apply the algorithm from Corollary 5.3 to graph $G$ and
the set $T$ of terminals. In order to be able to do so, we need to ensure that
$\epsilon>\frac{2}{(\log\tilde{k})^{1/12}}$ holds. Recall that
$\tilde{k}=2k\geq 2n^{\epsilon}$ from our assumption. Therefore:

$\frac{2^{12}}{\log\tilde{k}}\leq\frac{2^{12}}{\log(2n^{\epsilon})}\leq\frac{2^{12}}{\epsilon\cdot\log
n}.$

From our assumption that $\epsilon>\frac{2}{(\log n)^{1/24}}$, we get that
$\log n>\frac{2^{24}}{\epsilon^{24}}$. Therefore:

$\frac{2^{12}}{\log\tilde{k}}\leq\frac{\epsilon^{23}}{2^{12}}.$

We conclude that:

$\epsilon>\frac{2}{(\log\tilde{k})^{1/23}}\geq\frac{2}{(\log\tilde{k})^{1/12}}.$
(13)

Let $d^{\prime}=\frac{8d}{2^{c^{*}/\epsilon^{6}}}$ and
$\eta^{\prime}=\frac{8\eta}{2^{c^{*}/\epsilon^{6}}}$. Since
$128d<\eta\leq\frac{d^{2}}{2^{c^{*}/\epsilon^{6}}\cdot\log m}$,
$d^{\prime},\eta^{\prime}>1$. We apply the algorithm from Corollary 5.3 to
graph $G$, set $T$ of terminals, parameters $d^{\prime}$, $\eta^{\prime}$, and
parameter $\epsilon$ that remains unchanged. Recall that the running time of
the algorithm is:

$O\left(k^{1+O(\epsilon)}+m\cdot
k^{O(\epsilon^{3})}\cdot(\eta^{\prime}+d^{\prime}\log m)\right)\leq
O\left(m^{1+O(\epsilon)}(d^{\prime}+\eta^{\prime})\right)\leq
O\left(m^{1+O(\epsilon)}(d+\eta)\right).$

We now consider two cases.

##### Case 1.

The first case happens if the algorithm from Corollary 5.3 returns a pair
$T_{1},T_{2}\subseteq T$ of disjoint subsets of terminals, and a set
$E^{\prime}$ of edges of $G$, such that $|T_{1}|=|T_{2}|$ and
$|T_{1}|\geq\frac{\tilde{k}^{1-4\epsilon^{3}}}{4}\geq\frac{k^{1-4\epsilon^{3}}}{4}$.
Recall that the algorithm also guarantees for every pair $t\in
T_{1},t^{\prime}\in T_{2}$ of terminals, $\mbox{\sf dist}_{G\setminus
E^{\prime}}(t,t^{\prime})>d^{\prime}$.

Moreover, we are guaranteed that:
$|E^{\prime}|\leq\frac{d^{\prime}\cdot|T_{1}|}{\eta^{\prime}}=\frac{d\cdot|T_{1}|}{\eta}$.
Denote $\varphi=\frac{4d}{\eta}$, so that
$|E^{\prime}|\leq\frac{\varphi|T_{1}|}{4}$ holds. Since $\eta>128d$, we get
that $\varphi<1/2$. Since
$\eta\leq\frac{d^{2}}{2^{c^{*}/\epsilon^{6}}\cdot\log m}$, we get that:

$\frac{32\log m}{\varphi}=\frac{8\eta\log
m}{d}\leq\frac{8d}{2^{c^{*}/\epsilon^{6}}}=d^{\prime}.$

We can now apply the algorithm from Lemma 4.1, to compute a cut $(A,B)$ in
graph $G$, with $T_{1}\subseteq A$, $T_{2}\subseteq B$, such that
$|E_{G}(A,B)|\leq\varphi\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}=\frac{4d}{\eta}\cdot\min\left\\{|E_{G}(A)|,|E_{G}(B)|\right\\}$.
The running time of this algorithm is bounded by $O(m)$. We return the cut
$(A,B)$ as the output of the algorithm. Clearly, $|A\cap T|,|B\cap
T|\geq|T_{1}|\geq\frac{k^{1-4\epsilon^{3}}}{4}\geq\frac{k^{1-\epsilon}}{16}$.

##### Case 2.

In the second case, the algorithm from Corollary 5.3 must return a graph $H$
with $V(H)\subseteq T$,
$|V(H)|=N^{1/\epsilon}\geq\tilde{k}-\tilde{k}^{1-\epsilon/2}$, where
$N=\left\lfloor\tilde{k}^{\epsilon}\right\rfloor=\left\lfloor(2k)^{\epsilon}\right\rfloor$,
so that the maximum vertex degree in $H$ is at most
$\tilde{k}^{32\epsilon^{3}}$.

Recall that the algorithm must also return an embedding ${\mathcal{P}}^{*}$ of
$H$ into $G$ via paths of length at most $d^{\prime}$, that cause congestion
at most $\eta^{\prime}\cdot\tilde{k}^{32\epsilon^{3}}$, and a
level-$(1/\epsilon)$ hierarchical support structure for $H$, such that $H$ is
$(\tilde{\eta},\tilde{d})$-well-connected with respect to the set $S(H)$ of
vertices defined by the support structure, where
$\tilde{\eta}=N^{6+256\epsilon}$, and $\tilde{d}=2^{c/\epsilon^{5}}$, with $c$
being the constant used in the definition of the Hierarchical Support
Structure. In this case, we continue to Stage 2 of the algorithm.

This completes the description of the first stage of the algorithm. From the
above analysis, the running time of this stage is bounded by $O\left(m\cdot
n^{O(\epsilon)}(d+\eta)\right)$.

####  9.1.3 Stage 2: Computing the Routing

In this stage, we start with ${\mathcal{P}}=\emptyset$, and then gradually add
paths to ${\mathcal{P}}$. We also maintain a graph $\tilde{G}$, where
initially $\tilde{G}=G$. As the algorithm progresses, every edge $e\in
E(\tilde{G})$ that participates in $\eta$ paths of ${\mathcal{P}}$ is deleted
from $\tilde{G}$. Therefore, we can think of graph $\tilde{G}$ as a dynamic
graph, with edges deleted from $\tilde{G}$ over time. Whenever an edge $e$ is
deleted from graph $\tilde{G}$, for every edge $e^{\prime}\in E(H)$ whose
embedding path $P(e^{\prime})\in{\mathcal{P}}^{*}$ contains $e$, we also
delete edge $e^{\prime}$ from graph $H$. Therefore, graph $H$ can also be
viewed as a dynamic graph. We will maintain the following data structures
throughout the algorithm.

The first data structure, that we denote by ${\mathcal{D}}(H)$, will be used
in order to support approximate shortest-path queries in graph $H$. The data
structure is maintained using the algorithm from Theorem 7.1. Recall that
$N=\left\lfloor\tilde{k}^{\epsilon}\right\rfloor$, and that we have
established in Inequality 13 that
$\frac{2}{(\log\tilde{k})^{1/12}}<\epsilon<1/400$. In order to be able to use
Theorem 7.1, we need to verify that $\frac{N^{\epsilon^{4}}}{\log N}\geq
2^{128/\epsilon^{6}}$ holds. Indeed observe first that, since
$\epsilon>\frac{2}{(\log\tilde{k})^{1/12}}$, we get that

$\tilde{k}^{\epsilon^{8}}>\tilde{k}^{(2/(\log\tilde{k})^{1/12})^{8}}=\tilde{k}^{256/(\log\tilde{k})^{2/3}}>2^{(\log\tilde{k})^{1/3}}>\log\tilde{k}.$

Additionally, from the inequality $\epsilon>\frac{2}{(\log\tilde{k})^{1/12}}$,
we get that $\log\tilde{k}\geq(2/\epsilon)^{12}$, and:

$\tilde{k}\geq 2^{(2/\epsilon)^{12}}$ (14)

Lastly, since $N=\left\lfloor\tilde{k}^{\epsilon}\right\rfloor$ and
$\epsilon<1/400$, we get that:

$\frac{N^{\epsilon^{4}}}{\log
N}\geq\frac{\tilde{k}^{\epsilon^{6}}}{\epsilon\cdot\log\tilde{k}}\geq\tilde{k}^{\epsilon^{6}/2}\geq
2^{128/\epsilon^{6}}.$

We let $q=1/\epsilon$. We maintain the data structure from Theorem 7.1 in
graph $H$, with parameters $j=q$, and parameters $N$ and $\epsilon$ that
remain unchanged. Recall that we are given a level-$q$ hierarchical support
structure for $H$, such that $H$ is $(\tilde{\eta},\tilde{d})$-well-connected
with respect to the set $S(H)$ of vertices defined by the support structure,
where $\tilde{\eta}=N^{6+256\epsilon}=N^{6+256q\epsilon^{2}}=\eta_{q}$, and
$\tilde{d}=2^{c/\epsilon^{5}}=2^{cq/\epsilon^{4}}=\tilde{d}_{q}$, where
$\eta_{q}$ and $\tilde{d}_{q}$ are the parameters that are used in the
definition of the Hierarchical Support Structure.

We denote the data structure that the algorithm from Theorem 7.1 maintains by
${\mathcal{D}}(H)$. Recall that this data structure can withstand the deletion
of up to $\Lambda_{q}=N^{q-8-300q\epsilon^{2}}=N^{q-8-300\epsilon}$ edge
deletions from graph $H$. As long as fewer than $\Lambda_{q}$ edges are
deleted from $H$, the algorithm maintains a decremental set
$S^{\prime}(H)\subseteq V(H)$ of vertices, with
$|S^{\prime}(H)|\geq\frac{N^{q}}{16^{q}}=\frac{|V(H)|}{16^{q}}\geq\frac{k}{2^{8/\epsilon}}$.

The algorithm supports short-path queries between vertices of $S^{\prime}(H)$:
given a pair $x,y\in S^{\prime}(H)$ of vertices, return a path $P$ connecting
$x$ to $y$ in the current graph $H$, whose length is at most
$d^{*}_{q}=2^{O(q/\epsilon^{5})}=2^{O(1/\epsilon^{6})}$, in time $O(|E(P)|)$.

If we denote by $m^{\prime}$ the number of edges in $H$ at the beginning of
the algorithm, then the total update time of the algorithm is bounded by:

$O\left(qN^{q+3}\cdot 2^{O(1/\epsilon^{6})}+m^{\prime}\cdot N^{2}\cdot
2^{O(1/\epsilon^{6})}\right).$

Recall that $N\leq\tilde{k}^{\epsilon}\leq n^{\epsilon}$, and maximum vertex
degree in $H$ is at most $n^{O(\epsilon^{3})}$. Recall also that $N^{q}\leq
n$, and $q=1/\epsilon$. Furthermore, as established in Inequality 14,
$n\geq\tilde{k}\geq 2^{(2/\epsilon)^{12}}$, and so $2^{O(1/\epsilon^{6})}\leq
n^{O(\epsilon)}$. It is then easy to verify that the running time of the
algorithm is bounded by $O\left(n^{1+O(\epsilon)}\right)$.

The second data structure is, intuitively, an ES-Tree in $G$ that is rooted at
the set $S^{\prime}(H)$ of vertices, and whose depth parameter is $d/2$.
Specifically, we maintain a graph $G^{\prime}$, that is defined as follows.
Initially, we obtain graph $G^{\prime}$ from $G$, by adding a source vertex
$s$, that connects to every vertex $v\in S(H)$ with an edge. As the algorithm
progresses and new paths are added to the set ${\mathcal{P}}$ of paths that we
construct, whenever some edge $e\in E(G)$ appears in $\eta$ paths of
${\mathcal{P}}$, we delete $e$ from $G^{\prime}$. For every edge
$e^{\prime}\in E(H)$, whose embedding path $P(e^{\prime})\in{\mathcal{P}}^{*}$
contains edge $e$, we also delete $e^{\prime}$ from $H$, and update data
structure ${\mathcal{D}}(H)$ accordingly. If, as the result of this update,
some vertex $x$ is deleted from set $S^{\prime}(H)$, then we also delete edge
$(s,x)$ from graph $G^{\prime}$. We maintain an ES-Tree data structure in
graph $G^{\prime}$, rooted at vertex $s$, with depth bound $d/2+1$. We denote
the data structure, and the corresponding tree, by $\tau$. The total update
time that is needed in order to maintain the ES-Tree data structure $\tau$ is
bounded by $O(md\log n)$.

Lastly, for every edge $e\in E(G)$, we maintain a list $L(e)$ of all edges
$e^{\prime}\in E(H)$, such that the embedding path
$P(e^{\prime})\in{\mathcal{P}}^{*}$ contains $e$. We also maintain a pointer
from $e$ to every edge in $L(e)$ and back. Recall that the embedding
${\mathcal{P}}^{*}$ causes congestion at most
$\eta^{\prime}\cdot\tilde{k}^{32\epsilon^{3}}$, so the length of each such
list is bounded by $\eta^{\prime}\cdot\tilde{k}^{32\epsilon^{3}}$. Moreover,
the deletion of an edge $e\in E(G)$ from graph $G^{\prime}$ may trigger the
deletion of at most $\eta^{\prime}\cdot\tilde{k}^{32\epsilon^{3}}$ edges from
graph $H$. We will ensure that $|{\mathcal{P}}|\leq z$ holds throughout the
algorithm, and that every path in ${\mathcal{P}}$ has length at most $d$.
Therefore, if we denote by $E^{\prime}\subseteq E(G)$ the collection of all
edges that participate in $\eta$ paths in ${\mathcal{P}}$, the we are
guaranteed that throughout the algorithm:

$|E^{\prime}|\leq\frac{\sum_{P\in{\mathcal{P}}}|E(P)|}{\eta}\leq\frac{|{\mathcal{P}}|\cdot
d}{\eta}\leq\frac{zd}{\eta}.$

Therefore, the total number of edges that may be deleted from graph $H$ over
the course of the algorithm is bounded by:

$\begin{split}\frac{zd}{\eta}\cdot\eta^{\prime}\cdot\tilde{k}^{32\epsilon^{3}}&\leq\tilde{k}^{1-22\epsilon}\cdot\tilde{k}^{32\epsilon^{3}}\\\
&\leq\tilde{k}^{1-21\epsilon}\\\ &\leq\frac{N^{q}\cdot 2^{q}}{N^{21\epsilon
q}}\\\ &<N^{q-9}<\Lambda_{q}\end{split}$

(For the first inequality, we have used the fact that
$z=\frac{k^{1-22\epsilon}}{d}$, $k\leq\tilde{k}$, and
$\eta^{\prime}=\frac{8\eta}{2^{c^{*}/\epsilon^{6}}}\leq\eta$. For the third
inequality we used the fact that
$N=\left\lfloor\tilde{k}^{\epsilon}\right\rfloor$, and $q=1/\epsilon$, so
$N^{q}\leq\tilde{k}\leq N^{q}\cdot 2^{q}$ holds. The fourth inequality follows
since
$2^{q}=2^{1/\epsilon}<\left(\frac{\tilde{k}^{\epsilon}}{2}\right)^{9}\leq
N^{9}$ from Inequality 14.)

If $(s_{i},t_{i})$ is a pair of vertices in ${M}$, then we say that $s_{i}$ is
a _mate_ of $t_{i}$, and $t_{i}$ is a mate of $s_{i}$. Throughout the
algorithm, we will also maintain a subset $S^{\prime\prime}(H)\subseteq
S^{\prime}(H)$ containing all vertices $x\in S^{\prime}(H)$, such that no path
in ${\mathcal{P}}$ has $x$ as its endpoint, and the mate of $x$ still lies in
the tree $\tau$. We also maintain, for every edge $e\in E(G)$, a counter
$n(e)$, counting the number of paths in ${\mathcal{P}}$ that contain $e$.

We are now ready to describe our algorithm. The algorithm consists of at most
$z$ iterations, and they are performed as long as $|{\mathcal{P}}|<z$ and
$S^{\prime\prime}(H)\neq\emptyset$ hold.

In order to perform a single iteration, we let $x$ be any vertex in set
$S^{\prime\prime}(H)$. Assume w.l.o.g. that $x=s_{i}$, and that its mate is
$t_{i}$. Since $x\in S^{\prime\prime}(H)$, vertex $t_{i}$ currently lies in
the tree $\tau$. Using the tree, we can compute a path $Q$ in graph
$G^{\prime}$, that connects $t_{i}$ to some vertex $y\in S(H^{\prime})$, so
that the length of the path is bounded by $d/2$, and the path does not contain
any vertices of $S^{\prime}(H)\setminus\left\\{y\right\\}$. This can be done
in time $O(|E(Q)|)$. Next, using data structure ${\mathcal{D}}(H)$, we compute
a path $\tilde{Q}^{\prime}$ connecting $y$ to $s_{i}$ in graph $H$, such that
the length of the path is bounded by $2^{O(1/\epsilon^{6})}$. This can be done
in time $O(|E(\tilde{Q}^{\prime})|)$. Lastly, by replacing every edge
$e^{\prime}$ on path $\tilde{Q}^{\prime}$ with its embedding path
$P(e^{\prime})\in{\mathcal{P}}^{*}$, we obtain a path $Q^{\prime}$ in graph
$G$, connecting $y$ to $s_{i}$, whose length is bounded by:

$2^{O(1/\epsilon^{6})}\cdot d^{\prime}\leq d/2,$

since $d^{\prime}=\frac{8d}{2^{c^{*}/\epsilon^{6}}}$, and we can assume that
$c^{*}$ is a large enough constant. By combining the paths $Q$ and
$Q^{\prime}$, we obtain a path $P$, connecting $s_{i}$ to $t_{i}$ in graph
$G$, whose length is at most $d$. If path $P$ is not simple, then we convert
it into a simple path, in time $O(d)$. This can be done, for example, by
traversing the vertices of $P$ in the order of their appearance on the path,
and marking every vertex that has been traversed in an array of length $n$.
Whenever we attempt to mark a vertex $v$ that was already marked before, we
recognize that we closed a simple cycle $C\subseteq P$. We can then retrace
this cycle and un-mark all its vertices except for $v$. We delete all vertices
of $C\setminus\left\\{v\right\\}$ from $P$, and continue the traversal of $P$
starting from $v$. Since every vertex on $P$ may be traversed at most twice
(once when we visit it for the first time, and the second time when we remove
a cycle on which that vertex lies), this algorithm takes time $O(d)$, assuming
that we are provided an empty array of length $n$, that can be used in order
to mark and un-mark the vertices of $P$. At the end of this procedure, we un-
mark every vertex of $P$, so the array can be reused in the next iteration. We
denote the resulting simple path $P$ by $P_{i}$, and we add $P_{i}$ to the set
${\mathcal{P}}$ of paths that we maintain.

Next, we consider every edge $e\in E(P_{i})$ one by one. For each such edge
$e$, we increase the counter $n(e)$ by $1$. If $n(e)=\eta$ holds, then we
delete $e$ from graph $G^{\prime}$, and update data structure $\tau$
accordingly. Additionally, for every edge $e^{\prime}\in L(e)$, we delete
$e^{\prime}$ from graph $H$, updating the data structure ${\mathcal{D}}(H)$
accordingly, and we update all lists $L(e^{\prime\prime})$ of edges