T^{(j-1)}\setminus\hat{T}_{C_{j}}$ holds, so from Property (C5) of Procedure
$\mathsf{ProcCut}$, $\mbox{\sf dist}_{G_{j-1}}(t,t^{\prime})\geq 4d$. From the
fact that Invariant (I1) held at the beginning of the iteration, we then get
that $\mbox{\sf dist}_{G}(t,t^{\prime})\geq 4d$.

We conclude that at the end of iteration $j$, Properties (R1)–(R5), and
Invariants (I1) and (I2) continue to hold.

We terminate Procedure $\mathsf{ProcPartition}$ once Property (R6) holds.
Since, in every iteration, the number of vertices in the current graph $G_{j}$
decreases, we are guaranteed that the algorithm indeed terminates.

##### Running time analysis.

Recall that, from Lemma 3.7, the running time of Procedure $\mathsf{ProcCut}$
is bounded by $O(|E(C)|\cdot n^{64/\Delta})$, where $C$ is the cluster that
the procedure returns. Therefore, for all $j$, the running time of iteration
$j$ is at most $O(|E(C_{j})|\cdot n^{64/\Delta})$. The total running time of
the algorithm is then bounded by
$\sum_{C_{j}\in{\mathcal{C}}}O(|E(C_{j})|\cdot n^{64/\Delta})$. Since the
clusters in ${\mathcal{C}}$ are disjoint, we get that the total running time
of Procedure $\mathsf{ProcPartition}$ is bounded by $O(|E(G)|\cdot
n^{64/\Delta})$.

####  3.5.3 Procedure $\mathsf{ProcSeparate}$.

Lastly, we provide Procedure $\mathsf{ProcSeparate}$, whose input is similar
to that of Procedure $\mathsf{ProcPartition}$. The goal of the procedure is to
either produce two large subsets $T_{1},T_{2}$ of terminals that are
sufficiently far from each other in $G$, or to compute a single terminal $t\in
T$ with set $B_{G}(t,\Delta\cdot d)$ containing many terminals.

######  Lemma 3.10.

There is a deterministic algorithm, that we call $\mathsf{ProcSeparate}$,
whose input is an $n$-vertex graph $G$, a set $T\subseteq V(G)$ of $k$
vertices called terminals, distance parameters $d$ and $\Delta$, and an
additional parameter $0<\alpha\leq 1$. The algorithm either computes a
terminal $t\in T$ with $|B_{G}(t,\Delta\cdot d)\cap T|>\alpha k$, or it
computes two subsets $T_{1},T_{2}$ of terminals, with $|T_{1}|=|T_{2}|$, such
that $|T_{1}|\geq
k^{1-64/\Delta}\cdot\min\left\\{(1-\alpha),\frac{1}{3}\right\\}$, and for
every pair $t\in T_{1}$, $t^{\prime}\in T_{2}$ of terminals, $\mbox{\sf
dist}_{G}(t,t^{\prime})\geq d$. The running time of the algorithm is
$O(|E(G)|\cdot n^{64/\Delta})$.

###### Proof.

We use the following simple observation.

######  Observation 3.11.

There is a deterministic algorithm, that, given a collection
$\left\\{k_{1},k_{2},\ldots,k_{r}\right\\}$ of non-negative integers with
$\sum_{j=1}^{r}k_{j}=k$ and $\max_{j}\left\\{k_{j}\right\\}\leq\alpha k$,
computes a partition $(J_{1},J_{2})$ of the set
$J=\left\\{1,\ldots,r\right\\}$ of indices, such that $\sum_{j\in
J_{1}}k_{j},\sum_{j\in J_{2}}k_{j}\geq
k\cdot\min\left\\{(1-\alpha),1/3\right\\}$. The running time of the algorithm
is $O(r)$.

###### Proof.

Assume w.l.o.g. that $k_{1}=\max_{j}\left\\{k_{j}\right\\}$. Assume first that
$k_{1}\geq k/3$. In this case, we let $J_{1}=\left\\{k_{1}\right\\}$ and
$J_{2}=J\setminus J_{1}$. Clearly, $\sum_{j\in
J_{2}}k_{j}\geq\sum_{j=1}^{r}k_{j}-k_{1}\geq(1-\alpha)k$, while $\sum_{j\in
J_{1}}k_{j}\geq k/3$.

Assume now that $k_{1}<k/3$. In this case, we start with
$J_{1}=J_{2}=\emptyset$, and process the indices of $J$ one by one. When index
$j$ is processed, we add it to $J_{1}$ if $\sum_{j^{\prime}\in
J_{1}}k_{j^{\prime}}\leq\sum_{j^{\prime}\in J_{1}}k_{j^{\prime}}$ currently
holds, and we add it to $J_{2}$ otherwise. It is easy to verify that, at the
end of this algorithm, $|\sum_{j^{\prime}\in
J_{1}}k_{j^{\prime}}-\sum_{j^{\prime}\in
J_{2}}k_{j^{\prime}}|\leq\max_{j^{\prime}\in
J}\left\\{k_{j^{\prime}}\right\\}\leq k/3$. Therefore, $\sum_{j\in
J_{1}}k_{j},\sum_{j\in J_{2}}k_{j}\geq k/3$.

We are now ready to describe the algorithm for the proof of Lemma 3.10. We
start by applying Procedure $\mathsf{ProcPartition}$ from Lemma 3.9 to graph
$G$, the set $T$ of terminals, and parameters $d$ and $\Delta$. Let
$\left({\mathcal{C}}=\left\\{C_{1},\ldots,C_{r}\right\\},\left\\{t_{C_{j}}\right\\}_{j=1}^{r},\left\\{\hat{T}^{\prime}_{C_{j}}\right\\}_{j=1}^{r},\left\\{\hat{T}_{C_{j}}\right\\}_{j=1}^{r}\right)$
be the outcome of the procedure. For $1\leq j\leq r$, denote
$k_{j}=|\hat{T}_{j}|$. If there is a cluster $C_{j}\in{\mathcal{C}}$ with
$k_{j}>\alpha k$, then we return terminal $t_{C_{j}}$; from Property (R4),
$\hat{T}_{C_{j}}\subseteq B_{G}(t_{C_{j}},\Delta\cdot d)$, and so
$|B_{G}(t_{C},\Delta\cdot d)\cap T|\geq|\hat{T}_{C_{j}}|=k_{j}>\alpha k$ must
hold.

Assume now that, for all $1\leq j\leq r$, $k_{j}\leq\alpha k$. Using the
algorithm from 3.11, we compute a partition $(J_{1},J_{2})$ of the set
$J=\left\\{1,\ldots,r\right\\}$ of indices, such that $\sum_{j\in
J_{1}}k_{j},\sum_{j\in J_{2}}k_{j}\geq
k\cdot\min\left\\{(1-\alpha),1/3\right\\}$.

Denote $\hat{T}^{1}=\bigcup_{j\in J_{1}}\hat{T}_{C_{j}}$, and
$\hat{T}^{2}=\bigcup_{j\in J_{2}}\hat{T}_{C_{j}}$. Then
$|\hat{T}^{1}|,|\hat{T}^{2}|\geq k\cdot\min\left\\{(1-\alpha),1/3\right\\}$.
Lastly, we let $T_{1}=\bigcup_{j\in J_{1}}T^{\prime}_{C_{j}}$ and
$T_{2}=\bigcup_{j\in J_{2}}T^{\prime}_{C_{j}}$. From Property (R5) of
$\mathsf{ProcPartition}$, for every pair $t\in T_{1}$, $t^{\prime}\in T_{2}$
of terminals, $\mbox{\sf dist}_{G}(t,t^{\prime})\geq d$. From Property (R2),
$|T_{1}|\geq|\hat{T}^{1}|/k^{64/\Delta}$, and
$|T_{2}|\geq|\hat{T}^{2}|/k^{64/\Delta}$. We conclude that
$|T_{1}|,|T_{2}|\geq
k^{1-64/\Delta}\cdot\min\left\\{(1-\alpha),\frac{1}{3}\right\\}$. We discard
terminals from the larger of the sets $T_{1},T_{2}$ as needed, until the
cardinalities of both sets become equal.

The running time of the algorithm is dominated by the running time of the
algorithm from Lemma 3.9, and is bounded by $O(|E(G)|\cdot n^{64/\Delta})$.

###  3.6 Basic Path Peeling.

In this subsection we present an algorithm, that we refer to as
$\mathsf{ProcPathPeel}$. This is a simple greedy algorithm for connecting pre-
specified pairs of subsets of vertices to each other with short paths. Similar
algorithms were used numerous times before (see e.g. Lemma 6.2 in [CK19], as
well as [CS21, Chu21], and Theorems 3.2 and 3.8 in [CGL+20]).

The input to Procedure $\mathsf{ProcPathPeel}$ consists of a graph $G$,
collections $A_{1},B_{1},\ldots,A_{k},B_{k}$ of subsets of its vertices, and
parameters $d,\eta>0$. The output of the procedure is collections
${\mathcal{P}}_{1},{\mathcal{P}}_{2},\ldots,{\mathcal{P}}_{k}$ of paths in
graph $G$, for which the following properties hold:

  1. P1.

for all $1\leq i\leq k$, every path in ${\mathcal{P}}_{i}$ connects a vertex
of $A_{i}$ to a vertex of $B_{i}$, and the endpoints of all paths in
${\mathcal{P}}_{i}$ are distinct;

  2. P2.

every path in set ${\mathcal{P}}=\bigcup_{i=1}^{k}{\mathcal{P}}_{i}$ has
length at most $d$, and the paths in ${\mathcal{P}}$ cause congestion at most
$\eta$; and

  3. P3.

let $E^{\prime}$ be the set of all edges $e\in E(G)$, such that exactly $\eta$
paths of ${\mathcal{P}}$ use $e$. For all $1\leq i\leq k$, let
$A^{\prime}_{i}\subseteq A_{i}$, $B^{\prime}_{i}\subseteq B_{i}$ be the sets
of vertices that do not serve as endpoints of the paths in
${\mathcal{P}}_{i}$. Then for all $1\leq i\leq k$, $\mbox{\sf
dist}_{G\setminus E^{\prime}}(A^{\prime}_{i},B^{\prime}_{i})>d$.

We note that we allow a path of ${\mathcal{P}}_{i}$ to contain vertices of
$A_{i}\cup B_{i}$, and also vertices from other sets $A_{j}\cup B_{j}$ as
inner vertices. The following simple lemma summarizes our algorithm for
$\mathsf{ProcPathPeel}$.

######  Lemma 3.12.

There is a deterministic algorithm, called $\mathsf{ProcPathPeel}$, that,
given a graph $G$, collections $A_{1},B_{1},\ldots,A_{k},B_{k}$ of subsets of
its vertices, and parameters $d,\eta>0$, outputs sets
${\mathcal{P}}_{1},{\mathcal{P}}_{2},\ldots,{\mathcal{P}}_{k}$ of simple paths
in $G$, for which properties (P1) – (P3) hold. The running time of the
algorithm is $O(m\eta+mdk\log n)$, where $m=|E(G)|$ and $n=V(G)$.

###### Proof.

We use a simple greedy algorithm combined with the ES-Tree data structure. The
algorithm consists of $k$ phases, where for all $1\leq i\leq k$, we construct
the set ${\mathcal{P}}_{i}$ of paths in phase $i$. At the beginning of the
algorithm, we set, for all $1\leq i\leq k$, ${\mathcal{P}}_{i}=\emptyset$.
Throughout the algorithm, we maintain the set
${\mathcal{P}}=\bigcup_{i=1}^{k}{\mathcal{P}}_{i}$ of paths (that is set to
$\emptyset$ at the beginning), and, for every edge $e\in E(G)$, we maintain a
counter $n(e)$, whose value is equal to the number of paths in ${\mathcal{P}}$
containing $e$. At the beginning of the algorithm, we initialize $n(e)=0$ for
every edge $e$.

We now describe the execution of the $i$th phase, for some $1\leq i\leq k$. We
start by constructing a graph $G_{i}$. Initially, we let $G_{i}=G$. We then
delete from $G_{i}$ every edge $e\in E(G)$ with $n(e)=\eta$. Additionally, we
add a source vertex $s_{i}$ to $G_{i}$, that connects with an edge to every
vertex of $A_{i}$, and a destination vertex $t_{i}$, that connects with an
edge to every vertex of $B_{i}$. We also initialize an ES-Tree data structure
${\mathcal{T}}_{i}$ in graph $G_{i}$, with source vertex $s_{i}$, and distance
bound $d+2$.

We then perform iterations, as long as the distance between $s_{i}$ and
$t_{i}$ in ${\mathcal{T}}_{i}$ is bounded by $d+2$. In every iteration, we use
the ES-Tree data structure ${\mathcal{T}}_{i}$ to compute the shortest
$s_{i}$-$t_{i}$ path $P$ in the current graph $G_{i}$, whose length must be at
most $d+2$. We delete the first and the last edges of $P$, obtaining a path
$P^{\prime}$ of length at most $d$, that connects some vertex $x\in A_{i}$ to
some vertex $y\in B_{i}$. We add path $P^{\prime}$ to ${\mathcal{P}}_{i}$, and
increase the counter $n(e)$ for every edge $e\in E(P^{\prime})$. We then
update the current graph $G_{i}$, by deleting the edges $(s_{i},x),(y,t_{i})$
from it, as well as every edge $e$ whose counter $n(e)$ has reached $\eta$.
The ES-Tree data structure ${\mathcal{T}}_{i}$ is also updated with these
deletions. Once the ES-Tree data structure ${\mathcal{T}}_{i}$ reports that
the distance between $s_{i}$ and $t_{i}$ in the current graph $G_{i}$ is
greater than $d+2$, the phase terminates. This completes the description of a
phase, and of the algorithm.

From the description of the algorithm, it is immediate to verify that
properties (P1) and (P2) hold for the resulting sets
${\mathcal{P}}_{1},\ldots,{\mathcal{P}}_{k}$ of paths. Property (P3) is also
easy to establish. Indeed, assume for contradiction that, for some index
$1\leq i\leq k$, there is a path $P^{\prime}$ of length at most $d$,
connecting a vertex of $A^{\prime}_{i}$ to a vertex of $B^{\prime}_{i}$ in
graph $G\setminus E^{\prime}$. Then this path must have existed in graph
$G_{i}$ at the end of the $i$th phase, and so the phase should not have
terminated when it did.

Lastly, we bound the running time of the algorithm. Let $m=|E(G)|$. The time
that is required to maintain a single ES-Tree ${\mathcal{T}}_{i}$ is bounded
by $O(md\log n)$. Additionally, whenever a path $P$ is added to set
${\mathcal{P}}$, the algorithm spends $O(|E(P)|)$ time on processing this
path, and on increasing the counters $n(e)$ of edges $e\in E(G)$. Since the
counter of an edge may be increased at most $\eta$ times, the total running
time of the algorithm is bounded by $O(m\eta+mkd\log n)$.

##  4 The Distanced Matching Game

The goal of the Distanced Matching Game is to construct a well-connected
graph, that we define next.

######  Definition 4.1 (Well-connected graph).

Let $G=(V,E)$ be a graph, let $S(G)\subseteq V$ be a subset of its vertices
called _supported vertices_ , and let $\eta,D>0$ be parameters. We say that
graph $G$ is _$(\eta,D)$ -well-connected with respect to the set $S(G)$ of
supported vertices_ if, for every pair $A,B\subseteq S(G)$ of disjoint equal-
cardinality subsets of supported vertices, there is a collection
${\mathcal{P}}(A,B)$ of paths in graph $G$, routing every vertex of $A$ to a
distinct vertex of $B$ (that is, ${\mathcal{P}}(A,B)$ is a one-to-one routing
of $A$ to $B$), such that the paths in ${\mathcal{P}}(A,B)$ cause congestion
at most $\eta$, and the length of every path is at most $D$.

Unlike the Cut-Matching Game, whose goal is to construct an expander graph,
the goal of the Distanced Matching Game is to construct a graph that is
$(\eta,D)$-well-connected with respect to a set $S(G)$ of supported vertices;
typically, for an $n$-vertex graph $G$, we will require that $|S(G)|\geq
n-n^{1-\Theta(\epsilon)}$, $\eta\leq n^{O(\epsilon)}$, and
$D=2^{O(1/\epsilon)}$, for a given parameter $0<\epsilon<1$.

The main component of the Distanced Matching Game is a _distancing_ , that is
defined next. Distancings play a role similar to that of cuts in the Cut-
Matching Game.

######  Definition 4.2 (Distancing).

Let $G$ be an $n$-vertex graph, and let $0<\delta<1,d>0$ be parameters. A
$(\delta,d)$-distancing for $G$ is a triple $(A,B,E^{\prime})$, where $A,B$
are disjoint subsets of $V(G)$ of cardinality at least $n^{1-\delta}$ each,
with $|A|=|B|$, and $E^{\prime}\subseteq E(G)$ is a subset of edges of
cardinality at most $|A|/16$. We require that $\mbox{\sf dist}_{G\setminus
E^{\prime}}(A,B)\geq d$.

While the notion of distancing, to the best of our knowledge, was never
formally defined before, it is a well-known and widely used fact that one can
efficiently obtain a sparse cut in a graph from a distancing. The following
lemma, whose analogues have been widely used before, summarizes such an
algorithm. The proof uses standard ball-growing technique, and appears in
Section A of Appendix.

######  Lemma 4.1.

There is a deterministic algorithm, whose input consists of a connected graph
$G$ with $|V(G)|=n$ and $|E(G)|=m$, a parameter $0<\varphi<1/2$, and a
$(\delta,d)$-distancing $(X,Y,E^{\prime})$ in $G$, where $0<\delta<1$ is any
parameter, $d\geq(32\log m)/\varphi$, and $|E^{\prime}|\leq\varphi|X|/4$. The
algorithm computes a cut $(X^{\prime},Y^{\prime})$ in graph $G$, with
$X\subseteq X^{\prime}$ and $Y\subseteq Y^{\prime}$, such that
$|E_{G}(X^{\prime},Y^{\prime})|\leq\varphi\cdot\min\left\\{|E_{G}(X^{\prime})|,|E_{G}(Y^{\prime})|\right\\}$.
The running time of the algorithm is bounded by
$O(n+\min\left\\{|E_{G}(X^{\prime})|,|E_{G}(Y^{\prime})|\right\\})$.

We note that, if the maximum vertex degree in $G$ is bounded by $\Delta$, then
$|E_{G}(X^{\prime})|\leq\Delta\cdot|X^{\prime}|$, and similarly
$|E_{G}(Y^{\prime})|\leq\Delta\cdot|Y^{\prime}|$. Therefore, the algorithm
guarantees that
$|E_{G}(X^{\prime},Y^{\prime})|\leq\varphi\cdot\Delta\cdot\min\left\\{|X^{\prime}|,|Y^{\prime}|\right\\}$.

A Distanced Matching Game receives as input an integral parameter $n$, and two
other parameters $0<\delta<1$ and $d\geq 2^{4/\delta}$. The game is played
between a _distancing player_ and a _matching player_ , in iterations. Over
the course of the game, a graph $G$ is constructed. Initially, graph $G$
contains a set $V$ of $n$ vertices and no edges. In every iteration, some
edges are added to $G$.

The $i$th iteration is executed as follows. First, the distancing player
either computes a $(\delta,d)$-distancing $(A_{i},B_{i},E^{\prime}_{i})$ in
the current graph $G$, or returns “END”. If the distancing player returned
“END”, then the game terminates, and we say that the game lasted for $(i-1)$
iterations. Otherwise, the matching player computes a (possibly partial)
matching $M_{i}$ between vertices of $A_{i}$ and vertices of $B_{i}$, of
cardinality at least $|A_{i}|/8$. We require that $M_{i}$ does not contain
pairs $(u,v)$ of vertices for which edge $(u,v)\in E^{\prime}$. We note that
$M_{i}$ is not a subset of edges of $G$; it is just a collection of pairs of
vertices from $A_{i}\times B_{i}$, with every vertex of $A_{i}\cup B_{i}$
appearing in at most one pair in $M_{i}$. We add the edges of $M_{i}$ to graph
$G$, completing iteration $i$, and proceed to the next iteration.

We note that, once the current graph $G$ contains no $(\delta,d)$-distancing,
the game must terminate. From the above description, graph $G$ remains a
simple graph (that is, we never add parallel edges to it).

The main technical result of this section is the proof of Theorem 2.1, that
bounds the number of iterations in the Distanced Matching Game. We restate the
theorem here for convenience.

######  Theorem 4.2 (Restatement of Theorem 2.1).

Consider a Distanced Matching Game with parameters $n>0,0<\delta<1/4$ and $d$,
such that $d\geq 2^{4/\delta}$ and $n^{\delta}\geq\frac{2^{14}\log
n}{\delta^{2}}$. Then the number of iterations in the game is at most
$n^{8\delta}$.

We note that we do not currently know whether the bounds in this theorem are
tight, and in particular whether the requirement that $d\geq 2^{4/\delta}$ is
necessary. It would be interesting to establish whether a similar theorem can
be proved for values of $d$ that have a lower dependence on $1/\delta$.

We now turn to prove Theorem 4.2. We assume that the paramters $n,\delta$ and
$d$ are fixed. We let $V$ be a set of $n$ vertices, over which the game is
played.

Consider a Distanced Matching Game that lasts for $z$ iterations. We can
summarize the game via a _transcript_
$\mathbb{T}=\left((A_{1},B_{1},E_{1}^{\prime}),M_{1},\ldots,(A_{z},B_{z},E^{\prime}_{z}),M_{z}\right)$,
where for $1\leq i\leq z$, $(A_{i},B_{i},E_{i}^{\prime})$ is the distancing
computed by the distancing player, and $M_{i}$ is the matching returned by the
matching player in iteration $i$. For all $1\leq i\leq z$, we denote by
$G_{i}$ the graph obtained after $i$ iterations of the game, so $V(G_{i})=V$
and $E(G_{i})=\bigcup_{i^{\prime}=1}^{i}M_{i^{\prime}}$. We also let $G_{0}$
be the graph with $V(G_{0})=V$ and $E(G_{0})=\emptyset$.

Consider now any subset $I\subseteq\left\\{1,\ldots,z\right\\}$ of indices,
and assume that $I=\left\\{i_{1},i_{2},\ldots,i_{q}\right\\}$ with
$i_{1}<i_{2}<\cdots<i_{q}$. Consider now the following sequence, that,
intuitively corresponds to only executing the iterations of the Distanced
Matching Game whose indices lie in $I$:

$\mathbb{T}^{\prime}=\left((A_{i_{1}},B_{i_{1}},E_{i_{1}}^{\prime\prime}),M_{i_{1}},\ldots,(A_{i_{q}},B_{i_{q}},E^{\prime\prime}_{i_{q}}),M_{i_{q}}\right).$

Here for all $1\leq j\leq q$, $E^{\prime\prime}_{i_{j}}$ is defined to be
$E^{\prime}_{i_{j}}\cap\left(\bigcup_{j^{\prime}=1}^{j-1}M_{i_{j^{\prime}}}\right)$.

We claim that $\mathbb{T}^{\prime}$ is a valid transcript of a Distanced
Matching Game. In order to show this, for all $1\leq j\leq q$, let
$G^{\prime}_{j}$ be the graph obtained after $j$ iterations of the game, that
is, $V(G^{\prime}_{j})=V$, and
$E(G^{\prime}_{j})=\bigcup_{j^{\prime}=1}^{j}M_{i_{j^{\prime}}}$. We also let
$G_{0}^{\prime}$ be the graph containing the set $V$ of vertices and no edges.
It is enough to show that, for all $1\leq j\leq q$,
$(A_{i_{j}},B_{i_{j}},E_{i_{j}}^{\prime\prime})$ is a valid
$(\delta,d)$-distancing in graph $G^{\prime}_{j-1}$. We now prove that this is
indeed the case.

Since $(A_{i_{j}},B_{i_{j}},E_{i_{j}}^{\prime})$ is a valid
$(\delta,d)$-distancing in the graph $G_{i_{j}-1}$ obtained after $(i_{j}-1)$
iterations of the original Distanced Matching Game, it is enough to show that
there is no path of length less than $d$ connecting a vertex of $A_{i_{j}}$ to
a vertex of $B_{i_{j}}$ in graph $G^{\prime}_{i_{j-1}}\setminus
E^{\prime\prime}_{i_{j}}$. Assume for contradiction that such a path $P$
exists. Recall that $G^{\prime}_{i_{j-1}}\subseteq G_{i_{j}-1}$, and that
every edge $e\in E^{\prime}_{i_{j}}\cap E(G^{\prime}_{i_{j-1}})$ lies in
$E^{\prime\prime}_{i_{j}}$. Therefore, path $P$ also lies in graph
$G_{i_{j}-1}\setminus E_{i_{j}}^{\prime}$, contradicting the fact that
$(A_{i_{j}},B_{i_{j}},E_{i_{j}}^{\prime})$ is a valid $(\delta,d)$-distancing
in graph $G_{i_{j}-1}$. We conclude that
$(A_{i_{j}},B_{i_{j}},E_{i_{j}}^{\prime\prime})$ is a valid
$(\delta,d)$-distancing in graph $G^{\prime}_{j-1}$, and $\mathbb{T}^{\prime}$
is a valid transcript of a Distanced Matching Game.

To summarize, we can select a subset of iterations from the transcript of the
Distanced Matching Game, and obtain a valid transcript of a Distanced Matching
Game, induced by these iterations. We say that the Distanced Matching Game
associated with transcript $\mathbb{T}^{\prime}$ is _defined by the set $I$ of
indices_.

For the sake of the proof of Theorem 4.2, it would be convenient for us to
assume that the cardinalities of the matchings $M_{i}$ returned in every
iteration of the Distanced Matching Game are roughly the same. In order to do
so, we partition the set $I^{*}=\left\\{1,\ldots,z\right\\}$ of indices into
at most $r=\left\lceil 16\delta{\log n}\right\rceil$ subsets, as follows.
Recall that for all $1\leq i\leq z$, we are guaranteed that
$|M_{i}|\geq|A_{i}|/8\geq n^{1-\delta}/8$, and clearly $|M_{i}|\leq n$ must
hold. For all $1\leq j\leq r$, we let $I_{j}\subseteq I^{*}$ contain all
indices $i$, for which $\frac{n}{2^{j}}<|M_{i}|\leq\frac{n}{2^{j-1}}$.
Clearly, there must be an index $j$, such that
$|I_{j}|\geq\frac{z}{r}=\frac{z}{\left\lceil 16\delta\log n\right\rceil}$.
From now on we will focus on the Distanced Matching Game that is defined by
the set $I_{j}$ of indices, and we will bound the number of iterations in this
game, that we denote by $z^{\prime}\geq\frac{z}{\left\lceil 16\delta\log
n\right\rceil}$. For simplicity of notation, for all $1\leq i\leq z^{\prime}$,
we denote the distancing associated with the $i$th iteration of the game by
$(A_{i},B_{i},E^{\prime}_{i})$ and the matching associated with iteration $i$
by $M_{i}$. As before, we denote by $G_{0}$ the graph whose vertex set is $V$
and edge set is empty, and for $1\leq i\leq z^{\prime}$, we let $G_{i}$ be the
graph obtained after $i$ iterations of the game, that is, $V(G_{i})=V$ and
$E(G_{i})=M_{1}\cup\cdots\cup M_{i}$. We also denote
$I=\left\\{1,\ldots,z^{\prime}\right\\}$ and $G=G_{z^{\prime}}$.

Let $E^{*}=\bigcup_{i=1}^{z^{\prime}}E^{\prime}_{i}$, and for all $1\leq i\leq
z^{\prime}$, let $M^{\prime}_{i}=M_{i}\setminus E^{*}$. We also denote
$H_{0}=G_{0}$, and for all $1\leq i\leq z^{\prime}$, we let $H_{i}$ be a graph
whose vertex set is $V$, and edge set is $E(G_{i})\setminus
E^{*}=\bigcup_{i^{\prime}=1}^{i}M^{\prime}_{i^{\prime}}$. We also denote
$H=H_{z^{\prime}}$. The following observation is immediate from the
definitions.

######  Observation 4.3.

For all $1\leq i\leq z^{\prime}$, $(A_{i},B_{i},\emptyset)$ is a
$(\delta,d)$-distancing in graph $H_{i}$; in other words, there is no path of
length less than $d$ connecting $A_{i}$ to $B_{i}$ in $H_{i}$.

Note that:

$|E(H)|=|E(G)\setminus
E^{*}|=\sum_{i=1}^{z^{\prime}}|M_{i}|-\sum_{i=1}^{z^{\prime}}|E^{\prime}_{i}|\geq\sum_{i=1}^{z^{\prime}}(|M_{i}|-|E^{\prime}_{i}|)\geq\sum_{i=1}^{z^{\prime}}\frac{|M_{i}|}{2}\geq\frac{|E(G)|}{2}.$
(1)

We have used the fact that, from the definition of the Distanced Matching
Game, for all $i$, $|M_{i}|\geq|A_{i}|/8$, while
$|E^{\prime}_{i}|\leq|A_{i}|/16$, so $|E^{\prime}_{i}|\leq|M_{i}|/2$ must
hold.

We say that an iteration $i\in I$ is _bad_ if $|M^{\prime}_{i}|<|M_{i}|/16$;
otherwise, iteration $i$ is good. We let $I^{b}\subseteq I$ be the set of all
indices $i$, such that the $i$th iteration is bad, and we let
$I^{g}=I\setminus I^{b}$ be the set of all indices of good iterations. We use
the following simple observation.

######  Observation 4.4.

$|I^{b}|\leq 7z^{\prime}/8$.

###### Proof.

Denote $\frac{|I^{b}|}{z^{\prime}}=\beta$, and assume for contradiction that
$\beta>7/8$. Recall that, for all $i\in I$,
$\frac{n}{2^{j}}<|M_{i}|\leq\frac{n}{2^{j-1}}$. Therefore:

$\begin{split}|E(H)|&=\sum_{i\in I^{b}}|M^{\prime}_{i}|+\sum_{i\in
I^{g}}|M^{\prime}_{i}|\\\ &\leq\beta\cdot z^{\prime}\cdot\frac{n}{16\cdot
2^{j-1}}+(1-\beta)\cdot z^{\prime}\cdot\frac{n}{2^{j-1}}\\\
&=\frac{2z^{\prime}n}{2^{j}}-\frac{\beta
z^{\prime}n}{2^{j}}\cdot\frac{15}{8}\\\
&\leq\frac{2z^{\prime}n}{2^{j}}-\frac{z^{\prime}n}{2^{j}}\cdot\frac{7}{8}\cdot\frac{15}{8}\\\
&\leq\frac{23}{64}\cdot\frac{z^{\prime}n}{2^{j}}\\\
&<\frac{z^{\prime}n}{2^{j+1}}.\end{split}$

On the other hand, from Equation 1:

$|E(H)|\geq\sum_{i=1}^{z^{\prime}}\frac{|M_{i}|}{2}\geq\frac{z^{\prime}n}{2^{j+1}},$

a contradiction. We conclude that $\beta\leq 7z^{\prime}/8$ holds.

To summarize, so far we have shown that:

$|I^{g}|\geq\frac{z^{\prime}}{8}\geq\frac{z}{256\delta\log n}.$ (2)

In order to bound $z$, it is now enough to bound the number of good iterations
in the game. In order to do so, we partition the game into _phases_ , each of
which (except for, possibly, the last one), contains exactly $\left\lceil
n^{4\delta}\right\rceil$ good iterations. It is now enough to prove the
following lemma.

######  Lemma 4.5.

The number of phases is bounded by $\frac{2n^{2\delta}}{\delta}$.

Indeed, assume that Lemma 4.5 holds. Then
$|I_{g}|\leq\frac{2n^{2\delta}}{\delta}\cdot\left\lceil
n^{4\delta}\right\rceil\leq\frac{4n^{6\delta}}{\delta}$, and, from Equation 2,
we get that:

$z\leq|I^{g}|\cdot 256\delta\log n\leq 1024n^{6\delta}\log n\leq n^{7\delta},$

since $n^{\delta}\geq 1024\log n$.

In order to complete the proof of Theorem 4.2, it is now enough to prove Lemma
4.5, which we do next. We denote the number of phases in the game by
$\hat{z}$.

For every integer $1\leq k\leq\hat{z}$, we denote by $\hat{H}^{(k)}$ the graph
$H$ at the beginning of the $k$th phase. In other words, if the last iteration
of phase $(k-1)$ is $i$, then $\hat{H}^{(k)}=H_{i}$. We will define, for every
phase $k$, a collection ${\mathcal{C}}^{(k)}$ of disjoint subgraphs of
$H^{(k)}$, that we refer to as _clusters_ ; we also refer to
${\mathcal{C}}^{(k)}$ as a _clustering_ of graph $H^{(k)}$. For all integers
$1\leq s\leq\left\lceil 1/\delta\right\rceil$, we let
${\mathcal{C}}^{(k)}_{s}\subseteq{\mathcal{C}}^{(k)}$ be the set of all
clusters $C\in{\mathcal{C}}^{(k)}$, with $n^{(s-1)\delta}<|V(C)|\leq
n^{s\delta}$, and let ${\mathcal{C}}^{(k)}_{0}\subseteq{\mathcal{C}}^{(k)}$ be
the set of all clusters $C$ containing a single vertex. For $0\leq
s\leq\left\lceil 1/\delta\right\rceil$, we say that a cluster
$C\in{\mathcal{C}}^{(k)}_{s}$ _lies at level $s$ of the clustering
${\mathcal{C}}^{(k)}$_. If cluster $C$ lies at level $s$ of
${\mathcal{C}}^{(k)}$, then we say that every vertex of $C$ lies at level $s$
of ${\mathcal{C}}^{(k)}$.

We will ensure that the following invariants hold for every integer $1\leq
k\leq\hat{z}$:

  1. I1.

$V=\bigcup_{C\in{\mathcal{C}}^{(k)}}V(C)$;

  2. I2.

for all $0\leq s\leq\left\lceil 1/\delta\right\rceil$, if
$C\in{\mathcal{C}}^{(k)}_{s}$ is a level-$s$ cluster of ${\mathcal{C}}^{(k)}$,
then for every pair $x,y\in V(C)$ of vertices, $\mbox{\sf dist}_{C}(x,y)\leq
4^{s}$ (and in particular $\mbox{\sf dist}_{C}(x,y)<d$ must hold, as $d\geq
2^{4/\delta}$); and

  3. I3.

if $C$ is a cluster of ${\mathcal{C}}^{(k)}$, and $C^{\prime}$ is a cluster of
${\mathcal{C}}^{(k+1)}$, then either $V(C)\cap V(C^{\prime})=\emptyset$, or
$C\subseteq C^{\prime}$.

Note that Invariant I3 ensures that, if $C^{\prime}$ is a cluster of
${\mathcal{C}}^{(k+1)}$, then either $C^{\prime}$ is a cluster of
${\mathcal{C}}^{(k)}$, or $C^{\prime}$ is obtained by taking the union of
several clusters of ${\mathcal{C}}^{(k)}$, and possibly adding some edges to
the resulting graph. In particular, the level of any given vertex $v\in V$ may
only grow from phase to phase. Consider now some vertex $v\in V$. If vertex
$v$ lies at level $s$ of ${\mathcal{C}}^{(k)}$, and at level $s^{\prime}>s$ of
${\mathcal{C}}^{(k+1)}$, then we say that vertex $v$ was _promoted_ by
${\mathcal{C}}^{(k+1)}$, or that it is promoted during phase $k$.

Initially, we let ${\mathcal{C}}^{(1)}$ contain, for every vertex $v\in V$, a
separate cluster $C(v)$, consisting of only vertex $v$ iteslf, so
${\mathcal{C}}^{(1)}=\left\\{C(v)\mid v\in V\right\\}$. Therefore, every
vertex lies at level $0$ of ${\mathcal{C}}^{(1)}$. Clearly, as the algorithm
progresses, the level of a vertex may be at most $\left\lceil
1/\delta\right\rceil$. The key in bounding the number of phases is to show
that the clusterings ${\mathcal{C}}^{(k)}$ can be constructed so that a large
number of vertices are promoted in every phase. Since every vertex may only be
promoted at most $\left\lceil 1/\delta\right\rceil$ times, this will be
sufficient in order to bound the number of phases. In order to complete the
proof of Lemma 4.5, it is enough to prove the following claim.

######  Claim 4.6.

Consider some integer $k\geq 1$, such that phase $k$ is not the last phase,
and assume that we are given a clustering ${\mathcal{C}}^{(k)}$ of graph
$\hat{H}^{(k)}$, for which Invariants I1 and I2 hold. Then there is a
clustering ${\mathcal{C}}^{(k+1)}$ of graph $\hat{H}^{(k+1)}$, for which
Invariants I1 and I2 hold. Additionally, for every pair
$C\in{\mathcal{C}}^{(k)}$, $C^{\prime}\in{\mathcal{C}}^{(k+1)}$ of clusters,
either $V(C)\cap V(C^{\prime})=\emptyset$ or $C\subseteq C^{\prime}$ hold.
Lastly, the number of vertices that are promoted in ${\mathcal{C}}^{(k+1)}$ is
at least $n^{1-2\delta}$.

Note that Lemma 4.5 follows immediately from 4.6. Since every vertex may be
promoted at most $\left\lceil 1/\delta\right\rceil$ times, and every phase
promotes at least $n^{1-2\delta}$ vertices, the total number of phases must be
bounded by $\frac{n\cdot\left\lceil
1/\delta\right\rceil}{n^{1-2\delta}}\leq\frac{2n^{2\delta}}{\delta}$. We now
prove 4.6.

Proof of 4.6. Let $I_{k}\subseteq I$ be the collection of indices $i\in I$,
such that iteration $i$ belongs to phase $k$, and let
$I^{\prime}_{k}=I_{k}\cap I^{g}$ be the set of indices corresponding to good
iterations of phase $k$. Recall that $|I^{\prime}_{k}|=\left\lceil
n^{4\delta}\right\rceil$. We will use the following simple observation.

######  Observation 4.7.

Consider an iteration $i\in I_{k}$, and the corresponding distancing
$(A_{i},B_{i},E^{\prime}_{i})$. Then for every cluster
$C\in{\mathcal{C}}^{(k)}$, either $A_{i}\cap V(C)=\emptyset$, or $B_{i}\cap
V(C)=\emptyset$. Moreover, if there is a pair
$C,C^{\prime}\in{\mathcal{C}}^{(k)}$ of clusters, such that some edge $e\in
M^{\prime}_{i}$ connects a vertex of $C$ to a vertex of $C^{\prime}$, then for
every subsequent iteration $i^{\prime}>i$, either $A_{i^{\prime}}\cap(V(C)\cup
V(C^{\prime}))=\emptyset$, or $B_{i^{\prime}}\cap(V(C)\cup
V(C^{\prime}))=\emptyset$ must hold.

###### Proof.

We fix an index $i\in I_{k}$, and consider the corresponding distancing
$(A_{i},B_{i},E^{\prime}_{i})$. From 4.3, $(A_{i},B_{i},\emptyset)$ is a
$(\delta,d)$-distancing in graph $H_{i}$. Therefore, if $P$ is any path in
$H_{i}$ connecting a vertex of $A_{i}$ to a vertex of $B_{i}$, then the length
of $P$ is at least $d$. Consider now some cluster $C\in{\mathcal{C}}^{(k)}$,
and assume that $C\in{\mathcal{C}}^{(k)}_{s}$, for some $0\leq
s\leq\left\lceil 1/\delta\right\rceil$. Assume for contradiction that there is
a pair $u,v\in V(C)$ of vertices, with $u\in A_{i}$ and $v\in B_{i}$. From
Invariant I2, $\mbox{\sf dist}_{C}(u,v)\leq 4^{s}\leq 4^{\left\lceil
1/\delta\right\rceil}<d$ (since $d\geq 2^{4/\delta}$). Since
$C\subseteq\hat{H}^{(k)}\subseteq H_{i}$, this is a contradiction.

Assume now that there is a pair $C,C^{\prime}\in{\mathcal{C}}^{(k)}$ of
clusters, such that some edge $e\in M^{\prime}_{i}$ connects a vertex of $C$
to a vertex of $C^{\prime}$. Using the same reasoning as above, and since edge
$e$ is added to graph $H_{i+1}$, we get that, for every pair $u\in V(C),v\in
V(C^{\prime})$ of vertices, $\mbox{\sf dist}_{H_{i+1}}(u,v)\leq 1+2\cdot
4^{\left\lceil 1/\delta\right\rceil}<d$. Therefore, for all $i^{\prime}>i$,
$\mbox{\sf dist}_{H_{i^{\prime}}}(u,v)<d$ holds as well. Since, from 4.3,
$(A_{i^{\prime}},B_{i^{\prime}},\emptyset)$ is a $(\delta,d)$-distancing in
graph $H_{i^{\prime}}$, we conclude that at most one of the sets
$A_{i^{\prime}},B_{i^{\prime}}$ may contain a vertex of $V(C)\cup
V(C^{\prime})$.

In the remainder of the proof of 4.6, we consider good iterations $i\in
I^{\prime}_{k}$. For each such iteration $i$, we will select a large enough
subset $M^{\prime\prime}_{i}\subseteq M^{\prime}_{i}$ of edges, and integers
$0\leq s^{\prime},s\leq\left\lceil 1/\delta\right\rceil$, so that every edge
in $M^{\prime\prime}_{i}$ connects a vertex of
$\bigcup_{C\in{\mathcal{C}}^{(k)}_{s}}V(C)$ to a vertex of
$\bigcup_{C^{\prime}\in{\mathcal{C}}^{(k)}_{s^{\prime}}}V(C^{\prime})$. We
then say that iteration $i$ _belongs to class $(s,s^{\prime})$_. Since the
number of possible classes is small, we can find a class $(s,s^{\prime})$ to
which many iterations of $I^{\prime}_{k}$ belong. Assume w.l.o.g. that $s\geq
s^{\prime}$. We will then use the iterations of $I^{\prime}_{k}$ from class
$(s,s^{\prime})$ in order to identify a large number of level-$s$ clusters
that can be merged together, so that, on the one hand, Invariants I1 and I2
continue to hold, while, on the other hand, a large number of vertices are
promoted. The remainder of the proof of 4.6 consists of three steps. In the
first step, we define a subset $M^{\prime\prime}_{i}\subseteq M^{\prime}_{i}$
of edges for each iteration $i\in I^{\prime}_{k}$, and classify the iteration
into some class $(s,s^{\prime})$. Then in the second step we define a new
contracted graph $J$, representing the clusters of
${\mathcal{C}}^{(k)}_{s}\cup{\mathcal{C}}^{(k)}_{s^{\prime}}$, where
$(s,s^{\prime})$ is the most common class among the iterations of
$I_{k}^{\prime}$. Graph $J$ is then used in Step 3 in order to define the new
clustering ${\mathcal{C}}^{(k+1)}$. We now present each of the three steps in
turn.

##### Step 1: Iteration Classification.

Consider an iteration $i\in I^{\prime}_{k}$. Since iteration $i$ is good,
$|M^{\prime}_{i}|\geq\frac{|M_{i}|}{16}\geq\frac{|A_{i}|}{128}\geq\frac{n^{1-\delta}}{128}$.
Consider now an edge $e=(u,v)\in M^{\prime}_{i}$, with $u\in A_{i},v\in
B_{i}$. From Invariant I1, there must be clusters
$C,C^{\prime}\in{\mathcal{C}}^{(k)}$ with $u\in V(C)$ and $v\in
V(C^{\prime})$. Moreover, from 4.7, $C\neq C^{\prime}$ must hold. We say that
edge $e$ is of type $(s,s^{\prime})$, for a pair $0\leq
s,s^{\prime}\leq\left\lceil 1/\delta\right\rceil$ of indices, if
$C\in{\mathcal{C}}^{(k)}_{s}$ and
$C^{\prime}\in{\mathcal{C}}^{(k)}_{s^{\prime}}$; note that it is possible that
$s=s^{\prime}$. Clearly, there is a pair $0\leq s,s^{\prime}\leq\left\lceil
1/\delta\right\rceil$ of indices, such that the number of edges of type
$(s,s^{\prime})$ in $M^{\prime}_{i}$ is at least
$\frac{|M^{\prime}_{i}|}{(1+\left\lceil
1/\delta\right\rceil)^{2}}\geq\frac{n^{1-\delta}\cdot\delta^{2}}{512}$. From
now on we fix this pair of indices, and we denote by
$M^{\prime\prime}_{i}\subseteq M^{\prime}_{i}$ the set of all edges of type
$(s,s^{\prime})$ in $M^{\prime}_{i}$, so
$|M^{\prime\prime}_{i}|\geq\frac{n^{1-\delta}\cdot\delta^{2}}{512}$. We say
that iteration $i$ is an iteration of type $(s,s^{\prime})$.

Note that there must be an ordered pair $(s,s^{\prime})$ of indices, with
$0\leq s,s^{\prime}\leq\left\lceil 1/\delta\right\rceil$, such the number of
good iterations in $I^{\prime}_{k}$ that are of type $(s,s^{\prime})$ is at
least: $\frac{|I^{\prime}_{k}|}{(1+\left\lceil
1/\delta\right\rceil)^{2}}\geq\frac{\delta^{2}}{6}\cdot\left\lceil
n^{4\delta}\right\rceil$. From now on we fix this pair $(s,s^{\prime})$ of
indices, and we denote by $I^{\prime\prime}_{k}\subseteq I^{\prime}_{k}$ the
set of all good iterations $i$ from phase $k$ that are of type
$(s,s^{\prime})$, so
$|I^{\prime\prime}_{k}|\geq\frac{\delta^{2}}{6}\cdot\left\lceil
n^{4\delta}\right\rceil$. We assume w.l.o.g. that $s\geq s^{\prime}$.

##### Step 2: Contracted Graph.

In this step we construct a weighted contracted graph $J$, as follows. For
every cluster
$C\in{\mathcal{C}}^{(k)}_{s}\cup{\mathcal{C}}^{(k)}_{s^{\prime}}$, we add a
vertex $v(C)$ to graph $J$; we refer to vertices of $J$ as _supernodes_ , to
distinguish them from vertices of $V$. The set of edges of $J$ is the union of
the sets $\left\\{E_{i}\mid i\in I^{\prime\prime}_{k}\right\\}$ of edges that
we define below. We refer to the edges of $J$ as _meta-edges_. For every
iteration $i\in I^{\prime\prime}_{k}$, every meta-edge $\hat{e}\in E_{i}$
represents some collection $S(\hat{e})\subseteq M^{\prime\prime}_{i}$ of
edges.

Consider some iteration $i\in I^{\prime\prime}_{k}$. For every pair
$C\in{\mathcal{C}}^{(k)}_{s},C^{\prime}\in{\mathcal{C}}^{(k)}_{s^{\prime}}$ of
clusters, such that at least one edge of $M^{\prime\prime}_{i}$ connects a
vertex of $C$ to a vertex of $C^{\prime}$, we add a meta-edge
$\hat{e}=(v(C),v(C^{\prime}))$ to $E_{i}$. We let $S(\hat{e})$ be the set of
all edges of $M^{\prime\prime}_{i}$ that connect vertices of $C$ to vertices
of $C^{\prime}$, and we set the weight of the meta-edge $\hat{e}$ to be
$w(\hat{e})=|S(\hat{e})|$. We note that, since $M^{\prime\prime}_{i}$ is a
matching of cardinality at least $\frac{n^{1-\delta}\cdot\delta^{2}}{512}$, we
get that $\sum_{\hat{e}\in
E_{i}}w(e)\geq\frac{n^{1-\delta}\cdot\delta^{2}}{512}$. Moreover, for every
cluster $C\in{\mathcal{C}}^{(k)}_{s}\cup{\mathcal{C}}^{(k)}_{s^{\prime}}$, the
total weight of all meta-edges of $E_{i}$ incident to $C$ is at most $|V(C)|$.

Consider a pair $i,i^{\prime}\in I^{\prime\prime}_{k}$ of indices with
$i<i^{\prime}$. Note that, if a meta-edge $(v(C),v(C^{\prime}))$ belongs to
$E_{i}$, then, from 4.7, meta-edge $(v(C),v(C^{\prime}))$ may not lie in
$E_{i^{\prime}}$. We set $E(J)=\bigcup_{i\in I^{\prime\prime}_{k}}E_{i}$. From
the above discussion, graph $J$ contains no parallel edges. For every
supernode $v(C)\in V(J)$, the total weight of all meta-edges incident to
$v(C)$ is bounded by $|V(C)|\cdot|I^{\prime\prime}_{k}|$. The total weight of
all meta-edges in graph $J$ is at least
$\frac{n^{1-\delta}\cdot\delta^{2}}{512}\cdot|I^{\prime\prime}_{k}|$.

##### Step 3: Constructing the Clustering ${\mathcal{C}}^{(k+1)}$.

In order to construct clustering ${\mathcal{C}}^{(k+1)}$, we start with
${\mathcal{C}}^{(k+1)}={\mathcal{C}}^{(k)}$, and then iteratively merge some
clusters of ${\mathcal{C}}^{(k+1)}$. In every iteration, we consider the graph
$J$. Assume that there is a cluster
$C^{\prime}\in{\mathcal{C}}^{(k)}_{s^{\prime}}$, such that supernode
$v(C^{\prime})$ has at least $n^{\delta}$ neighbor vertices in graph $J$. We
denote the neighbor vertices of $v(C^{\prime})$ by $v(C_{1}),\ldots,v(C_{q})$.
Note that for all $1\leq a\leq q$, $C_{a}\in{\mathcal{C}}^{(k)}_{s}$ must
hold. We delete clusters $C^{\prime},C_{1},\ldots,C_{q}$ from
${\mathcal{C}}^{(k+1)}$, and instead add a single cluster $C^{*}$, whose
vertex set is $V(C^{\prime})\cup V(C_{1})\cup\cdots\cup V(C_{q})$, and edge
set is the union of $E(C^{\prime})\cup E(C_{1})\cup\cdots\cup E(C_{q})$ with
the set $\bigcup_{a=1}^{q}S(v(C^{\prime}),v(C_{a}))$ of edges. Note that
$C^{*}\subseteq\hat{H}^{(k+1)}$ holds. We then delete vertices
$v(C^{\prime}),v(C_{1}),\ldots,v(C_{q})$ from graph $J$.

Observe that, for every vertex $x\in V(C^{*})$, the level of $x$ in
${\mathcal{C}}^{(k)}$ was either $s$ or $s^{\prime}\leq s$. Moreover, if
$C\in{\mathcal{C}}^{(k)}$ is the cluster that contained $x$, then
$|V(C^{*})|>n^{\delta}\cdot|V(C)|$. Therefore, the level of $x$ in
${\mathcal{C}}^{(k+1)}$ is strictly greater than that in
${\mathcal{C}}^{(k)}$. We conclude that every vertex in $V(C^{*})$ is promoted
in the current phase, and the level of cluster $C^{*}$ is at least $(s+1)$. We
use the following simple observation, that will allow us to establish
Invariant I2.

######  Observation 4.8.

For every pair $x,y\in V(C^{*})$ of vertices, $\mbox{\sf
dist}_{C^{*}}(x,y)\leq 4^{s+1}$.

###### Proof.

If both $x$ and $y$ belong to a single cluster of
$\left\\{C^{\prime},C_{1},\ldots,C_{q}\right\\}$, then, since Invariant I2
held for ${\mathcal{C}}^{(k)}$, and since each such cluster is contained in
$C^{*}$, $\mbox{\sf dist}_{C^{*}}(x,y)\leq 4^{s}$ must hold. Assume now that
$x$ and $y$ belong to different clusters. We assume w.l.o.g. that $x\in
V(C_{1})$ and $y\in V(C_{2})$; the other cases are treated similarly.

From the definition of cluster $C^{*}$, meta-edges
$\hat{e}_{1}=(v(C^{\prime}),v(C_{1}))$, $\hat{e}_{2}=(v(C^{\prime}),v(C_{2}))$
lie in $J$. Consider any real edge $e_{1}\in S(\hat{e}_{1})$ and $e_{2}\in
S(\hat{e}_{2})$. Both edges must lie in $\hat{H}^{(k+1)}$, and in $C^{*}$. We
denote $e_{1}=(x_{1},y_{1})$ with $x_{1}\in V(C_{1})$, and
$e_{2}=(x_{2},y_{2})$ with $y_{2}\in V(C_{2})$. In particular, $y_{1},x_{2}\in
V(C^{\prime})$ must hold. From Invariant I2, there is a path $P_{1}$ of length
at most $4^{s}$ connecting $x$ to $x_{1}$ in $C_{1}$; a path $P^{\prime}$ of
length at most $4^{s^{\prime}}\leq 4^{s}$ connecting $y_{1}$ to $x_{2}$ in
$C^{\prime}$; and a path $P_{3}$ of length at most $4^{s}$ connecting $y_{2}$
to $y$ in $C_{2}$. By combining these three paths with edges $e_{1}$ and
$e_{2}$, we obtain a path in cluster $C^{*}$, connecting $x$ to $y$, whose
length is at most $3\cdot 4^{s}+1\leq 4^{s+1}$. Therefore, $\mbox{\sf
dist}_{C^{*}}(x,y)\leq 4^{s+1}$.

The algorithm terminates once, every supernode $v(C^{\prime})$ of $J$ with
$C^{\prime}\in{\mathcal{C}}^{(k)}_{s^{\prime}}$, the number of meta-edges
incident to $v(C^{\prime})$ in the current graph $J$ is less than
$n^{\delta}$.

From the above discussion, once the algorithm terminates, Invariant I2 holds
for the final clustering ${\mathcal{C}}^{(k+1)}$, as every newly added cluster
to ${\mathcal{C}}^{(k+1)}$ belongs to level $(s+1)$ or higher. It is immediate
to verify that Invariant I1 holds for the final set ${\mathcal{C}}^{(k+1)}$ of
clusters. It now only remains to prove that sufficiently many vertices are
promoted in the current iteration.

Consider the graph $J$ that is obtained at the end of the algorithm. In this
graph, for every cluster $C^{\prime}\in{\mathcal{C}}^{(k)}_{s^{\prime}}$, its
corresponding supernode $v(C^{\prime})$ has fewer than $n^{\delta}$ meta-edges
incident to $v(C^{\prime})$. Since, for every meta-edge $\hat{e}\in E(J)$ that
is incident to a supernode $v(C)$, $w(\hat{e})\leq|V(C)|$ must hold, we get
that the total weight of all edges remaining in graph $J$ at the end of the
algorithm is bounded by:

$\sum_{C^{\prime}\in{\mathcal{C}}^{(k)}_{s^{\prime}}}|V(C^{\prime})|\cdot
n^{\delta}\leq n^{1+\delta}.$

Recall that the total weight of all meta-edges of $J$ at the beginning of the
algorithm was at least:

$\frac{n^{1-\delta}\cdot\delta^{2}}{512}\cdot|I^{\prime\prime}_{k}|\geq\frac{n^{1+3\delta}\cdot\delta^{4}}{2^{12}}>2n^{1+\delta},$

since $|I^{\prime\prime}_{k}|\geq\frac{\delta^{2}}{6}\cdot\left\lceil
n^{4\delta}\right\rceil$ and $n^{\delta}\geq 2^{14}/\delta^{2}$.

Therefore, the total weight of the meta-edges that remain at the end of the
algorithm in $J$ is less than half the original total weight. In other words,
the total weight of all meta-edges that were deleted from $J$ is at least
$\frac{n^{1-\delta}\cdot\delta^{2}}{1024}\cdot|I^{\prime\prime}_{k}|$. Each of
the deleted meta-edges is incident to some supernode $v(C)$, with
$C\in{\mathcal{C}}^{(k)}_{s}$ that was deleted from $J$. Recall that every
vertex of such a cluster $C$ is promoted in the current phase.

Consider now some supernode $v(C)$ that was deleted from $J$ in the current
phase. The total weight of all meta-edges incident to $v(C)$ in the original
graph $J$ was at most $|V(C)|\cdot|I^{\prime\prime}_{k}|$, and each of the
vertices of $C$ was promoted in phase $k$. Therefore, if we denote by $U$ is
the set of all vertices of $V$ that were promoted in phase $k$, then the total
weight of all meta-edges that were deleted from $J$ is at most
$|U|\cdot|I^{\prime\prime}_{k}|$. Since, as shown above, the total weight of
all such edges is at least
$\frac{n^{1-\delta}\cdot\delta^{2}}{1024}\cdot|I^{\prime\prime}_{k}|$, and
since we have assumed that $n^{\delta}\geq 2^{14}/\delta^{2}$, we get that
$|U|\geq\frac{n^{1-\delta}\cdot\delta^{2}}{1024}\geq n^{1-2\delta}$.

This concludes the proof of Theorem 4.2. We obtain the following immediate
corollary of the theorem.

######  Corollary 4.9.

Consider a Distanced Matching Game with parameters $n>0,0<\delta<1/4$ and $d$,
such that $d\geq 2^{4/\delta}$, $n^{\delta}\geq\frac{2^{14}\log
n}{\delta^{2}}$. Let $G$ be the graph that is obtained at the end of the game.
Then $|E(G)|\leq n^{1+8\delta}$ holds, and every vertex of $G$ has degree at
most $n^{8\delta}$.

The corollary follows from the fact that the set $E(G)$ of edges is
partitioned into at most $n^{8\delta}$ matchings – the responses of the
matching player in the game.

##  5 Hierarchical Support Structure

A Hierarchical Support Structure uses two parameters, an integer $N>0$, and
another parameter $0<\epsilon\leq 1/4$. Throughout, we denote
$\epsilon^{\prime}=\epsilon^{4}$. For an integer $j\geq 1$, we also let
$\eta_{j}=N^{6+256j\epsilon^{2}}$ and $\tilde{d}_{j}=2^{cj/\epsilon^{4}}$,
where $c$ is a sufficiently large constant.

For all $1\leq j\leq\left\lceil 1/\epsilon\right\rceil$, we define a _level_
-$j$ Hierarchical Support Structure for a graph containing $N^{j}$ vertices.
The definition of the support structure is recursive.

##### Level-$1$ Hierarchical Support Structure.

Given a graph $H$ with $|V(H)|=N$, level-$1$ Hierarchical Support Structure
for $H$ consists of a subset $S(H)$ of vertices of $H$, such that
$|V(H)\setminus S(H)|\leq N^{1-\epsilon^{4}}$.

##### Level-$j$ Hierarchical Support Structure.

Consider now some integer $1<j\leq\left\lceil 1/\epsilon\right\rceil$. Let $H$
be a graph with $|V(H)|=N^{j}$. A _level- $j$ Hierarchical Support Structure_
for graph $H$ consists of the following:

  * •

a collection ${\mathcal{H}}=\left\\{H_{1},\ldots,H_{r}\right\\}$ of
$r=N-\left\lceil 2N^{1-\epsilon^{4}}\right\rceil$ graphs, such that all
vertices in sets $V(H_{1}),V(H_{2}),\ldots,V(H_{r})$ are mutually disjoint,
and additionally, for all $1\leq i\leq r$: $V(H_{i})\subseteq V(H)$;
$|V(H_{i})|=N^{j-1}$; and $|E(H_{i})|\leq N^{j-1+32\epsilon^{2}}$ hold;

  * •

an embedding of the graph $H^{\prime}=\bigcup_{i=1}^{r}H_{i}$ into graph $H$
via paths of length at most $2^{64/\epsilon^{4}}$, that causes congestion at
most $N^{128\epsilon^{2}}$;

  * •

for all $1\leq i\leq r$, a level-$(j-1)$ Hierarchical Support Structure for
graph $H_{i}$; and

  * •

a set $S(H)\subseteq V(H)$ of vertices, where
$S(H)=\bigcup_{H_{i}\in{\mathcal{H}}}S(H_{i})$, and, for all
$H_{i}\in{\mathcal{H}}$, $S(H_{i})$ is the set of vertices that is given as
part of the level-$(j-1)$ Hierarchical Support Structure for $H_{i}$.

Additionally, we require every graph $H_{i}\in{\mathcal{H}}$ is
$(\eta_{j-1},\tilde{d}_{j-1})$-well-connected with respect to the set
$S(H_{i})$ of vertices. We say that ${\mathcal{H}}$ is the set of graphs
associated with the level-$j$ Hierarchical Support Structure for graph $H$.

This completes the definition of a Hierarchical Support Structure. We will
need to use the following simple claim.

######  Claim 5.1.

Let $1\leq j\leq\left\lceil 1/\epsilon\right\rceil$ be an integer, and let $H$
be a graph with $|V(H)|=N^{j}$, together with a level-$j$ Hierarchical Support
Structure. Then $|V(H)\setminus
S(H)|\leq|V(H)|\cdot\frac{4j}{N^{\epsilon^{4}}}$.

###### Proof.

The proof is by induction on $j$. When $j=1$, then $|V(H)|=N$, and, from the
definition of level-$1$ Hierarchical Support Structure, $|V(H)\setminus
S(H)|\leq
N^{1-\epsilon^{4}}=\frac{|V(H)|}{N^{\epsilon^{4}}}\leq|V(H)|\cdot\frac{4j}{N^{\epsilon^{4}}}$.

Consider now some integer $j>1$, and assume that the claim holds for $j-1$.
Let $H$ be a graph with $|V(H)|=N^{j}$, for which a level-$j$ Hierarchical
Support Structure is given, and let ${\mathcal{H}}$ be the collection of
graphs associated with the structure. Let
$V_{1}=\bigcup_{H_{i}\in{\mathcal{H}}}V(H_{i})$ and $V_{2}=V(H)\setminus
V_{1}$. From the definition of level-$j$ Hierarchical Support Structure,
$|{\mathcal{H}}|=N-\left\lceil 2N^{1-\epsilon^{4}}\right\rceil\geq
N-4N^{1-\epsilon^{4}}$. Therefore, $|V_{1}|\geq
N^{j}-\frac{4N^{j}}{N^{\epsilon^{4}}}$, and
$V_{2}\leq\frac{4N^{j}}{N^{\epsilon^{4}}}=\frac{4|V(H)|}{N^{\epsilon^{4}}}$.

Let $V^{\prime}_{1}=\bigcup_{H_{i}\in{\mathcal{H}}}S(H_{i})$ and
$V^{\prime\prime}_{1}=V_{1}\setminus V^{\prime}_{1}$. Clearly, $V(H)\setminus
S(H)=V^{\prime\prime}_{1}\cup V_{2}$. We now bound $|V^{\prime\prime}_{1}|$.

Since, for every graph $H_{i}\in{\mathcal{H}}$, by the induction hypothesis,
$|V(H_{i})\setminus
S(H_{i})|\leq|V(H_{i})|\cdot\frac{4(j-1)}{N^{\epsilon^{4}}}=\frac{4(j-1)\cdot
N^{j-1}}{N^{\epsilon^{4}}}$, and since $|{\mathcal{H}}|<N$, we get that
$|V^{\prime\prime}_{1}|\leq\frac{4(j-1)\cdot
N^{j}}{N^{\epsilon^{4}}}=\frac{4(j-1)\cdot|V(H)|}{N^{\epsilon^{4}}}$.

Altogether, we get that:

$|V(H)\setminus
S(H)|=|V_{1}^{\prime\prime}|+|V_{2}|\leq\frac{4(j-1)\cdot|V(H)|}{N^{\epsilon^{4}}}+\frac{4|V(H)|}{N^{\epsilon^{4}}}=\frac{4j\cdot|V(H)|}{N^{\epsilon^{4}}}$

The following theorem provides an algorithm for the Distancing Player in the
Distanced Matching game.

######  Theorem 5.2.

There is a large enough constant $c$, and a deterministic algorithm, whose
input consists of a parameter $0<\epsilon<1/4$, a pair $N$, $1\leq
j\leq\left\lceil 1/\epsilon\right\rceil$ of integers, and a graph $H$ with
$|V(H)|=N^{j}$, such that $N$ is sufficiently large, so that
$\frac{N^{\epsilon^{4}}}{\log N}\geq 2^{128/\epsilon^{5}}$ holds. The
algorithm computes one of the following:

  * •

either a $(\delta_{j},d)$-distancing $(A,B,E^{\prime})$ in graph $H$, where
$\delta_{j}=4j\epsilon^{4}$, $d=2^{32/\epsilon^{4}}$ and
$|E^{\prime}|\leq\frac{|A|}{N^{j\epsilon^{4}}}$; or

  * •

a level-$j$ Hierarchical Support Structure for $H$, such that graph $H$ is
$(\eta_{j},\tilde{d}_{j})$-well-connected with respect to the set $S(H)$ of
vertices defined by the support structure, where
$\eta_{j}=N^{6+256j\epsilon^{2}}$ and $\tilde{d}_{j}=2^{cj/\epsilon^{4}}$.

The running time of the algorithm is bounded by:

$cj\cdot N^{j(1+64\epsilon^{2})+7}+c|E(H)|\cdot N^{6}.$

We prove Theorem 5.2 in Section 6. Note that Theorem 2.2 follows from the
theorem directly, by setting $j=1/\epsilon$.

The following immediate corollary of the theorem can be used in order to
either embed a large graph $H$ into an input graph $G$, and construct a
Hierarchical Support Structure for $H$, so that graph $H$ is well-connected
with respect to the resulting set $S(H)$ of vertices given by the Hierarchical
Support Structure; or to compute a distancing in graph $G$. The latter can in
turn be used in order to compute a sparse cut in $G$, via Lemma 4.1. We state
the corollary in a slightly more general form that will be helpful for us
later: we assume that, together with graph $G$, we are given a subset $T$ of
its vertices called terminals, and that we are interested in embedding a large
graph $H$ into $G$ with $V(H)\subseteq T$.

######  Corollary 5.3.

There is a deterministic algorithm, whose input consists of an $n$-vertex
graph $G$, a set $T$ of $k$ vertices of $G$ called terminals, and parameters
$\frac{2}{(\log k)^{1/12}}<\epsilon<\frac{1}{400}$, $d>1$ and $\eta>1$, such
that $1/\epsilon$ is an integer. The algorithm computes one of the following:

  * •

either a pair $T_{1},T_{2}\subseteq T$ of disjoint subsets of terminals, and a
set $E^{\prime}$ of edges of $G$, such that:

    * –

$|T_{1}|=|T_{2}|$ and $|T_{1}|\geq\frac{k^{1-4\epsilon^{3}}}{4}$;

    * –

$|E^{\prime}|\leq\frac{d\cdot|T_{1}|}{\eta}$; and

    * –

for every pair $t\in T_{1},t^{\prime}\in T_{2}$ of terminals, $\mbox{\sf
dist}_{G\setminus E^{\prime}}(t,t^{\prime})>d$;

  * •

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

The running time of the algorithm is $O\left(k^{1+O(\epsilon)}+|E(G)|\cdot
k^{O(\epsilon^{3})}\cdot(\eta+d\log n)\right)$.

###### Proof.

Let $q=1/\epsilon$, let $N=\left\lfloor k^{\epsilon}\right\rfloor$, and let
$T^{\prime}\subseteq T$ be any subset of $N^{q}$ terminals. Observe that:

$N^{q}=\left\lfloor
k^{\epsilon}\right\rfloor^{1/\epsilon}\geq\left(k^{\epsilon}-1\right)^{1/\epsilon}=k\cdot\left(1-\frac{1}{k^{\epsilon}}\right)^{1/\epsilon}\geq
k\cdot\left(1-\frac{1}{k^{\epsilon}\cdot\epsilon}\right)\geq
k-\frac{k^{1-\epsilon}}{\epsilon}\geq k-k^{1-\epsilon/2}$ (3)

(we have used the fact that for all $0<\delta<1$ and $a>2$,
$(1-\delta)^{a}\geq 1-\delta a$).

We will attempt to construct a graph $H$ with $V(H)=T^{\prime}$, together with
an embedding ${\mathcal{P}}$ of $H$ into $G$ with congestion at most
$\eta\cdot k^{32\epsilon^{3}}$ and path lengths at most $d$, and a level-$q$
Hierarchical Support Structure for $H$, such that $H$ is
$(\eta^{\prime},\tilde{d})$-well-connected with respect to the set $S(H)$ of
vertices defined by the support structure. If we fail to construct such a
graph $H$, we will compute the sets $T_{1},T_{2}\subseteq T$ of terminals and
the set $E^{\prime}\subseteq E(G)$ of edges as required.

We will employ the distanced-matching game on graph $H$ with parameters
$n=|T^{\prime}|$, $\delta=4\epsilon^{3}$, and distance parameter
$d^{\prime}=2^{32/\epsilon^{4}}$.

We will use the algorithm from Theorem 5.2 for the distancing player, with
parameter $j=q$, and parameters $N$ and $\epsilon$ remaining unchanged. In
order to be able to use the algorithm, we need to verify that
$\frac{N^{\epsilon^{4}}}{\log N}\geq 2^{128/\epsilon^{5}}$ holds. Recall that,
from the conditions of Corollary 5.3, $\frac{2}{(\log
k)^{1/12}}<\epsilon<\frac{1}{400}$. Therefore, $\log k>(2/\epsilon)^{12}$ and
$k>2^{(2/\epsilon)^{12}}$. Moreover, from the above calculations, $\frac{\log
k}{\log\log k}>\frac{1}{\epsilon^{8}}$ holds, and so $k^{\epsilon^{8}}>\log k$
must hold. Altogether, we get that:

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

We will bound the number of iterations of the Distanced Matching game via
Theorem 4.2. In order to use Theorem 4.2, we need to verify that
$\frac{|T^{\prime}|^{\delta}}{\log(|T^{\prime}|)}\geq\frac{2^{14}}{\delta^{2}}$,
or, equivalently:
$\frac{|T^{\prime}|^{4\epsilon^{3}}}{\log(|T^{\prime}|)}\geq\frac{2^{10}}{\epsilon^{6}}$.
Recall that $|T^{\prime}|=N^{q}=N^{1/\epsilon}$, and so
$\frac{|T^{\prime}|^{4\epsilon^{3}}}{\log(|T^{\prime}|)}=\frac{\epsilon\cdot
N^{4\epsilon^{2}}}{\log N}\geq\frac{N^{\epsilon^{4}}}{\log N}\geq
2^{128/\epsilon^{5}}\geq\frac{2^{10}}{\epsilon^{6}}$ from Equation 4, and
since $\epsilon\leq 1/400$. We also need to verify that $d^{\prime}\geq
2^{4/\delta}$. Since $d^{\prime}=2^{32/\epsilon^{4}}$ and
$\delta=4\epsilon^{3}$, this is immediate to verify. From Theorem 4.2, we can
now conclude that the number of iterations in a Distanced Matching game with
parameters $n=|T^{\prime}|$, $\delta=4\epsilon^{3}$, and distance parameter
$d^{\prime}=2^{32/\epsilon^{4}}$ is bounded by $|T^{\prime}|^{8\delta}\leq
k^{32\epsilon^{3}}$.

We start with a graph $H$ whose vertex set is $V(H)=T^{\prime}$, and edge set
is $E(H)=\emptyset$, and then iterate. In each iteration $i$, we will add some
set $E_{i}$ of edges to graph $H$, and we will define an embedding $P(e)$ for
every edge $e\in E_{i}$. We now describe the execution of a single iteration.

### Execution of Iteration $i$.

We apply the algorithm from Theorem 5.2 to the current graph $H$, with
parameter $j=q$, and parameters $N,\epsilon$ remaining unchanged. Note that
$|V(H)|=|T^{\prime}|=N^{q}$, and, as we have established above,
$\frac{N^{\epsilon^{4}}}{\log N}\geq 2^{128/\epsilon^{5}}$ holds.

We now consider two cases. The first case is when the algorithm from Theorem
5.2 returns a $(\delta_{q},d^{\prime})$-distancing
$(X_{i},Y_{i},E^{\prime}_{i})$ in graph $H$, where
$\delta_{q}=4j\epsilon^{4}=4q\epsilon^{4}=4\epsilon^{3}=\delta$ (since
$q=1/\epsilon$), and $d^{\prime}=2^{32/\epsilon^{4}}$. In this case, we say
that iteration $i$ is _regular_. We view this distancing as the response of
the distancing player in iteration $i$ of the Distanced Matching game that we
play on graph $H$.

We then apply Procedure $\mathsf{ProcPathPeel}$ from Lemma 3.12 to graph $G$
and sets $A_{1}=X_{i},B_{1}=Y_{i}$ of its vertices, together with parameters
$d$ and $\eta$ from the statement of Corollary 5.3. Let ${\mathcal{Q}}_{1}$
denote the collection of paths that the algorithm returns. Recall that every
path in ${\mathcal{Q}}_{1}$ connects some vertex of $X_{i}$ to a vertex of
$Y_{i}$, and that every vertex of $X_{i}\cup Y_{i}$ may serve as an endpoint
of at most one such path. We let $M_{i}\subseteq X_{i}\times Y_{i}$ be the
matching that is defined by the paths in ${\mathcal{Q}}_{1}$: a pair $(x,y)$
of vertices with $x\in X_{i},y\in Y_{i}$ is added to $M_{i}$ iff some path
$Q(x,y)\in{\mathcal{Q}}_{1}$ has endpoints $x,y$. We again consider two cases.
The first case happens if $|M_{i}|\geq|X_{i}|/2$. In this case, we say that
iteration $i$ is successful. We obtain a collection $E_{i}\subseteq M_{i}$ of
edges as follows: we start with $E_{i}=M_{i}$, and we delete from $E_{i}$ all
pairs $(x,y)$ of vertices where edge $(x,y)$ lies in $E^{\prime}_{i}$. Since,
from the definition of distancing, $|E^{\prime}_{i}|\leq|X_{i}|/16$, we get
that $|E_{i}|\geq|X_{i}|/4$. We let
${\mathcal{P}}_{i}=\left\\{Q(x,y)\mid(x,y)\in E_{i}\right\\}$ be the
collection of paths that route the pairs of vertices in $E_{i}$. We add the
edges of $E_{i}$ to graph $H$, and we view $E_{i}$ as the response of the
matching player in iteration $i$. We also view the set ${\mathcal{P}}_{i}$ of
paths in graph $H$ as an embedding of the set $E_{i}$ of edges. Recall that
each path in ${\mathcal{P}}_{i}$ has length at most $d$, and the paths in
${\mathcal{P}}_{i}$ cause congestion at most $\eta$. We then continue to the
next iteration.

The second case happens if $|M_{i}|<|X_{i}|/2$. In this case we say that
iteration $i$ is unsuccessful. Let $E^{\prime}$ be the set of all edges $e$ in
graph $G$ that participate in exactly $\eta$ paths in ${\mathcal{Q}}_{1}$. Let
$X^{\prime}\subseteq X_{i}$ and $Y^{\prime}\subseteq Y_{i}$ be the sets of
vertices that do not serve as endpoints of the paths in ${\mathcal{Q}}_{1}$.
Recall that Lemma 3.12 guarantees (via Property P3) that the length of the
shortest path connecting a vertex of $X^{\prime}$ to a vertex of $Y^{\prime}$
in $G\setminus E^{\prime}$ is greater than $d$.

Recall that
$|X^{\prime}|=|Y^{\prime}|\geq\frac{|X_{i}|}{2}\geq\frac{|T^{\prime}|^{1-\delta}}{2}\geq\frac{k^{1-\delta}}{4}\geq\frac{k^{1-4\epsilon^{3}}}{4}$.
Since every path in ${\mathcal{Q}}_{1}$ has length at most $d$, we get that
$\sum_{Q\in{\mathcal{Q}}_{1}}|E(Q)|\leq d\cdot\frac{|X_{i}|}{2}\leq
d\cdot|X^{\prime}|$. Since set $E^{\prime}$ contains edges that participate in
$\eta$ paths in ${\mathcal{Q}}_{1}$, we get that:
$|E^{\prime}|\leq\frac{d\cdot|X^{\prime}|}{\eta}$. We return the set
$E^{\prime}$ of edges and the sets $T_{1}=X^{\prime}$, $T_{2}=Y^{\prime}$ of
terminals. From the above discussion, $|T_{1}|=|T_{2}|$,
$|T_{1}|\geq\frac{k^{1-4\epsilon^{3}}}{4}$, and
$|E^{\prime}|\leq\frac{d\cdot|T_{1}|}{\eta}$ hold as required. Moreover, for
every pair $t\in T_{1},t^{\prime}\in T_{2}$ of terminals, $\mbox{\sf
dist}_{G\setminus E^{\prime}}(t,t^{\prime})>d$.

It remains to consider the second case, when the algorithm from Theorem 5.2
constructs a level-$q$ Hierarchical Support Structure for $H$, such that graph
$H$ is $(\eta_{q},\tilde{d}_{q})$-well-connected with respect to the set
$S(H)$ of vertices defined by the support structure, where
$\tilde{d}_{q}=2^{cq/\epsilon^{4}}=2^{c/\epsilon^{5}}=\tilde{d}$, and:

$\eta_{q}=N^{6+256q\epsilon^{2}}=N^{6+256\epsilon}=\eta^{\prime}.$

In this case, we say that iteration $i$ is irregular. Recall that
$|V(H)|=|T^{\prime}|=N^{q}\geq k-k^{1-\epsilon/2}$ from Inequality 3. As
observed already, the number of iterations in the Distanced Matching game is
bounded by $k^{32\epsilon^{3}}$, and so the maximum vertex degree in $H$ is
bounded by $k^{32\epsilon^{3}}$, and the number of edges in graph $H$ is
bounded by $k^{1+32\epsilon^{3}}$ throughout the algorithm. If we denote by
$z\leq k^{32\epsilon^{3}}$ the number of iterations in the Distanced Matching
game, then for all $1\leq i\leq z$, we have constructed a set
${\mathcal{P}}_{i}$ of paths in graph $H$ embedding the edges of $E_{i}$. The
paths in ${\mathcal{P}}_{i}$ have length at most $d$ each, and they cause
congestion at most $\eta$ in $G$. By letting
${\mathcal{P}}=\bigcup_{i=1}^{z}{\mathcal{P}}_{i}$, we obtain an embedding of
graph $H$ into $G$ via paths of length at most $d$, that cause congestion at
most $\eta\cdot z\leq\eta\cdot k^{32\epsilon^{3}}$. We output graph $H$, its
embedding ${\mathcal{P}}$, and the level-$q$ Hierarchical Support Structure
for $H$.

This completes the description of a single iteration. It now remains to bound
the running time of the algorithm.

### Running Time Analysis

Recall that, throughout the algorithm, $|E(H)|\leq k^{1+32\epsilon^{3}}$
holds, and that the number of regular successful iterations in the algorithm
is at most $k^{32\epsilon^{3}}$. Additionally, there could be at most one
irregular iteration, and at most one regular but unsuccessful iteration.

We now bound the running time of a single iteration. This running time is
dominated by the running times of the algorithms from Theorem 5.2 and Lemma
3.12.

The former is bounded by:

$O(q\cdot N^{q(1+64\epsilon^{2})+7}+|E(H)|\cdot N^{6})\leq
O\left(k^{1+O(\epsilon)}+k^{1+32\epsilon^{3}}\cdot k^{O(\epsilon)}\right)\leq
O\left(k^{1+O(\epsilon)}\right).$

The latter is bounded by: $O(|E(G)|(\eta+d\log n))$.

The total running time of the algorithm is then bounded by:

$O\left(k^{1+O(\epsilon)}+|E(G)|\cdot k^{O(\epsilon^{3})}\cdot(\eta+d\log
n)\right).$

##  6 Algorithm for the Distancing Player – Proof of Theorem 5.2

This section is dedicated to proving Theorem 5.2. Throughout the proof we use
the following three parameters: $\epsilon^{\prime}=\epsilon^{4}$;
$\Delta=64/\epsilon^{\prime}$; and $d^{\prime}=2d\cdot\Delta$. Note that:

$d^{\prime}=2\Delta d=\frac{128d}{\epsilon^{\prime}}=\frac{128\cdot
2^{32/\epsilon^{4}}}{\epsilon^{4}}\leq 2^{64/\epsilon^{4}}<\frac{1}{4}\cdot
2^{c/\epsilon^{4}},$ (5)

since $c$ is large enough.

The proof is by induction on $j$. We start with the base case, where $j=1$.

### Base Case: $j=1$

We assume that we are given a graph $H$ on $N$ vertices. Our goal is to either
compute a $(\delta_{1},d)$-distancing in graph $H$, or to construct a set
$S(H)\subseteq V(H)$ of vertices, such that $|V(H)\setminus S(H)|\leq
N^{1-\epsilon^{4}}$, and graph $H$ is $(\eta_{1},\tilde{d}_{1})$-well-
connected with respect to $S(H)$.

We apply Algorithm $\mathsf{ProcSeparate}$ from Lemma 3.10 to graph $H$, with
the set $T=V(H)$ of terminal vertices, with distance parameters $d$ and
$\Delta$ remaining the same, and parameter
$\alpha=1-\frac{1}{N^{\epsilon^{\prime}}}$.

Assume first that the outcome of the algorithm is a pair $T_{1},T_{2}\subseteq
V(H)$ of subsets of vertices, with $|T_{1}|=|T_{2}|$, such that for every pair
$t\in T_{1}$, $t^{\prime}\in T_{2}$ of vertices, $\mbox{\sf
dist}_{H}(t,t^{\prime})\geq d$, and additionally:

$|T_{1}|\geq
N^{1-64/\Delta}\cdot\min\left\\{(1-\alpha),\frac{1}{3}\right\\}\geq
N^{1-2\epsilon^{\prime}}.$

(recall that $\Delta=64/\epsilon^{\prime}$ and $N^{\epsilon^{\prime}}>3$). In
this case, since $\delta_{1}=4\epsilon^{\prime}$, we obtain a
$(\delta_{1},d)$-distancing $(T_{1},T_{2},\emptyset)$ in graph $H$. We return
this distancing as the outcome of the algorithm.

Otherwise, Procedure $\mathsf{ProcSeparate}$ must return a vertex $v\in V(H)$,
with $|B_{H}(v,\Delta\cdot d)|>\alpha\cdot
N=N\cdot\left(1-\frac{1}{N^{\epsilon^{\prime}}}\right)$. In this case, we set
$S(H)=B_{H}(v,\Delta\cdot d)$, and we report that graph $H$ is
$(\eta_{1},\tilde{d}_{1})$-well-connected with respect to $S(H)$. We also
return $S(H)$ as level-$1$ Hierarchical Support Structure for $H$. Note that
$|V(H)\setminus S(H)|\leq N^{1-\epsilon^{\prime}}=N^{1-\epsilon^{4}}$ as
required. It remains to show that graph $H$ is indeed
$(\eta_{1},\tilde{d}_{1})$-well-connected with respect to $S(H)$. Recall that
$\eta_{1}>N$ and $d^{\prime}<\tilde{d}_{1}$ from Inequality 5, since
$\tilde{d}_{1}=2^{c/\epsilon^{4}}$. Let $A,B\subseteq S(H)$ be any pair of
equal-cardinality subsets of vertices. We define an arbitrary perfect matching
$M\subseteq A\times B$ between vertices of $A$ and vertices of $B$. Consider
now any pair $(a,b)\in M$ of matched vertices. Since $a,b\in
B_{H}(v,\Delta\cdot d)$, there is a path $P(a,b)$ connecting $a$ to $b$ in $H$
of length at most $2\Delta\cdot d=d^{\prime}\leq\tilde{d}_{1}$. We then let
${\mathcal{P}}(A,B)=\left\\{P(a,b)\mid(a,b)\in M\right\\}$ be the resulting
collection of paths, that routes every vertex of $A$ to a distinct vertex of
$B$. The length of every path in ${\mathcal{P}}(A,B)$ is at most
$\tilde{d}_{1}$, and the congestion caused by the paths in
${\mathcal{P}}(A,B)$ is at most $|{\mathcal{P}}(A,B)|\leq|V(H)|\leq
N<\eta_{1}$.

The running time of the algorithm is dominated by the running time of
Procedure $\mathsf{ProcSeparate}$, which is bounded by $O(|E(H)|\cdot
N^{64/\Delta})\leq O(|E(H)|\cdot N^{\epsilon^{\prime}})<c|E(H)|\cdot N^{6}$,
if $c$ is large enough, since $\Delta=64/\epsilon^{\prime}$.

### Step: $1<j\leq h$

We now assume that we are given some integer $1<j\leq\left\lceil
1/\epsilon\right\rceil$, such that the statement of Theorem 5.2 holds for
$j-1$, and we prove the statement of the theorem for $j$. Recall that we are
given as input a graph $H$ with $|V(H)|=N^{j}$.

We partition the set $V(H)$ of vertices into $N$ subsets $V_{1},\ldots,V_{N}$,
each of which contains exactly $N^{j-1}$ vertices. The algorithm consists of
two phases. In the first phase, we run the Distanced Matching Game in parallel
on $N$ graphs $H_{1},\ldots,H_{N}$, where for all $1\leq i\leq N$,
$V(H_{i})=V_{i}$. We will add edges to graphs $H_{1},\ldots,H_{N}$ gradually
via the Distanced Matching Game, while computing an embedding of all resulting
edges into graph $H$, so that the resulting embedding paths have sufficiently
low length and cause sufficiently low congestion. In this phase, we will
either compute the required $(\delta_{j},d)$-distancing in $H$, or we will be
able to successfully complete the Distanced Matching Game on a sufficiently
large collection
${\mathcal{H}}^{\prime}\subseteq\left\\{H_{1},\ldots,H_{N}\right\\}$ of the
graphs. In the latter case, for each such graph
$H_{i}\in{\mathcal{H}}^{\prime}$, we will also compute a level-$(j-1)$
Hierarchical Support Structure for $H_{i}$. If the outcome of the first phase
is a $(\delta_{j},d)$-distancing for $H$, then we terminate the algorithm and
return this distancing. Otherwise, we continue to the second phase. In the
second phase we will exploit the graphs in ${\mathcal{H}}^{\prime}$ to either
compute a $(\delta_{j},d)$-distancing in graph $H$, or to compute a subset
${\mathcal{H}}^{\prime\prime}\subseteq{\mathcal{H}}^{\prime}$ of $r$ graphs,
so that, if we let
$S(H)=\bigcup_{H_{i}\in{\mathcal{H}}^{\prime\prime}}S(H_{i})$, then graph $H$
is $(\delta_{j},\tilde{d}_{j})$-well-connected with respect to the set $S(H)$
of vertices. We now describe each of the two phases in turn.

###  6.1 Phase 1: Construction of Smaller Well-Connected Graphs

In this phase, we gradually construct a collection
${\mathcal{H}}=\left\\{H_{1},\ldots,H_{N}\right\\}$ of graphs, over the course
of at most $N^{64\epsilon^{2}}$ iterations, by running the Distanced Matching
Game over these graphs in parallel with parameters $\delta=\delta_{j-1}$ and
$d=2^{32/\epsilon^{4}}$. Initially, for all $1\leq i\leq N$, we let
$V(H_{i})=V_{i}$ and $E(H_{i})=\emptyset$. In every iteration $q\geq 1$, we
will compute, for all $1\leq i\leq N$, a partial matching $E_{i}^{q}$ over the
vertices of $V_{i}$. We will ensure that either $E_{i}^{q}=\emptyset$, or
$|E_{i}^{q}|\geq N^{(j-1)(1-\delta_{j-1})}/8$. The edges of $E_{i}^{q}$ are
then added to graph $H_{i}$. Additionally, in the $q$th iteration, we will
compute an embedding ${\mathcal{P}}^{q}$ of all edges in
$\bigcup_{i=1}^{N}E_{i}^{q}$ into $H$. We now describe a single iteration $q$.

####  6.1.1 Description of Iteration $q$

Using the induction hypothesis, we apply the algorithm from Theorem 5.2 to
each of the graphs $H_{i}\in{\mathcal{H}}$, with parameter $(j-1)$. We denote
by ${\mathcal{H}}^{1}\subseteq{\mathcal{H}}$ the collection of all graphs
$H_{i}$, for which the algorithm returned a $(\delta_{j-1},d)$-distancing in
$H_{i}$, and we denote by
${\mathcal{H}}^{2}={\mathcal{H}}\setminus{\mathcal{H}}^{1}$ all remaining
graphs. Recall that, for each graph $H_{i}\in{\mathcal{H}}^{2}$, the algorithm
computes a level-$(j-1)$ Hierarchical Support Structure. We now consider two
cases, depending on whether $|{\mathcal{H}}^{1}|>N^{1-\epsilon^{\prime}}$.

##### Case 1: $|{\mathcal{H}}^{1}|>N^{1-\epsilon^{\prime}}$.

If this case happens, then we say that iteration $q$ is _regular_. Recall
that, for every graph $H_{i}\in{\mathcal{H}}^{1}$, the algorithm from Theorem
5.2 returned a $(\delta_{j-1},d)$\- distancing $(A_{i},B_{i},E^{\prime}_{i})$,
where
$|A_{i}|=|B_{i}|\geq|V(H_{i})|^{1-\delta_{j-1}}=N^{(j-1)(1-\delta_{j-1})}$,
and $|E^{\prime}_{i}|\leq\frac{|A_{i}|}{N^{(j-1)\epsilon^{\prime}}}$.

Let $z^{\prime}=\left\lceil\frac{2\log N}{\epsilon}\right\rceil$. We further
partition the collection ${\mathcal{H}}^{1}$ of graphs into subsets
${\mathcal{H}}^{1}_{0},\ldots,{\mathcal{H}}^{1}_{z^{\prime}}$, where for all
$0\leq z\leq z^{\prime}$, class ${\mathcal{H}}^{1}_{z}$ contains all graphs
$H_{i}\in{\mathcal{H}}^{1}$, for which
$\frac{N^{j-1}}{2^{z+1}}\leq|A_{i}|<\frac{N^{j-1}}{2^{z}}$ holds. Clearly,
there must be an index $0\leq z\leq z^{\prime}$, such that:

$|{\mathcal{H}}^{1}_{z}|\geq\frac{|{\mathcal{H}}^{1}|\cdot\epsilon}{4\log
N}\geq\frac{N^{1-\epsilon^{\prime}}\cdot\epsilon}{4\log N}\geq
N^{1-2\epsilon^{\prime}}.$ (6)

(since $\frac{N^{\epsilon^{\prime}}}{\log N}\geq 2^{128/\epsilon^{5}}$ from
the statement of Theorem 5.2).

From now on we fix this index $z$. Since, for all $H_{i}\in{\mathcal{H}}^{1}$,
$|A_{i}|\geq N^{(j-1)(1-\delta_{j-1})}\geq N^{j-j\delta_{j-1}-1}$, we get
that:

$2^{z}\leq N^{j\delta_{j-1}}.$ (7)

For convenience, we denote by $I\subseteq\left\\{1,\ldots,N\right\\}$ the set
of all indices $i$ with $H_{i}\in{\mathcal{H}}^{1}_{z}$. Next, we apply
Algorithm $\mathsf{ProcPathPeel}$ from Lemma 3.12, to graph $H$, collections
of subsets $\left\\{(A_{i},B_{i})\right\\}_{i\in I}$ of its vertices, length
parameter $d^{\prime}$, and congestion parameter $\eta=N^{8\epsilon^{3}}$.
Consider the resulting collections
$\left\\{{\mathcal{P}}^{q}_{i}\right\\}_{i\in I}$ of paths. Recall that, from
Lemma 3.12, for all $i\in I$, every path in the corresponding set
${\mathcal{P}}^{q}_{i}$ has length at most $d^{\prime}$, and it connects a
vertex of $A_{i}$ to a vertex of $B_{i}$, so that the endpoints of all paths
in ${\mathcal{P}}_{i}$ are distinct. Therefore, we can use the paths in
${\mathcal{P}}^{q}_{i}$ in order to define a partial matching $M_{i}^{q}$
between vertices of $A_{i}$ and vertices of $B_{i}$: a pair $(a,b)\in
A_{i}\times B_{i}$ of vertices is added to $M_{i}^{q}$ iff some path of
${\mathcal{P}}^{q}_{i}$ has endpoints $a,b$. We denote by
$A^{\prime}_{i}\subseteq A_{i}$ and $B^{\prime}_{i}\subseteq B_{i}$ the
subsets of vertices of $A_{i}$ and $B_{i}$ respectively, that do not serve as
endpoints of the paths in ${\mathcal{P}}_{i}^{q}$. Let $E^{*}\subseteq E(H)$
be the set of all edges $e$ that participate in exactly $\eta$ paths of
$\bigcup_{i\in I}{\mathcal{P}}^{q}_{i}$. Recall that Lemma 3.12 further
guarantees that the paths of $\bigcup_{i\in I}{\mathcal{P}}^{q}_{i}$ cause
congestion at most $\eta$ in $H$. Moreover, if we consider graph $H\setminus
E^{*}$, then for all $i\in I$, the length of a shortest path connecting a
vertex of $A^{\prime}_{i}$ to a vertex of $B^{\prime}_{i}$ is greater than
$d^{\prime}$.

Running time of Algorithm $\mathsf{ProcPathPeel}$ is
$O(|E(H)|\cdot(\eta+jNd^{\prime}\log N))\leq
O(|E(H)|\cdot(N^{8\epsilon^{3}}+jNd^{\prime}\log N))\leq O(|E(H)|\cdot
jNd^{\prime}\log N)$, since $|{\mathcal{H}}|=N$.

We say that a graph $H_{i}\in{\mathcal{H}}^{1}_{z}$ is _successful_ if
$|{\mathcal{P}}_{i}^{q}|\geq|A_{i}|/4$, and it is unsuccessful otherwise. We
let ${\mathcal{G}}^{s}\subseteq{\mathcal{H}}^{1}_{z}$ be the collection of all
successful graphs, and
${\mathcal{G}}^{u}={\mathcal{H}}^{1}_{z}\setminus{\mathcal{G}}^{s}$ the
collection of all unsuccessful graphs. For convenience, we also partition the
collection $I$ of indices into a set $I^{s}$ containing all indices $i\in I$
where $H_{i}\in{\mathcal{G}}^{s}$ and $I^{u}=I\setminus I^{s}$. We consider
again two cases, depending on whether
$|{\mathcal{G}}^{s}|\geq|{\mathcal{H}}^{1}_{z}|/2$.

##### Case 1a: $|{\mathcal{G}}^{s}|\geq|{\mathcal{H}}^{1}_{z}|/2$.

If Case 1a happens then we say that iteration $q$ is _successful_. Consider
some index $i\in I^{s}$. Recall that the matching $M_{i}^{q}$ that we have
defined contains at least $|A_{i}|/4$ pairs of vertices (that we refer to as
edges), while $|E^{\prime}_{i}|\leq|A_{i}|/16$ by the definition of
distancing. We discard from $M_{i}^{q}$ all edges that lie in
$E^{\prime}_{i}$; note that $|M_{i}^{q}|\geq|A_{i}|/8$ continues to hold. We
add the edges of the resulting matching $M_{i}^{q}$ to graph $H_{i}$, and we
say that graph $H_{i}$ _received a matching_ in iteration $q$. We view this
matching as the response of the matching player in the Distanced Matching
Game. We let ${\mathcal{P}}^{q}=\bigcup_{i\in I^{s}}{\mathcal{P}}_{i}^{q}$.
Notice that the paths in ${\mathcal{P}}^{q}$ can be viewed as an embedding of
the set $\bigcup_{i\in I^{s}}M_{i}^{q}$ of edges into graph $H$. The length of
each path is at most $d^{\prime}$, and the congestion of the embedding is at
most $\eta$. Observe that, if an iteration is successful, then the number of
graphs in ${\mathcal{H}}$ that receive matchings is at least
$|{\mathcal{G}}^{s}|\geq|{\mathcal{H}}^{1}_{z}|/2\geq
N^{1-2\epsilon^{\prime}}/2$ (from Equation 6). We terminate the current
iteration, and proceed to the next iteration.

##### Case 1b: $|{\mathcal{G}}^{s}|<|{\mathcal{H}}^{1}_{z}|/2$.

If Case 1b happens, then we say that the current iteration is _unsuccessful_.
In this case, we will construct a $(\delta_{j},d)$-distancing $(A,B,E^{*})$ in
graph $H$, where $E^{*}$ is the set of edges that we have defined above. We
will ensure that $|E^{*}|\leq|A|/N^{j\epsilon^{4}}$. The current iteration
then becomes the last iteration of the algorithm, and we return $(A,B,E^{*})$
as its output. We need the following simple observation bounding $|E^{*}|$:

######  Observation 6.1.

$|E^{*}|\leq\frac{N^{j}\cdot d^{\prime}}{\eta\cdot 2^{z}}$.

###### Proof.

Note that for every graph $H_{i}\in{\mathcal{H}}^{1}_{z}$,
$|{\mathcal{P}}^{q}_{i}|\leq|A_{i}|\leq\frac{N^{j-1}}{2^{z}}$. Since the
length of each such path is at most $d^{\prime}$, the total number of edges on
all paths in $\bigcup_{i\in I}{\mathcal{P}}^{q}_{i}$ is $\sum_{i\in
I}\sum_{P\in{\mathcal{P}}_{i}^{q}}|E(P)|\leq
d^{\prime}\cdot|{\mathcal{H}}^{1}_{z}|\cdot\frac{N^{j-1}}{2^{z}}\leq\frac{N^{j}\cdot
d^{\prime}}{2^{z}}$ (as $|{\mathcal{H}}^{1}_{z}\leq N$). Since set $E^{*}$
only contains edges that lie on $\eta$ path of ${\mathcal{P}}^{q}$, the
observation follows.

Recall that, if $H_{i}\in{\mathcal{G}}^{u}$, then
$|A^{\prime}_{i}|\geq\frac{|A_{i}|}{2}\geq\frac{N^{j-1}}{2^{z+2}}$. Recall
also that $|B^{\prime}_{i}|=|A^{\prime}_{i}|$, and $\mbox{\sf
dist}_{H\setminus E^{*}}(A^{\prime}_{i},B^{\prime}_{i})>d^{\prime}$.

We denote $T=\bigcup_{i\in I^{u}}(A^{\prime}_{i}\cup B^{\prime}_{i})$, and we
call the vertices of $T$ _terminals_. Since we have assumed that
$|{\mathcal{G}}^{s}|<|{\mathcal{H}}^{1}_{z}|/2$, we get that:

$|T|\geq|{\mathcal{G}}^{u}|\cdot\frac{N^{j-1}}{2^{z+1}}\geq|{\mathcal{H}}^{1}_{z}|\cdot\frac{N^{j-1}}{2^{z+2}}\geq\frac{N^{j-2\epsilon^{\prime}}}{2^{z+2}}.$
(8)

(we have used Equation 6.)

We need the following simple observation.

######  Observation 6.2.

For every terminal $t\in T$, at most $|T|/2$ terminals may lie in
$B_{H\setminus E^{*}}(t,d^{\prime}/2)$.

###### Proof.

Consider any terminal $t\in T$, and denote $B^{t}=B_{H\setminus
E^{*}}(t,d^{\prime}/2)$. Recall that for all
$H_{i^{\prime}}\in{\mathcal{G}}^{u}$, $\mbox{\sf dist}_{H\setminus
E^{*}}(A^{\prime}_{i^{\prime}},B^{\prime}_{i^{\prime}})>d^{\prime}$.
Therefore, $B^{t}$ may not contain a vertex of $A^{\prime}_{i^{\prime}}$ and a
vertex of $B^{\prime}_{i^{\prime}}$. We conclude that, for every terminal
$t\in T$, $|B^{t}\cap T|\leq|T|/2$.

We apply Algorithm $\mathsf{ProcSeparate}$ from Lemma 3.10 to graph
$G=H\setminus E^{*}$, the set $T$ of terminals, distance parameters $d$ and
$\Delta$ that remain unchanged, and $\alpha=1/2$. The running time of the
algorithm is $O(|E(H)|\cdot|V(H)|^{64/\Delta})\leq O(|E(H)|\cdot
N^{j\epsilon^{\prime}})$.

From 6.2, the algorithm may not return a terminal $t\in T$ with
$|B_{H\setminus E^{*}}(t,\Delta\cdot d)\cap T|=|B_{H\setminus
E^{*}}(t,d^{\prime}/2)\cap T|>\alpha\cdot|T|$. Therefore, it must compute two
subsets $T_{1},T_{2}$ of terminals, with $|T_{1}|=|T_{2}|$, such that for
every pair $t\in T_{1},t^{\prime}\in T_{2}$ of terminals, $\mbox{\sf
dist}_{H\setminus E^{*}}(t,t^{\prime})\geq d$. Moreover:

$\begin{split}|T_{1}|\geq\frac{|T|^{1-64/\Delta}}{3}\geq\frac{|T|^{1-\epsilon^{\prime}}}{3}\geq\frac{N^{(j-2\epsilon^{\prime})(1-\epsilon^{\prime})}}{3\cdot
2^{(z+2)(1-\epsilon^{\prime})}}\geq\frac{N^{j-2j\epsilon^{\prime}}}{2^{z+4}}\end{split}$

(we have used the fact that $\Delta=64/\epsilon^{\prime}$, and Equation 8).

Recall that, from 6.1, $|E^{*}|\leq\frac{N^{j}\cdot d^{\prime}}{\eta\cdot
2^{z}}$. Recall also that $\eta=N^{8\epsilon^{3}}$, $j\leq\left\lceil
1/\epsilon\right\rceil$, and $d^{\prime}\leq 2^{64/\epsilon^{4}\leq
N^{\epsilon^{\prime}}}$ from Inequality 5, and since
$\frac{N^{\epsilon^{\prime}}}{\log N}\geq 2^{128/\epsilon^{5}}$ from the
statement of Theorem 5.2. Therefore, we get that:

$\begin{split}|E^{*}|\leq\frac{N^{j}}{2^{z}}\cdot\frac{N^{\epsilon^{4}}}{N^{8\epsilon^{3}}}\leq\frac{N^{j}}{2^{z+4}}\cdot\frac{1}{N^{6\epsilon^{3}}}\leq\frac{N^{j}}{2^{z+4}}\cdot\frac{1}{N^{3\epsilon^{4}\cdot\left\lceil
1/\epsilon\right\rceil}}\leq\frac{N^{j}}{2^{z+4}}\cdot\frac{1}{N^{3\epsilon^{\prime}j}}\leq\frac{|T_{1}|}{N^{j\epsilon^{\prime}}}.\end{split}$

Lastly, recall that we have shown in Inequality 7, that $2^{z}\leq
N^{j\delta_{j-1}}$. Therefore, we get that:

$|T_{1}|\geq\frac{N^{j}}{16N^{j(2\epsilon^{\prime}+\delta_{j-1})}}\geq\frac{N^{j}}{16N^{j(4(j-1)\epsilon^{\prime}+2\epsilon^{\prime})}}\geq\frac{N^{j}}{N^{j(4j\epsilon^{\prime})}}=N^{j(1-\delta_{j})}.$

We conclude that $(T_{1},T_{2},E^{*})$ is a $(\delta_{j},d)$-distancing, with
$|E^{*}|\leq|T_{1}|/N^{j\epsilon^{\prime}}$ as required. We return this
distancing and terminate the algorithm.

##### Case 2: $|{\mathcal{H}}^{1}|\leq N^{1-\epsilon^{\prime}}$.

If this case happens, then we say that the current iteration is _irregular_.
In this case, we terminate Phase 1. The outcome of the phase is the collection
${\mathcal{H}}^{2}\subseteq{\mathcal{H}}$ of at least
$N-N^{1-\epsilon^{\prime}}$ graphs. Recall that, for each graph
$H_{i}\in{\mathcal{H}}^{2}$, we computed a level-$(j-1)$ Hierarchical Support
Structure, that includes a subset $S(H_{i})\subseteq V(H_{i})$ of vertices,
such that $H_{i}$ is $(\eta_{j-1},\tilde{d}_{j-1})$-well-connected with
respect to $S(H_{i})$. Let
$H^{\prime}=\bigcup_{H_{i}\in{\mathcal{H}}^{2}}H_{i}$. Notice that the sets
${\mathcal{P}}^{q}$ of paths that are computed in each iteration provide an
embedding of graph $H^{\prime}$ into $H$. The length of each resulting path is
bounded by $d^{\prime}$. We use the following observation in order to both
bound the congestion of this embedding, and the running time of the algorithm.

######  Observation 6.3.

At the end of Phase 1, for each graph $H_{i}\in{\mathcal{H}}$, $|E(H_{i})|\leq
N^{j-1+32\epsilon^{2}}$. The number of iterations in Phase 1 is at most
$N^{64\epsilon^{2}}$.

###### Proof.

Recall first that $\delta_{j-1}=4(j-1)\epsilon^{\prime}\geq 4\epsilon^{4}$,
while $d=2^{32/\epsilon^{4}}$. Therefore, $d\geq 2^{4/\delta_{j-1}}$ holds. We
can then view our algorithm from Phase 1 as running the Distanced Matching
Game simultaneously over the graphs in ${\mathcal{H}}$. Note that for every
graph $H_{i}\in{\mathcal{H}}$:

$|V(H_{i})|^{\delta_{j-1}}=N^{(j-1)\delta_{j-1}}\geq
N^{4\epsilon^{\prime}}\geq\frac{2^{128}\log
N}{\epsilon^{11}}\geq\frac{2^{124}\log
N}{16(\epsilon^{\prime})^{2}\epsilon^{3}}\geq\frac{2^{14}(j-1)\log
N}{\delta_{j-1}^{2}}=\frac{2^{14}\log(|V(H_{i})|)}{\delta_{j-1}^{2}},$

since $\delta_{j-1}=4(j-1)\epsilon^{\prime}$, $2\leq j\leq\left\lceil
1/\epsilon\right\rceil$, and $\frac{N^{\epsilon^{4}}}{\log N}\geq
2^{128/\epsilon^{5}}$ from the statement of Theorem 5.2. We conclude that
$|V(H_{i})|^{\delta_{j-1}}\geq\frac{2^{14}\log(|V(H_{i})|)}{\delta_{j-1}^{2}}$
holds, satisfying the conditions of Theorem 4.2. From Theorem 4.2, the number
of iterations in a Distanced Matching Game in a single graph
$H_{i}\in{\mathcal{H}}$ is bounded by:

$|V(H_{i})|^{8\delta_{j-1}}\leq N^{(j-1)\cdot 8\delta_{j-1}}\leq
N^{32(j-1)^{2}\epsilon^{\prime}}\leq N^{32\epsilon^{2}},$

since $\epsilon^{\prime}=\epsilon^{4}$,
$\delta_{j-1}=4(j-1)\epsilon^{\prime}$, and $j\leq\left\lceil
1/\epsilon\right\rceil$. Therefore, a graph $H_{i}\in{\mathcal{H}}$ may
receive a matching in at most $N^{32\epsilon^{2}}$ iterations, and the
cardinality of each such matching is at most $|V(H_{i})|/2\leq N^{j-1}/2$. We
conclude that at the end of Phase 1, for each graph $H_{i}\in{\mathcal{H}}$,
$|E(H_{i})|\leq N^{j-1}\cdot N^{32\epsilon^{2}}$.

Next, we bound the number of iterations in Phase 1. Note that at most one
iteration of Phase 1 may be irregular, and at most one iteration may be
regular and unsuccessful. It is now enough to bound the number of regular and
successful iterations. In every regular and successful iteration, at least
$N^{1-2\epsilon^{\prime}}/2$ graphs in ${\mathcal{H}}$ receive matchings.
Therefore, every regular and successful iteration of Phase 1 results in the
completion of a single iteration of the Distanced Matching Game in at least
$N^{1-2\epsilon^{\prime}}/2$ graphs of ${\mathcal{H}}$. At the same time, the
number of pairs $(i,q)$, where graph $H_{i}\in{\mathcal{H}}$ receives a
matching in iteration $q$ must be bounded by $|{\mathcal{H}}|\cdot
N^{32\epsilon^{2}}\leq N^{1+32\epsilon^{2}}$. Since in every regular and
successful iteration at least $N^{1-2\epsilon^{\prime}}/2$ graphs in
${\mathcal{H}}$ receive matchings, we get that the number of iterations is
bounded by $2N^{32\epsilon^{2}+2\epsilon^{\prime}}\leq N^{64\epsilon^{2}}$.

Since every set ${\mathcal{P}}^{q}$ of paths causes congestion at most
$\eta=N^{8\epsilon^{3}}$, and the number of iterations is bounded by
$N^{64\epsilon^{2}}$, we obtain an embedding of graph $H^{\prime}$ into $H$
via paths of length at most $d^{\prime}\leq 2^{64/\epsilon^{4}}$ (from
Equation 5), that cause total congestion at most $N^{64\epsilon^{2}}\cdot
N^{8\epsilon^{3}}\leq N^{128\epsilon^{2}}$. We denote this embedding by
${\mathcal{P}}$.

Note that the Phase 1 can either terminate with a regular unsuccessful
iteration, in which case we terminate the algorithm and return the resulting
distancing for graph $H$, or with an irregular iteration, in which case we
proceed to Phase 2 of the algorithm. Before we describe Phase 2 of the
algorithm, we analyze the running time of Phase 1.

#### Running Time Analysis of Phase 1.

We start by bounding the running time of a single iteration. Over the course
of the iteration, we apply the algorithm from Theorem 5.2 to each of the
graphs $H_{i}\in{\mathcal{H}}$, with parameter $(j-1)$. Recall that, from 6.3,
for each graph $H_{i}\in{\mathcal{H}}$, $|E(H_{i})|\leq
N^{j-1+32\epsilon^{2}}$. From the induction hypothesis, the running time of
the algorithm from Theorem 5.2 on a single graph $H_{i}\in{\mathcal{H}}$ is
bounded by:

$\begin{split}c(j-1)\cdot N^{(j-1)(1+64\epsilon^{2})+7}&+c|E(H_{i})|\cdot
N^{6}\\\ &\leq c(j-1)\cdot
N^{j+64(j-1)\epsilon^{2}+6}+cN^{j-1+32\epsilon^{2}}\cdot N^{6}\\\
&=c(j-1)\cdot N^{j+64(j-1)\epsilon^{2}+6}+cN^{j+5+32\epsilon^{2}}.\\\ &\leq
cj\cdot N^{j+64(j-1)\epsilon^{2}+6}.\end{split}$

Since $|{\mathcal{H}}|=N$, the running time of this part of the algorithm is
bounded by:

$cj\cdot N^{j+64(j-1)\epsilon^{2}+7}$

If the iteration is regular, then we apply Algorithm $\mathsf{ProcPathPeel}$
from Lemma 3.12, to graph $H$, collections of subsets
$\left\\{(A_{i},B_{i})\right\\}_{i\in I}$ of its vertices, length parameter
$d^{\prime}$, and congestion parameter $\eta=N^{8\epsilon^{3}}$. As observed
above, the running time of Algorithm $\mathsf{ProcPathPeel}$ is $O(|E(H)|\cdot
jNd^{\prime}\log N)=O(|E(H)|\cdot N\cdot 2^{64/\epsilon^{4}}\cdot\log
N/\epsilon)\leq O(|E(H)|\cdot N^{2})$, since $d^{\prime}\leq
2^{64/\epsilon^{4}}$ from Equation 5 and
$N^{\epsilon^{\prime}}>2^{64/\epsilon^{5}}\cdot\log N$ from the statement of
Theorem 5.2.

If the iteration is regular and unsuccessful, then we apply Algorithm
$\mathsf{ProcSeparate}$ from Lemma 3.10, whose running time, as observed
above, is bounded by $O(|E(H)|\cdot N^{j\epsilon^{\prime}})\leq O(|E(H)|\cdot
N^{2\epsilon^{3}})$, as $j\leq\left\lceil 1/\epsilon\right\rceil$ and
$\epsilon^{\prime}=\epsilon^{4}$.

Overall, the running time of a single iteration is bounded by:

$cj\cdot N^{j+64(j-1)\epsilon^{2}+7}+O\left(|E(H)|\cdot N^{2}\right).$

Since, from 6.3, the number of iterations in Phase 1 is at most
$N^{64\epsilon^{2}}$, we get that the total running time of Phase 1 is bounded
by:

$cj\cdot N^{j+64j\epsilon^{2}+7}+O\left(|E(H)|\cdot N^{3}\right).$

###  6.2 Phase 2: Distancing or Well-Connectedness

The starting point of Phase 2 is the collection
${\mathcal{H}}^{2}\subseteq{\mathcal{H}}$ of at least
$N-N^{1-\epsilon^{\prime}}$ graphs that was computed in Phase 1. Recall that,
for each graph $H_{i}\in{\mathcal{H}}_{2}$, we computed a level-$(j-1)$
Hierarchical Support Structure, that includes a subset $S(H_{i})\subseteq
V(H_{i})$ of vertices, such that $H_{i}$ is
$(\eta_{j-1},\tilde{d}_{j-1})$-well-connected with respect to $S(H_{i})$.
Additionally, we have computed an embedding ${\mathcal{P}}$ of graph
$H^{\prime}=\bigcup_{H_{i}\in{\mathcal{H}}^{2}}H_{i}$, so that the length of
each path in ${\mathcal{P}}$ is at most $d^{\prime}\leq 2^{64/\epsilon^{4}}$,
and the paths in ${\mathcal{P}}$ cause congestion at most
$N^{128\epsilon^{2}}$.

In this phase we will either compute a subset
${\mathcal{H}}^{\prime}\subseteq{\mathcal{H}}^{2}$ of $r$ graphs, such that
graph $H$ is $(\eta_{j},\tilde{d}_{j})$-well-connected with respect to the set
$S(H)=\bigcup_{H_{i}\in{\mathcal{H}}^{\prime}}S(H_{i})$ of vertices; or we
compute a $(\delta_{j},d)$-distancing $(A,B,E^{\prime})$ in graph $H$, with
$|E^{\prime}|\leq\frac{|A|}{N^{j\epsilon^{4}}}$.

We consider every pair $H_{i},H_{i^{\prime}}\in{\mathcal{H}}^{2}$ of graphs,
with $i<i^{\prime}$ one by one. When the pair $(H_{i},H_{i^{\prime}})$ of
graphs is considered, we apply Procedure $\mathsf{ProcPathPeel}$ from Lemma
3.12 to graph $H$, and two sets $A_{1}=S(H_{i}),B_{1}=S(H_{i^{\prime}})$ of
its vertices, with distance parameter $d^{\prime}$ and congestion parameter
$\eta=N^{4}$. Recall that the running time of the procedure is
$O(|E(H)|(N^{4}+jd^{\prime}\log N))\leq O(|E(H)|\cdot N^{4})$. We denote by
${\mathcal{Q}}_{i,i^{\prime}}$ the set of paths that the algorithm returns,
and by $E^{\prime}_{i,i^{\prime}}$ the set of all edges of $H$ that
participate in $N^{4}$ paths of ${\mathcal{Q}}_{i,i^{\prime}}$. We also denote
by $A^{\prime}_{i,i^{\prime}}\subseteq S(H_{i})$ and
$B^{\prime}_{i,i^{\prime}}\subseteq S(H_{i^{\prime}})$ the sets of vertices
that do not serve as endpoints of paths in ${\mathcal{Q}}_{i,i^{\prime}}$.
Recall that the paths in ${\mathcal{Q}}_{i,i^{\prime}}$ have length at most
$d^{\prime}$ each, and they cause congestion at most $N^{4}$. Every path in
${\mathcal{Q}}_{i,i^{\prime}}$ connects a vertex of $S(H_{i})$ to a vertex of
$S(H_{i^{\prime}})$, and every vertex of $S(H_{i})\cup S(H_{i^{\prime}})$ may
serve as an endpoint of at most one path in ${\mathcal{Q}}_{i,i^{\prime}}$.
Moreover, the length of the shortest path in $H\setminus
E^{\prime}_{i,i^{\prime}}$ connecting a vertex of $A^{\prime}_{i,i^{\prime}}$
to a vertex of $B^{\prime}_{i,i^{\prime}}$ is greater than $d^{\prime}$.
Observe also that, since
$|{\mathcal{Q}}_{i,i^{\prime}}|\leq|S(H_{i})|\leq|V(H_{i})|=N^{j-1}$, and
since the length of every path in ${\mathcal{Q}}_{i,i^{\prime}}$ is at most
$d^{\prime}$, we get that $\sum_{Q\in{\mathcal{Q}}_{i,i^{\prime}}}|E(Q)|\leq
d^{\prime}\cdot N^{j-1}$. Since $E^{\prime}_{i,i^{\prime}}$ only contains
edges that participate in $N^{4}$ paths in ${\mathcal{Q}}$, we get that
$|E^{\prime}_{i,i^{\prime}}|\leq d^{\prime}\cdot N^{j-5}$.

Let $E^{\prime}$ be the union of all sets $E^{\prime}_{i,i^{\prime}}$ of
edges, over all pairs $H_{i},H_{i^{\prime}}\in{\mathcal{H}}^{2}$ of graphs
with $i<i^{\prime}$. Clearly, $|E^{\prime}|\leq d^{\prime}\cdot N^{j-3}$.
Moreover, for every pair $H_{i},H_{i^{\prime}}\in{\mathcal{H}}^{2}$ of graphs
with $i<i^{\prime}$, the length of the shortest path in $H\setminus
E^{\prime}$ connecting a vertex of $A^{\prime}_{i,i^{\prime}}$ to a vertex of
$B^{\prime}_{i,i^{\prime}}$ is greater than $d^{\prime}$.

Next, we apply procedure $\mathsf{ProcSeparate}$ from Lemma 3.10 to graph
$\tilde{H}=H\setminus E^{\prime}$, with the set $T=V(H)$ of terminal vertices,
distance parameters $d$ and $\Delta$ that remain unchanged, and parameter
$\alpha=1-\frac{1}{8N^{\epsilon^{\prime}}}$. Recall that the running time of
the algorithm is $O(|E(H)|\cdot N^{64j/\Delta})\leq O(|E(H)|\cdot
N^{2\epsilon^{3}})$ (since $\Delta=64/\epsilon^{\prime}$, $j\leq\left\lceil
1/\epsilon\right\rceil$, and $\epsilon^{\prime}=\epsilon^{4}$).

We now consider two cases. The first case is that Procedure
$\mathsf{ProcSeparate}$ returns two subsets $A,B\subseteq V(H)$ of vertices,
such that $|A|=|B|$, and for every pair $v\in A,u\in B$ of vertices,
$\mbox{\sf dist}_{\tilde{H}}(u,v)\geq d$. Recall that in this case, the
algorithm also ensures that:

$\begin{split}|A|&\geq|V(H)|^{1-64/\Delta}\cdot\min\left\\{(1-\alpha),\frac{1}{3}\right\\}\\\
&\geq N^{j(1-\epsilon^{\prime})}\cdot\frac{1}{8N^{\epsilon^{\prime}}}\\\ &\geq
N^{j(1-\epsilon^{\prime})-2\epsilon^{\prime}}\\\ &\geq
N^{j(1-4j\epsilon^{\prime})}\\\ &=|V(H)|^{1-\delta_{j}}.\end{split}$ (9)

(We have used the fact that $\Delta=64/\epsilon^{\prime}$ and
$\delta_{j}=4j\epsilon^{\prime}$).

Recall that:

$|E^{\prime}|\leq d^{\prime}\cdot N^{j-3}\leq N^{j-3+\epsilon^{\prime}}.$

(since $d^{\prime}\leq 2^{64/\epsilon^{3}}$ from Equation 5 and
$N^{\epsilon^{4}}\geq 2^{128/\epsilon^{5}}$ from the statement of Theorem
5.2.) Since, from Equation 9, $|A|\geq
N^{j-j\epsilon^{\prime}-2\epsilon^{\prime}}\geq N^{j-3\epsilon^{3}}$ (as
$\epsilon^{\prime}=\epsilon^{4}$), we get that
$|E^{\prime}|\leq|A|/N^{j\epsilon^{4}}$.

We conclude that $(A,B,E^{\prime})$ is a valid $(\delta_{j},d)$-distancing in
graph $H$, with $|E^{\prime}|\leq|A|/N^{j\epsilon^{4}}$. We return this
distancing and terminate the algorithm.

From now on we assume that Procedure $\mathsf{ProcSeparate}$ computed a vertex
$v\in V(H)$, such that $|B_{\tilde{H}}(v,\Delta\cdot
d)|>\alpha\cdot|V(H)|=N^{j}\cdot\left(1-\frac{1}{8N^{\epsilon^{\prime}}}\right)$.
For convenience, we denote $B^{*}=B_{\tilde{H}}(v,\Delta\cdot d)$.

In this case, we construct a set
${\mathcal{H}}^{\prime}\subseteq{\mathcal{H}}^{2}$ of graphs as follows: we
add graph $H_{i}$ to ${\mathcal{H}}^{\prime}$ iff $|B^{*}\cap
V(H_{i})|\geq\frac{7|V(H_{i})|}{8}$. We need the following observation.

######  Observation 6.4.

$|{\mathcal{H}}^{\prime}|\geq N-2N^{1-\epsilon^{\prime}}$.

###### Proof.

Recall that $|{\mathcal{H}}^{2}|\geq N-N^{1-\epsilon^{\prime}}$. Notice that,
if $H_{i}\in{\mathcal{H}}^{2}\setminus{\mathcal{H}}^{\prime}$, then
$|V(H_{i})\setminus B^{*}|\geq|V(H_{i})|/8=N^{j-1}/8$. Since $|V(H)\setminus
B^{*}|\leq N^{j-\epsilon^{\prime}}/8$, we get that
$|{\mathcal{H}}^{2}\setminus{\mathcal{H}}^{\prime}|\leq\frac{N^{j-\epsilon^{\prime}}/8}{N^{j-1}/8}=N^{1-\epsilon^{\prime}}$.
Therefore,
$|{\mathcal{H}}^{\prime}|\geq|{\mathcal{H}}^{2}|-N^{1-\epsilon^{\prime}}\geq
N-2N^{1-\epsilon^{\prime}}$.

We discard arbitrary graphs from ${\mathcal{H}}^{\prime}$, until
$|{\mathcal{H}}^{\prime}|=N-\left\lceil 2N^{1-\epsilon^{\prime}}\right\rceil$
holds. Let $S(H)=\bigcup_{H_{i}\in{\mathcal{H}}^{\prime}}S(H_{i})$. Note that
we have now obtained a level-$j$ Hierarchical Support Structure for graph $H$,
whose associated collection of graphs is ${\mathcal{H}}^{\prime}$, with
$|{\mathcal{H}}^{\prime}|=N-\left\lceil
2N^{1-\epsilon^{\prime}}\right\rceil=r$. We use the embedding ${\mathcal{P}}$
of the graph $\bigcup_{H_{i}\in{\mathcal{H}}^{2}}H_{i}$ that we have computed
in Phase 1. By discarding paths that are no longer needed from
${\mathcal{P}}$, we obtain an embedding ${\mathcal{P}}$ of graph
$\bigcup_{H_{i}\in{\mathcal{H}}^{\prime}}H_{i}$ into $H$, such that every path
in the embedding has length at most $d^{\prime}\leq 2^{64/\epsilon^{4}}$, and
the paths in ${\mathcal{P}}$ cause congestion at most $N^{128/\epsilon^{3}}$.
We prove the following lemma in Section 6.3.

######  Lemma 6.5.

Graph $H$ is $(\eta_{j},\tilde{d}_{j})$-well-connected with respect to $S(H)$.

In order to complete the proof of Theorem 5.2, it is now enough to show that
the running time of the algorithm is suitably bounded.

#### Running Time Analysis

The algorithm performs at most $N^{2}$ calls to Procedure
$\mathsf{ProcPathPeel}$. As observed above, the running time of each such call
is at most $O(|E(H)|\cdot N^{4})$. The running time of Procedure
$\mathsf{ProcSeparate}$, as shown above, is at most $O(|E(H)|\cdot
N^{2\epsilon^{3}})$. Overall, the running time of Phase 2 is $O(|E(H)|\cdot
N^{6})$.

Altogether, the running time of the whole algorithm is bounded by:

$cj\cdot N^{j+64j\epsilon^{2}+7}+O\left(|E(H)|\cdot N^{6}\right)\leq cj\cdot
N^{j(1+64\epsilon^{2})+7}+c|E(H)|\cdot N^{6},$

if $c$ is a large enough constant.

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

###  6.3 Proof of Lemma 6.5

We will use the following simple observation.

######  Observation 6.6.

For every pair $H_{i},H_{i^{\prime}}\in{\mathcal{H}}^{\prime}$ with
$i<i^{\prime}$, $|{\mathcal{Q}}_{i,i^{\prime}}|\geq N^{j-1}/4$. (Here,
${\mathcal{Q}}_{i,i^{\prime}}$ is the set of paths that was computed in Phase
2 of the algorithm.)

###### Proof.

Recall that, from 5.1, $|V(H_{i})\setminus
S(H_{i})|\leq|V(H_{i})|\cdot\frac{4(j-1)}{N^{\epsilon^{4}}}<\frac{|V(H_{i})|}{64}$
(since $j\leq\left\lceil\frac{1}{\epsilon}\right\rceil$). Therefore,
$|S(H_{i})|\geq\frac{63|V(H_{i})|}{64}=\frac{63\cdot N^{j-1}}{64}$, and
similarly, $|S(H_{i^{\prime}})|\geq\frac{63\cdot N^{j-1}}{64}$.

Assume now for contradiction that
$|{\mathcal{Q}}_{i,i^{\prime}}|<\frac{N^{j-1}}{4}$. Recall that we have
defined sets $A^{\prime}_{i,i^{\prime}}\subseteq S(H_{i})$ and
$B^{\prime}_{i,i^{\prime}}\subseteq S(H_{i^{\prime}})$ of vertices that do not
serve as endpoints of paths in ${\mathcal{Q}}_{i,i^{\prime}}$. If
$|{\mathcal{Q}}_{i,i^{\prime}}|<\frac{N^{j-1}}{4}$, then:

$|A^{\prime}_{i,i^{\prime}}|\geq|S(H_{i})|-|{\mathcal{Q}}_{i,i^{\prime}}|\geq\frac{63\cdot
N^{j-1}}{64}-\frac{N^{j-1}}{4}>\frac{2\cdot N^{j-1}}{3}.$

Similarly, $|B^{\prime}_{i,i^{\prime}}|>\frac{2\cdot N^{j-1}}{3}$. Since
$H_{i}$ was added to ${\mathcal{H}}^{\prime}$, $|B^{*}\cap
V(H_{i})|\geq\frac{7\cdot N^{j-1}}{8}$. So at least one vertex $u\in
A^{\prime}_{i,i^{\prime}}$ must lie in $B^{*}$. For similar reasons, at least
one vertex $u^{\prime}\in B^{\prime}_{i,i^{\prime}}$ must lie in $B^{*}$. From
the definition of $B^{*}$, $\mbox{\sf dist}_{\tilde{H}}(u,u^{\prime})\leq
2\Delta\cdot d=d^{\prime}$. Recall however that $\tilde{H}=H\setminus
E^{\prime}$, and $E^{\prime}_{i,i^{\prime}}\subseteq E^{\prime}$. Procedure
$\mathsf{ProcPathPeel}$ guarantees that the shortest path connecting $u$ to
$u^{\prime}$ in graph $H\setminus E^{\prime}_{i,i^{\prime}}$ has length
greater than $d^{\prime}$. So $\mbox{\sf
dist}_{\tilde{H}}(u,u^{\prime})>d^{\prime}$ must hold, contradicting our
previous claim that $\mbox{\sf dist}_{\tilde{H}}(u,u^{\prime})\leq
d^{\prime}$.

We now turn to the proof of Lemma 6.5. We assume that we are given two
disjoint equal-cardinality subsets $A,B$ of vertices of $S(H)$. Our goal is to
prove that there exists a set ${\mathcal{P}}^{*}$ of paths in graph $H$,
routing every vertex of $A$ to a distinct vertex of $B$, such that the paths
in ${\mathcal{P}}^{*}$ cause congestion at most $\eta_{j}$ in $H$, and the
length of every path is at most $\tilde{d}_{j}$. We will prove that such a set
of paths exists by exploiting the fact that, every graph
$H_{i}\in{\mathcal{H}}^{\prime}$ is $(\eta_{j-1},\tilde{d}_{j-1})$-well-
connected with respect to the set $S(H_{i})$ of its vertices, together with
the embedding of these graphs into $H$, and the sets
${\mathcal{Q}}_{i,i^{\prime}}$ of paths that we have computed in Phase 2 of
the algorithm for every pair $H_{i},H_{i^{\prime}}\in{\mathcal{H}}^{\prime}$
of graphs with $i<i^{\prime}$.

The remainder of the proof of Lemma 6.5 consists of three steps. In the first
step, we route some pairs in $A\times B$ within the graphs
$H_{i}\in{\mathcal{H}}^{\prime}$. After the completion of this step, for every
graph $H_{i}\in{\mathcal{H}}^{\prime}$, either all vertices of $S(H_{i})$ that
remain to be routed lie in $A$, or all such vertices lie in $B$. In the
remaining two steps we complete the routing of these remaining vertices.
Specifically, in Step 2 we define a “meta-graph” $\hat{G}$, whose vertices
represent the graphs $H_{i}\in{\mathcal{H}}^{\prime}$, with weights on its
edges. Intuitively, if an edge connecting two vertices that represent graphs
$H_{i}$ and $H_{i^{\prime}}$ has weight $w(e)$, then we intend to construct
$w(e)$ paths that connect vertices of $S(H_{i})\cap A$ to vertices of
$S(H_{i^{\prime}})\cap B$. In this step, we also perform a “global routing”:
for every pair $H_{i},H_{i^{\prime}}\in{\mathcal{H}}^{\prime}$ of graphs,
whose corresponding edge in $\hat{G}$ has weight $w$, we connect vertices of
$S(H_{i})$ to vertices of $S(H_{i^{\prime}})$ with $w$ paths. In the third and
the final step, we complete the construction of the set ${\mathcal{P}}^{*}$ of
paths by using “local routing”, in which some pairs of vertex subsets are
routed within each graph $H_{i}\in{\mathcal{H}}^{\prime}$. We now describe
each of the three steps in turn.

#### Step 1: Initial Routing within the Graphs of ${\mathcal{H}}^{\prime}$

We process every graph $H_{i}\in{\mathcal{H}}^{\prime}$ one by one. When graph
$H_{i}$ is processed, we denote $N^{A}_{i}=|A\cap S(H_{i})|$ and
$N^{B}_{i}=|B\cap S(H_{i})|$. Denote
$\beta_{i}=\min\left\\{N^{A}_{i},N^{B}_{i}\right\\}$. Next, we select two
arbitrary subsets $X_{i}\subseteq A\cap S(H_{i})$ and $Y_{i}\subseteq B\cap
S(H_{i})$, each of which contains exactly $\beta_{i}$ vertices. Since our
algorithm ensures that graph $H_{i}$ is $(\eta_{j-1},\tilde{d}_{j-1})$-well-
connected with respect to $S(H_{i})$, there exists a set ${\mathcal{R}}_{i}$
of paths in graph $H_{i}$, which is a one-to-one routing of vertices of
$X_{i}$ to vertices of $Y_{i}$. Every path in ${\mathcal{R}}_{i}$ has length
at most $\tilde{d}_{j-1}$, and the paths in ${\mathcal{R}}_{i}$ cause
congestion at most $\eta_{j-1}$ in $H_{i}$.

Let $H^{\prime}=\bigcup_{H_{i}\in{\mathcal{H}}^{\prime}}H_{i}$. Recall that we
have computed, in Phase 1 of the algorithm, an embedding ${\mathcal{P}}$ of
$H^{\prime}$ into $H$, where every path in the embedding has length at most
$d^{\prime}$, and the paths in ${\mathcal{P}}$ cause congestion at most
$N^{128\epsilon^{2}}$ in $H$.

Consider now the set
$\bigcup_{H_{i}\in{\mathcal{H}}^{\prime}}{\mathcal{R}}_{i}$ of paths in graph
$H^{\prime}$. This set of paths defines a one-to-one routing of vertex set
$X=\bigcup_{H_{i}\in{\mathcal{H}}^{\prime}}X_{i}$ to vertex set
$Y=\bigcup_{H_{i}\in{\mathcal{H}}^{\prime}}Y_{i}$, where the length of every
path is at most $\tilde{d}_{j-1}$, and the paths in ${\mathcal{R}}$ cause
congestion at most $\eta_{j-1}$ in $H^{\prime}$. We now use the embedding
${\mathcal{P}}$ of $H^{\prime}$ into $H$ in order to compute a set
${\mathcal{P}}^{\prime}$ of paths in graph $H$, that route every vertex of $X$
to a distinct vertex of $Y$, via the algorithm from 3.1. We are then
guaranteed that the length of every path in ${\mathcal{P}}^{\prime}$ is at
most $\tilde{d}_{j-1}\cdot d^{\prime}$. Recall that
$\tilde{d}_{j-1}=2^{c(j-1)/\epsilon^{4}}$, while $d^{\prime}<\frac{1}{4}\cdot
2^{c/\epsilon^{4}}$ from Inequality 5. Therefore, the length of every path in
${\mathcal{P}}^{\prime}$ is bounded by:

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

The algorithm from 3.1 also guarantees that the congestion caused by the paths
in ${\mathcal{P}}^{\prime}$ in $H$ is at most $\eta_{j-1}\cdot
N^{128\epsilon^{2}}$. Since $\eta_{j-1}=N^{6+256(j-1)\epsilon^{2}}$, we get
that the congestion caused by the paths in ${\mathcal{P}}^{\prime}$ is bounded
by:

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

We have now obtained a set ${\mathcal{P}}^{\prime}$ of paths in graph $H$,
that routes every vertex of $X$ to a distinct vertex of $Y$, so that the
length of every path is at most $\tilde{d}_{j}$, and the congestion caused by
the paths in ${\mathcal{P}}^{\prime}$ is bounded by $\eta_{j}/2$.

We partition the graphs of ${\mathcal{H}}^{\prime}$ into three subsets. Set
${\mathcal{H}}^{N}$ contains all graphs $H_{i}\in{\mathcal{H}}^{\prime}$, in
which $N_{i}^{A}=N_{i}^{B}$. We no longer need to route any vertices in such
graphs, as for each such graph $\beta_{i}=N^{A}_{i}=N^{B}_{i}$; $X_{i}=A\cap
S(H_{i})$; and $Y_{i}=B\cap S(H_{i})$ must hold. Set ${\mathcal{H}}^{A}$
contains graphs $H_{i}\in{\mathcal{H}}^{\prime}$ with $N_{i}^{A}>N_{i}^{B}$.
For each such graph $H_{i}$, we denote by $D(H_{i})=N_{i}^{A}-N_{i}^{B}$, and
by $X^{\prime}_{i}=(A\cap S(H_{i}))\setminus X_{i}$ – the set of vertices of
$S(H_{i})$ that remain to be routed. Clearly, $|X^{\prime}_{i}|=D(H_{i})$.
Similarly, set ${\mathcal{H}}^{B}$ contains graphs
$H_{i}\in{\mathcal{H}}^{\prime}$ with $N_{i}^{B}>N_{i}^{A}$. For each such
graph $H_{i}$, we denote by $D(H_{i})=N_{i}^{B}-N_{i}^{A}$, and by
$X^{\prime}_{i}=(B\cap S(H_{i}))\setminus Y_{i}$ – the set of vertices that
remain to be routed. As before, $|X^{\prime}_{i}|=D(H_{i})$ holds. Notice also
that, since $|A|=|B|$,
$\sum_{H_{i}\in{\mathcal{H}}^{A}}D(H_{i})=\sum_{H_{i}\in{\mathcal{H}}^{B}}D(H_{i})$
must hold. Denote $\hat{A}=\bigcup_{H_{i}\in{\mathcal{H}}^{A}}X^{\prime}_{i}$
and $\hat{B}=\bigcup_{H_{i}\in{\mathcal{H}}^{B}}X^{\prime}_{i}$. It is now
enough to prove the following lemma.

######  Lemma 6.7.

There is a set ${\mathcal{P}}^{\prime\prime}$ of paths in graph $H$, routing
every vertex of $\hat{A}$ to a distinct vertex of $\hat{B}$, so that the
length of every path in ${\mathcal{P}}^{\prime\prime}$ is at most
$\tilde{d}_{j}$, and the paths in ${\mathcal{P}}^{\prime\prime}$ cause
congestion at most $\eta_{j}/2$ in $H$.

Indeed, by letting
${\mathcal{P}}^{*}={\mathcal{P}}^{\prime}\cup{\mathcal{P}}^{\prime\prime}$, we
obtain a set of paths in graph $H$ that defines a one-to-one routing of the
set $A$ of vertices to the set $B$ of vertices via paths of length at most
$\tilde{d}_{j}$, so that the paths in ${\mathcal{P}}^{*}$ cause congestion at
most $\eta_{j}$. In order to complete the proof of Lemma 6.5, it is now enough
to prove Lemma 6.7. We focus on the proof of Lemma 6.7 in the remainder of
this section.

We will start by constructing a “meta-graph” representing the graphs of
${\mathcal{H}}^{A}\cup{\mathcal{H}}^{B}$, that will guide the construction of
global routing.

### Step 2: Meta-Graph and Global Routing

Abusing the notation, for simplicity, in the remainder of this proof we denote
${\mathcal{H}}^{A}=\left\\{H_{1},H_{2},\ldots,H_{q}\right\\}$, and for all
$1\leq i\leq q$, we denote $D(H_{i})$ by $D_{i}$. We also denote
${\mathcal{H}}^{B}=\left\\{H^{\prime}_{1},H^{\prime}_{2},\ldots,H^{\prime}_{q^{\prime}}\right\\}$,
and for $1\leq i^{\prime}\leq q^{\prime}$, we denote
$D(H^{\prime}_{i^{\prime}})$ by $D^{\prime}_{i^{\prime}}$. For all $1\leq
i\leq q$, we denote the set $X^{\prime}_{i}\subseteq S(H_{i})$ of $D_{i}$
vertices that remains to be routed by $Y_{i}$, and for all $1\leq
i^{\prime}\leq q^{\prime}$, we denote the corresponding subset of
$D^{\prime}_{i}$ vertices of $S(H^{\prime}_{i^{\prime}})$ by
$Y^{\prime}_{i^{\prime}}$. We now define a _routing meta-graph_ , that will be
used in order to guide the construction of the paths in ${\mathcal{P}}^{*}$,
and show that such a graph exists.

### Routing Meta-Graph

We start by defining a routing meta-graph.

######  Definition 6.1 (Routing Meta-Graph).

A bipartite graph $\hat{G}=(U,U^{\prime},\hat{E})$ with integral weights
$w(e)\geq 0$ on its edges $e\in\hat{E}$ is a _routing meta-graph_ if:

  * •

$U=\left\\{v_{1},\ldots,v_{q}\right\\}$;

  * •

$U^{\prime}=\left\\{v^{\prime}_{1},\ldots,v^{\prime}_{q^{\prime}}\right\\}$;

  * •

for every vertex $v_{i}\in U$, $\sum_{e\in\delta_{\hat{G}}(v_{i})}w(e)=D_{i}$;
and

  * •

for every vertex $v_{i^{\prime}}^{\prime}\in U^{\prime}$,
$\sum_{e\in\delta_{\hat{G}}(v^{\prime}_{i^{\prime}})}w(e)=D^{\prime}_{i^{\prime}}$.

We refer to vertices of $\hat{G}$ as supernodes and edges of $\hat{G}$ as
meta-edges.

We use the following claim to show that a routing meta-graph exists.

######  Claim 6.8.

There exists a routing meta-graph.

###### Proof.

We start with the graph $\hat{G}=(U,U^{\prime},\hat{E})$, where
$U=\left\\{v_{1},\ldots,v_{q}\right\\}$,
$U^{\prime}=\left\\{v^{\prime}_{1},\ldots,v^{\prime}_{q^{\prime}}\right\\}$,
and $\hat{E}=\emptyset$, and then iterate, as long as there exist indices
$1\leq i\leq q$ and $1\leq i^{\prime}\leq q^{\prime}$, such that $D_{i}>0$ and
$D^{\prime}_{i^{\prime}}>0$ holds.

In order to execute an iteration, we consider any pair of such indices
$(i,i^{\prime})$. Let
$\hat{\Delta}=\min\left\\{D_{i},D^{\prime}_{i^{\prime}}\right\\}$. We add an
edge $(v_{i},v^{\prime}_{i^{\prime}})$ to $\hat{E}$, whose weight is
$\hat{\Delta}$, and we decrease $D_{i}$ and $D^{\prime}_{i^{\prime}}$ by
$\hat{\Delta}$. Once the algorithm terminates, since
$\sum_{i=1}^{q}D_{i}=\sum_{i^{\prime}=1}^{q^{\prime}}D^{\prime}_{i^{\prime}}$,
it is immediate to verify that the resulting graph $\hat{G}$ is a valid
routing meta-graph.

### Global Routing

Consider some pair $v_{i}\in U$, $v^{\prime}_{i^{\prime}}\in U^{\prime}$ of
supernodes in graph $\hat{G}$. From 6.6, there exists a collection of paths in
graph $H$, that we denote, abusing the notation, by
${\mathcal{Q}}_{i,i^{\prime}}$, such that the following hold:

  * •

every path in ${\mathcal{Q}}_{i,i^{\prime}}$ originates at a vertex of
$S(H_{i})$ and terminates at a vertex of $S(H^{\prime}_{i^{\prime}})$;

  * •

every vertex of $S(H_{i})\cup S(H^{\prime}_{i^{\prime}})$ is an endpoint of at
most one path in ${\mathcal{Q}}_{i,i^{\prime}}$;

  * •

$|{\mathcal{Q}}_{i,i^{\prime}}|=\left\lceil N^{j-1}/4\right\rceil$;

  * •

each path in ${\mathcal{Q}}_{i,i^{\prime}}$ has length at most $d^{\prime}$;
and

  * •

the paths in ${\mathcal{Q}}_{i,i^{\prime}}$ cause congestion at most $N^{4}$
in $H$.

The set ${\mathcal{Q}}_{i,i^{\prime}}$ of paths naturally defines a matching
$M_{i,i^{\prime}}\subseteq S(H_{i})\times S(H^{\prime}_{i^{\prime}})$: we
include a pair $(x,y)$ of vertices in $M_{i,i^{\prime}}$ if $x\in S(H_{i})$,
$y\in S(H^{\prime}_{i^{\prime}})$, and some path in
${\mathcal{Q}}_{i,i^{\prime}}$ has $x$ and $y$ as its endpoints. Clearly,
$|M_{i,i^{\prime}}|=\left\lceil N^{j-1}/4\right\rceil$. Notice that for every
meta-edge $e=(v_{i},v^{\prime}_{i^{\prime}})$ in graph $\hat{G}$, $w(e)\leq
D_{i}\leq|S(H_{i})|\leq N^{j-1}$ must hold. We will select, for every edge
$e=(v_{i},v^{\prime}_{i^{\prime}})\in\hat{G}$, a multi-set
$M^{\prime}_{i,i^{\prime}}$ of pairs $(x,y)\in M_{i,i^{\prime}}$ of vertices,
of cardinality $w(e)$. (We note that a pair $(x,y)\in M_{i,i^{\prime}}$ of
vertices may be added to $M^{\prime}_{i,i^{\prime}}$ multiple times). We will
ensure that, for every supernode $v_{i}\in U$, a vertex $x\in S(H_{i})$ may
participate in at most four pairs in
$\bigcup_{e=(v_{i},v^{\prime}_{i^{\prime}})\in\delta_{\hat{G}}(v_{i})}M^{\prime}_{i,i^{\prime}}$,
and the same holds for supernodes of $U^{\prime}$. For every meta-edge
$e=(v_{i},v^{\prime}_{i^{\prime}})\in\hat{E}$, we will then use the paths of
${\mathcal{Q}}_{i,i^{\prime}}$ whose endpoints lie in
$M^{\prime}_{i,i^{\prime}}$ to define a _global routing_. Let
${\mathcal{Q}}^{0}$ denote the resulting collection (multiset) of all such
paths. So for every meta-edge $(v_{i},v^{\prime}_{i^{\prime}})\in\hat{E}$, for
every pair $(x,y)\in M^{\prime}_{i,i^{\prime}}$ of vertices,
${\mathcal{Q}}^{0}$ contains the path of ${\mathcal{Q}}_{i,i^{\prime}}$ whose
endpoints are $x$ and $y$. If $(x,y)$ appears multiple times in
$M^{\prime}_{i,i^{\prime}}$, then ${\mathcal{Q}}^{0}$ contains multiple copies
of this path. For every graph
$\tilde{H}\in{\mathcal{H}}^{A}\cap{\mathcal{H}}^{B}$, for every vertex $x\in
S(\tilde{H})$, we denote by $k(x)$ the number of paths of ${\mathcal{Q}}^{0}$,
for which $x$ serves as an endpoint. Our construction will guarantee that, for
all $1\leq i\leq q$, $\sum_{x\in S(H_{i})}k(x)=D_{i}$, and similarly, for all
$1\leq i^{\prime}\leq q^{\prime}$, $\sum_{x\in
S(H^{\prime}_{i^{\prime}})}k(x)=D^{\prime}_{i^{\prime}}$. As mentioned
already, we will ensure that, for every graph
$\tilde{H}\in{\mathcal{H}}^{\prime}$, for every vertex $x\in S(\tilde{H})$,
$k(x)\in\left\\{0,\ldots,4\right\\}$. In our last step, we will perform _local
routing_ , in which, for all $1\leq i\leq q$, we connect every vertex of
$Y_{i}$ to some vertex of $S(H_{i})$ by a path, such that every vertex $x\in
S(H_{i})$ is the last endpoint of exactly $k(x)$ such paths. We perform a
similar routing in graphs of ${\mathcal{H}}^{B}$. This local routing exploits
the fact that every graph $\tilde{H}\in{\mathcal{H}}^{\prime}$ is
$(\eta_{j-1},\tilde{d}_{j-1})$-well-connected, together with the embedding
${\mathcal{P}}$ of the graph
$H^{\prime}=\bigcup_{\tilde{H}\in{\mathcal{H}}^{\prime}}\tilde{H}$ into $H$
that we have computed.

In order to simplify the notation, for all $1\leq i\leq q$, we denote by
$\hat{E}_{i}\subseteq\hat{E}$ the set of all meta-edges of $\hat{G}$ that are
incident to supernode $v_{i}$ in $\hat{G}$. Similarly, for all $1\leq
i^{\prime}\leq q^{\prime}$, we denote by
$\hat{E}_{i^{\prime}}^{\prime}\subseteq\hat{E}$ the set of all meta-edges of
$\hat{G}$ that are incident to supernode $v^{\prime}_{i^{\prime}}$ in
$\hat{G}$. We prove the following lemma, that allows us to perform global
routing.

######  Lemma 6.9.

For every meta-edge $e=(v_{i},v^{\prime}_{i^{\prime}})\in\hat{E}$, there is a
multiset $M^{\prime}_{i,i^{\prime}}$ of pairs of vertices of $S(H_{i})\times
S(H^{\prime}_{i^{\prime}})$, for which the following hold. For all $1\leq
i\leq q$, for every vertex $x\in S(H_{i})$, let $k(x)$ be the total number of
pairs in
$\bigcup_{(v_{i},v^{\prime}_{i^{\prime}})\in\hat{E}_{i}}M^{\prime}_{i,i^{\prime}}$,
in which vertex $x$ participates. Similarly, for all $1\leq i^{\prime}\leq
q^{\prime}$, for every vertex $x\in S(H^{\prime}_{i^{\prime}})$, let $k(x)$ be
the total number of pairs in
$\bigcup_{(v_{i},v^{\prime}_{i^{\prime}})\in\hat{E}^{\prime}_{i^{\prime}}}M^{\prime}_{i,i^{\prime}}$,
in which vertex $x$ participates. Then:

  * •

for every meta-edge $e=(v_{i},v^{\prime}_{i^{\prime}})\in E(\hat{G})$, a pair
$(x,y)$ of vertices may only belong to $M^{\prime}_{i,i^{\prime}}$ if
$(x,y)\in M_{i,i^{\prime}}$ (but it may be added to
$M^{\prime}_{i,i^{\prime}}$ multiple times);

  * •

for every vertex
$x\in\left(\bigcup_{i=1}^{q}S(H_{i})\right)\cup\left(\bigcup_{i^{\prime}=1}^{q^{\prime}}S(H^{\prime}_{i^{\prime}})\right)$,
$k(x)\in\left\\{0,\ldots,4\right\\}$;

  * •

for all $1\leq i\leq q$, $\sum_{x\in S(H_{i})}k(x)=D_{i}$; and

  * •

for all $1\leq i^{\prime}\leq q^{\prime}$, $\sum_{x\in
S(H^{\prime}_{i^{\prime}})}k(x)=D^{\prime}_{i^{\prime}}$.

###### Proof.

We construct the following directed flow network. We start with a bipartite
graph $\tilde{G}=(\tilde{X},\tilde{Y},\tilde{E})$, where
$\tilde{X}=\bigcup_{i=1}^{q}S(H_{i})$,
$\tilde{Y}=\bigcup_{i^{\prime}=1}^{q^{\prime}}S(H^{\prime}_{i^{\prime}})$, and
$\tilde{E}=\bigcup_{(v_{i},v^{\prime}_{i^{\prime}})\in
E(\hat{G})}M_{i,i^{\prime}}$. All edges are directed from vertices of
$\tilde{X}$ towards vertices of $\tilde{Y}$, and they have capacity $4$ each.
For all $1\leq i\leq q$, we add a vertex $s_{i}$, that connects to every
vertex in $S(H_{i})$ with an edge of capacity $4$. For all $1\leq
i^{\prime}\leq q^{\prime}$, we add a vertex $t_{i^{\prime}}$, to which every
vertex of $S(H^{\prime}_{i^{\prime}})$ connects with an edge of capacity $4$.
Lastly, we add a source vertex $s$, and a destination vertex $t$. For all
$1\leq i\leq q$, we add an edge $(s,s_{i})$ of capacity $D_{i}$, and for all
$1\leq i^{\prime}\leq q^{\prime}$, we add an edge $(t_{i},t)$ of capacity
$D^{\prime}_{i^{\prime}}$.

We claim that this network as a valid $s$-$t$ flow $f$ of value
$D=\sum_{i=1}^{q}D_{i}=\sum_{i^{\prime}=1}^{q^{\prime}}D^{\prime}_{i^{\prime}}$.
We obtain this flow as follows. Consider a meta-edge
$e=(v_{i},v^{\prime}_{i^{\prime}})\in E(\hat{G})$. Recall that we are given an
integral weight $w(e)\leq N^{j-1}$, and a matching $M_{i,i^{\prime}}\subseteq
S(H_{i})\times S(H^{\prime}_{i^{\prime}})$ of cardinality $\left\lceil
N^{j-1}/4\right\rceil$. For every edge $e^{\prime}=(x,y)\in M_{i,i^{\prime}}$,
we set the flow
$f(e^{\prime})=\frac{w(e)}{|M_{i,i^{\prime}}|}=\frac{w(e)}{\left\lceil
N^{j-1}/4\right\rceil}$. Notice that this ensures that the total flow on all
edges of $M_{i,i^{\prime}}$ is precisely $w(e)$, and for every edge
$e^{\prime}\in M_{i,i^{\prime}}$, $f(e^{\prime})\leq 4$. Once we process every
meta-edge of $\hat{G}$, we finalize the flow values $f(e^{\prime})$ for all
edges $e^{\prime}\in\tilde{E}$.

Consider now some index $1\leq i\leq q$, and some vertex $x\in S(H_{i})$. We
claim that the total flow on all edges of $\tilde{E}$ that are incident to $x$
in the flow network is at most $4$. Indeed, recall that $\hat{E}_{i}$ is the
set of all meta-edges of $\hat{G}$ that are incident to supernode $v_{i}$.
From the definition of a routing meta-graph, we are guaranteed that
$\sum_{e\in\hat{E}_{i}}w(e)=D_{i}$. For every meta-edge
$e=(v_{i},v_{i^{\prime}}^{\prime})\in\hat{E}_{i}$, if some edge of
$M_{i,i^{\prime}}$ is incident to $x$, then the flow on this edge is
$\frac{w(e)}{\left\lceil N^{j-1}/4\right\rceil}$. Therefore, the total flow on
all edges of $\tilde{E}$ that are incident to $x$ is bounded by:

$\sum_{e\in\hat{E}_{i}}\frac{w(e)}{\left\lceil
N^{j-1}/4\right\rceil}=\frac{D_{i}}{\left\lceil N^{j-1}/4\right\rceil}\leq 4,$

since $D_{i}\leq|S(H_{i})|\leq N^{j-1}$ must hold.

We set the flow on edge $(s_{i},x)$ to be equal to the total amount of flow on
all edges of $\tilde{E}$ that are incident to $x$ in the flow network, which,
from the above discussion, is bounded by $4$.

From similar arguments, for every index $1\leq i^{\prime}\leq q^{\prime}$, and
every vertex $y\in S(H^{\prime}_{i^{\prime}})$, the total flow on all edges of
$\tilde{E}$ that are incident to $y$ in the flow network is at most $4$. We
set the flow on the edge $(y,t_{i})$ to be the total flow on all edges of
$\tilde{E}$ that are incident to $y$ in the flow network.

Next, we consider an index $1\leq i\leq q$. We set the flow on edge
$(s,s_{i})$ to be $D_{i}$. We claim that $\sum_{x\in
S(H_{i})}f(s_{i},x)=D_{i}$. Indeed, from our construction:

$\sum_{x\in
S(H_{i})}f(s_{i},x)=\sum_{(v_{i},v^{\prime}_{i^{\prime}})\in\hat{E}_{i}}\sum_{(x,y)\in
M_{i,i^{\prime}}}f(x,y)=\sum_{e=(v_{i},v^{\prime}_{i^{\prime}})\in\hat{E}_{i}}\sum_{(x,y)\in
M_{i,i^{\prime}}}\frac{w(e)}{\left\lceil
N^{j-1}/4\right\rceil}=\sum_{e=(v_{i},v^{\prime}_{i^{\prime}})\in\hat{E}_{i}}w(e)=D_{i}.$

(we have used the fact that $|M_{i,i^{\prime}}|=\left\lceil
N^{j-1}/4\right\rceil$ for every meta-edge $(v_{i},v^{\prime}_{i^{\prime}})\in
E(\hat{G})$).

Similarly, we consider an index $1\leq i^{\prime}\leq q^{\prime}$. We set the
flow on edge $(t_{i^{\prime}},t)$ to be $D^{\prime}_{i^{\prime}}$. Using the
same reasoning as above, $\sum_{y\in
S(H^{\prime}_{i^{\prime}})}f(y,t_{i})=D^{\prime}_{i^{\prime}}$. We conclude
that we have obtained a valid $s$-$t$ flow in the above flow network, whose
value is $D$. Since all edge capacities in the flow network are integral, from
the integrality of flow, there is an integral $s$-$t$ flow $f^{\prime}$ of
value $D$ in this flow network.

We are now ready to define the multisets $M^{\prime}_{i,i^{\prime}}$ of pairs
of vertices from $S(H_{i})\times S(H^{\prime}_{i^{\prime}})$, for all
$(v_{i},v^{\prime}_{i^{\prime}})\in E(\hat{G})$. Consider any meta-edge
$(v_{i},v^{\prime}_{i^{\prime}})\in E(\hat{G})$, and some pair $(x,y)\in
M_{i,i^{\prime}}$ of vertices. If $f^{\prime}(x,y)>0$, then we include
$f^{\prime}(x,y)$ copies of the pair $(x,y)$ to $M^{\prime}_{i,i^{\prime}}$.

We now verify that all requirements hold for this definition of the multisets
$M^{\prime}_{i,i^{\prime}}$ for all $(v_{i},v^{\prime}_{i^{\prime}})\in
E(\hat{G})$. Clearly, a pair $(x,y)$ of vertices may only be added to
$M^{\prime}_{i,i^{\prime}}$ if $(x,y)\in M_{i,i^{\prime}}$.

Consider now some vertex $x\in\bigcup_{i=1}^{q}S(H_{i})$. Recall that $k(x)$
is the total number of pairs in
$\bigcup_{(v_{i},v^{\prime}_{i^{\prime}})\in\hat{E}}M^{\prime}_{i,i^{\prime}}$
in which $x$ participates. This is equal to the total flow leaving vertex $x$
in $f^{\prime}$, which, in turn, is equal to the flow on edge $(s_{i},x)$.
From our definition, the capacity of this edge is $4$, so
$k(x)\in\left\\{0,\ldots,4\right\\}$. If
$x\in\bigcup_{i^{\prime}=1}^{q^{\prime}}S(H^{\prime}_{i^{\prime}})$, then
$k(x)\in\left\\{0,\ldots,4\right\\}$ for similar reasons.

Consider now some index $1\leq i\leq q$. From the above discussion,
$\sum_{x\in S(H_{i})}k(x)=\sum_{x\in S(H_{i})}f^{\prime}(s_{i},x)$. In other
words, $\sum_{x\in S(H_{i})}k(x)$ is the total amount of flow leaving vertex
$s_{i}$ in $f^{\prime}$. From conservation of flow this must be equal to the
total amount of flow entering $s_{i}$. Since we send $D=\sum_{i=1}^{q}D_{i}$
flow units from $s$ to $t$, and since, for all $1\leq i\leq q$, the capacity
of the edge $(s,s_{i})$ is $D_{i}$, we must send $D_{i}$ flow units on edge
$(s,s_{i})$. In other words, for all $1\leq i\leq q$, $\sum_{x\in
S(H_{i})}k(x)=D_{i}$ must hold. From similar arguments, for all $1\leq
i^{\prime}\leq q^{\prime}$, $\sum_{x\in
S(H^{\prime}_{i^{\prime}})}k(x)=D^{\prime}_{i^{\prime}}$ must hold.

We are now ready to define the global routing. For every meta-edge
$e=(v_{i},v^{\prime}_{i^{\prime}})\in E(\hat{G})$, we consider the resulting
collection $M^{\prime}_{i,i^{\prime}}\subseteq S(H_{i})\times
S(H_{i^{\prime}})$ of pairs of vertices. We define a (multi)-set
${\mathcal{Q}}^{\prime}_{i,i^{\prime}}$ of paths, as follows. Consider any
pair $(x,y)\in M^{\prime}_{i,i^{\prime}}$, and assume that the number of times
that it appears in $M^{\prime}_{i,i^{\prime}}$ is $N(x,y)$. Recall that
$(x,y)\in M_{i,i^{\prime}}$ must hold, so there must be a path
$Q(x,y)\in{\mathcal{Q}}_{i,i^{\prime}}$ connecting $x$ to $y$. We add $N(x,y)$
copies of this path to ${\mathcal{Q}}^{\prime}_{i,i^{\prime}}$. Note that,
from Lemma 6.9, $N(x,y)\leq k(x)\leq 4$ must hold.

We then let ${\mathcal{Q}}^{0}=\bigcup_{(v_{i},v^{\prime}_{i^{\prime}})\in
E(\hat{G})}{\mathcal{Q}}^{\prime}_{i,i^{\prime}}$ (again, set
${\mathcal{Q}}^{0}$ is a multiset, so if some path appears several times in
some set ${\mathcal{Q}}^{\prime}_{i,i^{\prime}}$, then it will appear several
times in ${\mathcal{Q}}^{0}$).

Recall that, for every pair
$H_{i},H^{\prime}_{i^{\prime}}\in{\mathcal{H}}^{\prime}$ of graphs, the paths
in ${\mathcal{Q}}_{i,i^{\prime}}$ have length at most $d^{\prime}$ each, and
they cause congestion at most $N^{4}$ in $H$. Since
${\mathcal{Q}}^{\prime}_{i,i^{\prime}}$ contains at most four copies of each
path in ${\mathcal{Q}}_{i,i^{\prime}}$, and since
$|E(\hat{G})|\leq|{\mathcal{H}}^{\prime}|^{2}\leq N^{2}$, the paths in
${\mathcal{Q}}^{0}$ cause congestion at most $4N^{6}$ in $H$, and every path
has length at most $d^{\prime}$ as before. For every vertex
$x\in\left(\bigcup_{i=1}^{q}S(H_{i})\right)\cup\left(\bigcup_{i^{\prime}=1}^{q^{\prime}}S(H^{\prime}_{i^{\prime}})\right)$,
we use the definition of the value $k(x)$ from Lemma 6.9. The number of paths
in ${\mathcal{Q}}^{0}$, in which $x$ serves as an endpoint is then precisely
$k(x)$, and, from Lemma 6.9, $k(x)\in\left\\{0,\ldots,4\right\\}$. Recall also
that, for all $1\leq i\leq q$, $\sum_{x\in S(H_{i})}k(x)=D_{i}$, and for all
$1\leq i^{\prime}\leq q^{\prime}$, $\sum_{x\in
S(H^{\prime}_{i^{\prime}})}k(x)=D^{\prime}_{i^{\prime}}$.

### Step 3: Local Routing

Consider some graph $H_{i}\in{\mathcal{H}}^{A}$. We have defined a set
$Y_{i}\subseteq S(H_{i})$ of $D_{i}$ vertices of $H_{i}$ that need to be
routed. For every vertex $x\in S(H_{i})$, we are also now given a value
$k(x)\in\left\\{0,\ldots,4\right\\}$, which is exactly the number of paths in
${\mathcal{Q}}^{0}$ for which vertex $x$ serves as an endpoint. We are also
guaranteed that $\sum_{x\in S(H_{i})}k(x)=D_{i}$. We can then construct four
sets $Z_{i}^{1},Z_{i}^{2},Z_{i}^{3},Z_{i}^{4}$ of vertices of $S(X)$, such
that for every vertex $x\in S(X)$, each of the four sets contains at most one
copy of $x$; and the number of sets in
$\left\\{Z_{i}^{1},\ldots,Z_{i}^{4}\right\\}$ containing $x$ is exactly
$k(x)$. Clearly, $\sum_{a=1}^{4}|Z_{i}^{a}|=D_{i}$. We also partition the set
$Y_{i}$ of vertices into four subsets $Y_{i}^{1},\ldots,Y_{i}^{4}$
arbitrarily, so that, for all $1\leq a\leq 4$, $|Y_{i}^{a}|=|Z_{i}^{a}|$.
Since $Y_{i}\subseteq S(H_{i})$, from the fact that graph $H_{i}$ is
$(\eta_{j-1},\tilde{d}_{j-1})$-well-connected with respect to $S(H_{i})$, for
all $1\leq a\leq 4$, there is a set $\hat{\mathcal{P}}_{i}^{a}$ of
$|Z_{i}^{a}|$ paths in graph $H_{i}$, routing every vertex of $Y_{i}^{a}$ to a
distinct vertex of $Z_{i}^{a}$, such that the length of every path is at most
$\tilde{d}_{j-1}$, and the paths cause congestion at most $\eta_{j-1}$ in
graph $H_{i}$. Let
$\hat{\mathcal{P}}_{i}=\bigcup_{a=1}^{4}\hat{\mathcal{P}}_{i}^{a}$. We think
of the paths in $\hat{\mathcal{P}}_{i}$ as being directed away from vertices
of $Y_{i}$. Notice that the paths in $\hat{\mathcal{P}}_{i}$ route every
vertex of $Y_{i}$ to some vertex of $S(H_{i})$, such that, for every vertex
$x\in S(H_{i})$, exactly $k(x)$ paths of $\hat{\mathcal{P}}_{i}$ terminate at
$x$. The paths in $\hat{\mathcal{P}}_{i}$ cause congestion at most
$4\eta_{j-1}$ in graph $H_{i}$, and have length at most $\tilde{d}_{j-1}$
each.

Consider the graph $H^{\prime}=\bigcup_{H_{i}\in{\mathcal{H}}^{\prime}}H_{i}$.
Recall that we have computed, in Phase 1 of the algorithm, an embedding
${\mathcal{P}}$ of $H^{\prime}$ into $H$, where every path in the embedding
has length at most $d^{\prime}$, and the paths in ${\mathcal{P}}$ cause
congestion at most $N^{128\epsilon^{2}}$ in $H$.

Consider now the set $\hat{\mathcal{P}}=\bigcup_{1\leq i\leq
q}\hat{\mathcal{P}}_{i}$ of paths in graph $H^{\prime}$. This set of paths
routes every vertex of $\bigcup_{1\leq i\leq q}Y_{i}$ to some vertex of
$\bigcup_{1\leq i\leq q}S(H_{i})$, such that, for every vertex
$x\in\bigcup_{1\leq i\leq q}S(H_{i})$, exactly $k(x)$ paths of
$\hat{\mathcal{P}}$ terminate at $x$. Additionally, the length of every path
in $\hat{\mathcal{P}}$ is is at most $\tilde{d}_{j-1}$, and the paths in
$\hat{\mathcal{P}}$ cause congestion at most $4\eta_{j-1}$ in $H^{\prime}$.

We now use the algorithm from 3.1 with the collection $\hat{\mathcal{P}}$ of
paths, and the embedding ${\mathcal{P}}$ of graph
$H^{\prime}=\bigcup_{H_{i}\in{\mathcal{H}}^{\prime}}H_{i}$ into $H$, in order
to compute a set ${\mathcal{Q}}^{1}$ of paths in graph $H$, routing every
vertex $\bigcup_{1\leq i\leq q}Y_{i}$ to some vertex of $\bigcup_{1\leq i\leq
q}S(H_{i})$, such that, for every vertex $x\in\bigcup_{1\leq i\leq
q}S(H_{i})$, exactly $k(x)$ paths of $\hat{\mathcal{P}}$ terminate at $x$. The
algorithm ensures that the length of every path in $\hat{\mathcal{P}}$ is at
most $\tilde{d}_{j-1}\cdot d^{\prime}$, and the paths in $\hat{\mathcal{P}}$
cause congestion at most $4\eta_{j-1}\cdot N^{128\epsilon^{2}}$.

For every index $1\leq i^{\prime}\leq q^{\prime}$, we similarly compute a set
$\hat{\mathcal{P}}^{\prime}_{i^{\prime}}$ of paths in graph
$H^{\prime}_{i^{\prime}}$, that route some vertices of $S(H_{i^{\prime}})$ to
vertices of $Y^{\prime}_{i^{\prime}}$, so that for every vertex $y\in
Y^{\prime}_{i^{\prime}}$, exactly one path in
$\hat{\mathcal{P}}^{\prime}_{i^{\prime}}$ terminates at $y$, and for every
vertex $x\in S(H^{\prime}_{i^{\prime}})$, exactly $k(x)$ paths of
${\mathcal{P}}^{\prime}_{i^{\prime}}$ originate at $x$. We use the embedding
${\mathcal{P}}$ of graph $H^{\prime}$ into $H$ exactly as before, in order to
compute a set ${\mathcal{Q}}^{2}$ of paths in graph $H$, routing vertices of
$\bigcup_{1\leq i^{\prime}\leq q^{\prime}}S(H^{\prime}_{i^{\prime}})$ to
vertices of $\bigcup_{1\leq i^{\prime}\leq
q^{\prime}}Y^{\prime}_{i^{\prime}}$, such that, for every vertex
$x\in\bigcup_{1\leq i\leq q}S(H_{i})$, exactly $k(x)$ paths of
${\mathcal{Q}}^{2}$ originate at $x$, and for every vertex $y\in\bigcup_{1\leq
i^{\prime}\leq q^{\prime}}Y^{\prime}_{i^{\prime}}$, exactly one path of
${\mathcal{Q}}^{2}$ terminates at $y$. As before, we can ensure that the
length of each every path in ${\mathcal{Q}}^{2}$ is at most
$\tilde{d}_{j-1}\cdot d^{\prime}$, and the paths in ${\mathcal{Q}}^{2}$ cause
congestion at most $4\eta_{j-1}\cdot N^{128\epsilon^{2}}$ in $H$.

By concatenating the paths of ${\mathcal{Q}}^{1},{\mathcal{Q}}^{0}$ and
${\mathcal{Q}}^{2}$, we obtain the final set ${\mathcal{P}}^{\prime\prime}$ of
paths, that defines a one-to-one routing between vertices of
$\bigcup_{i=1}^{q}Y_{i}$ and vertices of
$\bigcup_{i^{\prime}=1}^{q^{\prime}}Y^{\prime}_{i^{\prime}}$. The length of
every path in ${\mathcal{P}}^{\prime\prime}$ is bounded by
$2\tilde{d}_{j-1}\cdot d^{\prime}+d^{\prime}\leq 3\tilde{d}_{j-1}\cdot
d^{\prime}$.