i<i^{\prime}\leq h$, in graph $G\setminus E^{\prime}$, $\mbox{\sf
dist}(T_{i},T_{i^{\prime}})>D^{\prime\prime}$.

The running time of the algorithm is
$\widetilde{O}\left(\left(k^{1+\epsilon}(\log
k)^{O(1/\epsilon^{2})}+|E(G)|D^{\prime\prime}\eta\right)\cdot h(\log
k)^{O(1/\epsilon)}\right)$.

###### Proof.

The proof easily follows by iteratively applying the algorithm from Corollary
E.4. We assume that $c^{\prime\prime\prime}\gg c^{\prime\prime}$, where
$c^{\prime\prime}$ is the constant from Corollary E.4. The algorithm consists
of $r\leq\left\lceil\log h\right\rceil+2$ phases. For all $1\leq j\leq r$, at
the beginning of the $j$th phase, we are given a partition
$\Pi^{j}=\left\\{T_{0}^{j},T_{1}^{j},\ldots,T_{q_{j}}^{j}\right\\}$ of the set
$T$ of terminals, and a set $E^{j}\subseteq E(G)$ of edges, such that the
following hold:

  * •

$|T_{0}^{j}|\leq jk/(4\log k)$;

  * •

$|E^{j}|\leq\frac{kjD^{\prime\prime}(\log
k)^{c^{\prime\prime}/\epsilon}}{\eta}$;

  * •

for all $1\leq i\leq q_{j}$, $\frac{k}{2^{j-1}\cdot(\log
k)^{c^{\prime\prime}/\epsilon}}\leq|T_{i}^{j}|\leq k/2^{j-1}$; and

  * •

for all $1\leq i<i^{\prime}\leq q_{j}$, $\mbox{\sf dist}_{G\setminus
E^{j}}(T_{i}^{j},T_{i^{\prime}}^{j})>D^{\prime\prime}$.

At the beginning of the algorithm, we set $T_{0}^{1}=\emptyset$,
$T_{1}^{1}=T$, and $q_{1}=1$. We also set $E^{1}=\emptyset$. It is easy to
verify that all invariants hold.

We now describe the $j$th phase. At the beginning of the phase, we set
$T_{0}^{j+1}=T_{0}^{j}$, $E^{j+1}=E^{j}$, and $\Pi^{j+1}=\emptyset$. We then
perform $q_{j}$ iterations, where in the $i$th iteration we process terminal
set $T_{i}^{j}\in\Pi^{j}$.

We now describe an iteration for processing the terminal set $T_{i}^{j}$. If
$|T_{i}^{j}|\leq k/2^{j}$, then we simply add $T_{i}^{j}$ to $\Pi^{j+1}$, set
$T_{0}^{i,j+1}=\emptyset$, $E_{i}^{j+1}=\emptyset$, and continue to the next
iteration. Assume now that $|T_{i}^{j}|>k/2^{j}$. Notice that in this case,
from our assumption that $h\leq k/(100(\log
k)^{c^{\prime\prime\prime}/\epsilon})$, we get that $|T_{i}^{j}|\geq
k/(4h)\geq 40(\log k)^{c^{\prime\prime}/\epsilon}$ holds. We then apply the
algorithm from Corollary E.4 to graph $G\setminus E^{j}$, vertex set
$T^{j}_{i}$, and the same parameters $k,\eta,D^{\prime\prime},\epsilon$ as
before. We now consider two cases. In the first case, the outcome of the
algorithm from Corollary E.4 is a graph $X$ with $V(X)\subseteq T_{i}^{j}$,
and $|V(X)|\geq|T_{i}^{j}|/4\geq k/2^{j+2}\geq k/(64h)$, such that the maximum
vertex degree in $X$ is at most $O(\log k)$, and $X$ is a $\varphi$-expander,
for $\varphi=1/(\log k)^{c^{\prime\prime}/\epsilon}\geq 1/(\log
k)^{c^{\prime\prime\prime}/\epsilon}$, together with an embedding
${\mathcal{P}}$ of $X$ into $G$, with congestion at most $\eta$, such that
every path in ${\mathcal{P}}$ has length at most
$64D^{\prime\prime}\log^{2}k$. We then terminate the algorithm, and return the
expander $X$ and its embedding ${\mathcal{P}}$.

Therefore, we assume from now on that the second case happens, and the
algorithm from Corollary E.4 returns a subset $E_{i}^{j+1}$ of at most
$\frac{|T_{i}^{j}|D^{\prime\prime}(\log k)^{c^{\prime\prime}/\epsilon}}{\eta}$
edges of $G\setminus E^{j}$, and a partition
$(S^{\prime\prime}_{0},S^{\prime\prime}_{1},S^{\prime\prime}_{2},\ldots,S^{\prime\prime}_{r})$
of $T_{i}^{j}$ into disjoint subsets, such that, for all $1\leq a\leq z$,
$|T_{i}^{j}|/(\log
k)^{c^{\prime\prime}/\epsilon}\leq|S^{\prime\prime}_{a}|\leq|T_{i}^{j}|/2$,
$|S^{\prime\prime}_{0}|\leq|T^{j}_{i}|/(4\log k)$, and, in graph
$G\setminus(E^{j}\cup E_{i}^{j+1})$, for all $1\leq i<i^{\prime}\leq z$,
$\mbox{\sf
dist}(S^{\prime\prime}_{i},S^{\prime\prime}_{i^{\prime}})>D^{\prime\prime}$.

We set $T_{0}^{i,j+1}=S^{\prime\prime}_{0}$; note that
$|T_{0}^{i,j+1}|\leq|T^{j}_{i}|/(4\log k)$. Since $k/2^{j}\leq|T_{i}^{j}|\leq
k/2^{j-1}$, we get that for all $1\leq a\leq z$, $k/(2^{j}(\log
k)^{c^{\prime\prime}/\epsilon})\leq|S^{\prime\prime}_{a}|\leq k/2^{j}$. We
then add all sets $S_{1}^{\prime\prime},\ldots,S^{\prime\prime}_{z}$ to
$\Pi^{j+1}$, and continue to the next iteration.

The phase terminates when all sets in $\Pi^{j}$ are processed. We set
$E^{j+1}=E^{j}\cup(E_{1}^{j+1}\cup\cdots\cup E^{j+1}_{q_{j}})$. Since, for all
$1\leq i\leq q_{j}$, $|E_{i}^{j+1}|\leq\frac{|T_{i}^{j}|D^{\prime\prime}(\log
k)^{c^{\prime\prime}/\epsilon}}{\eta}$, we get that
$|E_{1}^{j+1}\cup\cdots\cup E^{j+1}_{q_{j}}|\leq\frac{kD^{\prime\prime}(\log
k)^{c^{\prime\prime}/\epsilon}}{\eta}$, and so altogether,
$|E^{j+1}|\leq\frac{k(j+1)D^{\prime\prime}(\log
k)^{c^{\prime\prime}/\epsilon}}{\eta}$. We also set
$T_{0}^{j+1}=T_{0}^{j}\cup(T_{0}^{1,j+1}\cup\cdots\cup T_{0}^{q_{j},j+1})$.
Since, for all $1\leq i\leq q_{j}$, $|T_{0}^{i,j+1}|\leq|T^{j}_{i}|/(4\log
k)$, we get that $|T_{0}^{1,j+1}\cup\cdots\cup T_{0}^{q_{j},j+1}|\leq k/(4\log
k)$, and $|T_{0}^{j+1}|\leq k(j+1)/(4\log k)$. From the above discussion, for
all $T^{\prime}\in\Pi^{j+1}$, $\frac{k}{2^{j}\cdot(\log
k)^{c^{\prime\prime}/\epsilon}}\leq|T^{\prime}|\leq k/2^{j}$ holds, and it is
immediate to verify that for all $T^{\prime},T^{\prime\prime}\in\Pi^{j+1}$,
$\mbox{\sf dist}_{G\setminus
E^{j+1}}(T^{\prime},T^{\prime\prime})>D^{\prime\prime}$.

If the algorithm does not terminate with an expander $X$ and its embedding
${\mathcal{P}}$, then it terminates after $r=\left\lceil\log h\right\rceil+2$
phases. Since we are guaranteed that, for all $T^{\prime}\in\Pi^{r}$,
$|T^{\prime}|\leq k/2^{r}\leq k/(2h)$, while $|T_{0}^{r}|\leq rk/(4\log k)\leq
k/2$ we get that $|\Pi^{r}|\geq h$. We let $T_{1},\ldots,T_{h}$ be arbitrary
$h$ vertex sets in $\Pi^{r}$. We let $E^{\prime}=E^{r}$; from our invariants,
$|E^{\prime}|\leq\frac{kD^{\prime\prime}(\log
k)^{c^{\prime\prime}/\epsilon+1}}{\eta}\leq\frac{kD^{\prime\prime}(\log
k)^{c^{\prime\prime\prime}/\epsilon}}{\eta}$. Clearly, for all $1\leq
i<i^{\prime}\leq h$, in graph $G\setminus E^{\prime}$, $\mbox{\sf
dist}(T_{i},T_{i^{\prime}})>D^{\prime\prime}$. Our invariants also guarantee
that, for all $1\leq i\leq h$, $|T_{i}|\geq\frac{k}{4h\cdot(\log
k)^{c^{\prime\prime}/\epsilon}}\geq\frac{k}{(h(\log
k)^{c^{\prime\prime\prime}/\epsilon})}$.

It now remains to analyze the running time of the algorithm. The algorithm
consists of $O(\log k)$ phases, and each phase consists of $O(h)$ iterations.
From Corollary E.4, the running time of each iteration is bounded by
$\widetilde{O}\left(\left(k^{1+\epsilon}(\log
k)^{O(1/\epsilon^{2})}+|E(G)|D^{\prime\prime}\eta\right)\cdot(\log
k)^{O(1/\epsilon)}\right)$. Therefore, the total running time of the algorithm
is bounded by $\widetilde{O}\left(\left(k^{1+\epsilon}(\log
k)^{O(1/\epsilon^{2})}+|E(G)|D^{\prime\prime}\eta\right)\cdot h(\log
k)^{O(1/\epsilon)}\right)$.

We are now ready to complete the proof of Theorem 5.2. Recall that we are
given as input a valid input structure
${\mathcal{I}}=\left(C,\left\\{\ell(e)\right\\}_{e\in E(C)},D\right)$, where
$C$ is a connected graph, with arbitrary weights $w(x)\geq 0$ for vertices
$x\in V(C)$, and parameters $0<\epsilon<1$, $\hat{D}>D$, and
$\hat{W}\geq\max\left\\{W(C),|E(C)|,2^{\Omega(1/\epsilon)}\right\\}$, together
with a $(\hat{D},\rho)$-pseudocut $\hat{E}$ for $C$ of cardinality $k$, where
$\rho=\hat{W}^{\epsilon}$.

We need to consider a special case, where $\epsilon<O(1/\log k)$, or,
equivalently, $k<2^{O(1/\epsilon)}$. In this case, since we have assumed that
$\hat{W}>2^{\Omega(1/\epsilon)}$, $k<\hat{W}^{\epsilon}$ holds. We then select
an arbitrary edge $e\in\hat{E}$, and set $\hat{E}^{*}=\left\\{e\right\\}$. We
let the expander $X$ contain a single vertex $t_{e}$ and no edges, and its
embedding into $C_{|\hat{E}^{*}}$ is ${\mathcal{P}}=\emptyset$. We then return
$\hat{E}^{*},X$, and ${\mathcal{P}}$ and terminate the algorithm. Therefore,
we assume from now on that $\epsilon\geq\Omega(1/\log k)$. We also assume that
$k/(100(\log
k)^{c^{\prime\prime\prime}/\epsilon})\geq\left\lceil\hat{W}^{\epsilon}\right\rceil$,
where $c^{\prime\prime\prime}$ is the constant from Corollary E.5; otherwise,
$k\leq\hat{W}^{2\epsilon}$ holds. In this case, we proceed as before: we
select an arbitrary edge $e\in\hat{E}$, set $\hat{E}^{*}=\left\\{e\right\\}$,
and return an expander $X$ containing a single vertex $t_{e}$ and no edges,
and its embedding ${\mathcal{P}}=\emptyset$ into $C_{|\hat{E}^{*}}$.
Therefore, we assume from now on that $k/(100(\log
k)^{c^{\prime\prime\prime}/\epsilon}\geq\left\lceil\hat{W}^{\epsilon}\right\rceil$.

Let $G=C_{|\hat{E}}$ be the graph obtained from $C$ by subdividing every edge
$e=(u,v)\in\hat{E}$ with a vertex $t_{e}$. We denote the resulting edges by
$e_{1}=(u,t_{e})$, $e_{2}=(v,t_{e})$, and we set the length of each of these
edges to be $\ell(e)$. Let $T=\left\\{t_{e}\mid e\in\hat{E}\right\\}$ be the
set of the newly created vertices, that we refer to as _terminals_. Note that
$k\leq\hat{W}$ must hold, since $C$ is a connected graph and
$\hat{W}\geq|E(C)|$.

We use the following parameters: $D^{\prime\prime}=40\hat{D}$,
$h=\left\lceil\hat{W}^{\epsilon}\right\rceil$, and
$\eta=16D^{\prime\prime}\hat{W}^{\epsilon}(\log
k)^{2c^{\prime\prime\prime}/\epsilon}\leq\hat{D}\cdot\hat{W}^{\epsilon}(\log\hat{W})^{O(1/\epsilon)}$.
Note that, from our assumption, $h\leq k/(100(\log
k)^{c^{\prime\prime\prime}/\epsilon})$ holds. We apply the algorithm from
Corollary E.5 to graph $G$, the set $T$ of terminals, parameters
$\eta,D^{\prime\prime}$ and $h$ that we just defined, and the input parameter
$\epsilon$. We now consider two cases, depending on the algorithm’s outcome.

In the first, case, the algorithm from Corollary E.5 returns a graph $X$ with
$V(X)\subseteq T$, and $|V(X)|\geq k/(64h)\geq\Omega(k/\hat{W}^{\epsilon})$,
such that the maximum vertex degree in $X$ is at most $O(\log k)\leq
O(\log\hat{W})$, and $X$ is a $\varphi^{*}$-expander, for $\varphi^{*}=1/(\log
k)^{O(1/\epsilon)}\geq 1/(\log\hat{W})^{O(1/\epsilon)}$, together with an
embedding ${\mathcal{P}}$ of $X$ into $G$, with congestion at most
$\eta\leq\hat{D}\cdot\hat{W}^{\epsilon}(\log\hat{W})^{O(1/\epsilon)}$, such
that every path in ${\mathcal{P}}$ has length at most
$64D^{\prime\prime}\log^{2}k\leq O(\hat{D}\log^{2}\hat{W})$. We let
$\hat{E}^{*}\subseteq\hat{E}$ be the set of edges corresponding to vertices of
$X$, that is, $\hat{E}^{*}=\left\\{e\mid t_{e}\in V(X)\right\\}$. Then
$|\hat{E}^{*}|=|V(X)|\geq\Omega(k/\hat{W}^{\epsilon})$. Moreover, the set
${\mathcal{P}}$ of paths that embeds $X$ into $G$ immediately defines a set
${\mathcal{P}}^{\prime}$ of paths in graph $C_{|\hat{E}^{*}}$, embedding $X$
into this graph with congestion at most
$\eta\leq\hat{D}\cdot\hat{W}^{\epsilon}(\log\hat{W})^{O(1/\epsilon)}$, such
that the length of every path in ${\mathcal{P}}$ is at most
$O(\hat{D}\log^{2}\hat{W})$ (note that graph $G$ can be obtained from
$C_{|\hat{E}^{*}}$ by subdividing each edge in $\hat{E}\setminus\hat{E}^{*}$,
so the transformation from path set ${\mathcal{P}}$ to
${\mathcal{P}}^{\prime}$ is straightforward). We then return the expander $X$,
the edge set $\hat{E}^{*}$, and the embedding ${\mathcal{P}}^{\prime}$ of $X$
into $C_{|E^{*}}$ as the outcome of the algorithm.

From now on we focus on the second case, where the algorithm from Corollary
E.5 returned a subset $E^{\prime}$ of edges, of cardinality at most:

$\frac{kD^{\prime\prime}(\log
k)^{c^{\prime\prime\prime}/\epsilon}}{\eta}\leq\frac{k}{16\hat{W}^{\epsilon}(\log
k)^{c^{\prime\prime\prime}/\epsilon}}$

(since $\eta=16D^{\prime\prime}\hat{W}^{\epsilon}(\log
k)^{2c^{\prime\prime\prime}/\epsilon}$), together with a collection
$(T_{1},\ldots,T_{h})$ of disjoint subsets or $T$, such that the cardinality
of each subset $T_{i}$ is at least:

$\frac{k}{h(\log
k)^{c^{\prime\prime\prime}/\epsilon}}\geq\frac{k}{2\hat{W}^{\epsilon}(\log
k)^{c^{\prime\prime\prime}/\epsilon}}\geq 8|E^{\prime}|.$

Recall that we are guaranteed that, for all $1\leq i<i^{\prime}\leq h$,
$\mbox{\sf dist}_{G\setminus
E^{\prime}}(T_{i},T_{i^{\prime}})>D^{\prime\prime}=40\hat{D}$. In the
remainder of the proof, we will exploit the terminal sets
$T_{1},\ldots,T_{h}$, and the edge set $E^{\prime}$, in order to construct a
$(\hat{D},\rho)$-pseudocut $\hat{E}^{\prime}$ in $C$, with
$|\hat{E}^{\prime}|\leq|\hat{E}|\left(1-\frac{1}{\hat{W}^{\epsilon}(\log\hat{W})^{O(1/\epsilon)}}\right)$.

We define a set $E^{\prime\prime}$ of edges in graph $C$, as follows. For
every edge $e\in E^{\prime}$, if $e\in E(C)$, then we add $e$ to
$E^{\prime\prime}$. Otherwise, $e$ was obtained by subdividing some edge
$e^{\prime}\in\hat{E}$. We then add $e^{\prime}$ to $E^{\prime\prime}$.
Clearly, $|E^{\prime\prime}|\leq|E^{\prime}|$. For all $1\leq i\leq h$, we
denote $\hat{E}_{i}=\left\\{e\in\hat{E}\setminus E^{\prime\prime}\mid t_{e}\in
T_{i}\right\\}$, and we let $Z_{i}$ the set of all vertices of $C$ that serve
as endpoints of the edges in $\hat{E}_{i}$. Note that
$|\hat{E}_{i}|\geq|T_{i}|-|E^{\prime\prime}|\geq|T_{i}|/2\geq
4|E^{\prime\prime}|$. We need the following easy observation.

######  Observation E.6.

Let $C^{\prime}=C\setminus E^{\prime\prime}$. Then for all $1\leq i<j\leq h$,
$\mbox{\sf dist}_{C^{\prime}}(Z_{i},Z_{j})>4\hat{D}$.

###### Proof.

Assume otherwise, and let $x\in Z_{i},y\in Z_{j}$ be any pair of vertices with
$\mbox{\sf dist}_{C^{\prime}}(x,y)\leq 4\hat{D}$, and $i\neq j$. Let $P$ be a
shortest $x$-$y$ path in graph $C^{\prime}$. Let $e\in\hat{E}_{i}$ be the edge
with endpoint $x$, and define $e^{\prime}\in\hat{E}_{j}$ similarly. We claim
that there is a path $P^{\prime}$ of length at most $10\hat{D}$ connecting
$t_{e}$ to $t_{e^{\prime}}$ in graph $G\setminus E^{\prime}$. Since
$D^{\prime\prime}=40\hat{D}$, this will contradict the fact that $\mbox{\sf
dist}_{G\setminus E^{\prime}}(T_{i},T_{j})>D^{\prime\prime}$.

In order to obtain the path $P$, we start with the path $P^{\prime}$; for
every edge $\hat{e}\in E(P)$, if $\hat{e}\not\in E(G)$, then we subdivide
$\hat{e}$ to obtain a pair of edges that lie in $G$. Notice that this
increases the length of the path by at most factor $2$. We then append the
edges $(t_{e},x)$ and $(y,t_{e^{\prime}})$ to the beginning and the end of the
resulting path, respectively. Since the length of every edge in $C$ is at most
$D\leq\hat{D}$, it is easy to verify that the length of $P^{\prime}$ is at
most $10\hat{D}$. From our construction of edge set $E^{\prime\prime}$, and
edge sets $\hat{E}_{1},\ldots,\hat{E}_{h}$, it is also immediate to verify
that no edge of $P^{\prime}$ lies in $E^{\prime}$.

For all $1\leq i\leq h$, we let $B_{i}$ the set of all vertices of $C$ that
can reach a vertex in $Z_{i}$ via a path of length at most $2\hat{D}$ in graph
$C\setminus E^{\prime\prime}$. Equivalently: $B_{i}=B_{C\setminus
E^{\prime\prime}}(Z_{i},2\hat{D})$. Note that, from E.6, for all $1\leq
i<j\leq h$, $B_{i}\cap B_{j}=\emptyset$. Therefore, there must be an index
$1\leq i\leq h$, such that the total weight of all vertices in $B_{i}$ is
bounded by $\frac{W(C)}{h}\leq\frac{W(C)}{\hat{W}^{\epsilon}}$. We fix this
index $i$ from now on.

We are now ready to define the final set $\hat{E}^{\prime}$ of edges:
$\hat{E}^{\prime}=(\hat{E}\setminus\hat{E}_{i})\cup E^{\prime\prime}$. Recall
that $|\hat{E}_{i}|\geq|T_{i}|/2\geq 4|E^{\prime\prime}|$, and
$|\hat{E}_{i}|\geq\frac{k}{4\hat{W}^{\epsilon}(\log
k)^{c^{\prime\prime\prime}/\epsilon}}$. Therefore,
$|\hat{E}^{\prime}|\leq|\hat{E}|-|\hat{E}_{i}|+|E^{\prime\prime}|\leq
k\left(1-\frac{1}{\hat{W}^{\epsilon}(\log k)^{O(1/\epsilon)}}\right)\leq
k\left(1-\frac{1}{\hat{W}^{\epsilon}(\log\hat{W})^{O(1/\epsilon)}}\right)$. It
now remains to show that $\hat{E}^{\prime}$ is a valid
$(\hat{D},\rho)$-pseudocut, for $\rho=\hat{W}^{\epsilon}$. We do so in the
next claim.

######  Claim E.7.

Edge set $\hat{E}^{\prime}$ is a $(\hat{D},\rho)$-pseudocut for graph $C$.

###### Proof.

Consider any vertex $x\in V(C)$, and let
$B=B_{C\setminus\hat{E}^{\prime}}(x,\hat{D})$. It is enough to show that
$W(B)\leq\frac{W(C)}{\hat{W}^{\epsilon}}$. We consider two cases.

Assume first that $B\cap Z_{i}\neq\emptyset$. In this case, $B\subseteq
B_{C\setminus\hat{E}^{\prime}}(Z_{i},2\hat{D})\subseteq B_{C\setminus
E^{\prime\prime}}(Z_{i},2\hat{D})=B_{i}$ (since
$E^{\prime\prime}\subseteq\hat{E}^{\prime}$). But then, from our choice of the
index $i$, $W(B)\leq W(B_{i})\leq\frac{W(C)}{\hat{W}^{\epsilon}}$.

Therefore, we assume that $B\cap Z_{i}=\emptyset$. Since
$\hat{E}\setminus\hat{E}_{i}\subseteq\hat{E}^{\prime}$, and no edge of
$\hat{E}_{i}$ is incident to a vertex of $B$, if we consider the sub-graph $H$
of $C\setminus\hat{E}^{\prime}$ that is induced by $B$, then $H$ is also a
subgraph of $C\setminus\hat{E}$. In other words, $B\subseteq
B_{C\setminus\hat{E}}(x,\hat{D})$. But then, since $\hat{E}$ was a valid
$(\hat{D},\rho)$-pseudocut for $C$, $W(B)\leq\frac{W(C)}{\hat{W}^{\epsilon}}$
must hold.

It now remains to analyze the running time of the algorithm. In addition to
running the algorithm from Corollary E.5, we need to compute the balls
$B_{1},\ldots,B_{h}$, and the final edge set $\hat{E}^{\prime}$. Since the
balls $B_{1},\ldots,B_{h}$ are mutually disjoint, they can be computed in time
$O(|E(C)|)$. Therefore, the running time is dominated by the running time of
the algorithm from Corollary E.5, which is bounded by:

$\widetilde{O}\left(h(\log k)^{O(1/\epsilon)}\cdot\left(k^{1+\epsilon}(\log
k)^{O(1/\epsilon^{2})}+|E(G)|D^{\prime\prime}\eta\right)\right)\leq
O\left(|E(C)|\cdot\hat{D}^{2}\cdot\hat{W}^{O(\epsilon)}(\log\hat{W})^{O(1/\epsilon^{2})}\right).$

since $h\leq 2W^{\epsilon}$, $D^{\prime\prime}=\Theta(D)$,
$\eta=\hat{D}\cdot\hat{W}^{\epsilon}(\log\hat{W})^{O(1/\epsilon)}$,
$k\leq|E(C)|\leq\hat{W}$, and $|E(G)|\leq O(|E(C)|)$.

In order to complete the proof of Theorem 5.2, it is now enough to prove Lemma
E.1, which we do next.

####  E.1.1 Proof of Lemma E.1

The proof follows standard techniques, namely the Cut-Matching game of
Khandekar, Rao, and Vazirani [KRV09], and more specifically, its variant that
was studied in [KKOV07], and then used in [CGL+19]. At a high level, the Cut-
Matching game is a game played between two players: a cut player and a
matching player. The game starts with a graph $X$ containing an even number
$n$ of vertices and no edges, and then proceeds in iterations. In every
iteration $i$, a cut player computes some partition $(A_{i},B_{i})$ of $V(X)$,
with $|A_{i}|\leq|B_{i}|$. The matching player then returns a matching $M_{i}$
between vertices of $A_{i}$ and vertices of $B_{i}$, of cardinality $|A_{i}|$.
The edges of $M_{i}$ are added to the graph $X$, and the iteration terminates.
Once graph $X$ becomes a $\varphi$-expander, for some given parameter
$\varphi$, the game terminates. Intuitively, the goal of the cut player is to
make the game as short as possible, while the matching player wants to make it
longer. We will use the following theorem, that was proved in [CGL+19] in
order to implement the cut player.

######  Theorem E.8 (Theorem 4.1 in [CGL+19]).

There are universal constants $c_{0}$, $N_{0}$ and a deterministic algorithm,
that, given an $n$-vertex graph $G=(V,E)$ and parameters $N,q$ with $N>N_{0}$
an integral power of $2$, and $q\geq 1$ an integer, such that $n\leq N^{q}$,
and the maximum vertex degree in $G$ is at most $c^{\prime}\log n$ for a
constant $c^{\prime}$, computes one of the following:

  * •

either a partition $(A,B)$ of $V$ with $|A|,|B|\geq n/4$, $|A|\leq|B|$, and
$|E_{G}(A,B)|\leq n/100$; or

  * •

a subset $R\subseteq V$ of at least $n/2$ vertices of $G$, such that graph
$G[R]$ is a $\varphi^{\prime}$-expander, for $\varphi^{\prime}=1/\left(q\log
N\right)^{8q}$.

The running time of the algorithm is $O\left(N^{q+1}\cdot(q\log
N)^{c_{0}q^{2}}\right)$.

We will use the following immediate corollary of the theorem.

######  Corollary E.9.

There is a universal constant $c^{\prime\prime}$, and a deterministic
algorithm, that, given an $n$-vertex graph $G=(V,E)$, and a parameter
$0<\epsilon<1$, such that $\epsilon\geq c^{\prime\prime}/\log n$, and the
maximum vertex degree in $G$ is at most $c^{\prime}\log n$ for some constant
$c^{\prime}$, computes one of the following:

  * •

either a partition $(A,B)$ of $V(G)$ with $|A|,|B|\geq n/4$, $|A|\leq|B|$, and
$|E_{G}(A,B)|\leq n/100$; or

  * •

a subset $R\subseteq V$ of at least $n/2$ vertices of $G$, such that graph
$G[R]$ is a $\varphi^{\prime\prime}$-expander, for
$\varphi^{\prime\prime}=1/(\log n)^{O(1/\epsilon)}$.

The running time of the algorithm is $O\left(n^{1+O(\epsilon)}\cdot(\log
n)^{O(1/\epsilon^{2})}\right)$.

###### Proof.

We set $q=\left\lceil 1/\epsilon\right\rceil$, so that $1/\epsilon\leq q\leq
2/\epsilon$. Next, we let $N$ be the smallest integral power of $2$, so that
$N^{q}\geq n$. It is easy to verify that $N\leq 2n^{1/q}\leq 2n^{\epsilon}$.
Also, $N\geq n^{1/q}\geq n^{\epsilon/2}$. We can then set the constant
$c^{\prime\prime}$ to be large enough to ensure that $n^{\epsilon/2}>N_{0}$,
where $N_{0}$ is the constant in the statement of Theorem E.8. We then apply
Theorem E.8 to the graph $G$, together with parameters $q$ and $N$. If the
algorithm returns a partition $(A,B)$ of $V(G)$ with $|A|,|B|\geq n/4$ and
$|E_{G}(A,B)|\leq n/100$, then we also return this partition as the outcome of
our algorithm. Otherwise, the algorithm from Theorem E.8 computes a subset
$R\subseteq V$ of at least $n/2$ vertices of $G$, such that graph $G[R]$ is a
$\varphi^{\prime\prime}$-expander, for $\varphi^{\prime\prime}=1/\left(q\log
N\right)^{8q}$. Since $q=O(1/\epsilon)$, and $N^{q}\leq 2n$, it is easy to
verify that $\varphi^{\prime\prime}\geq 1/(\log n)^{O(q)}\geq 1/(\log
n)^{O(1/\epsilon)}$. We then return $R$ as the outcome of the algorithm.

Lastly, the running time of the algorithm is $O\left(N^{q+1}\cdot(q\log
N)^{c_{0}q^{2}}\right)$. Since $N^{q}\leq 2n$ and $q=\Theta(1/\epsilon)$, we
get that the running time is bounded by $O\left(n^{1+O(\epsilon)}\cdot(\log
n)^{O(1/\epsilon^{2})}\right)$.

Consider now the following implementation of the cut-matching game. We start
with a graph $X$ that contains an even number $n$ of vertices and no edges,
and play the game for at most $c^{\prime}\log n$ iterations, where
$c^{\prime}$ is the constant from Corollary E.9. In every iteration $i$, we
apply the algorithm from Corollary E.9 to the graph $X$, with the parameter
$\epsilon$. We now consider two cases. First, if the outcome of the algorithm
from Corollary E.9 is a partition $(A,B)$ of $V(G)$ with $|A|,|B|\geq n/4$,
$|A|\leq|B|$, and $|E_{G}(A,B)|\leq n/100$, then we let $(A_{i},B_{i})$ be any
partition of $V(G)$ with $|A_{i}|=|B_{i}|$, such that $A\subseteq A_{i}$. We
then compute an arbitrary perfect matching $M_{i}$ between vertices of $A_{i}$
and vertices of $B_{i}$. Lastly, we add the edges of $M_{i}$ to graph $X$, and
continue to the next iteration. In the second case, the outcome of the
algorithm from Corollary E.9 is a subset $R\subseteq V$ of at least $n/2$
vertices of $G$, such that graph $G[R]$ is a
$\varphi^{\prime\prime}$-expander, for $\varphi^{\prime\prime}=1/(\log
n)^{O(1/\epsilon)}$. In this case, we let $A_{i}=V\setminus R$, $B_{i}=R$, and
we compute an arbitrary matching $M_{i}$ of cardinality $|A_{i}|$ between
vertices of $A_{i}$ and vertices of $B_{i}$. We then add the edges of $M_{i}$
to graph $X$ and terminate the algorithm.

The following theorem follows immediately from the results of [KKOV07], and
was also proved explicitly in [CGL+19] (see Theorem 2.5 in [CGL+19]).

######  Theorem E.10.

There is a constant $\hat{c}$, such that, after at most $\hat{c}\log n$
iterations, the above algorithm is guaranteed to terminate, and the resulting
graph $X$ is a $\hat{\varphi}$-expander, for $\hat{\varphi}=1/(\log
n)^{\hat{c}/\epsilon}$.

Notice that the above theorem holds regardless of the specific choices of the
matchings $M_{i}$ in each iteration (though the partitions $(A_{i},B_{i})$ of
the vertices of $V$ that the algorithm computes in each iteration depend on
the choices of the matchings from previous iterations). We note that the
constant $c^{\prime}$ in the statement of Theorem E.8 from [CGL+19] was chosen
to be such that $\hat{c}\leq c^{\prime}$ holds.

The following theorem will be used in order to implement the matching player.
The proof uses techniques that are similar to those introduced in [CK19], and
then used in [CGL+19] and [CS21].

######  Theorem E.11.

There is a deterministic algorithm, that, given a graph $G$ with integral
lengths $\ell(e)\geq 1$ on its edges $e\in E(G)$, two disjoint subsets $A,B$
of its vertices with $|A|\leq|B|$ and $|A|=\kappa$, together with parameters
$D^{\prime},\eta>0$, and $z\geq 0$, computes one of the following:

  * •

either a collection ${\mathcal{P}}$ of at least $|A|-z$ paths in $G$, where
each path connects a distinct vertex of $A$ to a distinct vertex of $B$; every
path has length at most $D^{\prime}$; and every edge of $G$ participates in at
most $\eta$ paths; or

  * •

a collection $E^{\prime}$ of at most $\frac{|A|\cdot
D^{\prime}\log\kappa}{2\eta}$ edges of $G$, and two subsets $A^{*}\subseteq
A$, $B^{*}\subseteq B$ of at least $z/2$ vertices each, such that, in graph
$G\setminus E^{\prime}$, $\mbox{\sf dist}(A^{*},B^{*})>D^{\prime}$.

The running time of the algorithm is $\widetilde{O}(|E(G)|D^{\prime}\eta)$.

We delay the proof of Theorem E.11 to Section E.1.2, after we complete the
proof of Lemma E.1 using it.

In the remainder of the proof, we let $\hat{c}$ be the constant from Theorem
E.10, so that the number of iterations in the Cut-Matching game played over a
set of $k$ vertices is bounded by $\hat{c}\log k$, and the final graph $X$
obtained at the end of the game is a $\hat{\varphi}$-expander, for
$\hat{\varphi}=1/(\log k)^{\hat{c}/\epsilon}$. The algorithm consists of two
stages. In the first stage, we compute an expander $X$ over the vertex set
$S$, and a relatively small subset $F\subseteq E(X)$ of its edges (that we
call _fake edges_), together with an embedding of $X\setminus F$ into $G$; if
we fail to compute this expander, then we will produce the desired set
$E^{\prime}$ of at most $\frac{ckD^{\prime}\log^{2}k}{\eta}$ edges, and two
disjoint subsets $S_{1},S_{2}\subseteq S$ of vertices of cardinality at least
$k/(\log k)^{c/\epsilon}$ each, such that, in graph $G\setminus E^{\prime}$,
$\mbox{\sf dist}(S_{1},S_{2})>D^{\prime}$. In the second stage, we use
expander pruning in order to get rid of the fake edges and compute a final
expander $X^{\prime}\subseteq X\setminus F$. We now describe each stage in
turn.

##### Stage 1: Embedding the Expander.

We start with the graph $X$, whose vertex set is $S$, and edge set is empty.
We also let ${\mathcal{P}}=\emptyset$ be an initial embedding of the graph
$X$. We then perform at most $\hat{c}\log k$ iterations, with the $i$th
iteration performed as follows. First, we apply the algorithm from Corollary
E.9 to graph $X$. Assume first that the algorithm produces a partition
$(A_{i},B_{i})$ of $V(X)$ with $|A_{i}|,|B_{i}|\geq k/4$,
$|A_{i}|\leq|B_{i}|$, and $|E_{X}(A_{i},B_{i})|\leq k/100$. We let
$(A_{i}^{\prime},B_{i}^{\prime})$ be any partition of $V(X)$ with
$|A_{i}^{\prime}|=|B_{i}^{\prime}|$ and $A_{i}\subseteq A_{i}^{\prime}$.

Next, we apply the algorithm from Theorem E.11 to graph $C$, the sets
$A_{i}^{\prime},B_{i}^{\prime}$ of its vertices, with the same parameter
$D^{\prime}$, congestion parameter $\hat{\eta}=\eta/(\hat{c}\log k)$, and
$z=\hat{\varphi}k/(20\hat{c}^{2}\log^{2}k)$. Assume first that the algorithm
returns a collection $E^{\prime}$ of at most $\frac{|A_{i}^{\prime}|\cdot
D^{\prime}\log k}{2\hat{\eta}}\leq\frac{\hat{c}|A_{i}^{\prime}|\cdot
D^{\prime}\log^{2}k}{2\eta}=\frac{\hat{c}kD^{\prime}\log^{2}k}{4\eta}$ edges
of $G$, and two subsets $A^{*}\subseteq A_{i}$, $B^{*}\subseteq B_{i}$ of at
least $z/2=\hat{\varphi}k/(40\hat{c}^{2}\log^{2}k)$ vertices each, such that,
in graph $G\setminus E^{\prime}$, $\mbox{\sf dist}(A^{*},B^{*})>D^{\prime}$.
We then say that the current iteration was unsuccessful, terminate the
algorithm, and return the sets $S_{1}=A^{*},S_{2}=B^{*}$ of vertices, together
with the set $E^{\prime}$ of edges. It is easy to verify that they have all
required properties, since $\hat{\varphi}k/(40\hat{c}^{2}\log^{2}k)=k/(\log
k)^{O(1/\epsilon)}$.

Assume now that the algorithm returned a collection ${\mathcal{P}}_{i}$ of at
least $|A_{i}^{\prime}|-z$ paths in $G$, where each path connects a distinct
vertex of $A_{i}^{\prime}$ to a distinct vertex of $B_{i}^{\prime}$, every
path has length at most $D^{\prime}$, and every edge of $G$ participates in at
most $\hat{\eta}=\eta/(\hat{c}\log k)$ paths. We then say that the current
iteration is successful. We let $M^{\prime}_{i}$ be a partial matching between
vertices of $A_{i}^{\prime}$ and vertices of $B_{i}^{\prime}$, where $(x,y)\in
M_{i}^{\prime}$ iff some path in ${\mathcal{P}}_{i}$ connects $x$ to $y$. Let
$A^{\prime\prime}_{i}\subseteq A^{\prime}_{i},B^{\prime\prime}_{i}\subseteq
B^{\prime}_{i}$ be the sets of vertices that do not participate in the
matching $M_{i}^{\prime}$. We let $F_{i}$ be an arbitrary perfect matching
between vertices of $A^{\prime\prime}_{i}$ and vertices of
$B^{\prime\prime}_{i}$; observe that $|F_{i}|=|A^{\prime}_{i}\setminus
A^{\prime\prime}_{i}|\leq z$ must hold. We call the vertex pairs in $F_{i}$
_fake edges for graph $X$_. We then let $M_{i}=M_{i}^{\prime}\cup F_{i}$, and
add the edges of $M_{i}$ into $X$, terminating the current iteration.

Finally, assume that the algorithm from Corollary E.9 returns a subset
$R\subseteq V(X)$ of at least $k/2$ vertices of $X$, such that graph $X[R]$ is
a $\varphi$-expander. Let $i$ be the index of the current iteration. We set
$A_{i}^{\prime}=V(X)\setminus R$ and $B^{\prime}_{i}=R$, and apply the
algorithm from Theorem E.11 to graph $G$, vertex sets
$A_{i}^{\prime},B_{i}^{\prime}$, distance bound $D^{\prime}$, congestion bound
$\hat{\eta}=\eta/(\hat{c}\log k)$, and parameter
$z=\hat{\varphi}k/(20\hat{c}^{2}\log^{2}k)$ as before. We then continue
exactly as before. If the algorithm returns a collection $E^{\prime}$ of at
most $\frac{\hat{c}|A_{i}^{\prime}|\cdot
D^{\prime}\log^{2}k}{2\eta}\leq\frac{\hat{c}kD^{\prime}\log^{2}k}{4\eta}$
edges of $G$, and two subsets $A^{*}\subseteq A_{i}$, $B^{*}\subseteq B_{i}$
of at least $z/2=\hat{\varphi}k/(40\hat{c}^{2}\log^{2}k)$ vertices each, such
that, in graph $G\setminus E^{\prime}$, $\mbox{\sf
dist}(A^{*},B^{*})>D^{\prime}$, then, as before, we say that the current
iteration was unsuccessful, terminate the algorithm, and return the sets
$S_{1}=A^{*},S_{2}=B^{*}$ of vertices, together with the set $E^{\prime}$ of
edges. Otherwise, the algorithm from Theorem E.11 returns a collection
${\mathcal{P}}_{i}$ of at least $|A_{i}^{\prime}|-z$ paths in $G$, where each
path connects a distinct vertex of $A_{i}^{\prime}$ to a distinct vertex of
$B_{i}^{\prime}$, every path has length at most $D^{\prime}$, and every edge
of $G$ participates in at most $\hat{\eta}=\eta/(\hat{c}\log k)$ paths. We
then say that the current iteration is successful. We let $M^{\prime}_{i}$ be
a partial matching between vertices of $A_{i}^{\prime}$ and vertices of
$B_{i}^{\prime}$, where $(x,y)\in M_{i}^{\prime}$ iff some path in
${\mathcal{P}}_{i}$ connects $x$ to $y$. Let $A^{\prime\prime}_{i}\subseteq
A^{\prime}_{i},B^{\prime\prime}_{i}\subseteq B^{\prime}_{i}$ be the sets of
vertices that do not participate in the matching $M_{i}^{\prime}$. We let
$F_{i}$ be an arbitrary matching between vertices of $A^{\prime\prime}_{i}$
and vertices of $B^{\prime\prime}_{i}$ of cardinality
$|A^{\prime\prime}_{i}|$; observe that $|F_{i}|=|A^{\prime}_{i}\setminus
A^{\prime\prime}_{i}|\leq z$ must hold. We call the vertex pairs in $F_{i}$
_fake edges for graph $X$_. We then let $M_{i}=M_{i}^{\prime}\cup F_{i}$, and
add the edges of $M_{i}$ into $X$, terminating the current the algorithm.

If any iteration of the algorithm was unsuccessful, then we have obtained the
desired sets $S_{1},S_{2}$ of vertices of $S$, and the edge set $E^{\prime}$
as required. We assume now that every iteration of the algorithm was
successful. Then, from Theorem E.10, the total number of iterations in the
algorithm is bounded by $\hat{c}\log k$, and the final graph $X$ is a
$\hat{\varphi}$-expander, for $\hat{\varphi}=1/(\log k)^{\hat{c}/\epsilon}$.
Let $F=\bigcup_{i}F_{i}$ be the set of all fake edges of $X$. Then
$|F|\leq\hat{c}z\log k$. Let ${\mathcal{P}}=\bigcup_{i}{\mathcal{P}}_{i}$.
Then the paths in ${\mathcal{P}}$ provide an embedding of the graph
$X\setminus F$ into $G$, where the length of every path in ${\mathcal{P}}$ is
at most $D^{\prime}$. Since the number of iterations is at most $\hat{c}\log
k$, and each set ${\mathcal{P}}_{i}$ of paths causes edge-congestion at most
$\eta/(\hat{c}\log k)$, the total edge-congestion caused by the paths in
${\mathcal{P}}$ is at most $\eta$. This finishes the first stage of the
algorithm. We now analyze its running time.

The algorithm consists of $O(\log k)$ iterations. Each iteration involves
applying the algorithm from Corollary E.9, whose running time is
$O\left(k^{1+O(\epsilon)}\cdot(\log k)^{O(1/\epsilon^{2})}\right)$, and the
algorithm from Theorem E.11, whose running time is
$\widetilde{O}(|E(G)|D^{\prime}\hat{\eta})\leq\widetilde{O}(|E(G)|D^{\prime}\eta)$.
Therefore, the total running time of the algorithm is:

$\widetilde{O}\left(k^{1+O(\epsilon)}\cdot(\log
k)^{O(1/\epsilon^{2})}\right)+\widetilde{O}(|E(G)|D^{\prime}\eta).$

##### Stage 2: Pruning.

In this stage, we apply the algorithm from Theorem 2.2 to the graph $X$, with
expansion parameter $\hat{\varphi}=1/(\log k)^{\hat{c}/\epsilon}$, and the
sequence $\sigma$ containing the edges of $F$ in an arbitrary order. Observe
that the maximum vertex degree in $X$ is at most $\hat{c}\log k$, and
$|F|\leq(\hat{c}\log k)\cdot z\leq(\hat{c}\log
k)\cdot\hat{\varphi}k/(20\hat{c}^{2}\log^{2}k)\leq\hat{\varphi}k/(20\hat{c}\log
k)$. Clearly, if $\Delta$ denotes the maximum vertex degree in $X$, then
$|F|\leq\hat{\varphi}|E(X)|/(10\Delta)$ holds. Let $S^{\prime}=S_{|F|}$ be the
outcome of the algorithm, and let $X^{\prime}$ be the graph obtained from
$X\setminus F$ after the vertices of $S^{\prime}$ are removed from it. Then,
from Theorem 2.2 graph $X^{\prime}$ is a $\varphi$-expander, for
$\varphi=\hat{\varphi}/(6\Delta)=1/(\log k)^{O(1/\epsilon)}$. Let
${\mathcal{P}}^{\prime}\subseteq{\mathcal{P}}$ be the set of paths
corresponding to the edges in $X^{\prime}$. Then paths in
${\mathcal{P}}^{\prime}$ define an embedding of $X^{\prime}$ into $G$ with
congestion at most $\eta$, where each path has length at most $D^{\prime}$.
Recall also that Theorem 2.2 guarantees that $|S^{\prime}|\leq
8|F|\Delta/\hat{\varphi}\leq 8k/20$. Therefore, $|V(X^{\prime})|\geq|S|/2$
must hold.

The running time of the second stage of the algorithm is bounded by
$\widetilde{O}(|F|\Delta^{2}/\hat{\varphi}^{2})\leq\widetilde{O}(k\log^{2}k/\hat{\varphi})\leq\widetilde{O}\left(k\cdot(\log
k)^{O(1/\epsilon)}\right)$. The total running time of the whole algorithm is
therefore bounded by:

$\widetilde{O}\left(k^{1+O(\epsilon)}(\log
k)^{O(1/\epsilon^{2})}\right)+\widetilde{O}(|E(G)|D^{\prime}\eta).$

In order to complete the proof of Theorem 5.2, it is now enough to prove
Theorem E.11, which we do next.

####  E.1.2 Proof of Theorem E.11

The proof proceeds by iteratively applying the following claim.

######  Claim E.12.

There is a deterministic algorithm, that, given a graph $G$ with integral
lengths $\ell(e)\geq 1$ on its edges $e\in E(G)$, two disjoint subsets
$A^{\prime},B^{\prime}$ of its vertices with $|A^{\prime}|\leq|B^{\prime}|$,
together with parameters $D^{\prime}>0$ and $\eta^{\prime}>0$, computes one of
the following:

  * •

either a collection ${\mathcal{P}}^{\prime}$ of at least $|A^{\prime}|/2$
paths in $G$, where each path connects a distinct vertex of $A^{\prime}$ to a
distinct vertex of $B^{\prime}$, and every path has length at most
$D^{\prime}$, and every edge in $G$ participates in at most $\eta^{\prime}$
paths; or

  * •

a collection $E^{\prime}$ of at most $|A^{\prime}|\cdot
D^{\prime}/(2\eta^{\prime})$ edges of $G$, and two subsets
$A^{\prime\prime}\subseteq A^{\prime}$, $B^{\prime\prime}\subseteq B^{\prime}$
of at least $|A^{\prime}|/2$ vertices each, such that, in graph $G\setminus
E^{\prime}$, $\mbox{\sf dist}(A^{\prime\prime},B^{\prime\prime})>D^{\prime}$.

The running time of the algorithm is
$\widetilde{O}(|E(G)|D^{\prime}\eta^{\prime})$.

We provide the proof of E.12 below, after we complete the proof of Theorem
E.11 using it. We start with ${\mathcal{P}}=\emptyset$, set
$A^{\prime}=A,B^{\prime}=B$, and then iterate, as long as $|A^{\prime}|>z$. In
every iteration, we apply the algorithm from E.12 to the input graph $G$,
parameter $D^{\prime}$, and $\eta^{\prime}=\eta/\log\kappa$. If the outcome of
the algorithm is a set $E^{\prime}$ of edges, of cardinality at most
$\frac{|A^{\prime}|\cdot D^{\prime}}{2\eta^{\prime}}\leq\frac{|A|\cdot
D^{\prime}\log k}{2\eta}$, and two subsets $A^{\prime\prime}\subseteq
A^{\prime}$, $B^{\prime\prime}\subseteq B^{\prime}$ of at least
$|A^{\prime}|/2$ vertices each, such that, in graph $G\setminus E^{\prime}$,
$\mbox{\sf dist}(A^{\prime\prime},B^{\prime\prime})>D^{\prime}$, then we set
$A^{*}=A^{\prime\prime},B^{*}=B^{\prime\prime}$, and terminate the algorithm
with the output $A^{*},B^{*}$ and $E^{\prime}$. Note that, since
$|A^{\prime}|\geq z$ held, we are guaranteed that $|A^{*}|,|B^{*}|\geq z/2$,
as required. Otherwise, we obtain a collection ${\mathcal{P}}^{\prime}$ of at
least $|A^{\prime}|/2$ paths in $G$, where each path connects a distinct
vertex of $A^{\prime}$ to a distinct vertex of $B^{\prime}$, and every path
has length at most $D^{\prime}$, and every edge in $G$ participates in at most
$\eta^{\prime}$ paths in ${\mathcal{P}}^{\prime}$. We add the paths in
${\mathcal{P}}^{\prime}$ to the set ${\mathcal{P}}$, and we delete from
$A^{\prime}$ and $B^{\prime}$ vertices that serve as endpoints to paths in
${\mathcal{P}}^{\prime}$, terminating the current iterations.

If any iteration terminates with the set $E^{\prime}$ of edges, then the
algorithm produces the required output. Therefore, we assume from now on that
in every iteration, new paths are added to set ${\mathcal{P}}$. Since the
cardinality of the vertex set $A^{\prime}$ must decrease by at least factor
$2$ in every iteration, the number of iterations is bounded by $\log\kappa$.
Since each set ${\mathcal{P}}^{\prime}$ of paths computed by the algorithm
from E.12 causes edge-congestion at most $\eta^{\prime}=\eta/\log\kappa$, the
paths in the final set ${\mathcal{P}}$ cause edge-congestion at most $\eta$.
Clearly, the length of every path in ${\mathcal{P}}$ is at most $D^{\prime}$,
and the endpoints of all paths in ${\mathcal{P}}$ are distinct. Moreover, when
the algorithm terminates, $|A^{\prime}|\leq z$ holds, so we are guaranteed
that $|{\mathcal{P}}|\geq\kappa-z$. Since the running time of every iteration
is
$\widetilde{O}(|E(G)|D^{\prime}\eta^{\prime})=\widetilde{O}(|E(G)|D^{\prime}\eta/\log\kappa)$,
and the total number of iterations is bounded by $\log\kappa$, the total
running time is at most $\widetilde{O}(|E(G)|D^{\prime}\eta)$.

In order to complete the proof of Theorem E.11, it is now enough to prove
E.12, which we do next.

Proof of E.12. For convenience, we denote $|A^{\prime}|=\kappa$. We construct
a new graph $H$: start with the graph $G$, and add a source vertex $s$ that
connects to every vertex in $A^{\prime}$ with an edge of length $1$;
similarly, add a destination vertex $t$, that connects to every vertex in
$B^{\prime}$ with an edge of length $1$. All other edge lengths remain
unchanged in $H$. We use the standard Even-Shiloach Tree data structure on
graph $H$, with source vertex $s$, and distance threshold $D^{\prime}+2$.
Initialize ${\mathcal{P}}^{\prime}=\emptyset$. Additionally, for every edge
$e\in E(G)$, we maintain a value $\gamma(e)$ – the number of paths in
${\mathcal{P}}^{\prime}$ that contain the edge $e$. Initially, $\gamma(e)=0$
for all $e\in E(G)$.

While the distance from $s$ to $t$ is less than $D^{\prime}+2$, choose any
path $P$ in $H$ connecting $s$ to $t$ of length at most $D^{\prime}+2$. Let
$P^{\prime}$ be the path obtained from $P$ after we delete its endpoints, so
$\ell(P^{\prime})\leq D^{\prime}$. Add path $P^{\prime}$ to
${\mathcal{P}}^{\prime}$, and update, for every edge $e\in E(P^{\prime})$, the
value $\gamma(e)$. If $\gamma(e)$ exceeds $\eta^{\prime}$, then we remove edge
$e$ from graph $H$. Additionally, we remove from $H$ the fist and the last
edge of $P$ (the edges that are incident to $s$ and $t$). We then continue to
the next iteration. The total update time of the data structure is
$\widetilde{O}(|E(G)|D^{\prime})$, and the total running time of the
algorithm, that includes selecting the paths and deleting edges from $G$ as
required, is bounded by $\widetilde{O}(|E(G)|D^{\prime}\eta^{\prime})$, since
an edge may participate in at most $\eta^{\prime}$ paths in
${\mathcal{P}}^{\prime}$. We now consider two cases. First, if
$|{\mathcal{P}}^{\prime}|\geq|A^{\prime}|/2$ at the end of the algorithm, then
we terminate the algorithm, and return the set ${\mathcal{P}}^{\prime}$ of
paths. Clearly, the paths in ${\mathcal{P}}^{\prime}$ cause edge-congestion at
most $\eta^{\prime}$, and the length of every path is at most $D^{\prime}$.

From now on, we assume that, when the algorithm terminates,
$|{\mathcal{P}}^{\prime}|<|A^{\prime}|/2$ holds. Let $E^{\prime}$ denote the
set of all edges of graph $G$ that were deleted from $H$. Let
$A^{\prime\prime}\subseteq A^{\prime},B^{\prime\prime}\subseteq B^{\prime}$ be
the sets of vertices that do not serve as endpoints of paths in
${\mathcal{P}}^{\prime}$. Then $\mbox{\sf dist}_{G\setminus
E^{\prime}}(A^{\prime\prime},B^{\prime\prime})>D^{\prime}$ (as otherwise we
could have continued the algorithm). Moreover, an edge belongs to $E^{\prime}$
only if $\eta^{\prime}$ paths in ${\mathcal{P}}^{\prime}$ contain this edge.
Since each path in ${\mathcal{P}}^{\prime}$ contains at most $D^{\prime}$
edges, (as the length of each pedge is at least $1$),
$|E^{\prime}|\leq|{\mathcal{P}}^{\prime}|\cdot
D^{\prime}/\eta^{\prime}\leq|A^{\prime}|\cdot D^{\prime}/(2\eta^{\prime})$.

###  E.2 Proof of Theorem 5.3

The proof is almost identical to that of [CS21]. Our main tool is the
following theorem that allows us to embed a small expander into a large
expander. The theorem is almost identical to Theorem 3.8 in [CS21], except
that we need a slightly different tradeoff between various parameters and the
running time. We include the proof in Section E.2.1 for completeness.

######  Lemma E.13 (Analogue of Theorem 3.8 in [CS21]).

There is a constant $c$ and a deterministic algorithm that, given an
$n$-vertex graph $X$ that is a $\varphi$-expander with maximum vertex degree
$\Delta$, and a set $T\subseteq V(X)$ of its vertices whose cardinality is
$k$, together with a parameter $0<\epsilon<1$, such that $\varphi\leq
1/2^{\Omega(1/\epsilon)}$, computes a graph $X^{\prime}$ with
$V(X^{\prime})=T$ that has maximum vertex degree at most $c\log k$, such that
graph $X^{\prime}$ is a $\hat{\varphi}$-expander, for $\hat{\varphi}=1/(\log
k)^{c/\epsilon}$. The algorithm also computes an embedding ${\mathcal{P}}$ of
$X^{\prime}$ into $X$, such that the paths in ${\mathcal{P}}$ have length at
most $\frac{c\Delta\log n}{\varphi}$ and cause congestion at most
$\frac{c\Delta^{2}\log^{3}n}{\varphi^{2}}$. The running time of the algorithm
is $\widetilde{O}(\Delta^{4}n/\varphi^{3})+O\left(k^{1+O(\epsilon)}\cdot(\log
k)^{O(1/\epsilon^{2})}\right)$.

The proof of Lemma E.13 is deferred to Section E.2.1. We now turn to complete
the proof of Theorem 5.3 using it.

Throughout the algorithm, we denote $n=V(X)$. We use the parameters
$\gamma=\left\lceil n^{\epsilon}\right\rceil$ and $r=\left\lfloor
1/\epsilon\right\rfloor$. The idea is to construct and maintain a hierarchy
$X_{0},X_{1},\ldots,X_{r}$ of expanders, where $X_{0}=X$, and for $i>0$,
$|V(X_{i})|=\left\lceil n/\gamma^{i}\right\rceil$. For all $i$, we will ensure
that $V(X_{i})\subseteq V(X_{i-1})$, and we will maintain an embedding of
$X_{i}$ into $X_{i-1}$ via short paths that cause small edge-congestion.

Specifically, we will use the following parameters. We let $c$ be the constant
from Lemma E.13, that we can assume to be a large enough constant. We set
$\varphi_{0}=\varphi$, and, for $1\leq i\leq r$,
$\varphi_{i}=\hat{\varphi}=1/(\log n)^{c/\epsilon}$. We also denote
$\Delta_{0}=\Delta$, and for all $1\leq i\leq r$, $\Delta_{i}=c\log n$. We
will ensure that for all $0\leq i\leq r$, $X_{i}$ is a $\varphi_{i}$-expander,
whose maximum vertex degree is at most $\Delta_{i}$. We also define parameters
$\ell_{1}=c\Delta\log n/\varphi$, and for $1<i\leq r+1$,
$\ell_{i}=\hat{\ell}=c\Delta_{i-1}\log
n/\varphi_{i-1}=c^{2}\log^{2}n/\hat{\varphi}$. Additionally, we define
parameters $\eta_{1}=c\Delta^{2}\log^{3}n/\varphi^{2}$, and for $1<i\leq r+1$,
$\eta_{i}=c\Delta_{i-1}^{2}\log^{3}n/\varphi_{i-1}^{2}=c^{3}\log^{5}n/\hat{\varphi}^{2}$.

For all $1\leq i<r$, we will maintain an embedding ${\mathcal{P}}_{i}$ of
$X_{i}$ into $X_{i-1}$, where the paths in ${\mathcal{P}}_{i}$ have length at
most $\ell_{i}$ each, and cause total congestion at most $\eta_{i}$.
Additionally, we will maintain an ES-Tree data structure $\tau_{i}$ in graph
$X^{\prime}_{i}$, that is obtained from $X_{i}$ by adding a source vertex
$s_{i}$, and connecting it to all vertices in $V(X_{i+1})$. The tree is rooted
at $s_{i}$, and its depth bound is $D_{i}=4\ell_{i}$. Lastly, for every edge
$e\in E(X_{i-1})$, we will maintain a list $J_{i}(e)$ of all edges
$e^{\prime}\in E(G_{i})$, such that the embedding of $e^{\prime}$ in
${\mathcal{P}}_{i}$ contains the edge $e$; recall that $|J(e)|\leq\eta_{i}$
must hold. Whenever edge $e$ is deleted from graph $X_{i-1}$, this will
trigger the deletion of all edges in its list $J_{i}(e)$ from graph $X_{i}$.
We use the algorithm from Theorem 2.2 in order to maintain, for every expander
$X_{i}$, the set $S_{i}$ of “pruned-out” vertices. When set $S_{i}$ becomes
too large, we re-initialize the graphs $X_{i},X_{i+1},\ldots,X_{r}$, and all
the corresponding data structure.

The outcome of the algorithm (the vertex set $S$ that we maintain) is the set
$S=S_{0}$ of vertices – the vertices that we prune out of the main expander
$X_{0}=X$.

### Initializing the Data Structures

At the beginning of the algorithm, we run procedure
$\mathsf{InitializeExpander}(1)$, that constructs expander $X_{1}$, its
embedding ${\mathcal{P}}_{1}$ into $X_{0}$, and the lists $J_{1}(e)$ for edges
$e\in E(X_{0})$. The procedure then recursively calls to
$\mathsf{InitializeExpander}(2)$, that constructs the data structures for
higher levels. The algorithm for procedure $\mathsf{InitializeExpander}(i)$ is
described in Figure 1. We note that it is identical to the algorithm of
[CS21]. We emphasize that procedure $\mathsf{InitializeExpander}(i)$ is only
called when graph $X_{i-1}$ is defined, with $|V(X_{i-1})|\geq
n/(2\gamma^{i-1})$, and we are guaranteed that $X_{i-1}$ is a
$\varphi_{i-1}/(6\Delta_{i-1})$-expander, whose maximum vertex degree is at
most $\Delta_{i-1}$. From 2.1, every pair of vertices of $X_{i-1}$ is then
guaranteed to have a path of length at most $\frac{8\Delta_{i-1}\log
n}{\varphi_{i-1}}\leq\ell_{i}\leq D_{i}/2$, so throughout the algorithm, tree
$\tau_{i-1}$ spans all vertices of $X_{i-1}$.

We note that we will ensure that, over the course of the algorithm, for all
$1\leq i\leq r$, the size of set $S_{i}$ never exceeds $n/(2\gamma^{i})$.

Algorithm $\mathsf{InitializeExpander}(i)$ Assumption: graph $X_{i-1}$ is
defined; $|V(X_{i-1})|\geq n/(2\gamma^{i-1})$; graph $X_{i-1}$ is a
$\varphi_{i-1}/(6\Delta_{i-1})$-expander, with maximum vertex degree is at
most $\Delta_{i-1}$. • If $i=r+1$, then initialize an ES-Tree $\tau_{r}$ in
graph $X_{r}$, rooted at an arbitrary vertex, with distance threshold
$D_{r+1}$; return. • Let $V_{i}$ be an arbitrary subset of $V(X_{i-1})$, of
cardinality $\left\lceil n/\gamma^{i}\right\rceil$. • Apply the algorithm from
Lemma E.13, to graph $X_{i-1}$, with $T=V_{i}$, to compute an expander $X_{i}$
with vertex set $V_{i}$, and its embedding ${\mathcal{P}}_{i}$ into $X_{i-1}$,
so that $X_{i}$ is a $\varphi_{i}$-expander, with maximum vertex degree at
most $\Delta_{i}$; the paths in ${\mathcal{P}}_{i}$ cause edge-congestion at
most $\eta_{i}$ and have length at most $\ell_{i}$ each. • For every edge
$e\in E(X_{i-1})$, initialize the list $J_{i}(e)$ of all edges of $X_{i}$
whose embedding path in ${\mathcal{P}}_{i}$ contains $e$. • Initialize the
expander pruning algorithm from Theorem 2.2 on graph $X_{i}$, that will
maintain a pruned vertex set $S_{i}\subseteq V(X_{i})$. • Initialize an ES-
tree $\tau_{i-1}$ in graph $X^{\prime}_{i-1}$ that is obtained from $X_{i-1}$
by adding a source vertex $s_{i-1}$ and connecting it to all vertices in
$V(X_{i})$. The tree $\tau_{i-1}$ is rooted at $s_{i-1}$ and has depth
threshold $D_{i}$. • Call $\mathsf{InitializeExpander}(i+1)$.

Figure 1: Algorithm $\mathsf{InitializeExpander}(i)$

### Maintaining the Data Structures

For all $0\leq i<r$, we denote by $X_{i+1}^{(0)}$ the expander graph created
by Procedure $\mathsf{InitializeExpander}(i)$. For all $t>0$, we denote by
$X_{i+1}^{(t)}$ the graph that is obtained from $X_{i+1}^{(0)}$ after $t$ edge
deletions from $X$. As $t$ increases, our algorithm maintains the graph
$X_{i+1}=X_{i+1}^{(t)}\setminus S_{i+1}$. By Theorem 2.2, as long as
$t\leq\varphi_{i+1}|E(X_{i+1})|/(20\Delta_{i+1})$, graph $X_{i+1}$ remains a
$(\varphi_{i+1}/(6\Delta_{i+1}))$-expander, and
$|V(X_{i+1})|\geq|V(X_{i+1}^{(0)})|/2\geq n/(2\gamma^{i})$.

When some edge $e$ is deleted from graph $X$, we call Algorithm
$\mathtt{DeleteEdge}(0,e)$. The algorithm may recursively call to procedure
$\mathtt{DeleteEdge}(i,e^{\prime})$ for other expander graphs $X_{i}$ and
edges $e^{\prime}$. The algorithm $\mathtt{DeleteEdge}(i,e)$ is shown in
Figure 2. We assume that edge $e$ lies in graph $X_{i}$.

Algorithm $\mathtt{DeleteEdge}(i,e)$ Assumption: edge $e$ lies in graph
$X_{i}$. • If $i=r$, delete $e$ from graph $X_{r}$. Recompute the ES-Tree
$\tau_{r}$ in graph $X_{r}$, rooted at any vertex, with depth threshold
$D_{r+1}$; return. • Delete edge $e$ from graph $X_{i}$ and from the data
structure $\tau_{i}$. • Update the pruned-out vertex set $S_{i}$ using the
algorithm from Theorem 2.2, and update the tree $\tau_{i-1}$, by deleting
edges $(s,x)$ for every vertex $x$ that was added to $S_{i}$. • If the total
number of edge deletions from $X_{i}^{(0)}$ exceeds
$\varphi_{i}|E(X_{i}^{(0)})|/(20\Delta_{i})$, call
$\mathsf{InitializeExpander}(i-1)$; return. (Note: here we only count edges
that were deleted from $X$ as part of input edge-deletion sequence, and we do
not include edges that are incident to vertices of $S_{i}$). • Let
$Z_{i}^{new}$ denote the set of edges that were just removed from $X_{i}$.
That is, $Z_{i}^{new}$ contains the edge $e$ and all edges incident to
vertices that were just added to $S_{i}$. • For each edge $e\in Z_{i}^{new}$,
for every edge $e^{\prime}\in J_{i}(e)$, call
$\mathtt{Delete}(i+1,e^{\prime})$.

Figure 2: Algorithm $\mathtt{DeleteEdge}(i,e)$

### Total Update Time

For all $0\leq i\leq r$, we denote $n_{i}=\left\lceil
n/\gamma^{i}\right\rceil$. Recall that $|V(X_{i})|\leq n_{i}$. We bound the
total update time of the algorithm in the following lemma.

######  Lemma E.14.

The total update time of the algorithm is at most
$O\left(\frac{n^{1+O(\epsilon)}\Delta^{5}(\log
n)^{O(1/\epsilon^{2})}}{\varphi^{5}}\right)$.

###### Proof.

Fix an index $1\leq i\leq r$. We partition the execution of the algorithm into
_level- $i$ stages_, where each level-$i$ stage starts when
$\mathsf{InitializeExpander}(i)$ is called (that is, graph $X_{i}$ is
constructed from scratch), and terminates just before the subsequent call to
$\mathtt{InitializeExpander}(i)$. Recall that, over the course of a level-$i$
stage, at most $\varphi_{i}|E(X_{i}^{(0)})|/(20\Delta_{i})$ edges are deleted
from the graph $X_{i}^{(0)}$. We now bound the running time that is needed in
order to initialize and maintain the level-$i$ data structure over the course
of a single level-$i$ stage. This includes the following:

  * •

Constructing expander $X_{i}$ and its embedding ${\mathcal{P}}_{i}$ into graph
$X_{i-1}$, using the algorithm from Lemma E.13; the running time is bounded
by:

$\widetilde{O}\left(\frac{\Delta_{i-1}^{4}n_{i-1}}{\varphi_{i-1}^{3}}+n_{i}^{1+O(\epsilon)}\cdot(\log
n)^{O(1/\epsilon^{2})}\right);$

  * •

Initializing the lists $J_{i}(e)$ for edges $e\in E(X_{i-1})$: the time to
initialize all such lists is bounded by the time needed to compute the
embedding ${\mathcal{P}}_{i}$.

  * •

Initializing and maintaining the ES-Tree $\tau_{i-1}$: the running time is
$\widetilde{O}(|E(X_{i-1})|\cdot
D_{i-1})\leq\widetilde{O}(n_{i-1}\Delta_{i-1}\ell_{i-1})\leq\widetilde{O}\left(n_{i-1}\Delta^{2}_{i-1}/\varphi_{i-1}\right)$.

  * •

Running the algorithm from Theorem 2.2 for expander pruning on the expander
$X_{i}$. Since a single level-$i$ stage may involve the deletion of up to
$k=\varphi_{i}|E(X_{i}^{(0)})|/(20\Delta_{i})$ edges from $X_{i}$, the running
time is bounded by:

$\widetilde{O}\left(\frac{\Delta_{i}^{2}}{\varphi_{i}^{2}}\cdot\frac{\varphi_{i}|E(X_{i}^{(0)})|}{20\Delta_{i}}\right)=\widetilde{O}\left(\frac{n_{i}\Delta_{i}^{2}}{\varphi_{i}}\right).$

  * •

The remaining work, executed by $\mathtt{DeleteEdge}(i-1,e)$, for every edge
$e$ that is deleted from graph $X_{i-1}$ (including edges incident to the
vertices of the pruned out set $S_{i-1}$), requires $O(\eta_{i})$ time per
edge, with total time $O(|E(X_{i-1}^{(0)})|\cdot\eta_{i})\leq
O\left(n_{i-1}\Delta_{i-1}\eta_{i}\right)=\widetilde{O}\left(n_{i-1}\Delta_{i-1}^{3}/\varphi_{i-1}^{2}\right)$.

Therefore, the total time that is needed in order to initialize and maintain
the level-$i$ data structure over the course of a single level-$i$ stage is
bounded by:

$\widetilde{O}\left(\frac{\Delta_{i-1}^{4}n_{i-1}}{\varphi_{i-1}^{3}}+n_{i}^{1+O(\epsilon)}\cdot(\log
n)^{O(1/\epsilon^{2})}+\frac{n_{i}\Delta_{i}^{2}}{\varphi_{i}}\right).$

Note that we did not include in this running time the time required for
maintaining level-$(i+1)$ data structures, that is, calls to
$\mathtt{InitializeExpander}(i+1)$ and $\mathtt{Delete}(i,e)$.

Next, we bound the total number of level-$i$ stages. Consider some index
$1<i^{\prime}\leq r$, and consider a single level-$i^{\prime}$ stage. Clearly,
the total number of edges that are incident to the pruned-out vertices in
$S_{i^{\prime}}$ is bounded by $|E(X_{i^{\prime}}^{(0)})|\leq
O(n_{i^{\prime}}\Delta_{i^{\prime}})$. As the embedding
${\mathcal{P}}_{i^{\prime}+1}$ of $X_{i^{\prime}+1}$ into $X_{i^{\prime}}$ has
congestion at most
$\eta_{i^{\prime}+1}\leq\widetilde{O}(\Delta_{i^{\prime}}^{2}/\varphi_{i^{\prime}}^{2})$,
this can cause at most
$\widetilde{O}\left(n_{i^{\prime}}\Delta_{i^{\prime}}^{3}/\varphi_{i^{\prime}}^{2}\right)$
edge-deletions from graph $X_{i^{\prime}+1}^{(0)}$. As a single
level-$(i^{\prime}+1)$ stage requires
$k_{i^{\prime}+1}\geq\Omega\left(\varphi_{i^{\prime}+1}|E(X_{i^{\prime}+1}^{(0)})|/\Delta_{i^{\prime}+1}\right)=\Omega(\varphi_{i^{\prime}+1}n_{i^{\prime}+1})$
edge-deletions from $G_{i^{\prime}+1}^{(0)}$, the number of
level-$(i^{\prime}+1)$ stages that are contained in a single
level-$i^{\prime}$ stage is bounded by:

$\widetilde{O}\left(\frac{n_{i^{\prime}}\Delta_{i^{\prime}}^{3}/\varphi_{i^{\prime}}^{2}}{n_{i^{\prime}+1}\varphi_{i^{\prime}+1}}\right)=\widetilde{O}\left(\frac{n^{\epsilon}\Delta_{i^{\prime}}^{3}}{\varphi_{i^{\prime}}^{2}\cdot\varphi_{i^{\prime}+1}}\right).$

Since we only need to support at most $\varphi|E(X)|/(20\Delta)$ edge
deletions from the original graph $X$, there is only a single level-$0$ stage.
Recalling that $\varphi_{0}=\varphi$, and for all $1\leq i\leq r$,
$\varphi_{i}=\hat{\varphi}=1/(\log n)^{O(1/\epsilon)}$, and that
$\Delta_{0}=\Delta$, and for all $1\leq i\leq r$, $\Delta_{i}=O(\log n)$, we
get that for all $1\leq i\leq r$, the total number of level-$i$ stages is
bounded by:

$O\left(\frac{n^{\epsilon i}(\log
n)^{O(i)}\Delta^{3}}{\hat{\varphi}^{3i}\cdot\varphi^{2}}\right),$

while the running time of a single level-$i$ phase, for $i>1$ is bounded by:

$\begin{split}&\widetilde{O}\left(\frac{\Delta_{i-1}^{4}n_{i-1}}{\varphi_{i-1}^{3}}+n_{i}^{1+O(\epsilon)}\cdot(\log
n)^{O(1/\epsilon^{2})}+\frac{n_{i}\Delta_{i}}{\varphi_{i}}\right)\\\
&\leq\widetilde{O}\left(\frac{n}{n^{(i-1)\epsilon}\hat{\varphi}^{3}}+n^{(1-i\epsilon)(1+O(\epsilon))}\cdot(\log
n)^{O(1/\epsilon^{2})}+\frac{n}{n^{i\epsilon}\hat{\varphi}}\right)\\\
&\leq\widetilde{O}\left(\frac{n^{1+O(\epsilon)}\cdot(\log
n)^{O(1/\epsilon^{2})}}{n^{i\epsilon}\hat{\varphi}^{3}}\right).\end{split}$

For $i=1$, the running time of a single level-$1$ phase is bounded by:

$\widetilde{O}\left(\frac{\Delta^{4}n}{\varphi^{3}}+n^{(1+O(\epsilon))(1-\epsilon)}\cdot(\log
n)^{O(1/\epsilon^{2})}+\frac{n}{\hat{\varphi}n^{\epsilon}}\right).$

Therefore, for every $1<i\leq r$, the total running time for maintaining
level-$i$ data structure is bounded by:

$\widetilde{O}\left(\frac{n^{1+O(\epsilon)}(\log
n)^{O(1/\epsilon^{2})}}{n^{i\epsilon}\hat{\varphi}^{3}}\right)\cdot
O\left(\frac{n^{\epsilon i}(\log
n)^{O(i)}\Delta^{3}}{\hat{\varphi}^{3i}\cdot\varphi^{2}}\right)\leq\widetilde{O}\left(\frac{n^{1+O(\epsilon)}(\log
n)^{O(1/\epsilon^{2})}\Delta^{3}}{\hat{\varphi}^{3i+3}\cdot\varphi^{2}}\right)$

Since $i\leq r\leq 1/\epsilon$, and $\hat{\varphi}=1/(\log
n)^{O(1/\epsilon)}$, this is bounded by:
$O\left(\frac{n^{1+O(\epsilon)}\Delta^{3}(\log
n)^{O(1/\epsilon^{2})}}{\varphi^{2}}\right)$.

Lastly, the total running time for maintaining the level-$1$ data structure is
bounded by:

$\widetilde{O}\left(\frac{\Delta^{4}n}{\varphi^{3}}+\frac{n^{1+O(\epsilon)}\cdot(\log
n)^{O(1/\epsilon^{2})}}{\hat{\varphi}^{2}}\right)\cdot\widetilde{O}\left(\frac{n^{\epsilon}\Delta^{3}}{\hat{\varphi}^{3}\cdot\varphi^{2}}\right)\leq\widetilde{O}\left(\frac{n^{1+O(\epsilon)}\Delta^{7}(\log
n)^{O(1/\epsilon^{2})}}{\varphi^{5}}\right).$

Summing this up over all $1\leq i\leq r$, we get that the total update time of
the algorithm is at most $O\left(\frac{n^{1+O(\epsilon)}\Delta^{7}(\log
n)^{O(1/\epsilon^{2})}}{\varphi^{5}}\right)$.

### Responding to expander-short-path-query

Lastly, we provide an algorithm for responding to queries expander-short-path-
query. Recall that, given a pair of vertices $x,y\in V(X)\setminus S$, the
goal is to return a simple $x$-$y$ path $P$ in $X\setminus S$ of length at
most $O\left(\Delta^{2}(\log n)^{O(1/\epsilon^{2})}/\varphi\right)$, in time
$O(|E(P)|)$. We call algorithm $\mathtt{Query}(0,x,y)$, that is described in
Figure 3, which recursively calls $\mathtt{Query}(i,x^{\prime},y^{\prime})$
for $i>0$. The idea of the algorithm is simple: we use the ES-Tree $\tau_{0}$
in graph $X_{0}$ in order to compute two paths: one path connecting $x$ to
some vertex $x^{\prime}\in V(X_{1})$, and one path connecting $y$ to some
vertex $y^{\prime}\in V(X_{1})$, and then recursively call
$\mathtt{Query}(1,x^{\prime},y^{\prime})$ to obtain a short path connecting
$x^{\prime}$ to $y^{\prime}$ in $X_{1}$. We then use the embedding
${\mathcal{P}}_{1}$ of $X_{1}$ into $G_{0}$ in order to convert the resulting
path into an $x^{\prime}$-$y^{\prime}$ path in $X_{0}$. The final path
connecting $x$ to $y$ is obtained by concatenating the resulting three paths.

Algorithm $\mathtt{Query}(i,x,y)$ Assumption: vertices $x,y$ lie in graph
$X_{i}$. 1. If $i=r$, return the unique $x$-$y$ path in three $\tau_{r}$, of
length at most $D_{r+1}$. 2. Compute, in tree $\tau_{i}$, a unique path
$Q_{x,x^{\prime}}$ connecting $x$ to some vertex $x^{\prime}\in V(X_{i+1})$,
and a unique path $Q_{y^{\prime},y}$ connecting $y$ to some vertex
$y^{\prime}\in V(X_{i+1})$. The length of each path is bounded by $D_{i+1}$.
3. If $x^{\prime}=y^{\prime}$, set $R_{x^{\prime},y^{\prime}}=\emptyset$;
otherwise set
$R_{x^{\prime},y^{\prime}}=\mathtt{Query}(i+1,x^{\prime},y^{\prime})$. 4. Let
$Q_{x^{\prime},y^{\prime}}$ be a path in graph $X_{i}$ obtained by
concatenating, for all edges $e^{\prime}\in R_{x^{\prime},y^{\prime}}$, the
corresponding path $P(e^{\prime})\in{\mathcal{P}}_{i+1}$ from the embedding of
$X_{i+1}$ into $X_{i}$; recall that the length of each such path
$P(e^{\prime})$ is bounded by $\ell_{i+1}$. 5. Return the path $Q_{u,v}$,
obtained by concatenating three paths:
$Q_{x,x^{\prime}},Q_{x^{\prime},y^{\prime}}$, and $Q_{y^{\prime},y}$.

Figure 3: Algorithm $\mathtt{Query}(i,x,y)$

The following lemma summarizes the guarantees of the algorithm for processing
short-path queries.

######  Lemma E.15.

For all $0\leq i\leq r$, algorithm $\mathtt{Query}(i,x,y)$, given a pair $x,y$
of vertices in graph $X_{i}$, returns a path connecting $x$ to $y$ in graph
$X_{i}$ of length at most $L_{i}=(48c^{2}\log^{2}n/\hat{\varphi})^{r-i+1}$ for
$i>0$, and of length at most
$L_{0}=(48c^{2}\log^{2}n/\hat{\varphi})^{r+1}\cdot\Delta^{2}/\varphi$ for
$i=0$.

###### Proof.

The proof is by induction on $i$, where the base case is $i=r$. Recall that,
as observed already, one corollary from Lemma E.13, every pair $x,y$ of
vertices of $X_{r}$ have a path of length at most $D_{r+1}=4\ell_{r+1}\leq
4\hat{\ell}=4c^{2}\log^{2}n/\hat{\varphi}$ connecting them in $X_{r}$. The
path returned by algorithm $\mathtt{Query}(r,x,y)$ has length at most
$2D_{r+1}\leq 8c^{2}\log^{2}n/\hat{\varphi}\leq L_{r}$.

Assume now that the claim is true for some value $i+1$; we now prove it for
value $i$. Consider algorithm $\mathtt{Query}(i,x,y)$. We are guaranteed that
the algorithm computes a path $Q_{x,x^{\prime}}$ connecting $x$ to some vertex
$x^{\prime}\in V(X_{i+1})$, and a path $Q_{y^{\prime},y}$ connecting $y$ to
some vertex $y^{\prime}\in V(X_{i+1})$, in graph $X_{i}$, where the lengths of
both paths are bounded by $D_{i+1}$. The path
$R_{x^{\prime},y^{\prime}}=\mathtt{Query}(i+1,x^{\prime},y^{\prime})$ has
length at most $L_{i+1}$, and so the resulting path
$Q_{x^{\prime},y^{\prime}}$ has length at most $\ell_{i+1}\cdot L_{i+1}$.
Therefore, altogether, the final $x$-$y$ path computed by the algorithm has
length at most:

$2D_{i+1}+\ell_{i+1}\cdot L_{i+1}=8\ell_{i+1}+L_{i+1}\ell_{i+1}.$

For $i\geq 1$, $\ell_{i+1}=c^{2}\log^{2}n/\hat{\varphi}$, while
$\Delta_{i}=c\log n$, and so the length of the path is bounded by:

$8\ell_{i+1}+L_{i+1}\ell_{i+1}\leq 2L_{i+1}\cdot
c^{2}\log^{2}n/\hat{\varphi}\leq(2c^{2}\log^{2}n/\hat{\varphi})\cdot(48c^{2}\log^{2}n/\hat{\varphi})^{r-i}\leq(48c^{2}\log^{2}n/\hat{\varphi})^{r-i+1}.$

For $i=0$, $\ell_{1}=c\Delta\log n/\varphi$ and $\Delta_{0}=\Delta$, so the
length of the path is bounded by:

$8c\log n/\varphi+L_{1}\cdot c\Delta\log n/\varphi\leq(48c\Delta^{2}\log
n/\varphi)\cdot(48c^{2}\log^{2}n/\hat{\varphi})^{r-1}\leq(48c^{2}\log^{2}n/\hat{\varphi})^{r}\cdot\Delta^{2}/\varphi.$

From the algorithm’s description it is immediate to verify that the running
time is bounded by $O(|E(Q)|)$, where $Q$ is the returned path.

Recalling that $r=\left\lfloor 1/\epsilon\right\rfloor$ and
$\hat{\varphi}=1/(\log n)^{O(1/\epsilon)}$, we obtain the following immediate
corollary.

######  Corollary E.16.

Given any pair of vertices $x,y\in V(G)\setminus S$, algorithm
$\mathtt{Query}(0,x,y)$ returns a (possibly non-simple) $x$-$y$ path $Q$ in
$X\setminus S$, of length at most $O\left(\Delta^{2}(\log
n)^{O(1/\epsilon^{2})}/\varphi\right)$, in time $O(|E(Q)|)$.

####  E.2.1 Proof of Lemma E.13

The proof of the lemma is very similar to the proof of Lemma E.1. The
algorithm employs the cut-matching game outlined in Section E.1. The main
difference is that the Matching Player is implemented via the following
theorem, that was proved in [CGL+19], and its corollary.

######  Theorem E.17.

(Theorem 3.2 in [CGL+19], builds on similar result of [CK19]) There is a
deterministic algorithm, that, given an $n$-vertex graph $G=(V,E)$ with
maximum vertex degree $\Delta$, and two disjoint subsets $A,B$ of its
vertices, with $|A|\leq|B|$, and integers $z\geq 0$, $\ell\geq 32\Delta\log
n$, computes one of the following:

  * •

either a collection ${\mathcal{P}}^{\prime}$ of paths, each of which connects
a distinct vertex of $A$ to a distinct vertex of $B$, with
$|{\mathcal{P}}^{\prime}|\geq|A|-z$, such that the length of every path in
${\mathcal{P}}^{\prime}$ is at most $\ell$, and the paths in
${\mathcal{P}}^{\prime}$ cause congestion at most $\ell^{2}$; or

  * •

a cut $(X,Y)$ in $G$, with $|X|,|Y|\geq z/2$, and $\varphi_{G}(X,Y)\leq
72\Delta\log n/\ell$.

The running time of the algorithm is $\tilde{O}(\ell^{3}|E(G)|+\ell^{2}n)$.

We obtain the following immediate corollary of Theorem E.17.

######  Corollary E.18.

There is a deterministic algorithm, that, given an $n$-vertex graph $X=(V,E)$
with maximum vertex degree $\Delta$, that is a $\varphi$-expander, and two
disjoint subsets $A,B$ of its vertices, with $|A|\leq|B|$, computes a
collection ${\mathcal{P}}^{\prime}$ of paths, where each path in
${\mathcal{P}}^{\prime}$ connects a distinct vertex from $A$ to a distinct
vertex from $B$, and $|{\mathcal{P}}^{\prime}|=|A|$, such that the paths in
${\mathcal{P}}^{\prime}$ cause congestion at most
$O\left(\frac{\Delta^{2}\log^{2}n}{\varphi^{2}}\right)$, and every path has
length at most $O\left(\frac{\Delta\log n}{\varphi}\right)$. The running time
of the algorithm is $\widetilde{O}(\Delta^{4}n/\varphi^{3})$.

###### Proof.

We set the parameter $\ell=\frac{150\Delta\log n}{\varphi}$, and apply the
algorithm from Theorem E.17 to graph $X$, vertex sets $A$ and $B$, and the
parameter $\ell$, setting $z=0$. Notice that the algorithm may not return a
cut $(X,Y)$ with $\varphi_{G}(X,Y)\leq 72\Delta\log n/\ell<\varphi$, because
graph $X$ is a $\varphi$-expander. Therefore, it must return a collection
${\mathcal{P}}$ of paths, with each path connecting a distinct vertex from $A$
to a distinct vertex from $B$, and $|{\mathcal{P}}|=|A|$. The length of each
path in ${\mathcal{P}}$ is bounded by $\ell\leq O\left(\frac{\Delta\log
n}{\varphi}\right)$, and the paths in ${\mathcal{P}}$ cause congestion at most
$\ell^{2}\leq O\left(\frac{\Delta^{2}\log^{2}n}{\varphi^{2}}\right)$. The
running time of the algorithm is bounded by
$\tilde{O}(\ell^{3}|E(G)|+\ell^{2}n)\leq\widetilde{O}(\Delta^{4}n/\varphi^{3})$.

The remainder of the proof of Lemma E.13 is almost identical to the proof of
Lemma E.1. We first need to take care of the special case when
$\epsilon<c^{\prime\prime}/\log k$, where $c^{\prime\prime}$ is the constant
from Corollary E.9. In this case, $k<2^{c^{\prime\prime}/\epsilon}$ holds,
and, since we have assumed that $\varphi\leq 1/2^{\Omega(1/\epsilon)}$, we can
assume that $\varphi\leq 1/k$. In this case, we let $X^{\prime}$ be an
arbitrary constant-degree $\varphi^{\prime}$-expander, where
$\varphi^{\prime}=\Omega(1)$, with $V(X^{\prime})=T$. In order to embed this
expander into $X$, we select, for every edge $e=(x,y)\in E(X^{\prime})$, a
shortest $x$-$y$ path $P(e)$ connecting $x$ to $y$ in $X$; from 2.1, the
length of $P(e)$ is at most $O\left(\frac{\Delta\log n}{\varphi}\right)$. We
then let ${\mathcal{P}}=\left\\{P(e)\mid e\in E(X^{\prime})\right\\}$ be the
embedding of $X^{\prime}$ into $X$. Clearly, the congestion of this embedding
is bounded by $k\leq 1/\varphi$. The running time of this algorithm is bounded
by $O(k|E(X)|)\leq O(n\Delta/\varphi)$. Therefore, we assume from now on that
$\epsilon\geq c^{\prime\prime}/\log k$.

We start with a graph $X^{\prime}$, whose vertex set is $T$, and edge set is
empty. We initialize ${\mathcal{P}}=\emptyset$. For convenience, denote
$|T|=k$; assume for now that $k$ is an even integer. We then perform at most
$O(\log k)$ iterations. The $i$th iteration is performed as follows. First, we
apply the algorithm from Corollary E.9 to graph $X^{\prime}$. Assume for now
that the algorithm produces a partition $(A_{i},B_{i})$ of $V(X^{\prime})$
with $|A_{i}|,|B_{i}|\geq k/4$, $|A_{i}|\leq|B_{i}|$, and
$|E_{X^{\prime}}(A_{i},B_{i})|\leq k/100$. We let
$(A_{i}^{\prime},B_{i}^{\prime})$ be any partition of $V(X^{\prime})$ with
$|A_{i}^{\prime}|=|B_{i}^{\prime}|$ and $A_{i}\subseteq A_{i}^{\prime}$. Next,
we apply the algorithm from Corollary E.18 to graph $X^{\prime}$ and vertex
sets $A_{i}^{\prime},B_{i}^{\prime}$. The algorithm returns a collection
${\mathcal{P}}_{i}$ of paths, where each path in ${\mathcal{P}}_{i}$ connects
a distinct vertex from $A_{i}^{\prime}$ to a distinct vertex from
$B_{i}^{\prime}$ and $|{\mathcal{P}}_{i}|=|A_{i}^{\prime}|$, such that the
paths in ${\mathcal{P}}^{\prime}$ cause congestion at most
$O\left(\frac{\Delta^{2}\log^{2}n}{\varphi^{2}}\right)$, and every path has
length at most $O\left(\frac{\Delta\log n}{\varphi}\right)$. We let $M_{i}$ be
the perfect matching between vertices of $A_{i}^{\prime}$ and vertices of
$B_{i}^{\prime}$, where $(x,y)\in M_{i}$ iff some path in ${\mathcal{P}}_{i}$
connects $x$ to $y$. We add the paths in ${\mathcal{P}}_{i}$ to
${\mathcal{P}}$, and continue to the next iteration.

Finally, assume that the algorithm from Corollary E.9 returns a subset
$S\subseteq V(X^{\prime})$ of at least $k/2$ vertices of $X^{\prime}$, such
that graph $X[S]$ is a $\varphi^{\prime}$-expander, for
$\varphi^{\prime}=1/(\log k)^{O(1/\epsilon)}$. Let $i$ be the index of the
current iteration. We then set $A_{i}^{\prime}=V(X)\setminus S$ and
$B^{\prime}_{i}=S$, and apply the algorithm from Theorem E.11 to graph
$X^{\prime}$, and vertex sets $A_{i}^{\prime},B_{i}^{\prime}$. We continue
exactly as before, obtaining a matching $M_{i}$ between the vertices of
$A^{\prime}_{i}$ and the vertices of $B_{i}^{\prime}$, of cardinality
$|A^{\prime}_{i}|$, and its corresponding routing ${\mathcal{P}}_{i}$. We let
$M_{i}$ be a partial matching between vertices of $A_{i}^{\prime}$ and
vertices of $B_{i}^{\prime}$, where $(x,y)\in M_{i}^{\prime}$ iff some path in
${\mathcal{P}}_{i}$ connects $x$ to $y$, so $|M_{i}|=|A^{\prime}_{i}|$. We
then add the edges of $M_{i}$ to graph $X^{\prime}$, add the paths in
${\mathcal{P}}_{i}$ to set ${\mathcal{P}}$, and terminate the algorithm,
returning the graph $X^{\prime}$ and its embedding ${\mathcal{P}}$.

From Theorem E.10, the total number of iterations in the algorithm is bounded
by $O(\log k)$, and the final graph $X^{\prime}$ is a
$\hat{\varphi}$-expander, for $\hat{\varphi}=1/(\log k)^{O(1/\epsilon)}$. The
paths in ${\mathcal{P}}$ provide an embedding of the graph $X^{\prime}$ into
$X$, where the length of every path in ${\mathcal{P}}$ is at most
$O\left(\frac{\Delta\log n}{\varphi}\right)$. Since the number of iterations
is at most $O(\log k)$, and each set ${\mathcal{P}}_{i}$ of paths causes edge-
congestion at most $O\left(\frac{\Delta^{2}\log^{2}n}{\varphi^{2}}\right)$,
the total edge-congestion caused by the paths in ${\mathcal{P}}$ is at most
$O\left(\frac{\Delta^{2}\log^{3}n}{\varphi^{2}}\right)$.

Recall that we have assumed that $|T|$ is an even integer. If this is not the
case, then we let $t\in T$ be any vertex, and we run the same algorithm as
above, replacing the set $T$ of terminals with
$T^{\prime}=T\setminus\left\\{t\right\\}$. Let $X^{\prime}$ be the resulting
$\hat{\varphi}$-expander, with $V(X^{\prime})=T^{\prime}$, and let
${\mathcal{P}}$ be its embedding into $X$. Let $t^{\prime}\in T^{\prime}$ ba
any vertex, and let $P^{\prime}$ be the shortest path connecting $t$ to
$t^{\prime}$ in graph $X$. From 2.1, the length of $P^{\prime}$ is at most
$O(\Delta\log n/\varphi)$. We then obtain the final expander
$X^{\prime\prime}$ from $X^{\prime}$, by inserting the vertex $t$ and the edge
$(t,t^{\prime})$ into it. The set
${\mathcal{P}}\cup\left\\{P^{\prime}\right\\}$ of paths defines an embedding
of $X^{\prime\prime}$ into $X$ with edge-congestion bounded by
$O\left(\frac{\Delta^{2}\log^{3}n}{\varphi^{2}}\right)$, with path-lengths
bounded by $O\left(\frac{\Delta\log n}{\varphi}\right)$. It is easy to verify
that graph $X^{\prime\prime}$ remains a $\varphi^{\prime\prime}$-expander, for
$\varphi^{\prime\prime}=1/(\log k)^{O(1/\epsilon)}$. It now remains to analyze
the running time of the algorithm.

The algorithm consists of $O(\log k)$ iterations. Each iteration involves
applying the algorithm from Corollary E.9, whose running time is
$O\left(k^{1+O(\epsilon)}\cdot(\log k)^{O(1/\epsilon^{2})}\right)$, and the
algorithm from Corollary E.18, whose running time is
$\widetilde{O}(\Delta^{4}n/\varphi^{3})$. Therefore, the total running time of
the algorithm is
$\widetilde{O}(\Delta^{4}n/\varphi^{3})+O\left(k^{1+O(\epsilon)}\cdot(\log
k)^{O(1/\epsilon^{2})}\right)$.

## References

  * [ABCP98] Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg.  Near-linear time construction of sparse neighborhood covers.  SIAM Journal on Computing, 28(1):263–277, 1998.
  * [ACT14] Ittai Abraham, Shiri Chechik, and Kunal Talwar.  Fully dynamic all-pairs shortest paths: Breaking the O (n) barrier.  In LIPIcs-Leibniz International Proceedings in Informatics, volume 28. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014.
  * [AHK12] Sanjeev Arora, Elad Hazan, and Satyen Kale.  The multiplicative weights update method: a meta-algorithm and applications.  Theory of Computing, 8(1):121–164, 2012.
  * [AP90] Baruch Awerbuch and David Peleg.  Sparse partitions.  In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pages 503–513. IEEE, 1990.
  * [BBG+20] Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun.  Fully-dynamic graph sparsifiers against an adaptive adversary.  arXiv preprint arXiv:2004.08432, 2020.
  * [BC16] Aaron Bernstein and Shiri Chechik.  Deterministic decremental single source shortest paths: beyond the O(mn) bound.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 389–397. ACM, 2016.
  * [BC17] Aaron Bernstein and Shiri Chechik.  Deterministic partially dynamic single source shortest paths for sparse graphs.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 453–469. SIAM, 2017.
  * [Ber16] Aaron Bernstein.  Maintaining shortest paths under deletions in weighted directed graphs.  SIAM Journal on Computing, 45(2):548–574, 2016.
  * [Ber17] Aaron Bernstein.  Deterministic partially dynamic single source shortest paths in weighted graphs.  In LIPIcs-Leibniz International Proceedings in Informatics, volume 80. Schloss Dagstuhl-Leibniz-Center for Computer Science, 2017.
  * [BHG+20] Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein.  New techniques and fine-grained hardness for dynamic near-additive spanners.  arXiv preprint arXiv:2010.10134, 2020.
  * [BHS07] Surender Baswana, Ramesh Hariharan, and Sandeep Sen.  Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths.  J. Algorithms, 62(2):74–92, 2007.
  * [BKS12] Surender Baswana, Sumeet Khurana, and Soumojit Sarkar.  Fully dynamic randomized algorithms for graph spanners.  ACM Trans. Algorithms, 8(4):35:1–35:51, 2012.
  * [BR11] Aaron Bernstein and Liam Roditty.  Improved dynamic algorithms for maintaining approximate shortest paths under deletions.  In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1355–1365, 2011.
  * [CGL+19] Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak.  A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond.  CoRR, abs/1910.08025, 2019.
  * [Che18] Shiri Chechik.  Near-optimal approximate decremental all pairs shortest paths.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 170–181. IEEE, 2018.
  * [CK19] Julia Chuzhoy and Sanjeev Khanna.  A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 389–400, 2019.
  * [CS21] Julia Chuzhoy and Thatchaphol Saranurak.  Deterministic algorithms for decremental shortest paths via layered core decomposition.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2478–2496. SIAM, 2021.
  * [CZ20] Shiri Chechik and Tianyi Zhang.  Dynamic low-stretch spanning trees in subpolynomial time.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 463–475. SIAM, 2020.
  * [DHZ00] Dorit Dor, Shay Halperin, and Uri Zwick.  All-pairs almost shortest paths.  SIAM J. Comput., 29(5):1740–1759, 2000.
  * [Din06] Yefim Dinitz.  Dinitz’ algorithm: The original version and Even’s version.  In Theoretical computer science, pages 218–240. Springer, 2006\.
  * [ES81] Shimon Even and Yossi Shiloach.  An on-line edge-deletion problem.  Journal of the ACM (JACM), 28(1):1–4, 1981.
  * [FG19] Sebastian Forster and Gramoz Goranci.  Dynamic low-stretch trees via dynamic low-diameter decompositions.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 377–388, 2019.
  * [FGH20] Sebastian Forster, Gramoz Goranci, and Monika Henzinger.  Dynamic maintenance of low-stretch probabilistic tree embeddings with applications.  CoRR, abs/2004.10319, 2020.
  * [FHN14a] Sebastian Forster, Monika Henzinger, and Danupon Nanongkai.  Decremental single-source shortest paths on undirected graphs in near-linear total update time.  In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 146–155, 2014.
  * [FHN14b] Sebastian Forster, Monika Henzinger, and Danupon Nanongkai.  A subquadratic-time algorithm for decremental single-source shortest paths.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1053–1072, 2014.
  * [Fle00] Lisa Fleischer.  Approximating fractional multicommodity flow independent of the number of commodities.  SIAM J. Discrete Math., 13(4):505–520, 2000.
  * [GK98] Naveen Garg and Jochen Könemann.  Faster and simpler algorithms for multicommodity flow and other fractional packing problems.  In 39th Annual Symposium on Foundations of Computer Science, FOCS ’98, November 8-11, 1998, Palo Alto, California, USA, pages 300–309, 1998.
  * [GVY95] N. Garg, V.V. Vazirani, and M. Yannakakis.  Approximate max-flow min-(multi)-cut theorems and their applications.  SIAM Journal on Computing, 25:235–251, 1995.
  * [GWN20] Maximilian Probst Gutenberg and Christian Wulff-Nilsen.  Deterministic algorithms for decremental approximate shortest paths: Faster and simpler.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2522–2541. SIAM, 2020.
  * [HdLT01] Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup.  Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.  J. ACM, 48(4):723–760, July 2001.
  * [HK95] Monika Rauch Henzinger and Valerie King.  Fully dynamic biconnectivity and transitive closure.  In Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on, pages 664–672. IEEE, 1995.
  * [HKN16] Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai.  Dynamic approximate all-pairs shortest paths: Breaking the o(mn) barrier and derandomization.  SIAM Journal on Computing, 45(3):947–1006, 2016.
  * [HKNS15] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak.  Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture.  In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 21–30, 2015.
  * [KKOV07] Rohit Khandekar, Subhash Khot, Lorenzo Orecchia, and Nisheeth K Vishnoi.  On a cut-matching game for the sparsest cut problem.  Univ. California, Berkeley, CA, USA, Tech. Rep. UCB/EECS-2007-177, 6(7):12, 2007.
  * [KŁ19] Adam Karczmarz and Jakub Łacki.  Reliable hubs for partially-dynamic all-pairs shortest paths in directed graphs.  arXiv preprint arXiv:1907.02266, 2019.
  * [KMP12] Jonathan A. Kelner, Gary L. Miller, and Richard Peng.  Faster approximate multicommodity flow using quadratically coupled flows.  In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 1–18, 2012\.
  * [KRV09] Rohit Khandekar, Satish Rao, and Umesh Vazirani.  Graph partitioning using single commodity flows.  Journal of the ACM (JACM), 56(4):19, 2009.
  * [ŁN20] Jakub Łacki and Yasamin Nazari.  Near-optimal decremental approximate multi-source shortest paths.  arXiv preprint arXiv:2009.08416, 2020.
  * [LR99] F. T. Leighton and S. Rao.  Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.  Journal of the ACM, 46:787–832, 1999.
  * [Mad10] Aleksander Madry.  Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms.  In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 121–130, 2010.
  * [RZ11] Liam Roditty and Uri Zwick.  On dynamic shortest paths problems.  Algorithmica, 61(2):389–401, 2011.
  * [RZ12] Liam Roditty and Uri Zwick.  Dynamic approximate all-pairs shortest paths in undirected graphs.  SIAM Journal on Computing, 41(3):670–683, 2012.
  * [SW19] Thatchaphol Saranurak and Di Wang.  Expander decomposition and pruning: Faster, stronger, and simpler.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2616–2635, 2019.
  * [TZ01] M. Thorup and U. Zwick.  Approximate distance oracles.  Annual ACM Symposium on Theory of Computing, 2001.
  * [WW18] Virginia Vassilevska Williams and R Ryan Williams.  Subcubic equivalences between path, matrix, and triangle problems.  Journal of the ACM (JACM), 65(5):1–38, 2018.
  * [Zwi98] Uri Zwick.  All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms.  In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280), pages 310–319. IEEE, 1998.