vertices of $Z\cap\beta$ are deleted from graph $G$, and hence from set
$\beta$ as well. We say that the vertices of $Z\cap\beta$ are deleted from
$\beta$ _indirectly_.

Let $\Lambda$ denote the total increase in the lengths of edges over the
course of the algorithm, and denote $W^{0}=W^{0}(G)=n$. We also denote the
initial graph $G$ by $G^{0}$, and the set of all vertices that were deleted
from $\beta$ over the course of the algorithm, either directly or indirectly,
by $\beta^{\prime}$. We need the following claim and its corollary, whose
proofs are deferred to Section C.3 and C.4 of Appendix, respectively.

######  Claim 6.12.

$\Lambda\leq 4n-4|\beta^{0}|+5\Delta\cdot(\log N)^{64}\leq 4n$ and
$|\beta^{\prime}|\leq 45n-45|\beta^{0}|+56\Delta\cdot(\log N)^{64}$.

######  Corollary 6.13.

Throughout the algorithm, $\sum_{v\in V(G)\setminus\beta}w(v)\leq 0.2|\beta|$.

Note that the subdivided graph $H$ of $G$ is identical to graph $G$, so we can
use the adjacency list representation of $G$ also as the adjacency list
representation of $H$. We define a parameter $d^{\prime}=\frac{d}{(\log
N)^{64}}$. Recall that, from the definition of the
$\mathsf{MaintainSpecialCluster}$ problem, we are guaranteed that $d\leq
2^{r\cdot\sqrt{\log N}}$, and also that
$d\leq\frac{\eta}{\Delta}\left(n-|\beta^{0}|+\Delta\cdot(\log
N)^{64}\right)\leq n$, since $\eta\leq\Delta$, and
$\Delta\leq\frac{|\beta^{0}|}{(\log N)^{128}}$ from the problem definition.
Therefore, $d^{\prime}\leq\min\left\\{\frac{2^{r\sqrt{\log
N}}}{\log^{8}N},\frac{n}{8}\right\\}$. Since $|\beta^{0}|\geq\frac{99n}{100}$
from the problem definition, and $d^{\prime}\geq 1$ (as $d\geq(\log N)^{64}$),
we get that $|\beta^{0}|\geq\frac{W^{0}}{256d^{\prime}}$.

We apply the algorithm for the $\mathsf{ConnectToCenters}$ problem from
Theorem 6.7 to graph $G$, set $\beta$ of vertices, and parameters
$N,d^{\prime}$, and $r$. From our discussion, this is a valid input to the
problem. Recall that the algorithm uses a parameter $\rho=\frac{2^{12}\cdot
W^{0}\cdot\log^{3}N}{|\beta^{0}|}$. Since, from the definition of the
$\mathsf{MaintainSpecialCluster}$ problem, $|\beta^{0}|\geq\frac{99n}{100}$,
while $W^{0}=n$, we get that $\rho=O(\log^{3}N)$. Our algorithm consists of at
most $\Delta$ phases, that correspond to the phases of the
$\mathsf{ConnectToCenters}$ problem. Recall that the purpose of each such
phase is to construct a valid Layered Connectivity Data Structure with
$U_{\lambda}=\emptyset$. Our algorithm will only respond to queries at the end
of each phase, once such a data structure is obtained.

We now consider a single phase of the algorithm for the
$\mathsf{ConnectToCenters}$ problem, and one of its iterations. Assume first
that the algorithm produces a strongly well-structured
$\frac{1}{d^{\prime}}$-sparse cut $(A,B)$ in $G$ with $w(A)\geq 1.8|\beta\cap
A|$. Since $d^{\prime}=\frac{d}{(\log N)^{64}}$, the sparsity of the cut is at
most $\frac{(\log N)^{64}}{d}$. We claim that $w(A)<w(B)$ must hold in the
following simple obsevation, whose proof is deferred to Section C.5 of
appendix.

######  Observation 6.14.

$w(A)<w(B)$ must hold.

We delete from $G$ the vertices of $A$, and the endpoints of the edges of
$E_{G}(A,B)$ that lie in $B$, and continue with the resulting graph.

Next, we show that the algorithm to the $\mathsf{ConnectToCenters}$ may never
produce a weakly well-structured cut $(A^{\prime},B^{\prime})$ in graph $H$,
with $|A^{\prime}|\geq\frac{511|V(H)|}{512}$,
$|A^{\prime}\cap\beta|<\frac{2|\beta|}{\log^{3}N}$, and
$|E_{H}(A^{\prime},B^{\prime})|\leq\frac{|V(H)|}{d^{\prime}\cdot\log^{6}N}$.
Indeed, assume for contradiction that the algorithm produces such a cut. Since
every special edge incident to a vertex of $\beta$ has length $1$, we get that
$|V(H)\setminus\beta|=\sum_{v\in V(G)\setminus\beta}w(v)|\leq 0.2|\beta|$ from
Corollary 6.13. But then:

$|A^{\prime}|\leq|V(H)\setminus\beta|+\frac{2|\beta|}{\log^{3}N}\leq
0.21|\beta|.$

Since $|V(H)|\geq|\beta|$, it is then impossible that
$|A^{\prime}|\geq\frac{511|V(H)|}{512}$, a contradiction.

Therefore, if the algorithm for the $\mathsf{ConnectToCenters}$ problem does
not produce a a strongly well-structured $\frac{1}{d^{\prime}}$-sparse cut
$(A,B)$ in $G$ with $w(A)\geq 1.8|\beta\cap A|$, it must produce a valid
Layered Connectivity Data Structure, with $U_{\lambda}=\emptyset$. In this
case, our algorithm is ready to respond to a query. Let $x$ be a query vertex
that it receives. If $x\in\beta$, then we return a path consisting of the
vertex $x$ itself. Otherwise, we construct a path $P$ connecting $x$ to some
vertex $y\in\beta$, as follows. Since $U_{\lambda}=\emptyset$, there must be
an integer $1\leq i<\lambda$ with $x\in U_{i}$. We consider the path
$K(x)\in{\mathcal{Q}}_{i}$, that connects $x$ to some vertex $x_{1}\in
U_{i_{1}}$, for some $0\leq i_{1}<i$. If $x^{\prime}\in\beta$, then we
terminate this process, and otherwise we consider the path $K(x_{1})$, which
is concatenated to path $K(x)$. After at most $\lambda$ such iterations, we
must obtain a path $P$, that connects $x$ to some vertex $y\in\beta$. Since
the length of every path in set $\bigcup_{j=1}^{\lambda-1}{\mathcal{Q}}_{j}$
is at most $4d^{\prime}\log^{10}N$, the final length of the resulting path is
bounded by $4\lambda d^{\prime}\log^{10}N\leq 32d^{\prime}\log^{11}N<d$, since
$d^{\prime}=\frac{d}{(\log N)^{64}}$, and $N$ is sufficiently large. In time
$O(d)$, we can turn this path into a simple path, and truncate it so that it
still connects $x$ to some vertex of $\beta$, but the inner vertices on the
path do not belong to $\beta$. The time required to respond to a single query
is bounded by $O(d)$, and the total time required to respond to all queries is
bounded by $O(d\cdot\Delta)\leq O\left(n\cdot(n-|\beta^{0}|+\Delta)\cdot(\log
N)^{64}\right)$, since, from the problem definition, $\Delta\cdot
d\leq\eta\cdot\left(|V(G)|-|\beta|+\Delta\cdot(\log N)^{64}\right)$, and
$\eta\leq\Delta\leq|\beta|\leq n$.

Recall that, in our setting, $\rho=O(\log^{3}N)$, and so the running time of
the algorithm for the $\mathsf{ConnectToCenters}$ problem from Theorem 6.7 is
bounded by:

$O\left(c_{1}\cdot W^{0}\cdot(W^{0}-|\beta^{0}|+|\beta^{\prime}|+\Lambda)\cdot
2^{c_{2}\sqrt{\log N}}\cdot(\log N)^{16c_{2}(r-1)+8c_{2}+29}\right).$

Since, from 6.12, $\Lambda\leq 4n-4|\beta^{0}|+5\Delta\cdot(\log N)^{64}$ and
$|\beta^{\prime}|\leq 45n-45|\beta^{0}|+56\Delta\cdot(\log N)^{64}$, while
$n=W^{0}$, we get that the total running time of the algorithm is bounded by:

$\begin{split}&O\left(c_{1}\cdot W^{0}\cdot(W^{0}-|\beta^{0}|+\Delta)\cdot
2^{c_{2}\sqrt{\log N}}\cdot(\log N)^{16c_{2}(r-1)+8c_{2}+100}\right)\\\
&\quad\quad\quad\quad\leq c_{1}\cdot W^{0}\cdot(W^{0}-|\beta|+\Delta)\cdot
2^{c_{2}\sqrt{\log N}}\cdot(\log N)^{16c_{2}r}.\end{split}$

Finally, recall that the algorithm for the $\mathsf{ConnectToCenters}$ problem
may terminate with a “FAIL”, with probability at most $\frac{1}{N^{7}}$. If
this happens, then our algorithm terminates with a “FAIL” as well, but the
probability for this happening is bounded by $\frac{1}{N^{7}}$.

##  7 From the $\mathsf{MaintainCluster}$ Problem to $\mathsf{RouteAndCut}$
Problem – Comleting the Proof of Theorem 4.12

The goal of this section is to complete the proof of Theorem 4.12, by
providing an algorithm for the $\mathsf{MaintainCluster}$ problem, that is
summarized in the following theorem.

######  Theorem 7.1.

Suppose that, for some parameter $r\geq 1$, there exists a randomized
algorithm for the $r$-restricted $\mathsf{RouteAndCut}$ problem, that, given
as an input an instance $(G,A,B,\Delta,\eta,N)$ of the problem with
$|V(G)|=n$, has running time at most $c_{1}\cdot n\cdot(n-|B|)\cdot
2^{c_{2}\sqrt{\log N}}\cdot(\log N)^{16c_{2}(r-1)+8c_{2}}$. Then there exists
a randomized algorithm for the $r$-restricted $\mathsf{MaintainCluster}$
problem, that, on input $(G,\Delta,\eta,d,N)$ has running time at most:
$c_{1}\cdot(W^{0}(G))^{2}\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r}+c_{1}\cdot W^{0}(G)\cdot\Delta\cdot\log^{4}N$.

We assume that there exists a randomized algorithm ${\mathcal{A}}$ for the
$r$-restricted $\mathsf{RouteAndCut}$ problem, for some integer $r\geq 1$,
that, on an input an instance $(G,A,B,\Delta,\eta,N)$ of the problem with
$|V(G)|=n$, has running time at most $c_{1}\cdot n\cdot(n-|B|)\cdot
2^{c_{2}\sqrt{\log N}}\cdot(\log N)^{16c_{2}(r-1)+8c_{2}}$.

Recall that the input to the $r$-restricted $\mathsf{MaintainCluster}$ problem
consists of a perfect well-structured $n$-vertex graph $G=(L,R,E)$ with a
proper assignment $\ell(e)$ of lengths to its edges. Recall that we have
defined vertex weights for perfect well-structured graphs, where the weight
$w(v)$ of a vertex $v$ is the length of the unique special edge incident to
$v$. For every vertex $v\in V(G)$, we denote by $w^{0}(v)$ its initial weight,
and we denote $W^{0}(G)=\sum_{v\in V(G)}w^{0}(v)$. Additionally, we are given
a parameter $N\geq W^{0}(G)$, that is greater than a large enough constant,
with $r\leq\left\lceil\sqrt{\log N}\right\rceil$, and parameters
$1\leq\Delta\leq N$, $1\leq\eta\leq\Delta$, and $(\log N)^{64}\leq d\leq
2^{r\cdot\sqrt{\log N}}$, such that $\frac{\Delta\cdot d}{\eta}\leq n$. In
particular:

$d\leq\frac{n\eta}{\Delta}\leq n.$ (15)

Since $d\geq(\log N)^{64}$, we get that $(\log N)^{64}\leq n\leq N$, and so:

$\log\log N\leq\log n\leq\log N.$ (16)

Since we have assumed that $N$ is greater than a large enough constant, and in
particular that $N>2^{2^{c_{2}}}$, we can also assume that $n$ is greater than
a large enough constant. We also get following inequality that will be useful
for us later:

$\log(16N)=4+\log N\leq\left(1+\frac{1}{32c_{2}r}\right)\log N.$ (17)

Additionally, $\sqrt{\log(16N)}\leq\sqrt{4+\log N}\leq 2+\sqrt{\log N}$, and
so:

$2^{c_{2}\sqrt{\log(16N)}}\leq 2^{2c_{2}}\cdot 2^{c_{2}\sqrt{\log N}}\leq
2^{c_{2}\sqrt{\log N}}\cdot\log N,$ (18)

since $N$ is sufficiently large.

The algorithm consists of at most $\Delta$ iterations. At the beginning of
every iteration $i$, the algorithm is given two vertices $x,y\in V(G)$, and it
must return a simple path $P_{i}$ in $G$ connecting $x$ to $y$, whose length
is at most $d$. (We may sometimes say that the algorithm is given a short-path
query between the pair $(x,y)$ of vertices, and it returns the path $P_{i}$ in
response to the query). The lengths of some of the special edges on path
$P_{i}$ are then doubled. If $e$ is a special edge of $G$, and
$\tau<\tau^{\prime}$ are consecutive times during the algorithm’s execution
when the length of $e$ was doubled, then we are guaranteed that the number of
the paths $P_{i}$ that the algorithm returned in response to the queries
during time interval $(\tau,\tau^{\prime}]$ with $e\in E(P_{i})$ is at least
$\eta$.

The algorithm may, at any time, produce a strongly well-structured cut $(X,Y)$
in $G$ of sparsity $\Phi_{G}(X,Y)\leq\frac{(\log N)^{64}}{d}$. If $w(X)\leq
w(Y)$, then let $Z=X$ and $Z^{\prime}=Y$; otherwise, let $Z=Y$ and
$Z^{\prime}=X$. We also let $J^{\prime}\subseteq Z^{\prime}$ denote the set of
vertices that serve as endpoints of the edges of $E_{G}(X,Y)$. The vertices of
$Z\cup J^{\prime}$ are then deleted from $G$, and the algorithm continues with
the resulting graph $G=G[Z^{\prime}\setminus J^{\prime}]$. This modification
ensures that $G$ remains a perfect well-structured graph. Once $|V(G)|\leq
n/2$ holds, the algorithm terminates, even if fewer than $\Delta$ iterations
have passed. The algorithm may also, at any time, return “FAIL”, but the
probability of this ever happening must be bounded by $1/N^{4}$.

We can assume w.l.o.g. that, in the initial graph $G$, the length of every
edge is at most $d$. Indeed, if $(x,y)$ is an edge of $G$ of length greater
than $d$, then cut $(A,B)$ with $A=\left\\{x\right\\}$ and
$B=V(G)\setminus\left\\{x\right\\}$ is a strongly well-structured cut of
sparsity at most $\frac{1}{d}$, since $w(x),w(y)=d$, and $|E_{G}(A,B)|=1$. As
long as special edges of length greater than $d$ lie in $G$, we can therefore
produce $\frac{1}{d}$-sparse cuts that will result in the removal of such
edges from $G$. The time required to perform this preprocessing step is
$O(|E(G)|)\leq O(W^{0}(G))$. We will also ensure that, throughout the
algorithm, every edge of $G$ has length at most $2d$. Therefore, if we denote
by $W^{(\tau)}$ the total weight of all edges at some time $\tau$ during the
algorithm’s execution, then $W^{(\tau)}\leq 2n\cdot d\leq 2n^{2}$ must hold
(we have used Inequality 15). Since the algorithm terminates once the number
of vertices falls below $n/2$, the total weight $W$ of all vertices of $G$
satisfies $\frac{n}{2}\leq W\leq 2n^{2}$, at all times, and therefore, at all
times the following inequality holds:

$\log n-1\leq\log W\leq 4\log n.$ (19)

Throughout, we denote by $G^{0}$ the initial graph $G$, and by
$E^{\mathsf{spec}}$ be the set of all special edges of $G^{0}$. For each such
edge $e\in E^{\mathsf{spec}}$, let $\ell^{0}(e)$ be the length of $e$ at the
beginning of the algorithm, and let $\ell^{*}(e)$ be defined as follows. If
$e$ lies in graph $G$ at the end of the algorithm, then $\ell^{*}(e)$ is the
length of edge $e$ at the end of the algorithm. Otherwise, $\ell^{*}(e)$ is
the length of the edge $e$ just before it was deleted from $G$. We will use
the following simple observation to bound $\sum_{e\in
E^{\mathsf{spec}}}\ell^{*}(e)$. The proof is deferred to Section D.1 of
Appendix.

######  Observation 7.2.

$\sum_{e\in E^{\mathsf{spec}}}\ell^{*}(e)\leq 2\sum_{e\in
E^{\mathsf{spec}}}\ell^{0}(e)+\frac{2d\Delta}{\eta}\leq 2\sum_{e\in
E^{\mathsf{spec}}}\ell^{0}(e)+2n.$

Throughout the algorithm, instead of working with graph $G$, it will be
convenient for us to work with its corresponding subdivided graph $G^{+}$ (see
Definition 4.1). We denote the two sides of the bipartition of the vertices of
$G^{+}$ by $L^{+}$ and $R^{+}$, respectively. Recall that graph $G^{+}$ is
obtained from $G$ by replacing every special edge $e=(u,v)$ with a new path,
that we denote by $P^{*}(e)$, and call _the path represeinting $e$ in
$G^{+}$_. The number of special edges on path $P^{*}(e)$ is exactly $\ell(e)$.
For every special edge $e^{\prime}$ on path $P^{*}(e)$, we say that $e$ is the
_parent-edge_ of $e^{\prime}$, and that $e^{\prime}$ is the _child-edge_ of
$e$.

Assume that at some time during the algorithm’s execution, the length
$\ell(e)$ of an edge $e\in E(G)$ is doubled. Then for every special edge
$e^{\prime}=(x,y)$ on path $P^{*}(e)$, we replace the edge by a path
$(x,x^{\prime},y^{\prime},y)$, where $x^{\prime}$ and $y^{\prime}$ are new
vertices, edges $(x,x^{\prime})$ and $(y^{\prime},y)$ are special, and edge
$(x^{\prime},y^{\prime})$ is regular; we call this process the _splitting_ of
edge $e^{\prime}$. Notice that, since $(x,y)$ is a special edge of $G^{+}$,
$x\in R^{+}$ and $y\in L^{+}$ must hold. We add $x^{\prime}$ to $L^{+}$ and
$y^{\prime}$ to $R^{+}$. It is easy to verify that $G^{+}$ remains the
subdivided graph of $G$ after this update.

In order to simplify the notation, we will denote $G^{+}$ by $H$ from now on,
and we will also denote the bipartition $(L^{+},R^{+})$ by
$(L^{\prime},R^{\prime})$. Recall that $H$ is a uniform perfect well-
structured graph. The initial number of vertices in $H$ is $W^{0}$. As the
algorithm progresses and edges of $H$ are subdivided, we will denote by $W$
the current number of vertices in $H$, which is equal to $\sum_{v\in
V(G)}w(v)$.

From now on we will mostly work with graph $H$. In every iteration, we are
given a pair $(x,y)$ of vertices of $H$, and we need to return a simple path
$P$ connecting $x$ to $y$ in $H$, of length at most $d$. Such a path can be
easily trasformed into a path in graph $G$ of length at most $d$ connecting
$x$ to $y$. After that, some special edges on path $P$ are split. From the
definition of the $\mathsf{MaintainCluster}$ problem, we are guaranteed that
the following property holds throughout the algorithm.

  1. Q’1.

Consider any special edge $e$ of $H$ that did not lie in the original graph
$H=(G^{0})^{+}$. Assume that $e$ was added to $H$ at some time $\tau$ during
the algorithm’s execution, and was later split at some time
$\tau^{\prime}>\tau$ (so after time $\tau^{\prime}$, edge $e$ no longer lies
in $H$). Then the number of paths $P$ that the algorithm returned in response
to queries during the time interval $(\tau,\tau^{\prime}]$ with $e\in E(P)$ is
at least $\eta$.

Notice that $W^{0}=2\sum_{e\in E^{\mathsf{spec}}}\ell^{0}(e)$, and the total
number of vertices that ever belonged to $H$ over the course of the algorithm
is bounded by $\sum_{e\in E^{\mathsf{spec}}}2\ell^{*}(e)\leq 4\sum_{e\in
E^{\mathsf{spec}}}\ell^{0}(e)+4n\leq 2W^{0}+4n\leq 6W^{0}$, from 7.2. In
particular, $|V(H)|\leq 6W^{0}$ holds at all times.

Throughout, we use a parameter $d^{\prime}$, that is the smallest integral
power of $2$ that is greater than $\frac{d}{(\log N)^{28}}$, and we set
$\varphi=\frac{4}{d^{\prime}}$. Intuitively, if, at any time during the
algorithm’s execution, the length of any special edge $e=(x,y)$ in $G$ becomes
at least $d^{\prime}/2$, then we can immediately produce a cut $(A,B)$ with
$A=\left\\{x\right\\}$ and $B=V(G)\setminus\left\\{x\right\\}$. It is easy to
verify that $(A,B)$ is a strongly well-structured cut in $G$. Moreover, since
$w(x),w(y)=\ell(e)$, the sparsity of the cut is at most $\varphi$, and so our
algorithm could output this cut. In reality our algorithm is somewhat more
complex, but it uses a similar method to ensure that, at all times, the
lengths of all edges in $G$ are bounded by $d^{\prime}$. Additionally, as long
as the algorithm does not terminate, $\sum_{e\in
E(G)}\ell(e)\geq\frac{|V(G)|}{2}\geq\frac{n}{4}>d^{\prime}$ must hold.

Let $W$ be the total weight of all vertices of $G$ at any time during the
algorithm’s execution. Then $W\geq|V(G)|\geq\frac{n}{2}\geq\frac{d}{2}$ (from
Inequality 15). Therefore, throughout the algorithm:

$d^{\prime}\leq\frac{2d}{\log^{28}N}\leq\frac{4W}{\log^{28}N}$ (20)

holds. As long as the lengths of all edges in $G$ are bounded by
$d^{\prime}/2$, our algorithm may produce, at any time, a weakly well-
structured cut $(A,B)$ in the current graph $H$, of sparsity at most
$\frac{\varphi}{4}$. Let $A^{\prime}=A\cap V(G)$ and $B^{\prime}=B\cap V(G)$.
From 4.4, $(A,B)$ is a weakly well-structured cut in $G$ of sparsity at most
$2\varphi$. Furthermore, using the algorithm from 4.5, we can transform cut
$(A,B)$ into a strongly well-structured cut $(A^{*},B^{*})$ in $G$, of
sparsity at most $4\varphi$. We then return cut $(A^{*},B^{*})$, following
which graph $G$ is updated with the deletion of the vertices on the side of
the cut whose current weight is smaller, and the endpoints of the edges in
$E_{G}(A^{*},B^{*})$. We update graph $H$ by deleting from it every vertex
that was deleted from $G$, and, additionally, for every edge $e$ that was
deleted from $G$, its corresponding path $P^{*}(e)$ is deleted from $H$. As
before, the algorithm is allowed to halt and return “FAIL” at any time, but we
are required that this happens with probability at most $1/N^{4}$.

###  7.1 Partition into Phases and Probability of Failure

Our algorithm is partitioned into phases. A phase terminates if one of the
following happened: (i) the algorithm returned “FAIL”, in which case we say
that the phase is of _type 1_ ; or (ii) at least $\frac{\hat{W}}{\log^{30}N}$
vertices have been deleted from graph $H$ during the current phase, where
$\hat{W}$ is the number of vertices in $H$ at the beginning of the phase, in
which case we say that the phase is of _type 2_ ; or (iii) at least
$\Delta^{\prime}=\frac{\Delta}{\log^{30}N}$ queries have been responded to; in
which case we say that the phase is of _type 3_. We will ensure that the
probability that the algorithm returns “FAIL” in a single phase is bounded by
$\frac{1}{2}$. Since the total number of vertices that ever belong to graph
$H$ is bounded by $6W^{0}\leq O(N)$, we get that the total number of type-2
and type-3 phases is bounded by $O(\log^{30}N\cdot\log N)\leq\log^{32}N$. If
$\left\lceil 16\log N\right\rceil$ consecutive type-1 phases occur, then we
terminate the algorithm and return “FAIL”. Notice that, for each type-2 phase
and type-3 phase, the probability that it is followed by $\left\lceil 16\log
N\right\rceil$ consecutive type-1 phases is bounded by
$\left(\frac{1}{2}\right)^{\left\lceil 16\log
N\right\rceil}\leq\frac{1}{N^{16}}$. Therefore, overall, the probability that
the algorithm ever returns “FAIL” is bounded by $\frac{(\log
N)^{32}}{N^{16}}<\frac{1}{N^{4}}$, as required. The total number of phases in
the algorithm is then bounded by $O(\log^{32}N\cdot\log N)\leq O(\log^{33}N)$.

At a very high level, our algorithm follows a somewhat standard framework,
though the specific details are quite different. As a first step, we select a
random subset $T$ of vertices of $H$, that we call _terminals_ , where every
vertex of $H$ is selected to be added to $T$ independently with probability
$\frac{1}{d^{\prime}}$. Next, we will attempt to embed an expander $X$, whose
vertex set is $T$, into graph $H$, so that every embedding path has length
$\widetilde{O}(d^{\prime})$, and the paths cause edge-congestion
$O(\operatorname{poly}\log n)$. We show that, with high probability, if we are
unable to compute such an embedding, then we can compute a cut $(A,B)$ in $H$,
that can be transformed into a $\frac{(\log N)^{64}}{d}$-sparse strongly well-
structured cut $(A^{\prime},B^{\prime})$ in $G$ with
$w(A^{\prime}),w(B^{\prime})\geq\frac{\hat{W}}{\log^{30}N}$. We then output
this cut, and update graphs $G$ and $H$ with the corresponding deletions of
vertices and edges, which must lead to the deletion of at least
$\frac{\hat{W}}{\log^{30}N}$ vertices from $H$. Therefore, with high
probability, if we cannot successfully compute an expander $X$, and embed it
into $H$, the current phase will terminate. Assume now that we have
successfully computed an expander $X$ over the set $T$ of roughly
$\frac{\hat{W}}{d^{\prime}}$ vertices, and embedded it into $H$. Then we will
employ the Layered Connectivity Data Structure from Section 6, with the set
$V(X)$ of vertices serving as the set $\beta$ of centers, in order to maintain
a collection ${\mathcal{Q}}^{\operatorname{out}}$ of short paths, connecting
every vertex of $V(H)$ to some vertex of $V(X)$. We will also employ the same
data structure on graph $\overleftarrow{G}$, that is obtained from $G$ by
reversing the direction of each of its edges, to maintain a collection
${\mathcal{Q}}^{\operatorname{in}}$ of short paths, that, for every vertex
$v\in V(H)$, contains a path that connects some vertex of $V(X)$ to $v$.

We now formally describe the algorithm for executing a single phase. We assume
w.l.o.g. that, at the beginning of the phase, graph $G$ does not contain any
edge of length greater than $d^{\prime}$. Otherwise, as long as such an edge
$e=(x,y)$ lies in $G$, then cut $(A,B)$ with $A=\left\\{x\right\\}$ and
$B=V(G)\setminus\left\\{x\right\\}$ is a strongly well-structured cut of
sparsity $\frac{1}{d^{\prime}}\leq\varphi$, since $w(x)=d^{\prime}$, and
$|E_{G}(A,B)|=1$. As long as special edges of length greater than $d^{\prime}$
lie in $G$, we can therefore produce $\varphi$-sparse cuts that will result in
the removal of such edges from $G$. The time required to perform this
preprocessing step, including updating the graph $H$, is $O(|V(H)|)\leq
O(W^{0})$. Therefore, we assume that, at the beginning of the phase, $G$ does
not contain edges of length greater than $d^{\prime}$. We denote by $\hat{W}$
the number of vertices in $H$ at the beginning of the phase.

We start with a preprocessing step, in which we sample the vertices of $H$ to
be added to the set $T$. Then we describe our two main data structures. The
first data structure maintains a large expander that is defined over the set
$T$ of vertices, while the second data structure is Layered Connectivity Data
Structure in graphs $G$ and $\overleftarrow{G}$.

###  7.2 Preprocessing Step: Subsampling

Recall that the number of vertices in $H$ at the beginning of the phase,
denoted by $\hat{W}$, is bounded by $12W^{0}\leq 12N$.

In this step, we construct a set $T$ of vertices of $H$, that we call
_terminals_ , as follows: every vertex $v\in V(H)$ is added to $T$ with
probability $\frac{1}{d^{\prime}}$ independently. This is the only randomized
part in our algorithm for the Maximum Bipartite Matching problem. Next, we
will define four “bad” events, and we will show that each of them may only
happen with low probability. Eventually, if our algorithm returns “FAIL” and
halts, we will guarantee that at least one of these bad events must have
happened. This will ensure that the probability that the phase terminates with
the “FAIL” is at most $\frac{1}{2}$, as required.

####  7.2.1 Bad Event ${\cal{E}}_{1}$

Observe first that the expected cardinality of $T$ is
$\frac{\hat{W}}{d^{\prime}}$. We say that bad event ${\cal{E}}_{1}$ happens if
$|T|>\frac{8\hat{W}}{d^{\prime}}$ or $|T|<\frac{\hat{W}}{2d^{\prime}}$. From
Lemma 2.5, $\text{\bf Pr}\left[|T|>\frac{8\hat{W}}{d^{\prime}}\right]\leq
2^{-8\hat{W}/d^{\prime}}\leq\frac{1}{512}$, and $\text{\bf
Pr}\left[|T|<\frac{\hat{W}}{2d^{\prime}}\right]\leq
e^{-\hat{W}/(8d^{\prime})}\leq\frac{1}{512}$, since
$d^{\prime}\leq\frac{4\hat{W}}{\log^{28}N}$ from Inequality 20. Overall, we
get that $\text{\bf Pr}\left[{\cal{E}}_{1}\right]\leq\frac{1}{256}$, and, if
${\cal{E}}_{1}$ does not happen, then
$\frac{\hat{W}}{2d^{\prime}}\leq|T|\leq\frac{8\hat{W}}{d^{\prime}}$ holds.

Before we define the remaining two bad events, we need to inspect the well-
structured cuts of $H$ more closely.

####  7.2.2 Well-Structured Cuts and Their Structure

Recall that a cut $(A,B)$ of $H$ is weakly well-structured iff all edges of
$E_{H}(A,B)$ are special. Let $E^{\prime}$ be any subset of special edges of
$H$. We denote by ${\mathcal{C}}(E^{\prime})$ the collection of all weakly
well-structured cuts $(A,B)$ in $H$ with $E_{H}(A,B)=E^{\prime}$. Next, we
investigate the structure of the cuts in ${\mathcal{C}}(E^{\prime})$.

Let $J(E^{\prime})$ denote the set of all vertices $v\in V(H)$, such that some
edge of $E^{\prime}$ leaves $v$, and let $J^{\prime}(E^{\prime})$ denote the
set of all vertices $u\in V(H)$, such that some edge of $E^{\prime}$ enters
$u$. Next, we denote by $S^{*}(E^{\prime})$ the set of all vertices $v\in H$,
such that there is a path in $H\setminus E^{\prime}$ connecting a vertex of
$J(E^{\prime})$ to $v$. Notice that, for every cut
$(A,B)\in{\mathcal{C}}(E^{\prime})$, it must be the case that
$S^{*}(E^{\prime})\subseteq A$. Indeed, assume otherwise, and let $v\in
S^{*}(E^{\prime})$ be any vertex that lies in $B$. Since
$J(E^{\prime})\subseteq A$ must hold, there is a path $P$ connecting a vertex
of $A$ to $v$, such that $P$ is disjoint from the edges of $E^{\prime}$. But
then some edge of $P$ must lie in $E_{H}(A,B)$, contradicting the fact that
$E_{H}(A,B)=E^{\prime}$.

Similarly, we denote by $S^{**}(E^{\prime})$ the set of all vertices $v\in H$,
such that there is a path in $H\setminus E^{\prime}$ connecting $v$ to a
vertex of $J^{\prime}(E^{\prime})$. From the same arguments as above, for
every cut $(A,B)\in{\mathcal{C}}(E^{\prime})$, $S^{**}(E^{\prime})\subseteq B$
must hold.

Let ${\mathcal{X}}^{\prime}$ be the set of all strongly connected components
of $H\setminus\left(S^{*}(E^{\prime})\cup J(E^{\prime})\cup
S^{**}(E^{\prime})\cup J^{\prime}(E^{\prime})\right)$, where for each
$X\in{\mathcal{X}}^{\prime}$, we view $X$ as a set of vertices corresponding
to the connected component. Denote
${\mathcal{X}}(E^{\prime})={\mathcal{X}}^{\prime}\cup\left\\{S^{*}(E^{\prime})\cup
J(E^{\prime}),S^{**}(E^{\prime})\cup J^{\prime}(E^{\prime})\right\\}$.
Clearly, ${\mathcal{X}}(E^{\prime})$ is a partition of $V(H)$. Consider again
any cut $(A,B)\in{\mathcal{C}}(E^{\prime})$. As observed already,
$S^{*}(E^{\prime})\cup J(E^{\prime})\subseteq A$ and $S^{**}(E^{\prime})\cup
J^{\prime}(E^{\prime})\subseteq B$ must hold. Moreover, it is easy to see
that, since $E_{H}(A,B)=E^{\prime}$, for all $X\in{\mathcal{X}}^{\prime}$,
either $X\subseteq A$, or $X\subseteq B$ must hold. From the definition of the
sets $S^{*}(E^{\prime}),S^{**}(E^{\prime})$ of vertices, graph $H\setminus
E^{\prime}$ contains no path connecting a vertex of $S^{*}(E^{\prime})\cup
J(E^{\prime})$ to a vertex lying outside this set. Similarly, no path in
$H\setminus E^{\prime}$ may connect a vertex of
$V(H)\setminus\left(S^{**}(E^{\prime})\cup J^{\prime}(E^{\prime})\right)$ to a
vertex of $S^{**}(E^{\prime})\cup J^{\prime}(E^{\prime})$. It is now easy to
verify that, for every pair $X,X^{\prime}\in{\mathcal{X}}(E^{\prime})$ of
sets, it cannot be the case that $H\setminus E^{\prime}$ contains both a path
$P$ connecting a vertex of $X$ to a vertex of $X^{\prime}$, and a path
$P^{\prime}$ connecting a vertex of $X^{\prime}$ to a vertex of $X$. Indeed,
if such paths did exist, then neither of these paths could contain vertices of
$S^{*}(E^{\prime})\cup J(E^{\prime})\cup S^{**}(E^{\prime})\cup
J^{\prime}(E^{\prime})$, and so the vertices of $X\cup X^{\prime}$ should have
belonged to a single strongly connected component of
$H\setminus\left(S^{*}(E^{\prime})\cup J(E^{\prime})\cup
S^{**}(E^{\prime})\cup J^{\prime}(E^{\prime})\right)$.

We can now define an arbitrary topological ordering
$(X_{1},X_{2},\ldots,X_{q})$ of the sets in ${\mathcal{X}}(E^{\prime})$, such
that $X_{1}=S^{**}(E^{\prime})\cup J(E^{\prime})$,
$X_{q}=S^{*}(E^{\prime})\cup J^{\prime}(E^{\prime})$, and for all $1\leq
i<j\leq q$, there is no edge of $E(H)\setminus E^{\prime}$ that connects a
vertex of $X_{j}$ to a vertex of $X_{i}$. Notice that, for all $1\leq i\leq
q$, we can define a cut $(A_{i},B_{i})$ with $A_{i}=X_{i+1}\cup\cdots\cup
X_{q}$ and $B_{i}=X_{1}\cup\cdots\cup X_{i}$. From our discussion so far, the
only edges that connect vertices of $A_{i}$ to vertices of $B_{i}$ are the
edges of $E^{\prime}$, and so for each such $1\leq i<r$, cut $(A_{i},B_{i})$
lies in ${\mathcal{C}}(E^{\prime})$. We call all cuts in
$\left\\{(A_{i},B_{i})\mid 1\leq i\leq q\right\\}$ _canonical cuts_
corresponding to $E^{\prime}$, and denote the set of all such cuts by
${\mathcal{C}}^{\prime}(E^{\prime})$. Notice that
${\mathcal{C}}^{\prime}(E^{\prime})\subseteq{\mathcal{C}}(E^{\prime})$, and it
is possible that
${\mathcal{C}}(E^{\prime})\setminus{\mathcal{C}}^{\prime}(E^{\prime})\neq\emptyset$.
Note that the definition of the set ${\mathcal{C}}^{\prime}(E^{\prime})$ of
cuts depends on the topological ordering of the sets in
${\mathcal{X}}(E^{\prime})$, and there may be several such topological
orderings. We assume that we are given some tie-breaking rule that selects a
single topological ordering of the sets in ${\mathcal{X}}(E^{\prime})$, and we
define ${\mathcal{C}}^{\prime}(E^{\prime})$ with respect to that topological
ordering. We also assume that the above unique topological ordering can be
computed in time $O(n)$, given the sets in ${\mathcal{X}}(E^{\prime})$. We are
now ready to define the second bad event.

####  7.2.3 Bad Event ${\cal{E}}_{2}$

We start with intuition. Recall that our goal is to embed an expander over the
set $T$ of vertices into $H$, with polylogarithmic congestion. Intuitively, if
we are not able to do so, we will construct a cut $(A,B)$ in $H$, such that
$|T\cap A|,|T\cap B|\geq\Omega(|T|/\operatorname{poly}\log N)$, and
$|E_{H}(A,B)|$ is sufficiently low. If this happens, we would like to be able
to compute a sparse and a roughly balanced cut in graph $H$. If we denote by
$E^{\prime}=E_{H}(A,B)$, then ideally we would like to ensure that some
canonical cut corresponding to $E^{\prime}$ has this property. The second bad
event happens if this is not the case for some such cut $(A,B)$. Next, we
formally define the second bad event, and show that it can only happen with
small probability.

We say that bad event ${\cal{E}}_{2}$ happens if there is a weakly well-
structured cut $(A,B)$ in $H$, with $|A\cap T|,|B\cap
T|\geq\frac{|T|}{\log^{4}N}$, and $|E_{H}(A,B)|\leq\frac{|T|}{\log^{6}N}$,
such that, if we denote by $E^{\prime}=E_{H}(A,B)$, then for every canonical
cut $(A^{\prime},B^{\prime})\in{\mathcal{C}}^{\prime}(E^{\prime})$, either
$|A^{\prime}|\leq\frac{\hat{W}}{\log^{5}N}$, or
$|B^{\prime}|\leq\frac{\hat{W}}{\log^{5}N}$ holds.

######  Claim 7.3.

$\text{\bf Pr}\left[{\cal{E}}_{2}\right]\leq\frac{1}{64}.$

###### Proof.

Recall that, if event ${\cal{E}}_{1}$ does not happen, then
$\frac{\hat{W}}{2d^{\prime}}\leq|T|\leq\frac{8\hat{W}}{d^{\prime}}$ holds, and
so, if $E^{\prime}$ is a set of special edges with
$|E^{\prime}|\leq\frac{|T|}{\log^{6}N}$, then
$|E^{\prime}|\leq\frac{8\hat{W}}{d^{\prime}\log^{6}N}$.

For every subset $E^{\prime}$ of at most
$\frac{8\hat{W}}{d^{\prime}\log^{6}N}$ special edges, we define a bad event
${\cal{E}}(E^{\prime})$ to be the event that there is some cut $(A,B)$ in $H$
with $E_{H}(A,B)=E^{\prime}$, such that $|A\cap T|,|B\cap
T|\geq\frac{|T|}{\log^{4}N}$, and for every canonical cut
$(A^{\prime},B^{\prime})\in{\mathcal{C}}^{\prime}(E^{\prime})$, either
$|A^{\prime}|\leq\frac{\hat{W}}{\log^{5}N}$, or
$|B^{\prime}|\leq\frac{\hat{W}}{\log^{5}N}$ holds. We bound $\text{\bf
Pr}\left[{\cal{E}}(E^{\prime})\right]$ for each such set $E^{\prime}$ of edges
separately, and then use the union bound in order to bound $\text{\bf
Pr}\left[{\cal{E}}_{2}\right]$.

Fix any subset $E^{\prime}$ of at most $\frac{8\hat{W}}{d^{\prime}\log^{6}N}$
special edges. Let $X\in{\mathcal{X}}(E^{\prime})$ be the set of vertices with
maximum cardinality. We claim that Event ${\cal{E}}(E^{\prime})$ may only
happen if $|X|\geq\hat{W}-\frac{2\hat{W}}{\log^{5}N}$, in the following simple
observation.

######  Observation 7.4.

If ${\cal{E}}(E^{\prime})$ happened, then
$|X|\geq\hat{W}-\frac{2\hat{W}}{\log^{5}N}$ must hold.

###### Proof.

Assume otherwise, that is, Event ${\cal{E}}(E^{\prime})$ happened, but
$|X|<\hat{W}-\frac{2\hat{W}}{\log^{5}N}$. Denote
${\mathcal{X}}(E^{\prime})=(X_{1},X_{2},\ldots,X_{q})$, where the sets are
listed according to their topological order, and assume that $X=X_{i}$.

Assume first that $|X_{i}|\geq\frac{\hat{W}}{4}$. Then either
$|\bigcup_{i^{\prime}<i}X_{i^{\prime}}|\geq\frac{\hat{W}}{\log^{5}N}$, or
$|\bigcup_{i^{\prime}>i}X_{i^{\prime}}|\geq\frac{\hat{W}}{\log^{5}N}$. In the
former case, cut $(A_{i},B_{i})$ is a canonical cut with
$|A_{i}|,|B_{i}|\geq\frac{\hat{W}}{\log^{5}N}$, while in the latter case, cut
$(A_{i-1},B_{i-1})$ is a canonical cut with
$|A_{i-1}|,|B_{i-1}|\geq\frac{\hat{W}}{\log^{5}N}$, a contradiction (if $i=1$
then we are guaranteed that $(A_{i},B_{i})$ is the cut with the desired
properties, and if $i=q$, then we are guaranteed that $(A_{q-1},B_{q-1})$ is
such a cut).

Assume next that $|X_{i}|<\frac{\hat{W}}{4}$. In this case, we let $1<j<q$ be
the smallest index for which
$\sum_{j^{\prime}<j}|X_{j^{\prime}}|\geq\frac{\hat{W}}{2}$. It is easy to
verify that $\sum_{j^{\prime}<j}|X_{j^{\prime}}|\leq\frac{3\hat{W}}{4}$ must
hold, and so cut $(A_{j},B_{j})\in{\mathcal{C}}^{\prime}(E^{\prime})$
satisfies that both $|A_{j}|,|B_{j}|\geq\frac{\hat{W}}{\log^{5}N}$, a
contradiction.

We assume from now on that $|X|\geq\hat{W}-\frac{2\hat{W}}{\log^{5}N}$ holds
for the set $E^{\prime}$ of edges. Let $Y=V(H)\setminus X$, so
$|Y|\leq\frac{2\hat{W}}{\log^{5}N}$. Consider now any cut
$(A,B)\in{\mathcal{C}}(E^{\prime})$, and assume that $|A\cap T|,|B\cap
T|\geq\frac{|T|}{\log^{4}N}$. Notice that all vertices of $X$ must lie on one
side of the cut $(A,B)$. If $X\subseteq A$, then $B\subseteq Y$, and, since
$|T\cap B|\geq\frac{|T|}{\log^{4}N}$, we get that $|T\cap
Y|\geq\frac{|T|}{\log^{4}N}$. Similarly, if $X\subseteq B$, then $A\subseteq
Y$, and, since $|T\cap A|\geq\frac{|T|}{\log^{4}N}$, we get that $|T\cap
Y|\geq\frac{|T|}{\log^{4}N}$. In either case, we conclude that Event
${\cal{E}}(E^{\prime})$ may only happen if
$|X|\geq\hat{W}-\frac{2\hat{W}}{\log^{5}N}$ and $|T\cap
Y|\geq\frac{|T|}{\log^{4}N}$.

We start by bounding the probability that $|T\cap
X|<\frac{\hat{W}}{4d^{\prime}}$. Since we have assumed that
$|X|\geq\hat{W}-\frac{2\hat{W}}{\log^{5}N}\geq\frac{\hat{W}}{2}$, and since
every vertex is selected into $T$ independently with probability
$1/d^{\prime}$, we get that $\text{\bf E}\left[|T\cap
X|\right]\geq\frac{\hat{W}}{2d^{\prime}}$. From Lemma 2.5, $\text{\bf
Pr}\left[|T\cap X|<\frac{\hat{W}}{4d^{\prime}}\right]\leq
e^{-\hat{W}/(16d^{\prime})}$.

Assume now that $|T\cap X|\geq\frac{\hat{W}}{4d^{\prime}}$, so in particular
$|T|\geq\frac{\hat{W}}{4d^{\prime}}$. In this case, if $|T\cap
Y|\geq\frac{|T|}{\log^{4}N}$, then $|T\cap
Y|\geq\frac{\hat{W}}{4d^{\prime}\log^{4}N}$ must hold. Since $\text{\bf
E}\left[|T\cap
Y|\right]=\frac{|Y|}{d^{\prime}}\leq\frac{2\hat{W}}{d^{\prime}\log^{5}N}$,
from Lemma 2.5, $\text{\bf Pr}\left[|T\cap
Y|\geq\frac{\hat{W}}{4d^{\prime}\log^{4}N}\right]\leq
2^{-\hat{W}/(4d^{\prime}\log^{4}N)}\leq e^{-\hat{W}/(16d^{\prime})}$.

Altogether, we get that:

$\text{\bf Pr}\left[{\cal{E}}(E^{\prime})\right]\leq\text{\bf Pr}\left[|T\cap
X|<\frac{\hat{W}}{4d^{\prime}}\right]+\text{\bf Pr}\left[|T\cap
Y|\geq\frac{|T|}{\log^{4}N}\mid|T\cap
X|\geq\frac{\hat{W}}{4d^{\prime}}\right]\leq 2\cdot
e^{-\hat{W}/(16d^{\prime})}.$

Observe that $H$ has $\hat{W}$ special edges, and so the number of sets
$E^{\prime}$ containing at most $\frac{8\hat{W}}{d^{\prime}\log^{6}N}$ special
edges is bounded by:

$(2\hat{W})^{8\hat{W}/(d^{\prime}\log^{6}N)}\leq(24N)^{8\hat{W}/(d^{\prime}\log^{6}N)}\leq
2^{32\hat{W}/(d^{\prime}\log^{5}N)}.$

(We have used the fact that $\hat{W}\leq 12\hat{W}^{0}\leq 12N$). Using the
union bound over all sets $E^{\prime}$ of at most
$\frac{8\hat{W}}{d^{\prime}\log^{6}N}$ special edges, we get that the
probability that event ${\cal{E}}(E^{\prime})$ happens for any such set of
edges is bounded by:

$2^{\frac{32\hat{W}}{d^{\prime}\log^{5}N}}\cdot 2\cdot
2^{-\frac{\hat{W}}{16d^{\prime}\log^{4}N}}\leq
2^{-\frac{\hat{W}}{32d^{\prime}\log^{4}N}}\leq\frac{1}{512},$

since $d^{\prime}\leq\frac{8\hat{W}}{\log^{28}N}$ from Inequality 20.

Finally, if Event ${\cal{E}}_{2}$ happened, then either ${\cal{E}}_{1}$
happened, or, for some set $E^{\prime}$ of at most
$\frac{8\hat{W}}{d^{\prime}\log^{6}N}$ special edges, event
${\cal{E}}(E^{\prime})$ has happened. Therefore, overall, $\text{\bf
Pr}\left[{\cal{E}}_{2}\right]\leq\frac{1}{256}+\frac{1}{512}\leq\frac{1}{64}$.

####  7.2.4 Bad Event ${\cal{E}}_{3}$

We start again with intuition. Once we construct the expander $X$ and embed it
into $H$, we will need to route the remaining vertices of $H$ to the vertices
of $T$ via paths that cause congestion roughly $\widetilde{O}(d^{\prime})$. If
we are unable to do so, we will compute a sparse cut that separates some
vertices of $H$ from most terminals in $T$. Denote this cut by $(A,B)$. The
bad scenairo that we would like to avoid is when one side of the cut (say $A$)
contains almost all vertices of $H$, while the other side of the cut contains
few vertices of $H$, but it contains most terminals. If this happens, then the
vertices of $B$ will be subsequently deleted from $H$, thereby destroying the
expander that we have constructed. As we need to invest a large amount of time
into constructing the expander $X$ and embedding it into $H$, we would like to
avoid such a situation. Let $E^{\prime}=E_{G}(A,B)$. If some canonical cut
$(A^{\prime},B^{\prime})\in{\mathcal{C}}^{\prime}(E^{\prime})$ is roughly
balanced with respect to the vertices of $H$, then we can return cut
$(A^{\prime},B^{\prime})$ instead of cut $(A,B)$, and ensure that a
sufficiently large number of vertices is deleted from $H$, and the current
phase can be terminated. However, if ${\mathcal{C}}^{\prime}(E^{\prime})$
contains no such cut, then it is not clear how to bypass the problem mentioned
above. The third bad event is designed to capture exactly this scenario. We
now formally define it and show that it is unlikely to happen.

We say that the bad event ${\cal{E}}_{3}$ happens if there is a weakly well-
structured cut $(A,B)$ in $H$, with $|E_{H}(A,B)|\leq\frac{|T|}{\log^{6}N}$,
such that one of the sides of the cut contains at least $\frac{\hat{W}}{2}$
vertices of $H$ and at most $\frac{|T|}{32}$ vertices of $T$, and
additionally, if we denote by $E^{\prime}=E_{H}(A,B)$, then for every
canonical cut $(A^{\prime},B^{\prime})\in{\mathcal{C}}^{\prime}(E^{\prime})$,
either $|A^{\prime}|\leq\frac{\hat{W}}{\log^{5}N}$, or
$|B^{\prime}|\leq\frac{\hat{W}}{\log^{5}N}$ holds.

######  Claim 7.5.

$\text{\bf Pr}\left[{\cal{E}}_{3}\right]\leq\frac{1}{64}.$

###### Proof.

As before, if event ${\cal{E}}_{1}$ does not happen, and $E^{\prime}$ is a set
of special edges with $|E^{\prime}|\leq\frac{|T|}{\log^{6}N}$, then
$|E^{\prime}|\leq\frac{8\hat{W}}{d^{\prime}\log^{6}N}$ must hold. For every
subset $E^{\prime}$ of at most $\frac{8\hat{W}}{d^{\prime}\log^{6}N}$ special
edges, we define a bad event ${\cal{E}}^{\prime}(E^{\prime})$ to be the event
that there is some weakly well-structured cut $(A,B)$ in $H$ with
$E_{H}(A,B)=E^{\prime}$, such that one side of the cut cut contains at least
$\hat{W}/2$ vertices of $H$ and at most $\frac{|T|}{32}$ vertices of $T$, and
additionally, for every canonical cut
$(A^{\prime},B^{\prime})\in{\mathcal{C}}^{\prime}(E^{\prime})$, either
$|A^{\prime}|\leq\frac{\hat{W}}{\log^{5}N}$, or
$|B^{\prime}|\leq\frac{\hat{W}}{\log^{5}N}$ holds. We bound $\text{\bf
Pr}\left[{\cal{E}}^{\prime}(E^{\prime})\right]$ for each such set $E^{\prime}$
of edges separately, and then use the union bound in order to bound $\text{\bf
Pr}\left[{\cal{E}}_{3}\right]$.

Fix any subset $E^{\prime}$ of at most $\frac{8\hat{W}}{d^{\prime}\log^{6}N}$
special edges. Let $X\in{\mathcal{X}}(E^{\prime})$ be the set of vertices with
maximum cardinality. Using the same arguments as in the proof of 7.3, Event
${\cal{E}}^{\prime}(E^{\prime})$ may only happen if
$|X|\geq\hat{W}-\frac{2\hat{W}}{\log^{5}N}$. We assume from now on that
$|X|\geq\hat{W}-\frac{2\hat{W}}{\log^{5}N}$ holds. Let $Y=V(H)\setminus X$, so
that $|Y|\leq\frac{2\hat{W}}{\log^{5}N}$.

Consider now some weakly well-structured cut $(A,B)$ in $H$ with
$E_{H}(A,B)=E^{\prime}$, and assume that one of the sets
$Z\in\left\\{A,B\right\\}$ contains at least $\hat{W}/2$ vertices of $H$ and
at most $\frac{|T|}{32}$ vertices of $T$. Since set $X$ must be contained in
one of the sides of the cut, it must be the case that $X\subseteq Z$, and
$|T\cap X|\leq\frac{|T|}{32}=\frac{|T\cap X|+|T\cap Y|}{32}$. Therefore,
$|T\cap X|\leq\frac{|T\cap Y|}{31}$ must hold.

Using the same reasoning as in the proof of 7.3, $\text{\bf Pr}\left[|T\cap
X|<\frac{\hat{W}}{4d^{\prime}}\right]\leq e^{-\hat{W}/(16d^{\prime})}$.

Assume now that $|T\cap X|\geq\frac{\hat{W}}{4d^{\prime}}$. In this case, if
$|T\cap X|\leq\frac{|T|}{32}$ holds, then $|T\cap Y|\geq 31|T\cap
X|\geq\frac{31\hat{W}}{4d^{\prime}}$ must hold. Notice that, since
$|Y|\leq\frac{2\hat{W}}{\log^{5}N}$, $\text{\bf E}\left[|T\cap
Y|\right]\leq\frac{2\hat{W}}{d^{\prime}\log^{5}N}$. From Lemma 2.5, $\text{\bf
Pr}\left[|T\cap Y|\geq\frac{31\hat{W}}{4d^{\prime}}\right]\leq
2^{-31\hat{W}/(4d^{\prime})}\leq e^{-\hat{W}/(16d^{\prime})}$.

Altogether, we get that:

$\text{\bf Pr}\left[{\cal{E}}^{\prime}(E^{\prime})\right]\leq\text{\bf
Pr}\left[|T\cap X|<\frac{\hat{W}}{4d^{\prime}}\right]+\text{\bf
Pr}\left[|T\cap X|\leq\frac{|T|}{32}\mid|T\cap
X|\geq\frac{\hat{W}}{4d^{\prime}}\right]\leq 2\cdot
e^{-\hat{W}/(16d^{\prime})}.$

As in the proof of 7.3, the number of sets $E^{\prime}$ containing at most
$\frac{8\hat{W}}{d^{\prime}\log^{6}N}$ special edges is bounded by
$2^{32\hat{W}/(d^{\prime}\log^{5}N)}$.

Using the union bound over all sets $E^{\prime}$ of at most
$\frac{8\hat{W}}{d^{\prime}\log^{6}N}$ special edges, we get that the
probability that event ${\cal{E}}^{\prime}(E^{\prime})$ happens for any such
set of edges is bounded by:

$2^{\frac{32\hat{W}}{d^{\prime}\log^{5}N}}\cdot 2\cdot
2^{-\frac{\hat{W}}{16d^{\prime}\log^{4}N}}\leq
2^{-\frac{\hat{W}}{32d^{\prime}\log^{4}N}}\leq\frac{1}{512},$

since $d^{\prime}\leq\frac{8\hat{W}}{\log^{28}N}$ from Inequality 20.

Finally, if Event ${\cal{E}}_{3}$ happened, then either event ${\cal{E}}_{1}$
happened, or, for some set $E^{\prime}$ of at most
$\frac{8\hat{W}}{d^{\prime}\log^{6}N}$ special edges, event
${\cal{E}}^{\prime}(E^{\prime})$ has happened. Therefore, overall, $\text{\bf
Pr}\left[{\cal{E}}_{3}\right]\leq\frac{1}{256}+\frac{1}{512}\leq\frac{1}{64}$.

####  7.2.5 Bad Event ${\cal{E}}_{4}$

Recall that for every edge $e\in E(G)$, there is a corresponding path
$P^{*}(e)$, containing $2\ell(e)$ vertices, that represents $e$ in graph $H$.
Recall that we have ensured that, at the beginning of the phase, the length of
every edge $e\in E(G)$ is at most $d^{\prime}$. The fourth bad event,
${\cal{E}}_{4}$, happens if there is some edge $e\in E(G)$, such that at least
$16\log N$ vertices of $P^{*}(e)$ are in $T$.

######  Claim 7.6.

$\text{\bf Pr}\left[{\cal{E}}_{4}\right]\leq\frac{1}{64}$.

###### Proof.

For every special edge $e\in E(G)$, let ${\cal{E}}^{\prime\prime}(e)$ be the
bad event that at least $16\log N$ vertices of $P^{*}(e)$ are added to $T$.
Since the total number of vertices on $P^{*}(e)$ is $2\ell(e)\leq
2d^{\prime}$, and every edge is chosen to be added to $T$ with probability
$\frac{1}{d^{\prime}}$, the expectation of $|P^{*}(e)\cap T|$ is at most $2$.
From Lemma 2.5, the probability of ${\cal{E}}^{\prime\prime}(e)$ is then
bounded by $2^{-16\log N}\leq N^{-16}$.

By using the union bound over all special edges $e\in E(G)$, and since the
number of such edges is bounded by $n\leq N$, we get that:

$\text{\bf Pr}\left[{\cal{E}}_{4}\right]\leq N\cdot N^{-16}\leq\frac{1}{64}.$

Lastly, we let ${\cal{E}}$ be the bad event that either of the events
${\cal{E}}_{1},{\cal{E}}_{2}$, ${\cal{E}}_{3}$, or ${\cal{E}}_{4}$ happened.
Clearly:

$\text{\bf Pr}\left[{\cal{E}}\right]\leq\sum_{i=1}^{4}\text{\bf
Pr}\left[{\cal{E}}_{i}\right]\leq\frac{1}{16}.$

Note that we can check, in time $O(N)$, whether events ${\cal{E}}_{1}$ and
${\cal{E}}_{4}$ hold. If either of these events holds, we terminate the
algorithm and return “FAIL”. Therefore, we assume from now on that neither of
the events ${\cal{E}}_{1},{\cal{E}}_{4}$ happened.

As the phase progresses, vertices may be deleted from graphs $G$ and $H$. We
view the set $T$ of terminal vertices as static, that is, it does not change
even as some vertices of $T$ are deleted from $H$.

###  7.3 Finalizing Cuts

In this subsection we define a special kinds of cuts in graph $H$, that we
call _finalizing_ cuts. If, at any time during the execution of a phase, our
algorithm computes such a cut in the current graph $H$, we will be able to
terminate the current phase, by either correctly establishing that at least
one of the events ${\cal{E}}_{2},{\cal{E}}_{3}$ must have happened, or by
providing a strongly well-structured $\varphi$-sparse cut $(A,B)$ in the
current graph $G$, such that $w(A),w(B)\geq\frac{\hat{W}}{\log^{30}N}$. In the
former case, we will terminate the current phase with a “FAIL”, while in the
latter case, once cut $(A,B)$ is processed, and the corresponding vertices and
edges are deleted from $H$, we are guaranteed that at least
$\frac{\hat{W}}{\log^{30}N}$ vertices have been deleted from $H$ since the
beginning of the phase, and so the current phase terminates. We are now ready
to define finalizing cuts in $H$.

######  Definition 7.7 (Finalizing Cut).

Let $(A,B)$ be a cut in graph $H$ at any time during the execution of a phase.
We say that the cut $(A,B)$ is a _finalizing_ cut, if the following hold:

  * •

all edges in $E_{H}(A,B)$ are special edges;

  * •

$|E_{H}(A,B)|\leq\frac{|T|}{8\log^{6}N}$; and

  * •

one of the sides of the cut $Z\in\left\\{A,B\right\\}$ contains at least
$|V(H)|-\frac{\hat{W}}{32}$ vertices of $H$, and at most
$|T|\cdot\left(1-\frac{7}{\log^{4}N}\right)$ vertices of $T$.

Next, we show that, if our algorithm ever produces a finalizing cut during a
phase, then the phase can be terminated, in the following claim.

######  Claim 7.8.

Suppose, at any time during the execution of a phase, there is a finalizing
cut $(\tilde{A},\tilde{B})$ in the current graph $H$. Assume further that
neither of the events ${\cal{E}}_{2},{\cal{E}}_{3}$ has happened, and that
every edge in the current graph $G$ has length at most $d^{\prime}/2$. Then
there is a strongly well-structured $\varphi$-sparse cut $(A^{*},B^{*})$ in
the current graph $G$, such that
$w(A^{*}),w(B^{*})\geq\frac{\hat{W}}{\log^{30}N}$. Moreover, there is a
deterministic algorithm, that, given the graph $G$ at the beginning of the
current phase (that we denote by $G_{0}$), the sequence of the strongly well-
structured $\varphi$-sparse cuts $(A_{1},B_{1}),\ldots(A_{q},B_{q})$ in $G$
that the algorithm has produced during the current phase so far, the current
graphs $G$ and $H$, and the finalizing cut $(\tilde{A},\tilde{B})$ in the
current graph $H$, either correctly estabishes that at least one of the events
${\cal{E}}_{2},{\cal{E}}_{3}$ has happened, or computes a strongly well-
structured $\varphi$-sparse cut $(A^{*},B^{*})$ in the current graph $G$, such
that $w(A^{*}),w(B^{*})\geq\frac{\hat{W}}{\log^{30}N}$. The running time of
the algorithm is $O(\hat{W}^{2})$.

The remainder of this subsection is dedicated to the proof of 7.8. We denote
by $G_{0}$ the graph $G$ at the beginning of the current phase, and by $H_{0}$
its corresponding subdivided graph $H$. The main idea of the proof is to
exploit the cuts $(A_{1},B_{1}),\ldots(A_{q},B_{q})$ in graph $G$, together
with the finalizing cut $(\tilde{A},\tilde{B})$ in graph $H$, in order to
compute another well-structured cut $(\tilde{S},\tilde{S}^{\prime})$ in
$H_{0}$, such that
$|E_{H}(\tilde{S},\tilde{S}^{\prime})|\leq\frac{|T|}{\log^{6}N}$, and one side
of the cut contains all but at most $\frac{\hat{W}}{16}$ vertices of $H_{0}$,
but only a relatively small fraction of the vertices of $T$. Let
$E^{\prime\prime}=E_{H}(\tilde{S},\tilde{S}^{\prime})$. By inspecting all
canonical cuts in ${\mathcal{C}}^{\prime}(E^{\prime\prime})$, we will then
either correctly establish that at least one of the events
${\cal{E}}_{2},{\cal{E}}_{3}$ happened, or we will compute a cut
$(A^{*},B^{*})$ in $G$ with the required properties.

In the following technical claim, whose proof is deferred to Section D.2 of
Appendix, we provide an algorithm for computing the cut
$(\tilde{S},\tilde{S}^{\prime})$ in $H_{0}$ with the desired properties.

######  Claim 7.9.

There is a deterministic algorithm, that, given the graph $G_{0}$, the
sequence of the strongly well-structured $\varphi$-sparse cuts
$(A_{1},B_{1}),\ldots(A_{q},B_{q})$ in $G$ that the algorithm has produced
during the current phase so far, the current graphs $G$ and $H$, such that all
edge lengths in $G$ are bounded by $d^{\prime}/2$, and the finalizing cut
$(\tilde{A},\tilde{B})$ in the current graph $H$, computes a weakly well-
structured cut $(\tilde{S},\tilde{S}^{\prime})$ in $H_{0}$, such that
$|E_{H_{0}}(\tilde{S},\tilde{S}^{\prime})|\leq\frac{|T|}{\log^{6}N}$, and one
side $\tilde{Z}\in\left\\{\tilde{S},\tilde{S}^{\prime}\right\\}$ of the cut
contains all but at most $\hat{W}/8$ vertices of $H_{0}$, and at most
$\left(1-\frac{2}{\log^{4}N}\right)\cdot|T|$ vertices of $T$. The running time
of the algorithm is $O(\hat{W}^{2})$.

We are now ready to complete the proof of 7.8. Let
$E^{\prime\prime}=E_{H_{0}}(\tilde{S},\tilde{S}^{\prime})$. We construct, in
time $O(|E(H_{0})|)\leq O(\hat{W}^{2})$, the collection
${\mathcal{X}}(E^{\prime\prime})$ of subsets of $H_{0}$ associated with the
set $E^{\prime\prime}$ of edges, and then examine all canonical cuts
$(A,B)\in{\mathcal{C}}^{\prime}(E^{\prime\prime})$. For each such cut, we
check whether $|A|\leq\frac{\hat{W}}{\log^{5}N}$, or
$|B|\leq\frac{\hat{W}}{\log^{5}N}$ hold. From the definition of canonical
cuts, we can check this, for every cut
$(A,B)\in{\mathcal{C}}^{\prime}(E^{\prime\prime})$, in time $O(|V(H)|)\leq
O(\hat{W})$. We first claim that if, for each such canonical cut $(A,B)$,
either $|A|\leq\frac{\hat{W}}{\log^{5}N}$ or
$|B|\leq\frac{\hat{W}}{\log^{5}N}$ holds, then at least one of the events
${\cal{E}}_{2},{\cal{E}}_{3}$ must have happened.

######  Observation 7.10.

If, for every canonical cut
$(A,B)\in{\mathcal{C}}^{\prime}(E^{\prime\prime})$, either
$|A|\leq\frac{\hat{W}}{\log^{5}N}$ or $|B|\leq\frac{\hat{W}}{\log^{5}N}$
holds, then at least one of the events ${\cal{E}}_{2},{\cal{E}}_{3}$ must have
happened.

###### Proof.

Recall that one side
$\tilde{Z}\in\left\\{\tilde{S},\tilde{S}^{\prime}\right\\}$ of the cut
$(\tilde{S},\tilde{S}^{\prime})$ in $H$ contains all but at most $\hat{W}/8$
vertices of $H_{0}$, and at most $\left(1-\frac{2}{\log^{4}N}\right)\cdot|T|$
vertices of $T$. Denote the other side of the cut by $\tilde{Z}^{\prime}$. We
now consider two cases. The first case happens if $|\tilde{Z}\cap
T|\leq\frac{|T|}{32}$. Then $\tilde{Z}$ contains at least $\frac{\hat{W}}{2}$
vertices of $H$ and at most $\frac{|T|}{32}$ vertices of $T$. Since, for every
canonical cut $(A,B)\in{\mathcal{C}}^{\prime}(E^{\prime\prime})$, either
$|A|\leq\frac{\hat{W}}{\log^{5}N}$ or $|B|\leq\frac{\hat{W}}{\log^{5}N}$
holds, we conclude that Event ${\cal{E}}_{3}$ must have happened.

Otherwise, $|\tilde{Z}\cap T|\geq\frac{|T|}{32}$, and, since $|\tilde{Z}\cap
T|\leq\left(1-\frac{2}{\log^{4}N}\right)\cdot|T|$, we get that $|\tilde{Z}\cap
T|,|\tilde{Z}^{\prime}\cap T|\geq\frac{|T|}{\log^{4}N}$. Since, for every
canonical cut $(A,B)\in{\mathcal{C}}^{\prime}(E^{\prime\prime})$, either
$|A|\leq\frac{\hat{W}}{\log^{5}N}$ or $|B|\leq\frac{\hat{W}}{\log^{5}N}$
holds, we conclude that Event ${\cal{E}}_{2}$ must have happened.

If, for every canonical cut
$(A,B)\in{\mathcal{C}}^{\prime}(E^{\prime\prime})$, either
$|A|\leq\frac{\hat{W}}{\log^{5}N}$ or $|B|\leq\frac{\hat{W}}{\log^{5}N}$ hold,
then we terminate the algorithm, and report that at least one of the events
${\cal{E}}_{2},{\cal{E}}_{3}$ has happened. We assume from now on that there
is a canonical cut $(A,B)\in{\mathcal{C}}^{\prime}(E^{\prime\prime})$ with
$|A|,|B|\geq\frac{\hat{W}}{\log^{5}N}$. Recall that $(A,B)$ is a weakly
canonical cut in graph $H_{0}$, and
$|E_{H_{0}}|\leq\frac{|T|}{\log^{6}N}\leq\frac{8\hat{W}}{d^{\prime}\log^{6}N}\leq\frac{8}{d^{\prime}\log
N}\cdot\min\left\\{|A|,|B|\right\\}\leq\frac{\varphi}{64}\min\left\\{|A|,|B|\right\\}$.
Therefore, $(A,B)$ is a weakly canonical cut of sparsity at most
$\frac{\varphi}{64}$ in $H_{0}$. Recall also that every edge in $G_{0}$ has
length at most $\frac{d^{\prime}}{2}=\frac{2}{\varphi}$.

For every vertex $v\in V(G_{0})$, we denote the weight of $v$ in $G_{0}$ by
$w_{0}(v)$, and, for every subset $S\subseteq V(G_{0})$ of vertices, we denote
$w_{0}(S)=\sum_{v\in S}w_{0}(v)$. Similarly, for every vertex $v\in V(G)$, we
denote the weight of $v$ in $G$ by $w(v)$, and for a subset $S\subseteq V(G)$
of vertices, we denote $w(S)=\sum_{v\in S}w(v)$. Note that, for every vertex
$v\in V(G)$, $w_{0}(v)\leq w(v)$.

Consider now the cut $(A^{\prime},B^{\prime})$ in $G_{0}$, where
$A^{\prime}=A\cap V(G_{0})$ and $B^{\prime}=B\cap V(G_{0})$. From 4.4,
$(A^{\prime},B^{\prime})$ is a weakly well-structured cut in $G_{0}$, whose
sparsity is at most $\frac{\varphi}{8}$, with
$w_{0}(A^{\prime})\geq\frac{|A|}{8}\geq\frac{\hat{W}}{8\log^{5}N}$, and
$w_{0}(B^{\prime})\geq\frac{|B|}{8}\geq\frac{\hat{W}}{8\log^{5}N}$.

Recall that $d^{\prime}\leq\frac{2d}{(\log
N)^{28}}\leq\frac{n}{256}\leq\frac{\hat{W}}{128}\leq\frac{\sum_{e\in
E(G_{0})}\ell(e)}{2}$. Therefore, the length of every edge in $G_{0}$ is
bounded by $\frac{\sum_{e\in E(G_{0})}\ell(e)}{2}$. We call now apply the
algorithm from 4.5 to graph $G_{0}$, parameter $\frac{\varphi}{8}$, and the
cut $(A^{\prime},B^{\prime})$ in $G_{0}$, to compute a cut
$(A^{\prime\prime},B^{\prime\prime})$ in $G_{0}$ with
$w_{0}(A^{\prime\prime})\geq\frac{w_{0}(A^{\prime})}{4}\geq\frac{\hat{W}}{32\log^{5}N}$
and
$w_{0}(B^{\prime\prime})\geq\frac{w_{0}(B^{\prime})}{4}\geq\frac{\hat{W}}{32\log^{5}N}$,
such that $(A^{\prime\prime},B^{\prime\prime})$ is a strongly well-structured
cut in $G_{0}$, whose sparsity is at most $\varphi/4$. The running time of the
algorithm is bounded by $O(|E(G_{0})|)\leq O(\hat{W}^{2})$.

Lastly, we define the cut $(A^{*},B^{*})$ in the current graph $G$ as follows:
$A^{*}=A^{\prime\prime}\cap V(G)$ and $B^{*}=B^{\prime\prime}\cap V(G)$. Since
$(A^{\prime\prime},B^{\prime\prime})$ is a strongly well-structured cut in
$G_{0}$, and $G\subseteq G_{0}$, it is easy to verify that $(A^{*},B^{*})$ is
a strongly well-structured cut in $G$. Moreover, since the current phase has
not terminated yet, the total weight of all vertices deleted so far from $G$
is bounded by $\frac{\hat{W}}{\log^{30}N}$, so $w(A^{*})\geq w_{0}(A^{*})\geq
w_{0}(A^{\prime\prime})-\frac{\hat{W}}{\log^{30}N}\geq\frac{w_{0}(A^{\prime\prime})}{2}>\frac{\hat{W}}{\log^{30}N}$.
Similarly, $w(B^{*})\geq
w_{0}(B^{*})\geq\frac{w_{0}(B^{\prime\prime})}{2}>\frac{\hat{W}}{\log^{30}N}$.
Since $|E_{G}(A^{*},B^{*})|\leq E_{G_{0}}(A^{\prime\prime},B^{\prime\prime})$,
we conclude that cut $(A^{*},B^{*})$ has sparsity at most $\varphi$. We output
the cut $(A^{*},B^{*})$ as the outcome of the algorithm. From the above
discussion, the running time of the algorithm is bounded by $O(\hat{W}^{2})$.

###  7.4 First Data Structure: Expander $X$ and its Embedding

Throughout the phase, we will maintain an expander $X$, that is defined over
the terminals, and is embedded into $H$. We start by providing the algorithm
to initialize this data structure, and then provide the algorithm for
maintaining it throughout the phase.

####  7.4.1 Initialization

In this step, we will either compute an expander $X$ over the set $T$ of
vertices and embed it into $H$ via short paths that cause low congestion; or
we will compute a sparse cut $(A,B)$ in $H$, following which a sufficient
number of vertices will be deleted from $H$, so that the current phase will
terminate. We summarize the algorithm for initializing the expander in the
following lemma, whose statement uses the constant $\alpha_{0}$ from Theorem
2.1.

######  Lemma 7.11.

There is a randomized algorithm, that either returns “FAIL”, or computes one
of the following:

  * •

either a finalizing cut in $H$;

  * •

or a strongly well-structured $1/d^{\prime}$-sparse cut $(A,B)$ in $G$ with
$w(A),w(B)\geq\frac{\hat{W}}{(\log N)^{30}}$;

  * •

or a graph $X^{*}$ with $V(X^{*})=T$, such that $X^{*}$ has maximum vertex
degree at most $24$, and it is an $\frac{\alpha_{0}}{81}$-expander. In the
latter case, the algorithm additionally computes a set $F\subseteq E(X^{*})$
of at most $\frac{\alpha_{0}\cdot|T|}{500}$ edges, and an embedding
${\mathcal{P}}^{*}$ of $X^{*}\setminus F$ into $H$ via paths that have length
at most $O\left(d^{\prime}\cdot(\log N)^{16}\right)$ each, that cause
congestion $O\left((\log N)^{13}\right)$.

The probability that the algorithm returns “FAIL” is at most
$\frac{1}{N^{7}}$, and the running time of the algorithm is bounded by:

$O\left(c_{1}\cdot\hat{W}^{2}\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}(r-1)+8c_{2}+3}\right).$

The remainder of this subsubsection is dedicated to proving Lemma 7.11.

#### Recap of the Cut-Matching Game

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

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

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

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

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

#### Implementing the Cut Player

There are several known algorithms that we could use in order to implement the
cut player. For example, [BGS20], generalizing the results of [CGL+20] to
directed graphs, provided such an algorithm, whose running time is
$\widehat{O}(\hat{n})$ (see Theorem 7.3 in [BGS20]). We use instead the
algorithm of [CK24], whose analysis is very simple, even though its running
time is somewhat higher. The algorithm is summarized in the following theorem,
that uses the constant $\alpha_{0}$ from Theorem 2.1.

######  Theorem 7.13 (Theorem 8.5 in [CK24]).

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

  * •

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

  * •

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

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

Next, we discuss the implementation of the matching player, which is different
from that of [CK24]: to make the algorithm more efficient, we rely on
Algorithm ${\mathcal{A}}$ for the $r$-restricted $\mathsf{RouteAndCut}$
problem, whose existence we have assumed.

#### Implementing the Matching Player

We use the parameter $N^{\prime}=\max\left\\{N,\hat{W}\right\\}$, so that
$|V(H)|\leq N^{\prime}$ and $N\leq N^{\prime}\leq 12N$ holds, and additional
parameters $\hat{\Delta}=\left\lceil\frac{|T|}{4}\right\rceil$ and
$\eta^{\prime}=(\log N^{\prime})^{8}$. Throughout the algorithm, we will
sometimes compute disjoint subsets $A,B$ of vertices of $H$ of cardinality
$\hat{\Delta}$ each, and we will view
$(H,A,B,\hat{\Delta},\eta^{\prime},N^{\prime})$ as an instance of the
$r$-restricted $\mathsf{RouteAndCut}$ problem. We show that this must be
indeed a valid instance of the problem, in the following simple observation
whose proof is deferred to Section D.3 of Appendix.

######  Observation 7.14.

For any pair $(A,B)$ of disjoint subsets of $V(H)$ of cardinality
$\hat{\Delta}$ each, $(H,A,B,\hat{\Delta},\eta^{\prime},N^{\prime})$ is a
valid input to the $r$-restricted $\mathsf{RouteAndCut}$ problem.

The matching player will be implemented by applying Algorithm ${\mathcal{A}}$
for the $r$-restricted $\mathsf{RouteAndCut}$ problem to instances
$(H,A,B,\hat{\Delta},\eta^{\prime},N^{\prime})$, where $A,B$ are disjoint
subsets of $V(H)$ of cardinality $\hat{\Delta}$ each. Throughout, we will use
a parameter ${z=\frac{4|T|}{\log^{4}N}}$.

#### Proof of Lemma 7.11: the Cut-Matching Game

We let $\tilde{c}$ be a large enough constant, so that, in Theorem 7.13 the
parameter $\tilde{\eta}\leq\tilde{c}\log^{2}\hat{n}$. We start with the graph
$X$, whose vertex set is $T$, and edge set is $\emptyset$, and then run the
Cut-Matching game on it. Recall that the number of iterations in the game is
bounded by $c_{\mathsf{CMG}}\cdot\log\hat{n}$. This ensures that the graph $X$
that is maintained over the course of the game has maximum vertex degree
$O(\log\hat{n})$.

#### Description of a Single Iteration

We now describe the execution of the $i$th iteration. First, we apply the
algorithm from Theorem 7.13 to the current graph $X$. We say that the current
iteration is a _type-1 iteration_ , if the algorithm returns a cut
$(A_{i},B_{i})$ in $X$ with $|E_{X}(A_{i},B_{i})|\leq\hat{n}/100$ and
$|A_{i}|,|B_{i}|\geq\hat{n}/10$, and otherwise we say that it is a type-2
iteration. Assume first that the current iteration is a type-1 iteration. Then
we compute two arbitrary disjoint subsets $A^{\prime}_{i},B^{\prime}_{i}$ of
$V(X)$ of cardinality
$\left\lceil\frac{\hat{n}}{4}\right\rceil=\left\lceil\frac{|T|}{4}\right\rceil=\hat{\Delta}$
each, such that either $A_{i}\subseteq A^{\prime}_{i}$ or $B_{i}\subseteq
B^{\prime}_{i}$ holds. We treat $(A^{\prime}_{i},B^{\prime}_{i})$ as the move
of the cut player. Recall that the running time of the algorithm from Theorem
7.13 is $\widetilde{O}(\hat{n}^{2})\leq\widetilde{O}(\hat{W}^{2})$.

Next, we consider two instances of the $r$-restricted $\mathsf{RouteAndCut}$
problem: instance
$(H,A_{i}^{\prime},B_{i}^{\prime},\hat{\Delta},\eta^{\prime},N^{\prime})$, and
instance
$(H,B_{i}^{\prime},A_{i}^{\prime},\hat{\Delta},\eta^{\prime},N^{\prime})$. We
apply Algorithm ${\mathcal{A}}$ to each of these two instances. If the
algorithm returns “FAIL” on any of these instances, we repeat it up to
$\left\lceil 10\log N\right\rceil$ times, or until it terminates with a valid
output, whichever happens first. If, for any of the two instances of the
$\mathsf{RouteAndCut}$ problem, the algorithm returned “FAIL” repeatedly in
each of its $\left\lceil 10\log N\right\rceil$ applications, then we terminate
the algorithm and return “FAIL”. Since the probability that an algorithm for
the $\mathsf{RouteAndCut}$ problem returns “FAIL” is at most $1/2$, the
probability that the current iteration termintates with a “FAIL” is bounded by
$\frac{2}{N^{10}}$. We assume from now on that the last application of
Algorithm ${\mathcal{A}}$ to each of the two instances did not terminate with
a “FAIL”. We denote by ${\mathcal{Q}}^{\prime}_{i}$ and
${\mathcal{Q}}^{\prime\prime}_{i}$ the routings that these algorithms return,
where ${\mathcal{Q}}^{\prime}_{i}$ is the routing from $A^{\prime}_{i}$ to
$B^{\prime}_{i}$. Recall that the running time of Algorithm ${\mathcal{A}}$ on
each of these two instances is bounded by:

$\begin{split}&c_{1}\cdot\hat{W}^{2}\cdot 2^{c_{2}\sqrt{\log
N^{\prime}}}\cdot(\log N^{\prime})^{16c_{2}(r-1)+8c_{2}}\\\
&\quad\quad\quad\quad\quad\quad\leq O\left(c_{1}\cdot\hat{W}^{2}\cdot
2^{c_{2}\sqrt{\log N}}\cdot(\log(12N))^{16c_{2}(r-1)+8c_{2}+1}\right)\\\
&\quad\quad\quad\quad\quad\quad\leq O\left(c_{1}\cdot\hat{W}^{2}\cdot
2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}(r-1)+8c_{2}+1}\cdot\left(1+\frac{1}{32c_{2}r}\right)^{16c_{2}(r-1)+8c_{2}+1}\right)\\\
&\quad\quad\quad\quad\quad\quad\leq O\left(c_{1}\cdot\hat{W}^{2}\cdot
2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}(r-1)+8c_{2}+1}\cdot\left(1+\frac{1}{32c_{2}r}\right)^{32c_{2}r}\right)\\\
&\quad\quad\quad\quad\quad\quad\leq O\left(c_{1}\cdot\hat{W}^{2}\cdot
2^{c_{2}\sqrt{\log N}}\cdot(\log N)^{16c_{2}(r-1)+8c_{2}+1}\right)\\\
\end{split}$

(we have used Inequalities 17 and 18). Since Algorithm ${\mathcal{A}}$ may be
applied up to $O(\log N)$ times to the resulting instances of the
$\mathsf{RouteAndCut}$ problem, the total time spent in a single iteration by
the executions of Algorithm ${\mathcal{A}}$ is bounded by:

$O\left(c_{1}\cdot\hat{W}^{2}\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}(r-1)+8c_{2}+2}\right).$

We now consider two cases. The first case happens when both
$|{\mathcal{Q}}^{\prime}_{i}|,|{\mathcal{Q}}^{\prime\prime}_{i}|\geq\hat{\Delta}-z$.
In this case, we say that the current iteration is of _type (1a)_. Recall that
the paths in each of the sets ${\mathcal{Q}}^{\prime}_{i}$,
${\mathcal{Q}}^{\prime\prime}_{i}$ cause congestion at most
$4\eta^{\prime}\cdot\log N^{\prime}\leq 4(\log N^{\prime})^{9}\leq
4(\log(12N))^{9}\leq(\log N)^{10}$, since $\eta^{\prime}=(\log
N^{\prime})^{8}$ and $N^{\prime}\leq 12N$. Since regular and special edges
must alternate on each such path, and since the total number of special edges
is at most $\hat{W}/2$,
$\sum_{P\in{\mathcal{Q}}^{\prime}_{i}}|E(P)|\leq\hat{W}\cdot(\log N)^{10}$.
Similarly,
$\sum_{P\in{\mathcal{Q}}^{\prime\prime}_{i}}|E(P)|\leq\hat{W}\cdot(\log
N)^{10}$. We say that a path
$Q\in{\mathcal{Q}}^{\prime}_{i}\cup{\mathcal{Q}}^{\prime\prime}_{i}$ is _long_
, if it contains more than $8d^{\prime}\cdot(\log N)^{14}$ edges. Clearly, the
number of long paths in ${\mathcal{Q}}^{\prime}_{i}$ is bounded by:

$\frac{\hat{W}\cdot(\log N)^{10}}{8d^{\prime}\cdot(\log
N)^{14}}\leq\frac{\hat{W}}{2d^{\prime}(\log
N)^{4}}\leq\frac{|T|}{\log^{4}N}\leq z.$

(We have used the fact that $|T|\geq\frac{\hat{W}}{2d^{\prime}}$, as Event
${\cal{E}}_{1}$ did not happen.) Similarly, at most $z$ paths in
${\mathcal{Q}}^{\prime\prime}_{i}$ are long. We discard all long paths from
both ${\mathcal{Q}}^{\prime}_{i}$ and ${\mathcal{Q}}^{\prime\prime}_{i}$. At
the end of this process, every path in
${\mathcal{Q}}^{\prime}_{i}\cup{\mathcal{Q}}^{\prime\prime}_{i}$ has length at
most $8d^{\prime}\cdot(\log N)^{14}$, and
$|{\mathcal{Q}}^{\prime}_{i}|,|{\mathcal{Q}}^{\prime\prime}_{i}|\geq\hat{\Delta}-2z$.

The set ${\mathcal{Q}}^{\prime}_{i}$ of paths naturally defines a matching
${\mathcal{M}}^{\prime}_{i}\subseteq A^{\prime}_{i}\times B^{\prime}_{i}$,
where for every path $Q\in{\mathcal{Q}}_{i}$ whose endpoints are $a\in
A^{\prime}_{i},b\in B^{\prime}_{i}$, we add an edge $e=(a,b)$ to the matching.
We also let $Q(e)=Q$ be its embedding into $G$. Similarly, the set
${\mathcal{Q}}^{\prime\prime}_{i}$ of paths defines a matching
${\mathcal{M}}^{\prime\prime}_{i}\subseteq B^{\prime}_{i}\times
A^{\prime}_{i}$, together with an embedding
$Q(e)\in{\mathcal{Q}}^{\prime\prime}_{i}$ for each edge
$e\in{\mathcal{M}}^{\prime\prime}$. Recall that matching
${\mathcal{M}}^{\prime}_{i}$ has cardinality at least $\hat{\Delta}-2z$, while
$|A^{\prime}_{i}|=|B^{\prime}_{i}|=\hat{\Delta}$. Therefore, by adding a set
$F^{\prime}_{i}$ of at most $2z$ additional edges (that we refer to as _fake
edges_), we can turn matching ${\mathcal{M}}^{\prime}_{i}$ into a perfect one.
Similarly, we add a collection $F^{\prime\prime}_{i}$ of at most $2z$ fake
edges to ${\mathcal{M}}^{\prime\prime}_{i}$ in order to turn it into a perfect
matching. The edges of
${\mathcal{M}}^{\prime}_{i}\cup{\mathcal{M}}^{\prime\prime}_{i}$ are then
added to graph $X$, and the current iteration terminates.

Assume now that one of the two sets
${\mathcal{Q}}^{\prime}_{i},{\mathcal{Q}}^{\prime\prime}_{i}$ computed by
Algorithm ${\mathcal{A}}$ contains fewer than $\hat{\Delta}-z$ paths; we
assume w.l.o.g. that it is ${\mathcal{Q}}^{\prime}_{i}$. In this case we say
that the current iteration is of _type (1b)_.

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 serve as endpoints of the paths in
${\mathcal{Q}}^{\prime}_{i}$, so
$|A^{\prime\prime}_{i}|,|B^{\prime\prime}_{i}|\geq z$. Recall that the
algorithm must also return a cut $(Z,Z^{\prime})$ in $H$, such that:

$|E_{H}(Z,Z^{\prime})|\leq\frac{64\hat{\Delta}}{\eta^{\prime}\log^{4}\hat{W}}+\frac{256|{\mathcal{Q}}^{\prime}_{i}|}{\eta^{\prime}}\leq\frac{512\hat{\Delta}}{\eta^{\prime}}\leq\frac{256|T|}{(\log
N^{\prime})^{8}}\leq\frac{\hat{W}}{d^{\prime}(\log N)^{7}},$

since $\eta^{\prime}=(\log N^{\prime})^{8}$,
$\hat{\Delta}=\left\lceil\frac{|T|}{4}\right\rceil$,
$|T|\leq\frac{8\hat{W}}{d^{\prime}}$ since Event ${\cal{E}}_{1}$ did not
happen, and $N^{\prime}\geq N$. We are also guaranteed that
$A^{\prime\prime}_{i}\subseteq Z$ and $B^{\prime\prime}_{i}\subseteq
Z^{\prime}$, so $|Z\cap T|,|Z^{\prime}\cap T|\geq z=\frac{4|T|}{\log^{4}N}$.
We use the following simple claim, that either computes a finalizing cut in
$H$, or returns a strongly well-structured $1/d^{\prime}$-sparse cut $(A,B)$
in $G$ with $w(A),w(B)\geq\frac{\hat{W}}{(\log N)^{30}}$. The proof is
deferred to Section D.4 of Appendix.

######  Claim 7.15.

There is a deterministic algorithm, that, given a cut $(Z,Z^{\prime})$ in
graph $H$ with $|Z\cap T|,|Z^{\prime}\cap T|\geq\frac{4|T|}{\log^{4}N}$ and
$|E_{H}(Z,Z^{\prime})|\leq\frac{\hat{W}}{d^{\prime}(\log N)^{7}}$, either
computes a finalizing cut in $H$, or returns a strongly well-structured
$1/d^{\prime}$-sparse cut $(A,B)$ in $G$ with
$w(A),w(B)\geq\frac{\hat{W}}{(\log N)^{30}}$. The running time of the
algorithm is $O(\hat{W}^{2})$.

If the algorithm from 7.15 returns a finalizing cut in $H$, then we output
this cut as the outcome of the algorithm. Otherwise, we output the
$1/d^{\prime}$-sparse cut $(A,B)$ in $G$ with
$w(A),w(B)\geq\frac{\hat{W}}{(\log N)^{30}}$ that the algorithm returns.

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

Denote $\hat{F}=\bigcup_{i^{\prime}=1}^{i-1}(F^{\prime}_{i}\cup
F^{\prime\prime}_{i})$ – the collection of the fake edges that we have
computed so far. Since for all $1\leq i^{\prime}<i$, $|F^{\prime}_{i}\cup
F^{\prime\prime}_{i}|\leq 4z$ and $i\leq c_{\mathsf{CMG}}\log n$, we get that
$|\hat{F}|\leq 4c_{\mathsf{CMG}}z\log\hat{n}$.

We also denote
$\hat{\mathcal{Q}}=\bigcup_{i^{\prime}=1}^{i-1}({\mathcal{Q}}^{\prime}_{i}\cup{\mathcal{Q}}^{\prime\prime}_{i})$.
Note that $\hat{\mathcal{Q}}$ defines an embedding of $X\setminus\hat{F}$ into
$H$. All paths in $\hat{\mathcal{Q}}$ have lengths at most
$8d^{\prime}\cdot(\log N)^{14}$. Each set
${\mathcal{Q}}^{\prime}_{i}\cup{\mathcal{Q}}^{\prime\prime}_{i}$ causes
congestion at most $2(\log N)^{10}$, and so the total congestion caused by the
paths in $\hat{\mathcal{Q}}$ is bounded by $\hat{\eta}=O\left((\log
N)^{11}\right)$. We now terminate the execution of the Cut-Matching Game.

As our next step, we will construct a set $F\subseteq E(X^{\prime})$ of fake
edges, and an embedding of the remaining edges of $X^{\prime}$ into $H$. The
latter is done by comining the embedding ${\mathcal{P}}$ of
$X^{\prime}\setminus F^{\prime}$ into $X$ with the embedding
$\hat{\mathcal{Q}}$ of $X\setminus\hat{F}$ into $H$.

#### Constructing the Set $F$ of Fake Edges for $X^{\prime}$ and Embedding
$X^{\prime}\setminus F$ into $H$

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

Once every edge of $X^{\prime}\setminus F^{\prime}$ is processed, we obtain a
final set $F$ of fake edges, and, for every remaining edge $e\in
E(X^{\prime})\setminus F$, a simple path $\hat{P}(e)$ of length
$O\left(d^{\prime}\cdot(\log N)^{16}\right)$, that serves as the embedding of
$e$ in $G$. Recall that $|V(X^{\prime})|\geq\hat{n}/4$, and graph $X^{\prime}$
is an $\alpha_{0}$-expander with maximum vertex degree at most $18$. Next, we
bound the congestion caused by the paths in set
${\mathcal{P}}^{*}=\left\\{\hat{P}(e)\mid e\in E(X^{\prime})\setminus
F\right\\}$ in $H$, and the cardinality of the set $F$ of fake edges.

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

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

Note that graph $X^{\prime}$ has all required properties, except that
$V(X^{\prime})$ may not contain all terminals. In our last step, we fix this
problem, by connecting the terminals that do not lie in $X^{\prime}$ to the
vertices of $X^{\prime}$.

#### Extending the Expander to All Terminals

Let $T_{0}\subseteq T$ be the set of terminals that lie in $X^{\prime}$, so
$|T_{0}|\geq\left\lceil\frac{|T|}{4}\right\rceil$. We partition the terminals
of $T\setminus T_{0}$ into three subsets $T_{1},T_{2},T_{3}$ arbitrarily, so
that every subset contains at most $\left\lceil\frac{|T|}{4}\right\rceil$
terminals. We now perform last three iterations, that we will denote by
iterations $(i+1),(i+2)$ and $(i+3)$. In each of these three iterations, we
will only invoke the algorithm of the Matching Player, in order to connect the
vertices in one of the subsets $T_{1},T_{2},T_{3}$ to $T_{0}$.

We now describe iteration $(i+1)$. The remaining two iterations are performed
similarly. We let $A^{\prime}_{i+1}$ be any subset of $T_{0}$ containing
exactly $\hat{\Delta}=\left\lceil\frac{|T|}{4}\right\rceil$ vertices. We also
let $B^{\prime}_{i+1}$ be any subset of $\hat{\Delta}$ terminals with
$T_{1}\subseteq B^{\prime}_{i+1}$, so that $A^{\prime}_{i+1}$ and
$B^{\prime}_{i+1}$ are disjoint. Next, we consider two instances of the
$r$-restricted $\mathsf{RouteAndCut}$ problem: instance
$(H,A_{i+1}^{\prime},B_{i+1}^{\prime},\hat{\Delta},\eta^{\prime},N^{\prime})$,
and instance
$(H,B_{i+1}^{\prime},A_{i+1}^{\prime},\hat{\Delta},\eta^{\prime},N^{\prime})$.
We apply Algorithm ${\mathcal{A}}$ to each of these two instances. As before,
if either of these algorithms returns “FAIL”, then we repeat it at most
$\left\lceil 10\log N\right\rceil$ times, or until it terminates with a valid
input – whatever happens first. If the algorithm returned “FAIL” in all
$\left\lceil 10\log N\right\rceil$ applications, then we terminate the current
algorithm with a “FAIL”. We assume from now on that in the last application of
algorithm ${\mathcal{A}}$ to both instances a valid output was computed, and
we denote by ${\mathcal{Q}}^{\prime}_{i+1}$ and
${\mathcal{Q}}^{\prime\prime}_{i+1}$ the routings that these algorithms
return, where ${\mathcal{Q}}^{\prime}_{i+1}$ is the routing from
$A^{\prime}_{i+1}$ to $B^{\prime}_{i+1}$.

If either of the sets
${\mathcal{Q}}^{\prime}_{i+1},{\mathcal{Q}}^{\prime\prime}_{i+1}$ of paths has
cardinality less than $\hat{\Delta}-z$, then we employ the same algorithm as
before to either compute a finalizing cut in $H$, or to compute a strongly
well-structured $1/d^{\prime}$-sparse cut $(A,B)$ in $G$ with
$w(A),w(B)\geq\frac{\hat{W}}{(\log N)^{30}}$. We then terminate the algorithm
and return the resulting cut. We assume from now on that
$|{\mathcal{Q}}^{\prime}_{i+1}|,|{\mathcal{Q}}^{\prime\prime}_{i+1}|\geq\hat{\Delta}-z$.
We use the set ${\mathcal{Q}}^{\prime}_{i+1}$ of paths as before (except that
we ingore those paths that terminate at vertices of $B^{\prime}_{i+1}\setminus
T_{1}$), in order to compute a matching $M^{\prime}_{i+1}\subseteq T_{0}\times
T_{1}$, with $|M^{\prime}_{i+1}|\geq|T_{1}|-2z$, together with an embedding of
the edges of $M^{\prime}_{i+1}$ into the graph $H$, via paths of lengths at
most $8d^{\prime}\cdot(\log N)^{14}$, that cause congestion at most
$O(\log^{10}N)$. We then add a collection $F^{\prime}_{i+1}$ of at most $2z$
fake edges to $M^{\prime}_{i+1}$ to turn it into a matching of cardinality
$|T_{1}|$. Similarly, we use the paths in
${\mathcal{Q}}^{\prime\prime}_{i+1}$, in order to compute a matching
$M^{\prime\prime}_{i+1}\subseteq T_{1}\times T_{0}$, with
$|M^{\prime\prime}_{i+1}|=|T_{1}|$, together with a subset
$F^{\prime\prime}_{i+1}\subseteq M^{\prime\prime}_{i+1}$ of at most $2z$ fake
edges, and an embedding of the edges of $M^{\prime\prime}_{i+1}\setminus
F^{\prime\prime}_{i+1}$ into the graph $H$, via paths of lengths at most
$8d^{\prime}\cdot(\log N)^{14}$, that cause congestion at most
$O(\log^{10}N)$. The remaining two iterations are executed similarly, except
that we use sets $T_{2}$ and $T_{3}$ of terminals instead of $T_{1}$.

Consider now the final graph $X^{*}$, that is obtained from $X^{\prime}$ by
adding the vertices of $T_{1}\cup T_{2}\cup T_{3}$ to it, and the edges of
${\mathcal{M}}^{*}=\bigcup_{j=1}^{3}(M^{\prime}_{i+j}\cup
M^{\prime\prime}_{i+j})$. Then $V(X^{*})=T$, maximum vertex degree in $X^{*}$
is at most $18+6=24$. Moreover, from 2.2, graph $X^{*}$ is an
$\frac{\alpha_{0}}{81}$-expander.

Recall that each of the sets
$\left\\{F^{\prime}_{i+j},F^{\prime\prime}_{i+j}\mid 1\leq j\leq 3\right\\}$
of fake edges has cardinality at most $2z\leq\frac{8|T|}{\log^{4}N}$. We add
the fake edges from all these sets to the set $F$ of fake edges. Since
initially $|F|\leq\frac{3\alpha_{0}\cdot|T|}{2000}$, and since the number of
edges that we added to $F$ in this step is bounded by
$\frac{100|T|}{\log^{4}N}$, we get that
$|F|\leq\frac{\alpha_{0}\cdot|T|}{500}$ holds. For every edge
$e\in{\mathcal{M}}^{*}\setminus F$, we have computed an embedding path
$\tilde{P}(e)$, that is added to the set ${\mathcal{P}}^{*}$ of paths. The
final set ${\mathcal{P}}^{*}$ of paths is an embedding of $X^{*}\setminus F$
into $H$, where the length of every path is $O\left(d^{\prime}\cdot(\log
N)^{15}\right)$, and the paths in ${\mathcal{P}}^{*}$ cause congestion
$O\left((\log N)^{16}\right)$.

#### Running Time and Failure Probability Analysis

The algorithm has $O(\log\hat{n})\leq O(\log N)$ iterations. The probability
that it returns “FAIL” in a single iteration is at most $\frac{2}{N^{10}}$,
and so the probability that the algorithm ever returns “FAIL” is at most
$\frac{1}{N^{9}}$.

the total time spent in a single iteration on the executions of Algorithm
${\mathcal{A}}$ is bounded by:

$O\left(c_{1}\cdot\hat{W}^{2}\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}(r-1)+8c_{2}+2}\right).$

Additionally, in every iteration we use the algorithm for the Cut Player from
Theorem 7.13, whose running time is $\widetilde{O}(\hat{W}^{2})$.

The algorithm from 7.15, whose running time is $O(\hat{W}^{2})$, may only be
incurred once over the course of the execution of our algorithm.

Additionally, when computing the embedding ${\mathcal{P}}^{*}$ of
$X^{*}\setminus F$ into $G$, we spend time at most
$O\left(d^{\prime}\cdot(\log N)^{16}\right)$ per edge of $X^{\prime}$, and,
since $|E(X^{\prime})|\leq O(\hat{W})$, the time required to compute the
embedding is bounded by: $O\left(\hat{W}\cdot d^{\prime}\cdot(\log
N)^{15}\right)\leq O\left(\hat{W}^{2}\right)$, since
$d^{\prime}\leq\frac{2d}{(\log N)^{28}}$ and $d\leq n$ from Inequality 15.
Overall, the running time of the algorithm is bounded by:

$\begin{split}&O\left(c_{1}\cdot\hat{W}^{2}\cdot 2^{c_{2}\sqrt{\log
N}}\cdot(\log N)^{16c_{2}(r-1)+8c_{2}+3}\right)+\tilde{O}(\hat{W}^{2})\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\leq
O\left(c_{1}\cdot\hat{W}^{2}\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}(r-1)+8c_{2}+3}\right).\end{split}$

####  7.4.2 Maintaining the Expander

At the beginning of the phase, we execute the algorithm from Lemma 7.11. If
the algorithm terminated with a “FAIL”, which may only happen with probability
at most $\frac{1}{N^{7}}$, then we terminate the algorithm for the current
phase and return “FAIL”. If the algorithm returned a finalizing cut in $H$,
then we apply the algorithm from 7.8 to this cut. If the algorithm from 7.8
estabishes that at least one of the events ${\cal{E}}_{2},{\cal{E}}_{3}$
happened, we terminate the phase with a “FAIL”. Otherwise, we obtain a
strongly well-structured $\varphi$-sparse cut $(A^{*},B^{*})$ in the current
graph $G$, such that $w(A^{*}),w(B^{*})\geq\frac{\hat{W}}{\log^{30}N}$. In
this case, we output the cut $(A^{*},B^{*})$. Once this cut is processed, at
least $\frac{\hat{W}}{\log^{30}N}$ vertices are deleted from $H$, and the
current phase terminates. Finally, if the algorithm from Lemma 7.11 returns a
strongly well-structured $1/d^{\prime}$-sparse cut $(A,B)$ in $G$ with
$w(A),w(B)\geq\frac{\hat{W}}{(\log N)^{30}}$, then as before we output this
cut, and, once it is processed, at least $\frac{\hat{W}}{\log^{30}N}$ vertices
are deleted from $H$, and the current phase terminates. Therefore, we assume
from now on that the algorithm from Lemma 7.11 computed a graph $X^{*}$, that
we will denote for simplicity by $X$ from now on. Recall that $V(X)=T$,
maximum vertex degree in $X$ is at most $24$, and $X$ is an
$\frac{\alpha_{0}}{81}$-expander. Recall that we are also given a set
$F\subseteq E(X)$ of at most $\frac{\alpha_{0}\cdot|T|}{500}$ fake edges, and
an embedding ${\mathcal{P}}^{*}$ of $X\setminus F$ into $H$. We let
$d^{\prime\prime}=\Theta\left(d^{\prime}\cdot(\log N)^{15}\right)$ and
$\eta^{\prime\prime}=\Theta\left((\log N)^{13}\right)$ be such that every path
in ${\mathcal{P}}^{*}$ has length at most $d^{\prime\prime}$, and the
congestion caused by the paths in ${\mathcal{P}}^{*}$ is at most
$\eta^{\prime\prime}$. For convenience, we will denote the set
${\mathcal{P}}^{*}$ of paths by ${\mathcal{Q}}$ from now on, and, for every
edge $\hat{e}\in E(X)\setminus F$, we denote by $Q(\hat{e})\in{\mathcal{Q}}$
its corresponding embedding path.

Recall that, since Event ${\cal{E}}_{1}$ did not happen, we are guaranteed
that $\frac{\hat{W}}{2d^{\prime}}\leq|T|\leq\frac{8\hat{W}}{d^{\prime}}$. As
the phase progresses, some vertices and edges may be deleted from $X$ and from
$G$. We will view the set $T$ of terminals as a static set, so even if some
vertices of $T$ are deleted from $X$ or from $G$, the set $T$ remains
unchanged.

Throughout the algorithm, for every edge $e\in E(H)$, we maintain a collection
$S^{\prime}(e)\subseteq E(X)$ of edges $\hat{e}\in E(X)\setminus F$, such that
$e\in Q(\hat{e})$. Clearly, the time required to compute these initial sets
$S^{\prime}(e)$ of edges, for all $e\in E(H)$, is subsumed by the time
required to compute the embedding of $X\setminus F$ into $H$. Additionally,
for every edge $\hat{e}\in E(X)\setminus F$, we maintain the length
$\hat{\ell}(\hat{e})$ of the path $Q(\hat{e})$, which is equal to the number
of edges on the path, and must initially be bounded by $d^{\prime\prime}$.

As the phase progresses, graph $H$ undergoes changes, that may require
updating the expander $X$ and its embedding. Specifically, we need to ensure
that, even as vertices and edges are deleted from $H$, $V(X)\subseteq V(H)$,
and, for every edge $\hat{e}\in E(X)\setminus F$, $Q(\hat{e})\subseteq H$
continue to hold. Additionally, as edges in $H$ undergo splitting, some of the
embedding paths in ${\mathcal{Q}}$ may become longer, and we may need to
delete the corresponding edges from $X$, in order to ensure that the lengths
of all embedding paths are suitably bounded. Lastly, we need to ensure that,
throughout the phase, for every pair $x,y\in V(X)$ of vertices, there is a
path connecting $x$ to $y$ in $X\setminus F$, whose length is at most $O(\log
N)$. Whenever our algorithm discovers that this is no longer the case, it may
compute a sparse cut $(A,B)$ in $X$, and delete the vertices of the smaller
side of the cut from $X$. We now describe all updates that graph $X$ undergoes
over the course of the phase formally. We will ensure that, despite these
updates, throughout the phase, $|V(X)|\geq|T|/2$ holds.

#### First Type of Updates: Due to Edge Splitting

Recall that, as the algorithm progresses, the lengths of some edges $e\in
E(G)$ may be doubled. Whenever this happens, we update the corresponding path
$P^{*}(e)$ in $H$, by splitting every special edge $e^{\prime}\in
E(P^{*}(e))$. The latter is done by replacing the special edge
$e^{\prime}=(x,y)$ with a path $(x,z,z^{\prime},y)$, where $z,z^{\prime}$ are
new vertices, and $(x,z)$, $(z^{\prime},y)$ are new special edges. Notice that
once edge $e^{\prime}$ is split, it no longer lies in graph $H$. For every
edge $\hat{e}\in E(X)\setminus F$ that lies in $S^{\prime}(e^{\prime})$, we
consider the corresponding embedding path $Q(\hat{e})$, that must contain the
edge $e^{\prime}$. We replace $e^{\prime}$ with the new path
$(x,z,z^{\prime},y)$ on $Q(\hat{e})$, and insert $\hat{e}$ into the sets
$S^{\prime}((x,z))$, $S^{\prime}((z^{\prime},y))$, that correspond to the new
special edges $(x,z)$ and $(z^{\prime},y)$. We also update the length
$\hat{\ell}(\hat{e})$ of path $Q(\hat{e})$, which increases by additive $2$.
If, as the result of this procedure, the length of path $Q(\hat{e})$ became
greater than $8d^{\prime\prime}$, then edge $\hat{e}$ is deleted from graph
$X$.

We denote by $\hat{E}_{1}$ the set of all edges that were deleted from graph
$X$ over the course of the phase due to this type of updates. We now show that
the number of such edges must be small.

######  Claim 7.16.

$|\hat{E}_{1}|\leq\frac{\alpha_{0}\cdot|T|}{5000}$.

###### Proof.

Recall that, over the course of the phase, the algorithm only needs to respond
to at most $\Delta^{\prime}$ queries. Given such a query between a pair
$(x,y)$ of vertices, the algorithm must return a path $P$ of length at most
$d$ connecting $x$ to $y$. Denote by $\tilde{\ell}(P)$ the length of the path
$P$ at the time when it was returned in response to the query. Then the
lengths of some edges on path $P$ are doubled. If ${\mathcal{P}}$ is the set
of all paths that the algorithm returned in response to queries over the
course of the phase, then
$\sum_{P\in{\mathcal{P}}}\tilde{\ell}(P)\leq\Delta^{\prime}\cdot d$ must hold.

Let $G_{0}$ denote the graph $G$ at the beginning of the phase. Recall that,
if $e$ is any edge of $G_{0}$, and $\tau,\tau^{\prime}$ are two consecutive
times during the current phase when the length of $e$ is doubled, then $e$
must have participated in at least $\eta$ paths that the algorithm returned
during the time interval $(\tau,\tau^{\prime}]$. However, the first time that
the length of $e$ is doubled during the current phase may occur even before it
participates in $\eta$ such paths. For every edge $e\in E(G_{0})$, denote by
$\tilde{\ell}^{0}(e)$ the length of $e$ at the beginning of the current phase.
If $e\in E(G)$ at the end of the phase, then we denote by
$\tilde{\ell}^{*}(e)$ the length of $e$ at the end of the phase; otherwise,
$\tilde{\ell}^{*}(e)$ is the length of $e$ just before it is deleted from $G$.

Let $E^{\prime}\subseteq E(G_{0})$ be the set of all edges $e$ with
$\tilde{\ell}^{*}(e)>2\tilde{\ell}^{0}(e)$, so $E^{\prime}$ contains all edges
of $G_{0}$ whose lengths were doubled at least twice. Consider now any edge
$e\in E^{\prime}$, and assume that $\tilde{\ell}^{*}(e)=2^{i}$. Let $\tau$ be
the time during the current phase when the length of $e$ was doubled from
$2^{i-2}$ to $2^{i-1}$, and let $\tau^{\prime}$ be the time when it was
doubled from $2^{i-1}$ to $2^{i}$. Then $e$ participated in at least $\eta$
paths that were returned by the algorithm in response to queries during the
time interval $(\tau,\tau^{\prime}]$. For each such path $P$, it contributed
$2^{i-1}=\frac{\tilde{\ell}^{*}(e)}{2}$ to $\tilde{\ell}(P)$. Therefore, every
edge $e\in E^{\prime}$ contributes at least
$\frac{\eta\cdot\tilde{\ell}^{*}(e)}{2}$ to
$\sum_{P\in{\mathcal{P}}}\tilde{\ell}(P)$. We conclude that $\sum_{e\in
E^{\prime}}\tilde{\ell}^{*}(e)\leq\frac{2}{\eta}\sum_{P\in{\mathcal{P}}}\tilde{\ell}(P)\leq\frac{2\Delta^{\prime}\cdot
d}{\eta}$.

Notice that, for every edge $e\in E(G)$, at any time during the execution of
the algorithm, the number of special edges on $P^{*}(e)$ is equal to the
current length of $e$, while the splitting of a speical edge on $P^{*}(e)$
increases the number of special edges on $P^{*}(e)$ by $1$. Therefore, if the
current length of $e$ is $\ell(e)$, then the edges of $P^{*}(e)$ underwent
$\ell(e)-\tilde{\ell}^{0}(e)$ splittings since the beginning of the algorithm.

Consider the graph $H$ at the beginning of the current phase, that we denote
by $H_{0}$. Note that, whenever a special edge $e\in E(H)$ undergoes a
splitting, the edge itself is deleted from $H$, and instead two new edges are
inserted. Consider now a special edge $e\in E(H)$, and suppose it underwent a
splitting at some time. We say that this splitting operation is _unimportant_
if $e\in E(H_{0})$, and we say that it is _important_ otherwise. Note that, if
an edge $e\in E(H)$ undergoes an important splitting update, then its parent-
edge must lie in $E^{\prime}$. Therefore, from the above discussion, the total
number of important splitting operations in graph $H$ is bounded by
$\sum_{e\in E^{\prime}}\tilde{\ell}^{*}(e)$.

Consider now some edge $\hat{e}\in E(X)\setminus F$, and its embedding path
$Q(\hat{e})$. Let $\mu(\hat{e})$ be the total number of important splitting
operations that the edges of path $Q(\hat{e})$ underwent over the course of
the algorithm. Since the embedding ${\mathcal{Q}}$ of $X\setminus F$ into $H$
causes congestion at most $\eta^{\prime\prime}$, we get that $\sum_{e\in
X\setminus F}\mu(\hat{e})\leq\eta^{\prime\prime}\cdot\sum_{e\in
E^{\prime}}\tilde{\ell}^{*}(e)\leq\frac{2\Delta^{\prime}\cdot
d\cdot\eta^{\prime\prime}}{\eta}$. On the other hand, if
$\hat{e}\in\hat{E}_{1}$, then the length of $Q(\hat{e})$ increased from
$d^{\prime\prime}$ to $8d^{\prime\prime}$ over the course of the algorithm,
and so the edges on $Q(\hat{e})$ must have undergone at least
$6d^{\prime\prime}$ important splitting operations so $\mu(\hat{e})\geq
6d^{\prime\prime}$. Therefore:

$|\hat{E}^{\prime}|\leq\frac{2\Delta^{\prime}\cdot
d\cdot\eta^{\prime\prime}}{6\eta d^{\prime\prime}}\leq
O\left(\frac{\Delta\cdot d}{\eta\cdot d^{\prime}\cdot(\log N)^{33}}\right)\leq
O\left(\frac{n}{d^{\prime}\cdot(\log N)^{33}}\right)\leq
O\left(\frac{\hat{W}}{d^{\prime}\cdot(\log
N)^{33}}\right)<\frac{\alpha_{0}\cdot|T|}{5000},$

since $d^{\prime\prime}=\Theta\left(d^{\prime}\cdot(\log N)^{16}\right)$,
$\Delta^{\prime}=\frac{\Delta}{(\log N)^{30}}$, and
$\eta^{\prime\prime}=\Theta\left((\log N)^{13}\right)$. We have also used the
fact that $\frac{\Delta\cdot d}{\eta}\leq n$ from the problem definition, that
$\hat{W}\geq\frac{n}{2}$, and that $|T|>\frac{8\hat{W}}{d^{\prime}}$, since
Event ${\cal{E}}_{1}$ did not happen.

#### Second Type of Updates: Due to Sparse Cuts in $X$

Throughout the execution of the phase, we may sometimes find cuts $(A,B)$ in
$X\setminus F$, with $|E_{X\setminus
F}(A,B)|\leq\frac{\alpha_{0}}{2^{20}}\cdot\min\left\\{|A|,|B|\right\\}$.
Denote $A$ and $B$ by $Z$ and $Z^{\prime}$, where $Z$ is the smaller of the
two sets, breaking ties arbitrarily. We then delete the vertices of $Z$ from
graph $X$. Notice that $|E_{X\setminus
F}(A,B)|\leq\frac{\alpha_{0}}{2^{20}}\cdot|Z|$. We _charge_ the vertices of
$Z$ for the edges of $E_{X\setminus F}(A,B)$, where each vertex $v\in Z$ is
charged $\frac{\alpha_{0}}{2^{20}}$ units, so the total charge is at least
$|E_{X\setminus F}(A,B)|$.

Let $\hat{E}_{2}$ be the set of edges in the initial graph $X$, that is
defined as follows. Initially, $\hat{E}_{2}=\emptyset$. Whenever our algorithm
computes a cut $(A,B)$ in $X\setminus F$, with $|E_{X\setminus
F}(A,B)|\leq\frac{\alpha_{0}}{2^{20}}\cdot\min\left\\{|A|,|B|\right\\}$, we
add the edges of $E_{X\setminus F}(A,B)$ to set $\hat{E}_{2}$. From the
charging scheme that we just described, it is easy to verify that, at the end
of the algorithm, $|\hat{E}_{2}|\leq\frac{\alpha_{0}\cdot|T|}{2^{20}}$ holds.

#### Third Type of Updates: Due to Sparse Cuts in $G$

Recall that our algorithm may, at any time, produce a strongly well-structured
$\varphi$-sparse cut $(A,B)$ in graph $G$. If $w(A)\leq W(B)$, then the
vertices of $A$ are deleted from $G$, and otherwise the vertices of $B$ are
deleted from $G$. Additionally, the endpoints of the edges of $E_{G}(A,B)$ are
also deleted from $G$, and graph $H$ is also updated with corresponding edge-
and vertex-deletions. This may require updating graph $X$, for example, if
some of the embedding paths in ${\mathcal{Q}}$ use vertices or edges that were
deleted from $H$. We emphasize that edges and vertices may only be deleted
from $G$ via this procedure, and the only other updates that graph $G$
undergoes is the doubling of the lengths of its edges.

Let $(A_{1},B_{1}),\ldots,(A_{q},B_{q})$ denote the sequence of all strongly
well-structured $\varphi$-sparse cuts in $G$ that our algorithm produced
during the current phase, indexed in the order in which the algorithm produced
them. If the last sparse cut that the algorithm produced caused the total
number of vertices that were deleted from $H$ over the course of the phase to
reach $\frac{\hat{W}}{\log^{30}N}$ (after which the current phase is
immediately terminated), then we do not include that cut in this sequence. For
all $1\leq i\leq q$, denote by $\tau_{i}$ the time when cut $(A_{i},B_{i})$
was produced, by $E_{i}=E_{G}(A_{i},B_{i})$ at time $\tau_{i}$, and by
$J_{i}\subseteq A_{i},J^{\prime}_{i}\subseteq B_{i}$ the vertices that serve
as endpoints of the edges in $E_{i}$ (with respect to $G^{(\tau_{i})}$ – graph
$G$ at time $\tau_{i}$). If $w(A_{i})\geq w(B_{i})$, then we denote
$Z_{i}=A_{i}\setminus J_{i}$, and otherwise we denote $Z_{i}=B_{i}\setminus
J^{\prime}_{i}$. We also let $\overline{Z}_{i}=V(G^{(\tau_{i})})\setminus
Z_{i}$ contain the remaining vertices of the current graph $G^{(\tau_{i})}$.
For convenience, if $Z_{i}=A_{i}\setminus J_{i}$, then we say that cut
$(A_{i},B_{i})$ is of _type 1_ , and otherwise we say that it is of _type 2_.

We denote by $G_{0}$ the graph $G$ at the beginning of the phase, and, for all
$1\leq i\leq q$, we denote by $G_{i}$ the graph $G$ that is obtained after cut
$(A_{i},B_{i})$ has been processed. Therefore, for all $1\leq i\leq q$, graph
$G_{i}$ is obtained from graph $G_{i-1}$ by deleting the vertices of
$\overline{Z}_{i}$ from it, or, equivalently, $G_{i}=G_{i-1}[Z_{i}]$.

We denote by $H_{0}$ the graph $H$ at the beginning of the current phase. For
all $1\leq i\leq q$, we denote by $H^{\prime}_{i}$ the graph $H$ just before
the cut $(A_{i},B_{i})$ is processed, and we denote by $H_{i}$ the graph $H$
immediately after cut $(A_{i},B_{i})$ is processed. Therefore, graph $H_{i}$
is obtained from $H^{\prime}_{i}$ by deleting from it all vertices and regular
edges that were deleted from $G_{i-1}$; additionally, for every special edge
$e$ that was deleted from $G_{i-1}$, all vertices and edges on the
corresponding path $P^{*}(e)$ are deleted from $H^{\prime}_{i}$. We denote
$V(H_{i})$ by $Z^{*}_{i}$, and we denote by
$\overline{Z}^{*}_{i}=V(H^{\prime}_{i})\setminus V(H_{i})$ the set of all
vertices that were deleted from $H^{\prime}_{i}$ when cut $(A_{i},B_{i})$ of
$G$ was processed.

We note that, in addition to the updates due to processing the cuts
$(A_{j},B_{j})$, the only other kind of updates that graph $H$ undergoes is
the splitting of some of its special edges, that happens whenever the length
of the corresponding parent-edge is doubled. Therefore, for all $1\leq i\leq
q$, graph $H^{\prime}_{i}$ can be obtained from $H_{i-1}$ by executing a
sequence of special edge splitting operations.

Consider some index $1\leq i\leq q$, and consider an edge $e=(x,y)\in E_{i}$.
Recall that this edge is represented by a path $P^{*}(e)$ in graph $H$.
Additionally, every regular edge $e^{\prime}$ that is incident to $x$ or $y$
in $G$ is present in graph $H$. We let $\Gamma(e)\subseteq E(H^{\prime}_{i})$
contain all regular edges that are incident to $x$ or $y$ in $H^{\prime}_{i}$,
and all edges of $P^{*}(e)$. We then set $\Gamma_{i}=\bigcup_{e\in
E_{i}}\Gamma(e)$. Notice that, if $(A_{i},B_{i})$ is a type-1 cut (so
$Z_{i}=A_{i}\setminus J_{i}$), then graph $H^{\prime}_{i}\setminus\Gamma_{i}$
contains no edge connecting a vertex of $Z^{*}_{i}$ to a vertex of
$\overline{Z}^{*}_{i}$. Similarly, if $(A_{i},B_{i})$ is a type-2 cut (so
$Z_{i}=B_{i}\setminus J^{\prime}_{i}$), the graph
$H^{\prime}_{i}\setminus\Gamma_{i}$ contains no edge connecting a vertex of
$\overline{Z}^{*}_{i}$ to a vertex of $Z^{*}_{i}$. Therefore, it may be
convenient to think of the update to graph $H^{\prime}_{i}$ due to the cut
$(A_{i},B_{i})$ in $G$ as follows: first, we delete the edges of $\Gamma_{i}$
from $H^{\prime}_{i}$. Then we obtain a sparsity-$0$ cut in the resulting
graph (with the cut being $(Z^{*}_{i},\overline{Z}^{*}_{i})$ if
$(A_{i},B_{i})$ is a type-1 cut, or $(\overline{Z}^{*}_{i},Z^{*}_{i})$
otherwise). After that we delete the vertices of one of the sides of the cut
(vertices of $\overline{Z}^{*}_{i}$) from the resulting graph, obtaining graph
$H_{i}$.

Before we describe the updates to the expander $X$, recall that $X$ undergoes
other types of updates, in which edges and vertices may be deleted from it.
But for the sake of analyzing the updates of type 3, it will be helpful for us
to ignore the other types of updates that expander $X$ undergoes. Therefore,
we denote the initial graph $X$ by $X_{0}$, and, for $1\leq i\leq q$, we
denote by $X_{i}$ the graph that is obtained from $X_{i-1}$ once the cut
$(A_{i},B_{i})$ is processed. Except for updating the graph $X$ while
processing the cuts $(A_{i},B_{i})$, we currently do not allow any other
updates to $X$. We will show how combine all types of updates to $X$ together
later.

Fix again an index $1\leq i\leq q$, and consider an edge $e=(x,y)\in E_{i}$.
Recall that we have defined a collection $\Gamma(e)$ of edges of
$H^{\prime}_{i}$, that includes all edges on the path $P^{*}(e)$, and all
regular edges that are incident to $x$ or to $y$ in $H^{\prime}_{i}$. We
define the corresponding subset $\hat{\Gamma}(e)$ of edges of
$X_{i-1}\setminus F$:
$\hat{\Gamma}(e)=\bigcup_{e^{\prime}\in\Gamma(e)}S^{\prime}(e^{\prime})$. In
other words, an edge $\hat{e}\in E(X_{i-1})\setminus F$ belongs to the set
$\hat{\Gamma}(e)$ if and only if its corresponding embedding path $Q(\hat{e})$
contains at least one edge of $\Gamma(e)$. We need the following simple
observation.

######  Observation 7.17.

For every edge $e=(x,y)\in E_{i}$, $|\hat{\Gamma}(e)|\leq
2\eta^{\prime\prime}$.

###### Proof.

Let $T(e)$ be the set of all terminals that lie on path $P^{*}(e)$. Since we
have assumed that Event ${\cal{E}}_{4}$ did not happen, $|T(e)|\leq 16\log N$.

We classify the edges in set $\hat{\Gamma}(e)$ into three different types, and
bound the number of edges of each type separately. Consider any edge
$\hat{e}\in\hat{\Gamma}(e)$.

We say that $\hat{e}$ is of type 1, if at least one of its endpoints lies on
$P^{*}(e)$. On this case, at least one endpoint of $\hat{e}$ belongs to set
$T(e)$. Since $|T(e)|\leq 16\log N$, and since the degree of every vertex in
$X$ is at most $24$, we get that the total number of type-1 edges in
$\hat{\Gamma}(e)$ is bounded by $O(\log N)\leq\eta^{\prime\prime}$.

We say that edge $\hat{e}$ is of type 2, if it is not of type 1, and,
additionally, its embedding path $Q(\hat{e})$ contains at least one edge of
$P^{*}(e)$. Since every inner vertex on $P^{*}(e)$ has in- and out-degree $1$,
and the endpoints of $\hat{e}$ do not lie on $P^{*}(e)$, it must be the case
that $P^{*}(e)\subseteq Q(\hat{e})$. Since the embedding of $X\setminus F$
into $H$ causes congestion at most $\eta^{\prime\prime}$, we get that the
total number of type-2 edges in $\hat{\Gamma}$ is bounded by
$\eta^{\prime\prime}$.

If edge $\hat{e}$ is not of the first two types, then we say that it is of
type 3. We claim that no type-3 edges may exist. Indeed, assume for
contradiction that some edge $\hat{e}\in\hat{\Gamma}(e)$ is of type $3$. Then
path $Q(\hat{e})$ must contain some regular edge $e^{\prime}$ of
$H^{\prime}_{i}$ that is incident to $x$ or $y$; assume w.l.o.g. that
$e^{\prime}$ is incident to $x$. However, $x$ is not an endpoint of $\hat{e}$,
and so it is not an endpoint of $Q(\hat{e})$. Since the only edge leaving $x$
in $G$ is $e$, path $Q(\hat{e})$ must contain the first edge on $P^{*}(e)$.
But then $\hat{e}$ must belong to one of the first two types, a contradiction.

Fix again an index $1\leq i\leq q$. We now define the set $\hat{\Gamma}_{i}$
of edges of $X_{i-1}\setminus F$, as follows: $\hat{\Gamma}_{i}=\bigcup_{e\in
E_{i}}\hat{\Gamma}(e)$. Note that, equivalently, $\hat{\Gamma}_{i}$ contains
all edges $\hat{e}$ of $X_{i-1}\setminus F$, whose embedding path $Q(\hat{e})$
contains at least one edge of $\Gamma_{i}$. Notice that, from 7.17,
$|\hat{\Gamma}_{i}|\leq 2|E_{i}|\cdot\eta^{\prime\prime}$. We denote
$\hat{E}_{3}=\bigcup_{i=1}^{q}\hat{\Gamma}_{i}$. We need the following simple
observation.

######  Observation 7.18.

$\sum_{i=1}^{q}|E_{i}|\leq\frac{\varphi\cdot\hat{W}}{\log^{30}N}$, and
$|\hat{E}_{3}|\leq\frac{\alpha_{0}\cdot|T|}{2^{20}}$.

###### Proof.

Fix an index $1\leq i\leq q$. Since cut $(A_{i},B_{i})$ is $\varphi$-sparse in
$G_{i-1}$, $|E_{i}|\leq\varphi\cdot\min\left\\{w(A_{i}),w(B_{i})\right\\}$.
Moreover, once cut $(A_{i},B_{i})$ is processed, the total weight of all
vertices in $G$ decreases by at least
$\min\left\\{w(A_{i}),w(B_{i})\right\\}\geq\frac{|E_{i}|}{\varphi}$, and so at
least $\frac{|E_{i}|}{\varphi}$ vertices are deleted from $H^{\prime}_{i}$ to
obtain $H_{i}$. Since we have assumed that, by the time that cut
$(A_{q},B_{q})$ has been processed, fewer than $\frac{\hat{W}}{\log^{30}N}$
vertices were deleted from $H$, we get that
${\sum_{i=1}^{q}|E_{i}|\leq\frac{\varphi\cdot\hat{W}}{\log^{30}N}}$.

From 7.17, for all $1\leq i\leq q$, $|\hat{\Gamma}_{i}|\leq
2|E_{i}|\cdot\eta^{\prime\prime}$. Therefore:

$|\hat{E}_{3}|=\sum_{i=1}^{q}|\hat{\Gamma}_{i}|\leq
2\eta^{\prime\prime}\cdot\sum_{i=1}^{q}|E_{i}|\leq\frac{2\varphi\cdot\eta^{\prime\prime}\cdot\hat{W}}{\log^{30}N}\leq
O\left(\frac{\hat{W}}{d^{\prime}\cdot\log^{17}N}\right)\leq\frac{\alpha_{0}\cdot\hat{W}}{2^{21}\cdot
d^{\prime}}\leq\frac{\alpha_{0}\cdot|T|}{2^{20}},$

since $\eta^{\prime\prime}=\Theta(\log^{13}N)$,
$\varphi=\frac{4}{d^{\prime}}$, and $N$ is large enough.

We are now ready to describe the type-3 updates to the expander $X$. Fix an
index $1\leq i\leq q$. In order to update expander $X_{i-1}$ following the cut
$(A_{i},B_{i})$ in graph $G_{i-1}$ that our algorithm produced, we start by
deleting the edges of $\hat{\Gamma}_{i}$ from $X_{i-1}$. For each such edge
$\hat{e}\in\hat{\Gamma}_{i}$, we consider every edge $e\in Q(\hat{e})$, and
update the set $S^{\prime}(e)$ of edges by deleting $\hat{e}$ from it. Next,
we denote $T_{i}=V(X_{i-1})\cap Z^{*}_{i}$, and
$\overline{T}_{i}=V(X_{i-1})\cap\overline{Z}_{i}^{*}$. If
$\overline{T}_{i}\neq\emptyset$, then we delete the vertices of
$\overline{T}_{i}$ from $X_{i-1}$, obtaining the final graph $X_{i}$. We now
discuss this latter update in more detail, presenting a slightly different
view of this update, that will be helpful for us later.

Assume first that $(A_{i},B_{i})$ in $G_{i-1}$ is a type-1 cut, so
$Z_{i}=A_{i}\setminus J_{i}$. As observed already, in this case, graph
$H^{\prime}_{i}\setminus\Gamma_{i}$ contains no edge connecting a vertex of
$Z^{*}_{i}$ to a vertex of $\overline{Z}^{*}_{i}$. It is then easy to verify
that graph $X_{i-1}\setminus\hat{\Gamma}_{i}$ contains no edge connecting a
vertex of $T_{i}$ to a vertex of $\overline{T}_{i}$. Indeed, if such an edge
$\hat{e}$ existed, then its corresponding path $Q(\hat{e})$ would connect a
vertex of $Z^{*}_{i}$ to a vertex of $\overline{Z}^{*}_{i}$ in
$H_{i}^{\prime}$, and so it must contain an edge of $\Gamma_{i}$. But then
$\hat{e}\in\hat{\Gamma}_{i}$ holds, a contradiction. Therefore, if
$(A_{i},B_{i})$ is a type-1 cut, and $T_{i},\overline{T}_{i}\neq\emptyset$,
then $(T_{i},\overline{T}_{i})$ is a cut of sparsity $0$ in
$X_{i-1}\setminus\hat{\Gamma}_{i}$.

Next, assume that $(A_{i},B_{i})$ is a type-2 cut. As observed already, in
this case, graph $H^{\prime}_{i}\setminus\Gamma_{i}$ contains no edge
connecting a vertex of $\overline{Z}^{*}_{i}$ to a vertex of $Z^{*}_{i}$. From
the same arguments as above, graph $X_{i-1}\setminus\hat{\Gamma}_{i}$ contains
no edge connecting a vertex of $\overline{T}_{i}$ to a vertex of
$\overline{T}_{i}$. Therefore, if $(A_{i},B_{i})$ is a type-2 cut, and
$T_{i},\overline{T}_{i}\neq\emptyset$, then $(\overline{T}_{i},T_{i})$ is a
cut of sparsity $0$ in $X_{i-1}\setminus\hat{\Gamma}_{i}$.

To conclude, we can view the update to graph $X_{i-1}$ as follows: first, we
delete all edges of $\hat{\Gamma}_{i}$ from $X_{i-1}$. Then we either delete
all vertices from $X_{i-1}$ (if $T_{i}=\emptyset$), or delete no vertices from
$X_{i-1}$ (if $\overline{T}_{i}=\emptyset$), or we obtain a sparsity-$0$ cut
in the resulting graph $X_{i-1}\setminus\hat{\Gamma}$, and we delete all
vertices on one side of this cut from $X_{i-1}$. This view of the update
procedure will be helpful for us later. It is easy to verify that, at the end
of this update, the collection
$\left\\{Q(\hat{e})\in{\mathcal{Q}}\mid\hat{e}\in E(X_{i})\setminus
F\right\\}$ defines a valid embedding of graph $X_{i}\setminus F$ into graph
$H_{i}$. Indeed, we have ensured that $T_{i}\subseteq V(H_{i})$. Additionally,
for every edge $\hat{e}\in E(X_{i})\setminus F$, both endpoints of $\hat{e}$
lie in set $Z^{*}_{i}$, and, since path $Q(\hat{e})$ is disjoint from the
edges of $\Gamma_{i}$, it may not use vertices of $\overline{Z}^{*}_{i}$, and
must therefore be contained in $H_{i}$.

Lastly, we would like to claim that $|V(X_{q})|$ remains sufficiently large
compared to $|T|=|V(X_{0})|$, but unfortunately this may not be the case.
Instead we will show that, if $1\leq i\leq q$ is the smallest index, for which
$|X_{i}|\leq|T|\cdot\left(1-\frac{8}{\log^{4}N}\right)$ holds, then we can
compute a finalizing cut in graph $G_{i-1}$. In our algorithm, we will monitor
the number of vertices in the current graph $X_{i}$, and, if it ever falls
below $|T|\cdot\left(1-\frac{8}{\log^{4}N}\right)$, we will compute a
finalizing cut, and apply the algorithm from 7.8 to it, after which the
current phase will be terminated, so in particular no further cuts
$(A_{j},B_{j})$ will be produced by the algorithm during the current phase.
Therefore, essentially we only need to consider the case where
$|V(X_{q-1})|\geq|T|\cdot\left(1-\frac{8}{\log^{4}N}\right)$ but
$|V(X_{q})|<|T|\cdot\left(1-\frac{8}{\log^{4}N}\right)$. The following claim
summarizes the algorithm that will allow us to complete the current phase in
such a case. For a vertex $v\in V(G_{0})$, we denote by $\hat{w}(v)$ its
weight at the beginning of current phase, and for a subset $S$ of vertices of
$G_{0}$, we denote by $\hat{w}(S)=\sum_{v\in S}\hat{w}(v)$.

######  Claim 7.19.

Suppose that $|V(X_{q-1})|\geq|T|\cdot\left(1-\frac{8}{\log^{4}N}\right)$ but
$|V(X_{q})|<|T|\cdot\left(1-\frac{8}{\log^{4}N}\right)$. Then there is a
deterministic algorithm, that, given graphs $G_{0},X_{0}$, and the sequence
$(A_{1},B_{1}),\ldots,(A_{q},B_{q})$ of cuts in $G$, and graph $H_{q-1}$,
computes a finalizing cut $(\tilde{A},\tilde{B})$ in $H_{q-1}$. The running
time of the algorithm is $O(\hat{W}^{2})$.

###### Proof.

For convenience, in this proof we denote graph $G_{q-1}$ by $G^{\prime}$ and
graph $H_{q-1}$ by $H^{\prime}$. We compute the finalizing cut
$(\tilde{A},\tilde{B})$ in $H^{\prime}$ as follows. First, for every vertex
$v\in V(G^{\prime})$, if $v\in A_{q}$, then we add $v$ to $\tilde{A}$, and
otherwise we add $v$ to $\tilde{B}$. Next, we consider every special edge
$e=(x,y)$ in $G^{\prime}$. If $x,y\in A_{q}$, then we add all inner vertices
on path $P^{*}(e)$ to $\tilde{A}$. If $x,y\in B_{q}$, then we add all inner
vertices on path $P^{*}(e)$ to $\tilde{B}$.

Next, we consider two cases. The first case happens if $(A_{q},B_{q})$ is a
type-1 cut, so $V(G_{q})=A_{q}\setminus J_{q}$. For each remaining special
edge (that must have first endpoint in $A_{q}$ and last endpoint in $B_{q}$),
we add all inner vertices of $P^{*}(e)$ to $\tilde{B}$.

Note that, for every special edge $e$ of $G^{\prime}$, the first and the last
edges on path $P^{*}(e)$ are special edges, so the resulting cut
$(\tilde{A},\tilde{B})$ in $H^{\prime}$ is weakly well-structured. Clearly:

$|E_{H^{\prime}}(\tilde{A},\tilde{B})|=|E_{G^{\prime}}(A_{q},B_{q})|\leq\varphi\cdot\min\left\\{w(A_{q}),w(B_{q})\right\\}\leq\frac{4}{d^{\prime}}\cdot\frac{\hat{W}}{\log^{30}N}\leq\frac{8|T|}{\log^{30}N},$

since $\varphi=\frac{4}{d^{\prime}}$. We have also used the fact that, since
the current phase has not terminated yet,
$w(A_{q}),w(B_{q})\leq\frac{\hat{W}}{\log^{30}N}$, and that, since Event
${\cal{E}}_{1}$ did not happen, $|T|\geq\frac{\hat{W}}{2d^{\prime}}$.

Notice that, from our construction, $\tilde{A}=V(H_{q})\cup J_{q}$. All
vertices of $\tilde{B}$ are deleted from $H^{\prime}$ when the cut
$(A_{q},B_{q})$ is processed, and, since the current phase did not terminate
yet, $|\tilde{B}|\leq\frac{\hat{W}}{\log^{30}N}$. Since
$\tilde{A}=V(H_{q})\cup J_{q}$, we get that $|\tilde{A}\cap
T|\leq|T_{q}|+|J_{q}|$. Recall that we have assumed that
$|T_{q}|=|V(X_{q})|<|T|\cdot\left(1-\frac{8}{\log^{4}N}\right)$. Additionally,
$|J_{q}|\leq|E_{G^{\prime}}(A_{q},B_{q})|\leq\frac{8|T|}{\log^{30}N}$.
Altogether, we conclude that $|\tilde{A}\cap
T|\leq|T|\cdot\left(1-\frac{7}{\log^{4}N}\right)$, and
$|\tilde{A}|\geq|V(H^{\prime})|-\frac{\hat{W}}{32}$. Therefore, cut
$(\tilde{A},\tilde{B})$ is a finalizing cut in graph $H^{\prime}$.

The case where $(A_{q},B_{q})$ is a type-2 cut is treated similarly, except
that now, for every special edge $e$ of $G^{\prime}$ whose endpoints belong to
different sets in $\left\\{A_{q},B_{q}\right\\}$, we place all inner vertices
of $P^{*}(e)$ in $\tilde{A}$. Using the same reasoning as before, all edges of
$E_{H^{\prime}}(\tilde{A},\tilde{B})$ are special edges, and
$|E_{H^{\prime}}(\tilde{A},\tilde{B})|\leq\frac{8|T|}{\log^{30}N}$ holds. Our
construction ensures that $\tilde{B}=V(H_{q})\cup J^{\prime}_{q}$. Using the
same argument as above, we conclude that $|\tilde{B}\cap
T|\leq|T_{q}|+|J^{\prime}_{q}|\leq|T_{q}|+|E_{H^{\prime}}(\tilde{A},\tilde{B})\leq|T|\cdot\left(1-\frac{7}{\log^{4}N}\right)$.
Similarly, $|\tilde{B}|\geq|V(H^{\prime})|-\frac{\hat{W}}{32}$, and so cut
$(\tilde{A},\tilde{B})$ is finalizing.

Whenever our algorithm computes a strongly well-structured $\varphi$-sparse
cut $(A_{i},B_{i})$ in the current graph $G$, we will first compute the
corresponding sets $E_{i}$, $\Gamma_{i}$, and $\hat{\Gamma}_{i}$ of edges,
together with the set $T_{i}$ of terminals, before applying any changes to
graphs $G$ and $H$. If
$|T_{i}|\geq|T|\cdot\left(1-\frac{8}{\log^{4}N}\right)$, then we proceed with
updating the graphs $G,H$ and $X$, as described above. But otherwise, we use
the algorithm from 7.19 in order to compute a finalizing cut
$(\tilde{A},\tilde{B})$ in the current graph $H$, and then employ the
algorithm from 7.8, that either correctly establishes that at least one of the
events ${\cal{E}}_{2},{\cal{E}}_{3}$ has happened (in which case we terminate
the phase with a “FAIL”), or computes a strongly well-structured
$\varphi$-sparse cut $(A^{*},B^{*})$ in the current graph $G$, such that
$w(A^{*}),w(B^{*})\geq\frac{\hat{W}}{\log^{30}N}$. In the latter case, we do
not process the cut $(A_{i},B_{i})$, but instead output the cut
$(A^{*},B^{*})$, and update both graphs $G$ and $H$ accordingly, following
which at least $\frac{\hat{W}}{\log^{30}N}$ vertices must be deleted from $H$,
and the current phase terminates.

#### Combining All Three Types of Updates

We now complete our description of the algorithm for maintaining the expander
$X$ and the embedding of $X\setminus F$ into $H$ throughout the phase. We will
also maintain another graph $X^{\prime}$. Initially, $X^{\prime}=X$. Whenever
a type-3 update $(A_{i},B_{i})$ occurs, we update the graph $X^{\prime}$ as
described above, but we will ignore type-1 and type-2 updates when maintaining
$X^{\prime}$. We will sometimes refer to $X^{\prime}$ as the “shadow
expander”, while we refer to $X$ as the “expander”, even though, as the
algorithm progresses, it is possible that both graphs stop being expanders.

In order to maintain the graph $X$, whenever a type-1 or a type-2 update
arrives, we process it exactly as describe above. Assume now that the $i$th
type-3 update $(A_{i},B_{i})$ arrives. In this case, we use graph $X^{\prime}$
in order to compute the set $\hat{\Gamma}_{i}$ of edges, and the partition
$(T_{i},\overline{T}_{i})$ of the vertices of $X^{\prime}$, as described
above, and we update graph $X^{\prime}$ accordingly. If, as the result,
$|V(X^{\prime})|$ falls below $|T|\cdot\left(1-\frac{8}{\log^{4}N}\right)$,
then we invoke the algorithm from 7.19, that computes a finalizing cut
$(\tilde{A},\tilde{B})$ in the current graph $H$. We then apply the algorithm
from 7.8 to the resulting cut. If the algorithm correctly estabishes that at
least one of the events ${\cal{E}}_{2},{\cal{E}}_{3}$ has happened, then we
terminate our algorithm and return “FAIL”. Otherwise, we obtain a strongly
well-structured $\varphi$-sparse cut $(A^{*},B^{*})$ in the current graph $G$,
such that $w(A^{*}),w(B^{*})\geq\frac{\hat{W}}{\log^{30}N}$. We output this
cut, and update the graphs $G$ and $H$ accordingly, following which at least
$\frac{\hat{W}}{\log^{30}N}$ vertices are deleted from $H$ and the current
phase terminates.

Assume now that
$|V(X^{\prime})|\geq|T|\cdot\left(1-\frac{8}{\log^{4}N}\right)$ continues to
hold after the current update. We then update graph $X$ as follows: we delete
the edges of $\hat{\Gamma}_{i}$, and the vertices of $\overline{T}_{i}$ from
it. This completes the description of the algorithm for maintaining graph $X$.
It is easy to verify that, at all times, $X\subseteq X^{\prime}$ holds.
Therefore, when the $i$th type-3 update is processed, immediately after the
edges of $\hat{\Gamma}_{i}$ are deleted from $X$, one of the cuts $(T_{i}\cap
V(X),\overline{T}_{i}\cap V(X))$, $(\overline{T}_{i}\cap V(X),T_{i}\cap V(X))$
must be a cut of sparsity $0$ in the resulting graph $X$.

Let $E^{*}=F\cup\hat{E}_{1}\cup\hat{E}_{2}\cup\hat{E}_{3}$. Recall that
$|F|\leq\frac{\alpha_{0}\cdot|T|}{500}$, and we have shown that
$|\hat{E}_{1}|\leq\frac{\alpha_{0}\cdot|T|}{5000}$ (in 7.16),
$|\hat{E}_{2}|\leq\frac{\alpha_{0}\cdot|T|}{2^{20}}$, and
$|\hat{E}_{3}|\leq\frac{\alpha_{0}\cdot|T|}{2^{20}}$ (in 7.18). Altogether, we
get that $|E^{*}|\leq\frac{\alpha_{0}\cdot|T|}{400}$ holds throughout the
phase. We now prove that, throughout the phase, $|V(X)|\geq|T|/2$ holds.

######  Claim 7.20.

Throughout the phase, $|V(X)|\geq|T|/2$.

###### Proof.

Assume otherwise. Consider the first time $\tau$ at which $|V(X)|<|T|/2$
holds. For convenience, we denote by $X_{0}$ the original graph $X$, which is
an $\alpha_{0}$-expander, with $|T|$ vertices and we denote by $\tilde{X}$ the
graph $X\setminus E^{*}$.

We construct the set ${\mathcal{Y}}$ of subsets of vertices of $X_{0}$, as
follows. Initially, ${\mathcal{Y}}=\emptyset$. Whenever a type-2 update
arrives, with a cut $(A,B)$ of the current graph $X$, if $|A|\leq|B|$, then we
add $A$ to ${\mathcal{Y}}$ (recall that in this case, the vertices of $A$ are
deleted from $X$); otherwise, we add $B$ to ${\mathcal{Y}}$. Clearly the
cardinality of the set that we just added to ${\mathcal{Y}}$ is bounded by
$|T|/2$. Moreover, since the edges of $E_{X}(A,B)$ belong to $E^{*}$, cut
$(A,B)$ has sparsity $0$ in $\tilde{X}$.

Assume now that a type-3 update arrives, and let $T^{\prime}$ denote the set
of vertices deleted from $X$ in the current iteration. We then add
$T^{\prime}$ to ${\mathcal{Y}}$. Since we did not terminate the current phase
after the current iteration,
$|V(X^{\prime})|\geq|T|\cdot\left(1-\frac{8}{\log^{4}N}\right)$ must currently
hold, and so $|T^{\prime}|\leq\frac{8|T|}{\log^{4}N}\leq\frac{|T|}{2}$ must
hold. Moreover, as we have shown, one of the cuts $(T^{\prime},V(X)\setminus
T^{\prime})$ or $(V(X)\setminus T^{\prime},T^{\prime})$ is a sparsity-$0$ cut
in graph $\tilde{X}$.

Let ${\mathcal{Y}}=(Y_{1},\ldots,Y_{q})$ be the final collection of vertex
subsets obtained after all updates that occured until time $\tau$ have been
processed, where the sets are indexed in the order in wich they were added to
${\mathcal{Y}}$. We also add the set $Y_{q+1}$ that contains all vertices that
lie in $X$ at time $\tau$ to ${\mathcal{Y}}$. From our assumption,
$|X|\leq|T|/2$, and so for all $1\leq q^{\prime}\leq q+1$,
$|Y_{q^{\prime}}|\leq|T|/2$.

For all $1\leq j\leq q$, let $Y^{\prime}_{j}=Y_{j+1}\cup\cdots\cup Y_{q}$. At
the time when $Y_{j}$ was added to ${\mathcal{Y}}$, it defined a cut of
sparsity $0$ in graph $\tilde{X}$. In other words, either
$E_{\tilde{X}}(Y_{j},Y^{\prime}_{j})=\emptyset$, or
$E_{\tilde{X}}(Y_{j},Y^{\prime}_{j})=\emptyset$. Let $\alpha$ be such that
$\max_{Y_{j}\in{\mathcal{Y}}}\left\\{|Y_{j}|\right\\}=\alpha\cdot|T|$. From
our discussion so far, $\alpha\leq\frac{1}{2}$. From 2.4, there is a cut
$(A,B)$ in $\tilde{X}$ with $|A|,|B|\geq|T|/4$, and
$E_{\tilde{X}}(A,B)=\emptyset$.

Observe that $|E_{X_{0}}(A,B)|\leq|E^{*}|\leq\frac{\alpha_{0}\cdot|T|}{400}$.
Since $|A|,|B|\geq\frac{|T|}{4}$, we obtain a cut $(A,B)$ in $X_{0}$, whose
sparsity is below $\alpha_{0}$, contradicting the fact that $X_{0}$ is an
$\alpha_{0}$-expander.

###  7.5 Second Data Structure: Connecting to the Vertices of $X$

At the beginning of the phase, we initialize the algorithm for the
$\mathsf{ConnectToCenters}$ problem from Theorem 6.7 on the current graph $G$,
with $\beta=V(X)$, parameters $d^{\prime}$ and $r$ remaining unchanged, and
parameter $N$ replaced by $N^{\prime}=8N$. We slightly modify the lengths of
the special edges: for each such edge $e\in E^{\mathsf{spec}}$, we define the
new length $\ell^{\prime}(e)=\max\left\\{\ell(e),2\ell^{0}(e)\right\\}$. We
define, for every vertex $v\in V(G)$, a weight $w^{\prime}(v)$ to be the
length $\ell^{\prime}(e)$ of the unique special edge $e$ incident to $v$, and
we let $W^{\prime}=\sum_{v\in V(G)}w^{\prime}(v)$. Clearly, $W^{\prime}\leq
2\hat{W}$. As the lengths of special edges in the original graph $G$ grow, we
always set, for every edge $e\in E(G)$, the length $\ell^{\prime}(e)$ that is
used by the algorithm for the $\mathsf{ConnectToCenters}$ problem to
$\ell^{\prime}(e)=\max\left\\{\ell(e),2\ell^{0}(e)\right\\}$, and we also
define the weights $w^{\prime}(v)$ of vertices $v\in V(G)$ with respect to
these edge lengths. Clearly, for all $e\in E^{\mathsf{spec}}$,
$\ell(e)\leq\ell^{\prime}(e)\leq 2\ell(e)$ and for all $v\in V(G)$, $w(v)\leq
w^{\prime}(v)\leq 2w(v)$ always hold. We use $W^{\prime}$ to denote the sum of
the initial weights $w^{\prime}(v)$ for $v\in V(G)$, so it does not change
over the course of the algorithm. Finally, the graphs $G$ and the
corresponding subdivided graph $H^{\prime}$ that serve as input to the
$\mathsf{ConnectToCenters}$ problem must be given in the adjacency-list
representation. We can compute both adjacency-list representations in time
$O(|V(H^{\prime})|^{2})\leq O((W^{\prime})^{2})\leq O((W^{0})^{2})$. We prove
that we obtain a valid input to the $\mathsf{ConnectToCenters}$ problem in the
following simple claim, whose proof deferred to Section D.5 of Appendix.

######  Claim 7.21.

$(G,\left\\{\ell^{\prime}(e)\right\\}_{e\in
E(G)},H^{\prime},N^{\prime},d^{\prime},r,\beta)$ is a valid input to the
$\mathsf{ConnectToCenters}$ problem.

As the algorithm progresses, we will ensure that $\beta=V(X)$ always holds.
Since, from 7.20, $|V(X)|\geq|T|/2$ holds throghout the phase, this will
ensure that at most half the vertices may be deleted from the initial set
$\beta$ over the course of the phase. From 7.2, $\sum_{e\in
E^{\mathsf{spec}}}\ell^{*}(e)\leq 2\sum_{e\in
E^{\mathsf{spec}}}\ell^{0}(e)+2n$. Therefore, the total increase in the
lengths $\ell^{\prime}(e)$ of edges $e\in E(G)$ over the course of the entire
algorithm is at most $2n\leq 8|V(G)|$, as required.

Consider the graph $H^{\prime}$, that is the subdivided graph corresponding to
$G$ and the lengths $\ell^{\prime}(e)$ of its edges, and recall that $H$ is
the subdivided graph corresponding to $G$ and the lengths $\ell(e)$ of its
edges. Recall that, for every edge $e\in E(G)$,
$\ell(e)\leq\ell^{\prime}(e)\leq 2\ell(e)$. Since the lengths of all special
edges are integral powers of $2$, for every special edge $e\in E(G)$, either
$\ell^{\prime}(e)=\ell(e)$ or $\ell^{\prime}(e)=2\ell(e)$ holds. Therefore,
graph $H^{\prime}$ can be obtained from graph $H$ as follows: for every edge
$e\in E^{\mathsf{spec}}$ with $\ell^{\prime}(e)=2\ell(e)$, we subdivide every
special edge $\hat{e}\in E(H)$ that lies on the path $P^{*}(e)$ representing
$e$ once, obtaining a path $\hat{P}(\hat{e})$ with $2$ special edges,
representing edge $\hat{e}$ in $H^{\prime}$. For all edges $\hat{e}\in
E(H^{\prime})\cap E(H)$, we let $\hat{P}(\hat{e})=(\hat{e})$.