$U=\left\\{u_{1},\ldots,u_{|U|}\right\\}$. Finally, for each $1\leq i\leq|U|$,
we let $E^{i}\subseteq{\mathcal{M}}^{\prime}_{2}$ be the subset of edges that
have an endpoint in $V_{i}$, and we let $B^{i}_{2}$ be the subset of vertices
of $B_{2}$ that serve as endpoints of the edges in $E^{i}$. Since $|V_{i}\cap
C_{2}|\geq 3\rho$, we have $|B^{i}_{2}|\geq 3\rho$ for each $1\leq i\leq|U|$.

We are now ready to define the embeddings of the vertices of $H$ into $G$. For
each $1\leq i\leq|U|$, we let $f(u_{i})=G[B_{2}^{i}\cup V_{i}]$. Notice that
for all $1\leq i\leq|U|$, $f(u_{i})$ is a connected graph, and for all $1\leq
i<j\leq|U|$, $f(u_{i})\cap f(u_{j})=\emptyset$. In the remaining steps, we
focus on embedding the edges of $H$ into $G$, such that the resulting paths
are internally disjoint from $B_{2}\cup T_{2}$.

Figure 3.4: A sketch of the partition of $T_{2}$ and $B_{2}$ with $|U|=4$.
Vertices of $B_{2}$ and $C_{2}$ are shown in blue and red respectively.

###### Step 2: Routing all but a small fraction of edges of $H$ in
$G^{\prime\prime}_{\Pi}$.

Consider some vertex $u_{i}\in U$, its corresponding graph $f(u_{i})$, and the
set $B_{2}^{i}\subseteq B_{2}$ of vertices that lie in $f(u_{i})$. Recall that
the maximum vertex degree in $H$ is at most $3$ and for each $1\leq i\leq|U|$
we have $|B_{2}^{i}|\geq 3\rho$. For every edge $e\in\delta_{H}(u_{i})$, we
now select an arbitrary subset $B_{2}^{i}(e)\subseteq B_{2}^{i}$ of $\rho$
vertices, so that all resulting sets
$\left\\{B_{2}^{i}(e)\right\\}_{e\in\delta_{H}(u_{i})}$ are mutually disjoint.

Recall that graph $G_{\Pi}$ contains a perfect matching ${\mathcal{M}}_{2}$
between the vertices of $B_{2}$ and the vertices of $A_{3}$. We let
$\hat{E}^{i}\subseteq{\mathcal{M}}_{2}$ be the subset of edges whose endpoints
lie in $B_{2}^{i}$, and denote by $A_{3}^{i}\subseteq A_{3}$ the set of
endpoints of the edges of $E^{i}$ that lie in $A_{3}$. For every edge
$e\in\delta(v_{i})$, we let $A_{3}^{i}(e)\subseteq A_{3}^{i}$ be the set of
$\rho$ vertices that are connected to the vertices of $B_{2}^{i}(e)$ with an
edge of ${\mathcal{M}}_{2}$. Clearly, all resulting vertex sets
$\left\\{A_{3}^{i}(e)\right\\}_{e\in\delta_{H}(u_{i})}$ are mutually disjoint.
Let $A_{3}^{\prime}=\bigcup_{u_{i}\in
U}\bigcup_{e\in\delta_{H}(u_{i})}A_{3}^{i}(e)$, and notice that

$|A_{3}^{\prime}|\leq 3\rho\cdot|U|\leq
3\rho\cdot\frac{w}{8d\rho}=\frac{3w}{8d}\leq\frac{w}{2}.$

The following lemma, whose proof is deferred to Section 3.4.1, allows us to
embed a large number of edges of $H$ in $G^{\prime\prime}_{\Pi}$.

######  Lemma 3.4.2.

There is an efficient algorithm, that, given a Path-of-Expanders System
$\Pi=({\mathcal{S}},{\mathcal{M}},A_{1},B_{6},{\mathcal{T}},{\mathcal{M}}^{\prime})$
of expansion $\alpha$ and width $w$, where $0<\alpha<1$ and $w$ is an integral
multiple of $4$, whose corresponding graph $G_{\Pi}$ contains at most $n$
vertices and has maximum vertex degree at most $d$, together with a subset
$A^{\prime}_{3}\subseteq A_{3}$ of at most $w/2$ vertices, and a collection
$\left\\{A_{3}^{1},\ldots,A_{3}^{2r}\right\\}$ of mutually disjoint subsets of
$A^{\prime}_{3}$ of cardinality $\rho=2^{16}\left\lfloor\frac{d^{3}n\log
n}{\alpha^{2}w}\right\rfloor$ each, where $r>\frac{w\alpha^{2}(\log\log
n)^{2}}{d^{3}\log^{3}n}$, returns a partition
${\mathcal{I}}^{\prime},{\mathcal{I}}^{\prime\prime}$ of
$\left\\{1,\ldots,r\right\\}$, and a set
${\mathcal{P}}^{*}=\left\\{P^{*}_{j}\mid j\in{\mathcal{I}}^{\prime}\right\\}$
of disjoint paths in $G^{\prime\prime}_{\Pi}$, such that for each
$j\in{\mathcal{I}}^{\prime}$, path $P^{*}_{j}$ connects $A_{3}^{j}$ to
$A_{3}^{j+r}$, and
$|{\mathcal{I}}^{\prime\prime}|\leq\frac{w\alpha^{2}(\log\log
n)^{2}}{d^{3}\log^{3}n}$.

We obtain the following immediate corollary of the lemma.

######  Corollary 3.4.3.

There is an efficient algorithm to compute a partition $(F_{1},F_{2})$ of the
set $F$ of edges of $H$, and for each edge $e=(u_{i},u_{j})\in F_{1}$, a path
$P^{*}_{e}$ in graph $G^{\prime\prime}_{\Pi}$, connecting a vertex of
$A_{3}^{i}(e)$ to a vertex of $A_{3}^{j}(e)$, such that all paths in set
${\mathcal{P}}^{*}_{1}=\left\\{P^{*}(e)\mid e\in F_{1}\right\\}$ are disjoint,
and $|F_{2}|\leq\frac{w\alpha^{2}(\log\log n)^{2}}{d^{3}\log^{3}n}$.

###### Proof.

By appropriately ordering the collection $\left\\{A_{3}^{i}(e)\mid u_{i}\in
U,e\in\delta_{H}(e)\right\\}$ of vertex subsets, and applying Lemma 3.4.2 to
the resulting sequence of subsets of $A_{3}^{\prime}$, we obtain a set
$F_{1}\subseteq F$ of edges of $H$, and for each edge $e=(u_{i},u_{j})\in
F_{1}$, a path $P^{*}_{e}$, connecting a vertex of $A_{3}^{i}(e)$ to a vertex
of $A_{3}^{j}(e)$ in graph $G^{\prime\prime}_{\Pi}$, such that all paths in
set ${\mathcal{P}}^{*}_{1}=\left\\{P^{*}(e)\mid e\in F_{1}\right\\}$ are
disjoint. Let $F_{2}=F\setminus F_{1}$. From Lemma 3.4.2,
$|F_{2}|\leq\frac{w\alpha^{2}(\log\log n)^{2}}{d^{3}\log^{3}n}$.

For each edge $e=(u_{i},u_{j})\in F_{1}$, we extend the path $P^{*}_{e}$ to
include the two edges of ${\mathcal{M}}_{2}$ incident to its endpoints, so
that $P^{*}_{e}$ now connects a vertex of $B_{2}^{i}$ to a vertex of
$B_{2}^{j}$. Path $P^{*}_{e}$ becomes the embedding $f(e)$ of $e$ in the model
$f$ of $H$ that we are constructing. For convenience, the resulting set of
paths $\left\\{P^{*}_{e}\mid e\in F_{1}\right\\}$ is still denoted by
${\mathcal{P}}^{*}_{1}$. The paths in ${\mathcal{P}}^{*}_{1}$ remain disjoint
from each other; they are internally disjoint from $W_{2}$, and completely
disjoint from $W_{1}$ (see Figure 3.6).

###### Step 3: Routing remaining edges of $H$ in $G^{\prime}_{\Pi}$.

In this last step we complete the construction of a minor of $H$ in $G$, by
embedding the edges of $F_{2}$. The main tool that we use is the following
lemma, whose proof is deferred to Section 3.4.2.

######  Lemma 3.4.4.

There is a universal constant $c$, and an efficient algorithm that, given a
Path-of-Expanders System
$\Pi=({\mathcal{S}},{\mathcal{M}},A_{1},B_{6},{\mathcal{T}},{\mathcal{M}}^{\prime})$
of expansion $\alpha$ and width $w$, such that the corresponding graph
$G_{\Pi}$ contains at most $n$ vertices and has maximum vertex degree at most
$d$, computes a subset $B^{\prime}_{1}\subseteq B_{1}$ of at least
$\frac{cw\alpha^{2}}{d^{3}\log^{2}n}$ vertices, such that the following holds.
There is an efficient randomized algorithm, that given any matching
${\mathcal{M}}^{*}$ over the vertices of $B^{\prime}_{1}$, with high
probability returns a set ${\mathcal{P}}$ of disjoint paths in $W_{1}$,
routing ${\mathcal{M}}^{*}$.

We now complete the embedding using the above lemma. Let
$B^{\prime}_{1}\subseteq B_{1}$ be the subset of at least
$\frac{cw\alpha^{2}}{d^{3}\log^{2}n}$ vertices, computed by algorithm from
Lemma 3.4.4. Let $A^{\prime}_{2}\subseteq A_{2}$ be the set of all the
vertices connected to the vertices of $B^{\prime}_{1}$ by the edges of the
matching ${\mathcal{M}}_{1}$. Observe that $|A^{\prime}_{2}|\geq 2|F_{2}|$,
since:

$2|F_{2}|\leq\frac{2w\alpha^{2}(\log\log
n)^{2}}{d^{3}\log^{3}n}\leq\frac{cw\alpha^{2}}{d^{3}\log^{2}n}=|B^{\prime}_{1}|=|A^{\prime}_{2}|.$

Here, the last inequality follows since we have assumed that $n$ is
sufficiently large.

We let $A^{\prime\prime}_{2}$ be an arbitrary subset of $2|F_{2}|$ vertices of
$A^{\prime}_{2}$. Recall that for every vertex $u_{i}\in U$ and every edge
$e\in\delta_{H}(u_{i})$ incident on it, we have defined a subset
$B_{2}^{i}(e)\subseteq B_{2}^{i}$ of vertices. We select an arbitrary
representative vertex $b_{2}^{i}(e)\in B_{2}^{i}(e)$, and we let
$B^{\prime}_{2}=\left\\{b_{2}^{i}(e)\mid u_{i}\in U,e\in\delta(u_{i})\cap
F_{2}\right\\}$ be the resulting set of representative vertices, so that
$|B^{\prime}_{2}|=2|F|$.

Since $(A_{2}\cup B_{2})$ are well-linked in $S_{2}$, there is a set
${\mathcal{Q}}_{2}$ of $2|F_{2}|$ disjoint paths in $S_{2}$, connecting every
vertex of $B^{\prime}_{2}$ to some vertex of $A^{\prime\prime}_{2}$, such that
the paths in ${\mathcal{Q}}_{2}$ are internally disjoint from $A_{2}\cup
B_{2}$. For each vertex $b_{2}^{i}(e)\in B^{\prime}_{2}$, let $a_{2}^{i}(e)\in
A^{\prime\prime}_{2}$ be the corresponding endpoint of the path of
${\mathcal{Q}}_{2}$ that originates at $b_{2}^{i}(e)$ (see Figure 3.6). Let
$b_{1}^{i}(e)\in B^{\prime}_{1}$ be the vertex of $B_{1}$ that is connected to
$a_{2}^{i}(e)$ with an edge from ${\mathcal{M}}_{1}$. We can now naturally
define a matching ${\mathcal{M}}^{*}$ over the vertices of $B^{\prime}_{1}$,
where for every edge $e=(u_{i},u_{j})\in F_{2}$, we add the pair
$(b_{1}^{i}(e),b_{1}^{j}(e))$ of vertices to the matching. From Lemma 3.4.4,
with high probability we obtain a collection
${\mathcal{P}}^{*}_{2}=\left\\{P^{*}_{e}\mid e\in F_{2}\right\\}$ of disjoint
paths in $W_{1}$, such that, for every edge $e=(u_{i},u_{j})\in F_{2}$, the
corresponding path $P^{*}_{e}$ connects $b_{1}^{i}(e)$ to $b_{1}^{j}(e)$. We
extend this path to connect the vertex $b_{2}^{i}(e)$ to the vertex
$b_{2}^{j}(e)$, by using the edges of ${\mathcal{M}}_{1}$ that are incident to
$b_{1}^{i}(e)$ to $b_{1}^{j}(e)$, and the paths of ${\mathcal{Q}}_{2}$ that
are incident to $a_{2}^{i}(e)$ to $a_{2}^{j}(e)$. Notice that the resulting
extended paths are internally disjoint from $B_{2}$, and are completely
disjoint from $T_{2}\cup G^{\prime\prime}_{\Pi}$. We now embed each edge $e\in
F_{2}$ into the path $P^{*}_{e}$, that is, we set $f(e)=P^{*}_{e}$. This
completes the construction of the model of $H$ in $G_{\Pi}$, except for the
proofs of Lemmas 3.4.2 and 3.4.4, that are provided in Sections 3.4.1 and
3.4.2, respectively.

Figure 3.5: An illustration of a path $P^{*}_{e}\in{\mathcal{P}}^{*}_{1}$
routing an edge $e=(u_{i},u_{j})\in F_{1}$. Dashed boundaries represent the
labeled subsets.

Figure 3.6: An illustration of the path $P^{*}_{e}\in{\mathcal{P}}^{*}_{2}$
connecting $e=(u_{i},u_{j})\in F_{2}$.

####  3.4.1 Embedding Almost All Edges of the Target-Graph

This section is dedicated to the proof of Lemma 3.4.2. We define a new
combinatorial object, called a Duo-of-Expanders System.

######  Definition..

A Duo-of-Expanders System of width $w$, expansion $\alpha$ (see Figure 3.7)
consists of:

  * •

two disjoint graphs $T_{1},T_{2}$, each of which is an $\alpha$-expander;

  * •

a set $X$ of $w$ vertices that are disjoint from $T_{1}\cup T_{2}$, and three
subsets $D_{0},D_{1}\subseteq V(T_{1})$ and $D_{2}\subseteq V(T_{2})$ of $w$
vertices each, where all three subsets are disjoint; and

  * •

a complete matching $\tilde{\mathcal{M}}$ between the vertices of $X$ and the
vertices of $D_{0}$, and a complete matching $\tilde{\mathcal{M}}^{\prime}$
between the vertices of $D_{1}$ and the vertices of $D_{2}$, so
$|\tilde{\mathcal{M}}|=|\tilde{\mathcal{M}}^{\prime}|=w$.

We denote the Duo-of-Expanders System by
${\mathcal{D}}=(T_{1},T_{2},X,\tilde{\mathcal{M}},\tilde{\mathcal{M}}^{\prime})$.
The set $X$ of vertices is called the _backbone_ of ${\mathcal{D}}$. Let
$G_{{\mathcal{D}}}$ be the graph corresponding to the Duo-of-Expanders System
${\mathcal{D}}$, so $G_{{\mathcal{D}}}$ is the union of graphs $T_{1},T_{2}$,
the set $X$ of vertices, and the set
$\tilde{\mathcal{M}}\cup\tilde{\mathcal{M}}^{\prime}$ of edges.

Figure 3.7: An illustration of the Duo-of-Expanders System.

Similarly to Path-of-Expanders System, given a graph $G$, we say that it
contains a Duo-of-Expanders System ${\mathcal{D}}$ as a minor iff
$G_{{\mathcal{D}}}$ is a minor of $G$.

The following lemma is central to the proof of Lemma 3.4.2.

######  Lemma 3.4.5.

There is an efficient algorithm that, given a Duo-of-Expanders System
${\mathcal{D}}$ of width $w/4$ and expansion $\alpha$, for some $0<\alpha<1$,
such that the corresponding graph $G_{{\mathcal{D}}}$ contains at most $n$
vertices and has maximum vertex degree at most $d$, together with a collection
$\left\\{X_{1},\ldots,X_{2r}\right\\}$ of mutually disjoint subsets of the
backbone $X$ of cardinality $\sigma=2^{15}\left\lfloor\frac{d^{3}n\log
n}{\alpha^{2}w}\right\rfloor$ each, where $r>\frac{w\alpha^{2}(\log\log
n)^{2}}{d^{3}\log^{3}n}$, returns a partition
${\mathcal{I}}^{\prime},{\mathcal{I}}^{\prime\prime}$ of
$\left\\{1,\ldots,r\right\\}$, and for each $j\in{\mathcal{I}}^{\prime}$, a
path $P_{j}$ connecting a vertex of $X_{j}$ to a vertex of $X_{j+r}$ in
$G_{{\mathcal{D}}}$, such that the paths in set
${\mathcal{P}}=\left\\{P_{j}\mid j\in{\mathcal{I}}^{\prime}\right\\}$ are
disjoint, and $|{\mathcal{I}}^{\prime\prime}|\leq r\cdot\frac{\log\log n}{\log
n}$.

We prove Lemma 3.4.5 after we complete the proof of Lemma 3.4.2 using it.
Recall that we are given a Path-of-Expanders System
$\Pi=({\mathcal{S}},{\mathcal{M}},A_{1},B_{6},{\mathcal{T}},{\mathcal{M}}^{\prime})$,
together with its corresponding graph $G_{\Pi}$. We are also given a subset
$A^{\prime}_{3}\subseteq A_{3}$ of at most $w/2$ vertices, and a partition of
$A^{\prime}_{3}$ into $2r$ disjoint subsets $A^{1}_{3},\ldots,A^{2r}_{3}$, of
cardinality $\rho=2^{16}\left\lfloor\frac{d^{3}n\log
n}{\alpha^{2}w}\right\rfloor$ each, where $r\geq\frac{w\alpha^{2}(\log\log
n)^{2}}{d^{3}\log^{3}n}$.

For each $1\leq i\leq 2r$, we arbitrarily partition $A_{3}^{i}$ into two
subsets, $W^{i}_{1},W^{i}_{2}$, of cardinality $\rho/2$ each (note that $\rho$
is an even integer). Let $W_{1}=\bigcup_{i=1}^{2r}W_{1}^{i}$ and let
$W_{2}=\bigcup_{i=1}^{2r}W^{i}_{2}$. Note that
$|W_{1}|,|W_{2}|\leq|A^{\prime}_{3}|/2\leq w/4$. We add arbitrary vertices of
$A_{3}\setminus A_{3}^{\prime}$ to $W_{1}$ and $W_{2}$, until each of them
contains $w/4$ vertices (recall that $w/4$ is an integer), while keeping them
disjoint. The vertices of $A_{3}\setminus(W_{1}\cup W_{2})$ are then
arbitrarily partitioned into two subsets, $Y_{1}$ and $Y_{2}$, of cardinality
$w/4$ each.

Next, we show that graph $G^{\prime\prime}_{\Pi}$ contains two disjoint Duo-
of-Expanders Systems as minors. We will then use Lemma 3.4.5 in each of the
two Duo-of-Expanders Systems in turn in order to obtain the desired routing.

######  Claim 3.4.6.

There is an efficient algorithm to compute two disjoint subgraphs, $G^{(1)}$
and $G^{(2)}$ of $G^{\prime\prime}_{\Pi}$, and for each
$z\in\left\\{1,2\right\\}$, to compute a model $f^{(z)}$ of a Duo-of-Expanders
System
${\mathcal{D}}^{(z)}=(T_{1}^{(z)},T_{2}^{(z)},X^{(z)},\tilde{\mathcal{M}}^{(z)},(\tilde{\mathcal{M}}^{\prime})^{(z)})$
of width $w/4$ and expansion $\alpha$ in $G^{(z)}$, such that the
corresponding graph $G_{{\mathcal{D}}^{(z)}}$ has maximum vertex degree at
most $d$, and for every vertex $w\in W_{z}$, there is a distinct vertex $v(w)$
in the backbone $X^{(z)}$, such that $w\in f^{(z)}(v(w))$.

The proof of this claim is deferred to Section B.2.2. We are now ready to
complete the proof of Lemma 3.4.2. We apply Lemma 3.4.5 to
${\mathcal{D}}^{(1)}$, together with vertex sets
$W_{1}^{1},\ldots,W_{1}^{2r}$, each of which now contains
$\rho/2=2^{15}\left\lfloor\frac{d^{3}n\log n}{\alpha^{2}w}\right\rfloor$
vertices obtaining a partition
$({\mathcal{I}}^{\prime},{\mathcal{I}}^{\prime\prime})$ of
$\left\\{1,\ldots,r\right\\}$, together with a set
${\mathcal{P}}_{1}=\left\\{P_{j}\mid j\in{\mathcal{I}}^{\prime}\right\\}$ of
disjoint paths in $G_{{\mathcal{D}}^{(1)}}$, such that for all
$j\in{\mathcal{I}}^{\prime}$ path $P_{j}$ connects a vertex of $W_{1}^{j}$ to
a vertex of $W_{1}^{r+j}$, and $|{\mathcal{I}}^{\prime\prime}|\leq
r\cdot\frac{\log\log n}{\log n}$. Since $G_{{\mathcal{D}}^{(1)}}$ is a minor
of $G^{(1)}$, it is immediate to obtain a collection
${\mathcal{P}}_{1}^{\prime}=\left\\{P^{\prime}_{j}\mid
j\in{\mathcal{I}}^{\prime}\right\\}$ of disjoint paths in $G^{(1)}$, such that
for all $j\in{\mathcal{I}}^{\prime}$ path $P^{\prime}_{j}$ connects a vertex
of $A_{3}^{j}$ to a vertex of $A_{3}^{j+r}$.

If $|{\mathcal{I}}^{\prime\prime}|\leq\frac{w\alpha^{2}(\log\log
n)^{2}}{d^{3}\log^{3}n}$, then we terminate the algorithm, and return the set
${\mathcal{P}}^{\prime}$ of paths, together with the partition
$({\mathcal{I}}^{\prime},{\mathcal{I}}^{\prime\prime})$ of ${\mathcal{I}}$.
Thus, we assume from now on that
$|{\mathcal{I}}^{\prime\prime}|>\frac{w\alpha^{2}(\log\log
n)^{2}}{d^{3}\log^{3}n}$.

For convenience, we denote $r^{\prime}:=|{\mathcal{I}}^{\prime\prime}|$. We
apply Lemma 3.4.5 to ${\mathcal{D}}^{(2)}$, together with vertex sets
$\left\\{W^{j}_{2},W^{j+r}_{2}\mid j\in{\mathcal{I}}^{\prime\prime}\right\\}$,
that are appropriately ordered. We then obtain a partition
${\mathcal{I}}_{1},{\mathcal{I}}_{2}$ of ${\mathcal{I}}^{\prime\prime}$, and a
set ${\mathcal{P}}_{2}=\left\\{P_{j}\mid j\in{\mathcal{I}}_{1}\right\\}$ of
disjoint paths in $G_{{\mathcal{D}}^{(2)}}$, such that for each
$j\in{\mathcal{I}}_{2}$ path $P_{j}$ connects a vertex of $W^{j}_{2}$ to a
vertex of $W_{2}^{j+r}$, and $|{\mathcal{I}}_{2}|\leq
r^{\prime}\cdot\frac{\log\log n}{\log n}\leq r\cdot\frac{(\log\log
n)^{2}}{\log^{2}n}$. As before, since $G_{{\mathcal{D}}^{(2)}}$ is a minor of
$G^{(2)}$, it is immediate to obtain a collection
${\mathcal{P}}_{2}^{\prime}=\left\\{P^{\prime}_{j}\mid
j\in{\mathcal{I}}_{1}\right\\}$ of disjoint paths in $G^{(2)}$, such that for
all $j\in{\mathcal{I}}_{1}$ path $P^{\prime}_{j}$ connects a vertex of
$A_{3}^{j}$ to a vertex of $A_{3}^{j+r}$. We return the partition
$({\mathcal{I}}^{\prime}\cup{\mathcal{I}}_{1},{\mathcal{I}}_{2})$ of
$\left\\{1,\ldots,r\right\\}$, together with the set
${\mathcal{P}}_{1}^{\prime}\cup{\mathcal{P}}_{2}^{\prime}$ of paths. Since the
graphs $G^{(1)}$ and $G^{(2)}$ are disjoint, all paths in
${\mathcal{P}}_{1}^{\prime}\cup{\mathcal{P}}_{2}^{\prime}$ are disjoint. It
now remains to show that $|{\mathcal{I}}_{2}|\leq\frac{w\alpha^{2}(\log\log
n)^{2}}{d^{3}\log^{3}n}$.

Recall that the set $A_{3}^{\prime}$, consisting of at most $w/2$ vertices, is
partitioned into $2r$ subsets of cardinality
$\rho=2^{16}\left\lfloor\frac{d^{3}n\log n}{\alpha^{2}w}\right\rfloor$ each.
Therefore:

$r\leq\frac{w}{4\rho}=\frac{w}{2^{18}\left\lfloor d^{3}n\log
n/(\alpha^{2}w)\right\rfloor}\leq\frac{w^{2}\alpha^{2}}{2^{17}d^{3}n\log
n}\leq\frac{w\alpha^{2}}{2^{17}d^{3}\log n}.$

We now conclude that $|{\mathcal{I}}_{2}|\leq r\cdot\frac{(\log\log
n)^{2}}{\log^{2}n}\leq\frac{w\alpha^{2}(\log\log n)^{2}}{d^{3}\log^{3}n}$, as
required. This completes the proof of Lemma 3.4.2 assuming Lemma 3.4.5 that we
complete in the remainder of this subsection.

##### Routing in Duo-of-Expanders — Proof of Lemma 3.4.5

Our proof is inspired by the algorithm of Frieze [Fri01] for routing a large
set of demand pairs in an expander graph via edge-disjoint paths. Recall that
we are given a Duo-of-Expanders System ${\mathcal{D}}$ of width $w/4$ and
expansion $\alpha$, for some $0<\alpha<1$, such that the maximum vertex degree
in the corresponding graph $G_{{\mathcal{D}}}=(V,E)$ is at most $d$, and
$|V|\leq n$. We are also given mutually disjoint subsets
$\left\\{X_{1},\ldots,X_{2r}\right\\}$ of the backbone $X$, of cardinality
$\sigma=2^{15}\left\lfloor\frac{d^{3}n\log n}{w\alpha^{2}}\right\rfloor$ each,
where $r>\frac{w\alpha^{2}(\log\log n)^{2}}{d^{3}\log^{3}n}$. In particular,
since $|X|=w/4$, we get that $2r\sigma\leq w/4$, and so
$r\leq\frac{w}{8\sigma}\leq\frac{w}{8\cdot 2^{15}\left\lfloor d^{3}n\log
n/(w\alpha^{2})\right\rfloor}\leq\frac{w^{2}\alpha^{2}}{2^{17}d^{3}n\log n}$.
Therefore, we obtain the following bounds on $r$ that we will use throughout
the proof:

$\frac{w\alpha^{2}}{d^{3}}\cdot\frac{(\log\log
n)^{2}}{\log^{3}n}<r\leq\frac{w^{2}\alpha^{2}}{2^{17}d^{3}n\log n}.$ (3.1)

For convenience, we will denote $G_{{\mathcal{D}}}$ by $G$ for the rest of
this subsection. We will iteratively construct the set ${\mathcal{P}}$ of
disjoint paths in $G$, where for each path $P\in{\mathcal{P}}$, there is some
index $j\in\left\\{1,\ldots,r\right\\}$, such that $P$ connects $X_{j}$ to
$X_{j+r}$. Whenever a path $P$ is added to ${\mathcal{P}}$, we delete all
vertices of $P$ from $G$. Throughout the algorithm, we say that an index
$j\in[r]$ is _settled_ iff there is a path $P_{j}\in{\mathcal{P}}$ connecting
$X_{j}$ to $X_{j+r}$, and otherwise we say that it is _not settled_. We use a
parameter $\gamma=512nd^{2}/w\alpha$. We say that a path $P$ in $G$ is
_permissible_ iff $P$ contains at most $\gamma\log\log n$ nodes of $T_{1}$ and
at most $\gamma\log n$ nodes of $T_{2}$.

###### The Algorithm.

Start with ${\mathcal{P}}=\emptyset$. While there is an index $j\in[r]$ and a
permissible path $P^{*}_{j}$ in the current graph $G:=G_{{\mathcal{D}}}$ such
that:

  * •

$j$ is not settled;

  * •

$P^{*}_{j}$ connects $X_{j}$ to $X_{j+r}$; and

  * •

$P^{*}_{j}$ is internally disjoint from $X$:

add $P^{*}_{j}$ to ${\mathcal{P}}$ and delete all vertices of $P^{*}_{j}$ from
$G$.

In order to complete the proof of Lemma 3.4.5, it is enough to show that, when
the algorithm terminates, at most $\frac{r\log\log n}{\log n}$ indices
$j\in[r]$ are not settled. Assume for contradiction that this is not true. Let
${\mathcal{P}}$ be the path set obtained at the end of the algorithm, and let
$\tilde{V}=V({\mathcal{P}})$ be the set of vertices participating in the paths
of ${\mathcal{P}}$. We further partition $\tilde{V}$ into three subsets:
$\tilde{V}_{1}=\tilde{V}\cap V(T_{1})$; $\tilde{V}_{2}=\tilde{V}\cap
V(T_{2})$; and $\tilde{X}=\tilde{V}\cap X$. Note that, since
$|{\mathcal{P}}|\leq r$, we are guaranteed that $|\tilde{V}_{1}|\leq\gamma
r\log\log n$; $|\tilde{V}_{2}|\leq\gamma r\log n$, and, since we have assumed
that $|{\mathcal{P}}|\leq r(1-\log\log n/\log n)$, and all paths in
${\mathcal{P}}$ are internally disjoint from $X$, we get that $|\tilde{X}|\leq
2r-\frac{2r\log\log n}{\log n}$.

We now proceed as follows. First, we show that $T_{1}\setminus\tilde{V}_{1}$
and $T_{2}\setminus\tilde{V}_{2}$ both contain very large
$\alpha/4$-expanders. We also show that there is a large number of edges in
$\tilde{\mathcal{M}}^{\prime}$ that connect these two expanders. This will be
used to show that there must still be a permissible path $P^{*}_{j}$,
connecting two sets $X_{j}$ and $X_{j+r}$ for some index $j$ that is not
settled yet, leading to a contradiction. We start with the following claim
that allows us to find large expanders in $T_{1}\setminus\tilde{V}_{1}$ and
$T_{2}\setminus\tilde{V}_{2}$.

######  Claim 3.4.7.

Let $T$ be an $\alpha$-expander with maximum vertex degree at most $d$, and
let $Z$ be any subset of vertices of $T$. Then there is an $\alpha/4$-expander
$T^{\prime}\subseteq T\setminus Z$, with
$|V(T^{\prime})|\geq|V(T)|-\frac{4d|Z|}{\alpha}$.

The proof of Claim 3.4.7 follows immediately from Claim 3.2.3, by letting
$E^{\prime}$ be the set of all edges incident to the vertices of $Z$. The
following corollary follows immediately from Claim 3.4.7

######  Corollary 3.4.8.

There is a subgraph $T^{\prime}_{1}\subseteq T_{1}\setminus\tilde{V}_{1}$ that
is an $\alpha/4$-expander, and $|V(T_{1})\setminus V(T^{\prime}_{1})|\leq
4dr\gamma\log\log n/\alpha$. Similarly, there is a subgraph
$T^{\prime}_{2}\subseteq T_{2}\setminus\tilde{V}_{2}$ that is an
$\alpha/4$-expander, and $|V(T_{2})\setminus V(T^{\prime}_{2})|\leq
4dr\gamma\log n/\alpha$.

Let $R_{1}=V(T_{1})\setminus V(T_{1}^{\prime})$ and let
$R_{2}=V(T_{2})\setminus V(T_{2}^{\prime})$. We refer to the vertices of
$R_{1}$ and $R_{2}$ as the vertices that were _discarded_ from $T_{1}$ and
$T_{2}$, respectively. The vertices that belong to $T_{1}^{\prime}$ and
$T_{2}^{\prime}$ are called _surviving_ vertices. It is easy to verify that
$|R_{1}|,|R_{2}|\leq w/64$. Indeed, observe that $|R_{1}|,|R_{2}|\leq
4dr\gamma\log n/\alpha$. Since, from Equation 3.1,
$r\leq\frac{w^{2}\alpha^{2}}{2^{17}d^{3}n\log n}$, we get that altogether:

$|R_{1}|,|R_{2}|\leq\frac{4dr\gamma\log n}{\alpha}\leq\frac{\gamma
w^{2}\alpha}{2^{15}d^{2}n}\leq\frac{w}{64},$

since $\gamma=512nd^{2}/w\alpha$.

Recall that the Duo-of-Expanders ${\mathcal{D}}$ contains a matching
$\tilde{\mathcal{M}}^{\prime}$ between the set $D_{1}\subseteq V(T_{1})$ of
$w/4$ vertices and the set $D_{2}\subseteq V(T_{2})$ of $w/4$ vertices. Next,
we show that there are large subsets $D^{\prime}_{1}\subseteq D_{1}$ and
$D^{\prime}_{2}\subseteq D_{2}$ of surviving vertices, such that a subset of
$\tilde{\mathcal{M}}^{\prime}$ defines a complete matching between them.

######  Observation 3.4.9.

There are two sets $D^{\prime}_{1}\subseteq D_{1}$ and
$D_{2}^{\prime}\subseteq D_{2}$ containing at least $w/16$ vertices each, and
a subset $\hat{\mathcal{M}}\subseteq\tilde{\mathcal{M}}^{\prime}$ of edges,
such that $\hat{\mathcal{M}}$ is a complete matching between $D_{1}^{\prime}$
and $D_{2}^{\prime}$.

###### Proof.

Let $\hat{D}_{1}=D_{1}\setminus R_{1}$. Since $|R_{1}|\leq w/64$,
$|\hat{D}_{1}|\geq w/8$. Let
$\hat{\mathcal{M}}^{\prime}\subseteq{\mathcal{M}}^{\prime}$ be the set of
edges whose endpoints lie in $\hat{D}_{1}$, and let $\hat{D}_{2}\subseteq
D_{2}$ be the set of vertices that serve as endpoints for the edges in
$\hat{\mathcal{M}}^{\prime}$, so $|\hat{D}_{2}|\geq w/8$. Finally, let
$D_{2}^{\prime}=D_{2}\setminus R_{2}$, so $|D_{2}^{\prime}|\geq
w/8-|R_{2}|\geq w/16$. We let
$\hat{\mathcal{M}}\subseteq\hat{\mathcal{M}}^{\prime}$ be the set of all edges
incident to the vertices of $D_{2}^{\prime}$, and we let $D_{1}^{\prime}$ be
the set of endpoints of these edges.

Our second main tool is the following claim, that shows that for any pair of
large enough sets of vertices in an expander, there is a short path connecting
them. The proof uses standard methods and is deferred to Section B.2.1.

######  Claim 3.4.10.

Let $T$ be an $\alpha^{\prime}$-expander for some $0<\alpha^{\prime}<1$, such
that $|V(T)|\leq n$, and the maximum vertex degree in $T$ is at most $d$. Let
$Z,Z^{\prime}\subseteq V(T)$ be two vertex subsets, with $|Z|=z$ and
$|Z^{\prime}|=z^{\prime}$. Then there is a path in $T$, connecting a vertex of
$Z$ to a vertex of $Z^{\prime}$, whose length is at most
$\frac{8d}{\alpha^{\prime}}(\log(n/z)+\log(n/z^{\prime}))$. In particular, for
every pair $v,v^{\prime}$ of vertices in $T$, there is a path of length at
most $16d\log n/\alpha^{\prime}$ connecting $v$ to $v^{\prime}$ in $T$.

Let $J\subseteq\left\\{1,\ldots,r\right\\}$ be the set of indices that are not
settled yet. From our assumption, $|J|\geq\frac{r\log\log n}{\log n}$. For
every index $j\in J$, consider the corresponding sets $X_{j},X_{j+r}$ of
vertices of $X$, and let $Y_{j},Y_{j+r}$ be the sets of vertices of $D_{0}$,
that are connected to $X_{j}$ and $X_{j+r}$ via the matching
$\tilde{\mathcal{M}}$. Let $Y_{j}^{\prime}=Y_{j}\setminus R_{1}$ and let
$Y_{j+r}^{\prime}=Y_{j+r}\setminus R_{1}$ be the subsets of surviving vertices
in $Y_{j}$ and $Y_{j+r}$ respectively. We say that index $j$ is _bad_ iff
$|Y^{\prime}_{j}|<\sigma/2$ or $|Y^{\prime}_{j+r}|<\sigma/2$; otherwise we say
that it is a _good index_. Recall that $|R_{1}|\leq 4dr\gamma\log\log
n/\alpha$. Therefore, the total number of bad indices is at most:

$\begin{split}\frac{2|R_{1}|}{\sigma}&\leq\frac{8dr\gamma\log\log
n}{\alpha\cdot 2^{15}\left\lfloor d^{3}n\log n/(w\alpha^{2})\right\rfloor}\\\
&\leq\frac{w\alpha r\gamma\log\log n}{2^{11}d^{2}n\log n}\\\
&\leq\frac{r\log\log n}{4\log n}\cdot\frac{w\alpha\gamma}{512d^{2}n}\\\
&\leq\frac{r\log\log n}{4\log n},\end{split}$

since $\gamma=512nd^{2}/w\alpha$.

Let $J^{\prime}\subseteq J$ be the set of all good indices, so
$|J^{\prime}|\geq\frac{r\log\log n}{2\log n}$. We say that an index $j\in
J^{\prime}$ is _happy_ iff there is a path $P_{1}(j)$ in $T^{\prime}_{1}$, of
length at most $(\gamma\log\log n)/4$, connecting a vertex of $Y^{\prime}_{j}$
to a vertex of $D^{\prime}_{1}$, and there is a path $P_{2}(j)$ in
$T^{\prime}_{1}$, of length at most $(\gamma\log\log n)/4$, connecting a
vertex of $Y^{\prime}_{j+r}$ to a vertex of $D^{\prime}_{1}$. The following
claim, whose proof is deferred to Section B.2.4 will complete the proof of
Lemma 3.4.2.

######  Claim 3.4.11.

At least one index of $J^{\prime}$ is happy.

Consider the paths $P_{1}(j)$ and $P_{2}(j)$ in $T^{\prime}$, given by Claim
3.4.11, and assume that path $P_{1}(j)$ connects a vertex $v\in
Y^{\prime}_{j}$ to a vertex $v^{\prime}\in D^{\prime}_{1}$. Let
$v^{\prime\prime}\in D^{\prime}_{2}$ be the vertex connected to $v^{\prime}$
by an edge of $\hat{\mathcal{M}}$, that we denote by $e_{v}$. Similarly,
assume that path $P_{2}(j)$ connects a vertex $u\in Y^{\prime}_{j}$ to a
vertex $u^{\prime}\in D^{\prime}_{1}$. Let $u^{\prime\prime}\in
D^{\prime}_{2}$ be the vertex connected to $u^{\prime}$ by an edge of
$\hat{\mathcal{M}}$, that we denote by $e_{u}$. From Claim 3.4.10, there is a
path $P$ in $T_{2}^{\prime}$, of length at most $64d\log n/\alpha<\gamma\log
n$, connecting $v^{\prime\prime}$ to $u^{\prime\prime}$. By combining
$P_{1}(j),e_{v},P^{\prime},e_{u},P_{2}(j)$, together with the edges of
$\tilde{\mathcal{M}}$ incident to $u$ and $v$, we obtain an admissible path,
connecting a vertex of $X_{j}$ to a vertex of $X_{j+r}$, a contradiction. This
completes the proof of Lemma 3.4.2.

####  3.4.2 Embedding Remaining Edges of the Target-Graph

The goal of this subsection is to prove Lemma 3.4.4. We use the following
lemma, whose proof uses standard techniques and is deferred to Section B.2.5.

######  Lemma 3.4.12.

There is a universal constant $c$, and an efficient randomized algorithm,
that, given graph $G=(V,E)$ with $|V|\leq n$, such that the maximum vertex
degree in $G$ is at most $d$ and a parameter $0<\alpha<1$, together with a
collection $\left\\{C_{1},\ldots,C_{2r}\right\\}$ of mutually disjoint subsets
of $V$ of cardinality $q=\left\lceil cd^{2}\log^{2}n/\alpha^{2}\right\rceil$
each, computes one of the following:

  * •

either a collection ${\mathcal{Q}}=\left\\{Q_{1},\ldots,Q_{r}\right\\}$ of
paths in $G$, where for each $1\leq j\leq r$, path $Q_{j}$ connects a vertex
of $C_{j}$ to a vertex of $C_{r+j}$, and with high probability the paths in
${\mathcal{Q}}$ are disjoint; or

  * •

a cut $(S,S^{\prime})$ in $G$ of sparsity less than $\alpha$.

Consider the subgraph $W^{\prime}$ of $G_{\Pi}$; recall that it consists of
two graphs, $S_{1}$ and $T_{1}$, where $S_{1}$ is a connected graph and
$T_{1}$ is an $\alpha$-expander. Recall that $S_{1}$ contains a set $B_{1}$ of
$w$ vertices; $T_{1}$ contains a set $C_{1}$ of $w$ vertices, and
${\mathcal{M}}^{\prime}_{1}$ is a perfect matching between these two sets.

We let $q=\left\lceil cd\log^{2}n/\alpha^{2}\right\rceil$, where $c$ is the
constant from Lemma 3.4.12, and we let $r=\left\lfloor
w/dq\right\rfloor=\Omega(w\alpha^{2}/d^{3}\log^{2}n)$. Observe that
$q\leq\left\lfloor w/dr\right\rfloor$. We use Observation 3.4.1 to compute $r$
connected subgraphs $S^{1},\ldots,S^{r}$ of $S_{1}$, each of which contains at
least $\left\lfloor w/dr\right\rfloor\geq q$ vertices of $B_{1}$. For $1\leq
i\leq r$, we denote $B^{i}=B_{1}\cap V(S^{i})$. We also let
${\mathcal{M}}^{i}\subseteq{\mathcal{M}}^{\prime}_{1}$ be the set of edges
incident to the vertices of $B^{i}$ in ${\mathcal{M}}^{\prime}_{1}$, and we
let $C^{i}\subseteq C_{1}$ be the set of the endpoints of the edges of
${\mathcal{M}}^{i}$ that lie in $C_{1}$. Observe that for all $1\leq i\leq
2r$, $|C^{i}|\geq q$. For each $1\leq i\leq 2r$, we select an arbitrary vertex
$b_{i}\in B^{i}$, and we let $B^{\prime}=\left\\{b_{i}\mid 1\leq i\leq
2r\right\\}$, so that $|B^{\prime}|=2r=\Omega(w\alpha^{2}/d^{3}\log^{2}n)$, as
required.

Assume now that we are given an arbitrary matching ${\mathcal{M}}^{*}$ over
the vertices of $B^{\prime}$. By appropriately re-indexing the sets $B^{i}$,
we can assume w.l.o.g. that
${\mathcal{M}}^{*}=\left\\{(b_{i},b_{r+i})\right\\}_{i=1}^{r}$. Since $T_{1}$
is an $\alpha$-expander, the algorithm of Lemma 3.4.12 computes a collection
${\mathcal{Q}}=\left\\{Q_{1},\ldots,Q_{r}\right\\}$ of paths in $T_{1}$, where
for each $1\leq j\leq r$, path $Q_{j}$ connects some vertex $c^{*}_{j}\in
C^{j}$ to some vertex $c^{*}_{j+r}\in C^{j+r}$, and with high probability the
paths in ${\mathcal{Q}}$ are disjoint.

Consider now some index $1\leq j\leq 2r$. We let $e_{j}$ be the unique edge of
the matching ${\mathcal{M}}^{\prime}_{1}$ incident to $c^{*}_{j}$, and we let
$b^{*}_{j}\in B^{j}$ be the other endpoint of this edge. Since graph $S^{j}$
is connected, and it contains both $b_{j}$ and $b^{*}_{j}$, we can find a path
$P_{j}$ in $S^{j}$, connecting $b_{j}$ to $b^{*}_{j}$. For each $1\leq j\leq
r$, let $P^{*}_{j}$ be the path obtained by concatenating
$P_{j},e_{j},Q_{j},e_{j+r},P_{j+r}$, and let
${\mathcal{P}}^{*}=\left\\{P^{*}_{j}\mid 1\leq j\leq r\right\\}$. It is
immediate to verify that, if the paths in ${\mathcal{Q}}$ are disjoint from
each other, then so are the paths in ${\mathcal{P}}^{*}$, since all graphs in
$\left\\{S^{j}\mid 1\leq j\leq 2r\right\\}$ are disjoint from each other and
from $T_{1}$. Moreover, for each $1\leq j\leq r$, path $P^{*}_{j}$ connects
$b_{j}$ to $b_{j+r}$. Thus, we have obtained a set ${\mathcal{P}}^{*}$ of
disjoint paths in $W_{1}$ routing ${\mathcal{M}}^{*}$ as required. This
completes the proof of Lemma 3.4.4.

###  3.5 Large Path-of-Expanders System in Expanders

The goal of this section is to prove Theorem 3.3.2. Recall that we are given
an $\alpha$-expander $G$ and our goal is to construct a Path-of-Expanders
System $\Pi$ with large enough expansion and width, such that the
corresponding graph $G_{\Pi}$ is low degree and is a minor of $G$. Our
algorithm consists of three parts. In the first part, we construct an
$\alpha^{\prime}$-expanding Path-of-Sets System of length $24$ in $G$, for
some $\alpha^{\prime}$ to be fixed later. In the second part, we transform it
into a Strong Path-of-Sets System of the same length. In the third and the
final part, we turn the Strong Path-of-Sets System into a Path-of-Expanders
System with the guarantees claimed in Theorem 3.3.2.

####  3.5.1 Expanding Path-of-Sets System

The main technical result of this section is the following theorem.

######  Theorem 3.5.1.

There is a constant $c_{x}>3$, and a deterministic algorithm, that, given an
$n$-vertex $\alpha$-expander $G$ with maximum vertex degree at most $d$, where
$0<\alpha<1$, computes, in time
$\operatorname{poly}(n)\cdot\left(\frac{d}{\alpha}\right)^{O(\log(d/\alpha))}$
a partition $(V^{\prime},V^{\prime\prime})$ of $V(G)$, such that
$|V^{\prime}|,|V^{\prime\prime}|\geq\frac{\alpha|V(G)|}{256d}$, and each graph
$G[V^{\prime}],G[V^{\prime\prime}]$ is an $\alpha^{*}$-expander, for
$\alpha^{*}\geq\left(\frac{\alpha}{d}\right)^{c_{x}}$.

The main tool that we use in the proof of the theorem is the following lemma,
that we prove first.

######  Lemma 3.5.2.

There is a constant $c^{\prime}_{x}$, and deterministic algorithm, that, given
an $n$-vertex $\alpha$-expander $G$ with maximum vertex degree at most $d$,
where $0<\alpha<1$, computes, in time
$\operatorname{poly}(n)\cdot\left(\frac{d}{\alpha}\right)^{O(\log(d/\alpha))}$,
a subset $V^{\prime}\subseteq V(G)$ of vertices, such that
$\frac{\alpha|V(G)|}{256d}\leq|V^{\prime}|\leq\frac{\alpha|V(G)|}{8d}$, and
$G[V^{\prime}]$ is an $\hat{\alpha}^{*}$-expander, for
$\hat{\alpha}^{*}\geq\left(\frac{\alpha}{d}\right)^{c^{\prime}_{x}}$.

###### Proof.

Given a graph $G$, we say that a partition $(U^{\prime},U^{\prime\prime})$ of
$V(G)$ is a _balanced cut_ iff $|U^{\prime}|,|U^{\prime\prime}|\geq|V(G)|/4$.
Our starting point is the following claim whose proof by Cheeger’s inequality
(Theorem 3.2.2) is present in Section B.3.1.

######  Claim 3.5.3.

There is an efficient algorithm that, given an $n$-vertex graph $G=(V,E)$, and
a parameter $\beta$, returns one of the following:

  * •

either a subset $V^{\prime}\subseteq V$ of vertices, such that
$n/2\leq|V^{\prime}|\leq 3n/4$ and $G[V^{\prime}]$ is an
$\Omega(\frac{\beta^{2}}{d})$-expander;

  * •

or a partition $(S,T)$ of $V$ with
$|E_{G}(S,T)|<\beta\cdot\min\left\\{|S|,|T|\right\\}$.

By combining Claim 3.5.3 with Observation 3.2.1, we obtain the following
simple corollary.

######  Corollary 3.5.4.

There is an efficient algorithm that, given an $n$-vertex graph $G=(V,E)$ with
maximum vertex degree at most $d$, and a parameter $\beta$, returns one of the
following:

  * •

either a subset $V^{\prime}\subseteq V$ of vertices, such that
$n/4\leq|V^{\prime}|\leq 3n/4$ and $G[V^{\prime}]$ is an
$\Omega(\frac{\beta^{2}}{d})$-expander;

  * •

or a balanced partition $(S,T)$ of $V$ with
$|E_{G}(S,T)|<\beta\cdot\min\left\\{|S|,|T|\right\\}$.

The proof of Corollary 3.5.4 is present in Section B.3.2. We now turn to
complete the proof of Lemma 3.5.2. We denote $|V(G)|=n$, and let
${n^{*}=\alpha|V(G)|/(8d)}$. Our goal now is to compute a subset
$V^{\prime}\subseteq V(G)$ of vertices, with $n^{*}/32\leq|V^{\prime}|\leq
n^{*}$, such that $G[V^{\prime}]$ is an $\hat{\alpha}^{*}$-expander, where
$\hat{\alpha}^{*}\geq\left(\frac{\alpha}{d}\right)^{c^{\prime}_{x}}$ for some
constant $c^{\prime}_{x}$. Our algorithm is recursive. Over the course of the
algorithm, we will consider smaller and smaller sub-graphs of $G$, containing
at least $n^{*}/4$ vertices each. For each such subgraph $G^{\prime}\subseteq
G$, we define its _level_ $L(G^{\prime})$ as follows. Let
$n^{\prime}=|V(G^{\prime})|$. If $n^{\prime}\leq 4n^{*}/3$, then
$L(G^{\prime})=0$; otherwise,
$L(G^{\prime})=\left\lceil\log_{4/3}(n^{\prime}/n^{*})\right\rceil$.
Intuitively, $L(G^{\prime})$ is the number of recursive levels that we will
use for processing $G^{\prime}$. Notice that, from the definition of $n^{*}$,
$L(G)\leq O(\log(d/\alpha))$. We use the following claim.

######  Claim 3.5.5.

There is a deterministic algorithm, that, given a subgraph
$G^{\prime}\subseteq G$, such that $|V(G^{\prime})|\geq n^{*}/4$, and a
parameter $0<\beta<1$, returns one of the following:

  * •

Either a balanced cut $(S,T)$ in $G^{\prime}$ with
$|E_{G^{\prime}}(S,T)|<\beta\cdot\min\left\\{|S|,|T|\right\\}$; or

  * •

A subset $V^{\prime}\subseteq V(G^{\prime})$ of vertices of $G^{\prime}$, such
that $n^{*}/32\leq|V^{\prime}|\leq n^{*}$, and $G^{\prime}[V^{\prime}]$ is an
$\hat{\beta}$-expander, for
$\hat{\beta}\geq\Omega\left(\frac{\beta^{2}}{d\cdot
2^{10L(G^{\prime})}}\right)$.

The running time of the algorithm is
$\operatorname{poly}(n)\cdot\left(\frac{256d}{\hat{\beta}}\right)^{L(G^{\prime})}$.

We prove the claim below, after we complete the proof of Lemma 3.5.2 using it.
We apply Claim 3.5.5 to the input graph $G$ and the parameter $\alpha$. Since
$G$ is an $\alpha$-expander, we cannot obtain a cut $(S,T)$ in $G$ with
$|E(S,T)|<\alpha\min\left\\{|S|,|T|\right\\}$. Therefore, the outcome of the
algorithm is a subset $V^{\prime}\subseteq V$ of vertices of $G$, with
$n^{*}/32\leq V^{\prime}\leq n^{*}$, such that $G[V^{\prime}]$ is a
$\hat{\alpha}$-expander, for
$\hat{\alpha}=\Omega\left(\frac{\alpha^{2}}{d\cdot 2^{10L(G)}}\right)$, in
time
$\operatorname{poly}(n)\cdot\left(\frac{256d}{\hat{\alpha}}\right)^{L(G)}$.
Recall that $L(G)\leq O(\log(d/\alpha))$. Therefore, we get that
$\hat{\alpha}=\Omega\left(\frac{\alpha^{2}}{d\cdot
2^{O(\log(d/\alpha))}}\right)\geq(\alpha/d)^{c^{\prime}_{x}}$ for some
constant $c^{\prime}_{x}$, and the running time of the algorithm is
$\operatorname{poly}(n)\cdot\left(\frac{d}{\alpha}\right)^{O(\log(d/\alpha))}$.
This completes the proof of Lemma 3.5.2 assuming Claim 3.5.5 that we show
next.

Proof of Claim 3.5.5. We denote $|V(G^{\prime})|=n^{\prime}$. We let $c$ be a
large enough constant. We prove by induction on $L(G^{\prime})$ that the claim
is true, with the running time of the algorithm bounded by
$n^{c}\cdot\left(256d/\beta\right)^{L(G^{\prime})}$. The base of the recursion
is when $L(G^{\prime})=0$, and so $n^{*}/4\leq n^{\prime}\leq 4n^{*}/3$. We
apply Corollary 3.5.4 to graph $G^{\prime}$ with the parameter $\beta$. If the
outcome of the corollary is a subset $V^{\prime}\subseteq V(G^{\prime})$ of
vertices with $n^{\prime}/4\leq|V^{\prime}|\leq 3n^{\prime}/4$, such that
$G^{\prime}[V^{\prime}]$ is an $\Omega(\beta^{2}/d)$-expander, then we
terminate the algorithm and return $V^{\prime}$. Notice that in this case, we
are guaranteed that $n^{*}/16\leq|V^{\prime}|\leq n^{*}$. Otherwise, the
algorithm returns a balanced cut $(S,T)$ in $G^{\prime}$, with
$|E_{G^{\prime}}(S,T)|<\beta\cdot\min\left\\{|S|,|T|\right\\}$. We then return
this cut. The running time of the algorithm is $\operatorname{poly}(n)$.

We now assume that the theorem holds for all graphs $G^{\prime}$ with
$L(G^{\prime})<i$, for some integer $i>0$, and prove it for a given graph
$G^{\prime}$ with $L(G^{\prime})=i$. Let $n^{\prime}=|V(G^{\prime})|$. The
proof is somewhat similar to the proof of Corollary 3.5.4. Throughout the
algorithm, we maintain a balanced cut $(U^{\prime},U^{\prime\prime})$ of
$G^{\prime}$, with $|U^{\prime}|\geq|U^{\prime\prime}|$. Initially, we start
with an arbitrary such balanced cut. Notice that
$|E(U^{\prime},U^{\prime\prime})|\leq|E(G^{\prime})|\leq n^{\prime}d$. While
$|E(U^{\prime},U^{\prime\prime})|\geq\beta n^{\prime}/4$, we perform
iterations (that we call phases for convenience, since each of them consists
of a number of iterations). At the end of every phase, we either compute a
subset $V^{\prime}\subseteq V(G^{\prime})$ of vertices of $G^{\prime}$, such
that $n^{*}/32\leq|V^{\prime}|\leq n^{*}$, and $G^{\prime}[V^{\prime}]$ is an
$\hat{\beta}$-expander, in which case we terminate the algorithm and return
$V^{\prime}$; or we compute a new balanced cut $(J^{\prime},J^{\prime\prime})$
in $G^{\prime}$, such that
$|E(J^{\prime},J^{\prime\prime})|\leq|E(U^{\prime},U^{\prime\prime})|-\frac{\beta
n^{\prime}}{32}$. If $|E(J^{\prime},J^{\prime\prime})|<\beta n^{\prime}/4$,
then we return this cut; it is easy to verify that
$|E(J^{\prime},J^{\prime\prime})|<\beta\cdot\min\left\\{|J^{\prime}|,|J^{\prime\prime}|\right\\}$.
Otherwise, we replace $(U^{\prime},U^{\prime\prime})$ with the new cut
$(J^{\prime},J^{\prime\prime})$, and continue to the next iteration. Since
initially $|E(U^{\prime},U^{\prime\prime})|\leq n^{\prime}d$, and since
$|E(U^{\prime},U^{\prime\prime})|$ decreases by at least $\frac{\beta
n^{\prime}}{32}$ in every phase, the number of phases is bounded by
$\frac{32d}{\beta}$. We now proceed to describe a single phase.

###### An execution of a phase.

We assume that we are given a balanced cut $(U^{\prime},U^{\prime\prime})$ in
$G^{\prime}$, with $|U^{\prime}|\geq|U^{\prime\prime}|$, and
$|E(U^{\prime},U^{\prime\prime})|\geq\beta n^{\prime}/4$. Our goal is to
either compute a subset $V^{\prime}$ of vertices of $G^{\prime}$ such that
$n^{*}/32\leq|V^{\prime}|\leq n^{*}$ and $G^{\prime}[V^{\prime}]$ is an
$\hat{\beta}$-expander, or return another balanced cut
$(J^{\prime},J^{\prime\prime})$ in $G^{\prime}$, with
$|E(J^{\prime},J^{\prime\prime})|\leq|E(U^{\prime},U^{\prime\prime})|-\frac{\beta
n^{\prime}}{32}$. Let $\beta^{\prime}=\beta/32$. Over the course of the
algorithm, we will maintain a set $E^{\prime}$ of edges that we remove from
the graph, starting with $E^{\prime}=\emptyset$, and a collection
${\mathcal{G}}$ of subgraphs of $G[U^{\prime}]$ (that will contain at most $4$
such subgraphs). As each graph $H\in{\mathcal{G}}$ is a subgraph of
$G[U^{\prime}]$, we are guaranteed that $|V(H)|\leq 3n^{\prime}/4$, and so
$L(H)\leq L(G^{\prime})-1$. We start with ${\mathcal{H}}$ containing a single
graph, the graph $G^{\prime}[U^{\prime}]$. We then iterate, while there is a
graph $H\in{\mathcal{H}}$ with $|V(H)|>|U^{\prime}|/2$.

In every iteration, we let $H\in{\mathcal{H}}$ be the unique graph with
$|V(H)|>|U^{\prime}|/2$. Notice that $|V(H)|\geq n^{\prime}/4\geq n^{*}/3$,
since we have assumed that $L(G^{\prime})>0$ and so $n^{\prime}\geq 4n^{*}/3$.
We apply the algorithm from the induction hypothesis to $H$, with the
parameter $\beta^{\prime}=\beta/32$. If the outcome is a subset
$V^{\prime}\subseteq V(H)$ of vertices of $G^{\prime}$, such that
$n^{*}/32\leq|V^{\prime}|\leq n^{*}$ and $H[V^{\prime}]$ is a
$\hat{\beta}^{\prime}$-expander, for
$\hat{\beta}^{\prime}\geq\Omega\left(\frac{(\beta^{\prime})^{2}}{d\cdot
2^{10L(H)}}\right)$ then we terminate the algorithm and return $V^{\prime}$.
Notice that, since $L(H)\leq L(G)-1$, and $\beta^{\prime}=\beta/32$, we get
that $\frac{(\beta^{\prime})^{2}}{d\cdot
2^{10L(H)}}\geq\frac{\beta^{2}}{d\cdot 2^{10L(G^{\prime})}}$, so
$G^{\prime}[V^{\prime}]$ is a $\hat{\beta}$-expander. Otherwise, the algorithm
returns a balanced cut $(S,T)$ of $V(H)$, such that
$|E(S,T)|<\beta^{\prime}\cdot\min\left\\{|S|,|T|\right\\}$. We add the edges
of $E(S,T)$ to $E^{\prime}$, remove $H$ from ${\mathcal{H}}$, and add $H[S]$
and $H[T]$ to ${\mathcal{H}}$. The algorithm terminates once for every graph
$H\in{\mathcal{H}}$, $|V(H)|\leq|U^{\prime}|/2$. Let $r=|{\mathcal{H}}|$ at
the end of the algorithm. Since the cuts $(S,T)$ that we compute in every
iteration are balanced, it is easy to verify that we run the algorithm from
the induction hypothesis at most $3$ times, and that $r\leq 4$, since in every
iteration the size of the largest graph in ${\mathcal{H}}$ decreases by at
least factor $3/4$, and $(3/4)^{3}<1/2$. Denote
${\mathcal{H}}=\left\\{H_{1},\ldots,H_{r}\right\\}$, and for each $1\leq j\leq
r$, let $V_{j}=V(H_{j})$, and let $m_{j}=|E(V_{j},U^{\prime\prime})|$. Since
$|E(U^{\prime},U^{\prime\prime})|\geq\beta n^{\prime}/4$, there is some index
$1\leq j\leq r$, such that $|E(V_{j},U^{\prime\prime})|\geq\beta
n^{\prime}/16$. We define a new balanced cut $(J^{\prime},J^{\prime\prime})$,
by setting $J^{\prime}=U^{\prime}\setminus V_{j}$ and
$J^{\prime\prime}=U^{\prime\prime}\cup V_{j}$. Since
$|V_{j}|\leq|U^{\prime}|/2$, it is immediate to verify that it is a balanced
cut. Moreover, it is immediate to verify that
$|E^{\prime}|\leq\beta^{\prime}|U^{\prime}|\leq
3\beta^{\prime}n^{\prime}/4\leq\beta n^{\prime}/32$, and so:

$|E(J^{\prime},J^{\prime\prime})|\leq|E(U^{\prime},U^{\prime\prime})|-|E(V_{j},U^{\prime\prime})|+|E^{\prime}|\leq|E(U^{\prime},U^{\prime\prime})|-\frac{\beta
n^{\prime}}{16}+\frac{\beta
n^{\prime}}{32}\leq|E(U^{\prime},U^{\prime\prime})|-\frac{\beta
n^{\prime}}{32}.$

Finally, we bound the running time of the algorithm. The running time is at
most $\operatorname{poly}(n)$ plus the time required for the recursive calls
to the same procedure. Recall that the number of phases in the algorithm is at
most $32d/\beta$, and every phase requires up to $3$ recursive calls.
Therefore, the total number of recursive calls is bounded by $100d/\beta$.
Each recursive call is to a graph $H$ that has $L(H)<L(G)$. From the induction
hypothesis, the running time of each recursive call is bounded by
$n^{c}\cdot\left(256d/\hat{\beta}^{\prime}\right)^{L(G)-1}\leq
n^{c}\cdot\left(256d/\hat{\beta}\right)^{L(G)-1}$, and so the total running
time of the algorithm is bounded by:

$n^{c}+\frac{100d}{\beta}\cdot
n^{c}\cdot\left(\frac{256d}{\hat{\beta}}\right)^{L(G)-1}\leq
n^{c}\cdot\left(\frac{256d}{\hat{\beta}}\right)^{L(G)},$

since $\beta>\hat{\beta}$. $\Box$

We are now ready to complete the proof of Theorem 3.5.1.

Proof of Theorem 3.5.1. We start with the input $n$-vertex $\alpha$-expander
$G$ and apply Lemma 3.5.2 to it, obtaining a subset $V_{1}\subseteq V(G)$ of
vertices, such that $G[V_{1}]$ is a $\hat{\alpha}^{*}$-expander and
$\frac{\alpha n}{256d}\leq|V_{1}|\leq\frac{\alpha n}{8d}$. Let
$E^{\prime}=\delta_{G}(V_{1})$. Since the maximum vertex degree in $G$ is at
most $d$, $|E^{\prime}|\leq\frac{\alpha n}{8}$.

We use the following claim, which is similar to Claim 3.2.3, except that it
provides an efficient algorithm instead of the existential result of Claim
3.2.3, at the expense of obtaining somewhat weaker parameters. The proof
appears in Section B.3.3.

######  Claim 3.5.6.

There is an efficient algorithm, that given an $\alpha$-expander $G=(V,E)$
with maximum vertex degree at most $d$ and a subset $E^{\prime}\subseteq E$ of
its edges, computes a subgraph $H\subseteq G\setminus E^{\prime}$ that is an
$\Omega\left(\frac{\alpha^{2}}{d}\right)$-expander, and
$|V(H)|\geq|V|-\frac{4|E^{\prime}|}{\alpha}$.

We apply Claim 3.5.6 to graph $G$ and the set $E^{\prime}$ of edges computed
above. Let $H\subseteq G\setminus E^{\prime}$ be the resulting graph, and let
$V_{2}=V(H)$. From Claim 3.5.6, $|V_{2}|\geq
n-\frac{4|E^{\prime}|}{\alpha}\geq n/2$. Since $|V_{1}|<n/2$ and the set
$E^{\prime}$ of edges disconnects the vertices of $V_{1}$ from the rest of the
graph, while $H$ is an $\Omega\left(\frac{\alpha^{2}}{d}\right)$-expander and
therefore a connected graph, $V_{1}\cap V_{2}=\emptyset$.

We are now ready to define the final partition $(V^{\prime},V^{\prime\prime})$
of $V(G)$, by letting it be the minimum cut separating the vertices of $V_{1}$
from the vertices of $V_{2}$ in $G$: that is, we require that $V_{1}\subseteq
V^{\prime}$, $V_{2}\subseteq V^{\prime\prime}$, and among all such partitions
$(V^{\prime},V^{\prime\prime})$ of $V(G)$, we select the one minimizing
$|E(V^{\prime},V^{\prime\prime})|$. The partition
$(V^{\prime},V^{\prime\prime})$ can be computed efficiently using standard
techniques: we construct a new graph $\hat{G}$ by starting with $G$,
contracting all vertices of $V_{1}$ into a source $s$, contracting all
vertices of $V_{2}$ into a destination $t$, and computing a minimum $s$-$t$
cut in the resulting graph. The resulting cut naturally defines the partition
$(V^{\prime},V^{\prime\prime})$ of $V(G)$. Let
$E^{\prime\prime}=E(V^{\prime},V^{\prime\prime})$, and denote
$|E^{\prime\prime}|=z$. From Menger’s theorem, there is a set ${\mathcal{P}}$
of $z$ edge-disjoint paths in $G$, connecting $V_{1}$ to $V_{2}$. Therefore,
there is a set ${\mathcal{P}}_{1}$ of $z$ edge-disjoint paths in
$G[V^{\prime}]\cup E^{\prime\prime}$, where each path in ${\mathcal{P}}_{1}$
connects a distinct edge of $E^{\prime\prime}$ to a vertex of $V_{1}$, and
similarly, there is a set ${\mathcal{P}}_{2}$ of $z$ edge-disjoint paths in
$G[V^{\prime\prime}]\cup E^{\prime\prime}$, where each path in
${\mathcal{P}}_{2}$ connects a distinct edge of $E^{\prime\prime}$ to a vertex
of $V_{2}$.

We claim that each of the graphs $G[V^{\prime}],G[V^{\prime\prime}]$ is an
$\alpha^{*}$-expander, for $\alpha^{*}=\frac{\alpha\hat{\alpha}^{*}}{512d}$.
We prove this for $G[V^{\prime}]$; the proof for $G[V^{\prime\prime}]$ is
similar. Assume for contradiction that $G[V^{\prime}]$ is not an
$\alpha^{*}$-expander. Then there is a cut $(X,Y)$ in $G[V^{\prime}]$, such
that $|E(X,Y)|<\alpha^{*}\cdot\min\left\\{|X|,|Y|\right\\}$. Assume w.l.o.g.
that $|X\cap V_{1}|\leq|Y\cap V_{1}|$. We now consider two cases.

The first case happens when $|X\cap V_{1}|\geq\frac{\alpha|X|}{512d}$. In that
case, since $G[V_{1}]$ is an $\hat{\alpha}^{*}$-expander, there are at least
$\hat{\alpha}^{*}\cdot|X\cap
V_{1}|\geq\frac{\hat{\alpha}^{*}\cdot\alpha|X|}{512d}\geq\alpha^{*}|X|$ edges
connecting $X\cap V_{1}$ to $Y\cap V_{1}$, and so
$|E(X,Y)|>\alpha^{*}\cdot\min\left\\{|X|,|Y|\right\\}$, a contradiction.
Therefore, we assume now that $|X\cap V_{1}|<\frac{\alpha|X|}{512d}$.

Figure 3.8: An illustration for the proof of Theorem 3.5.1

We partition the edges of $\delta_{G}(X)$ into two subsets: set $E_{1}$
contains all edges that lie in $E(V^{\prime},V^{\prime\prime})$, and set
$E_{2}$ contains all remaining edges, so $E_{2}=E(X,Y)$ (see Figure 3.8). Note
that from the definition of the cut $(X,Y)$, $|E_{2}|<\alpha^{*}|X|$. Recall
that for every edge $e\in E(V^{\prime},V^{\prime\prime})$, there is a path
$P_{e}\in{\mathcal{P}}_{1}$ contained in $G[V^{\prime}]\cup
E(V^{\prime},V^{\prime\prime})$, connecting $e$ to a vertex of $V_{1}$, such
that all paths in ${\mathcal{P}}_{1}$ are edge-disjoint. Let
$\tilde{\mathcal{P}}\subseteq{\mathcal{P}}_{1}$ be the set of paths
originating at the edges of $E_{1}$. We further partition
$\tilde{\mathcal{P}}$ into two subsets: set $\tilde{\mathcal{P}}^{\prime}$
contains all paths $P_{e}$ that contain an edge of $E_{2}$, and
$\tilde{\mathcal{P}}^{\prime\prime}$ contains all remaining paths. Notice that
$|\tilde{\mathcal{P}}^{\prime}|\leq|E_{2}|<\alpha^{*}|X|$. On the other hand,
every path $P_{e}\in\tilde{\mathcal{P}}^{\prime\prime}$ is contained in
$G[X]\cup E_{1}$, and contains a vertex of $V_{1}\cap X$ – the endpoint of
$P_{e}$. Since we have assumed that $|V_{1}\cap X|<\frac{\alpha|X|}{512d}$,
and since the maximum vertex degree in $G$ is at most $d$, while the paths in
$\tilde{\mathcal{P}}^{\prime\prime}$ are edge-disjoint, we get that
$|\tilde{\mathcal{P}}^{\prime\prime}|<\frac{\alpha|X|}{512}$. Altogether, we
get that
$|E_{1}|=|\tilde{\mathcal{P}}|\leq\alpha^{*}|X|+\frac{\alpha|X|}{512}$, and
$|\delta_{G}(X)|=|E_{1}|+|E_{2}|\leq
2\alpha^{*}|X|+\frac{\alpha|X|}{512}\leq\frac{\alpha|X|}{256}<\alpha\cdot\min\left\\{|X|,n/256\right\\}\leq\alpha\cdot\min\left\\{|X|,|V(G)\setminus
X|\right\\}$, since $|V(G)\setminus X|\geq n/256$, as $V_{2}\cap X=\emptyset$.
This contradicts the fact that $G$ is an $\alpha$-expander. $\Box$

######  Corollary 3.5.7.

There is an algorithm, that, given, an $n$-vertex $\alpha$-expander $G$ with
maximum vertex degree at most $d$ and an integer $\ell\geq 1$, where
$0<\alpha<1/3$, computes an $\alpha_{\ell}$-expanding Path-of-Sets system
$\Sigma$ of length $\ell$ and width
$w_{\ell}=\left\lceil\alpha_{\ell}n\right\rceil$, together with a subgraph
$G_{\Sigma}$ of $G$, where
$\alpha_{\ell}=\alpha^{{c_{x}}^{\ell-1}}/d^{c_{x}^{2\ell-2}}$, and $c_{x}\geq
3$ is the constant from Theorem 3.5.1. The running time of the algorithm is
$\operatorname{poly}(n)\cdot\left(\frac{d}{\alpha_{\ell}}\right)^{O(\log(d/\alpha_{\ell}))}$.

We note that we will use the corollary for with $\ell=48$, and so the
resulting Path-of-Sets System will have expansion $(\alpha/d)^{O(1)}$, and the
running time of the algorithm from Corollary 3.5.7 is
$\operatorname{poly}(n)\cdot\left(\frac{d}{\alpha}\right)^{O(\log(d/\alpha))}$.

###### Proof.

The proof is by induction on $\ell$. The base case is when $\ell=1$. We choose
two arbitrary disjoint subsets $A_{1},B_{1}$ of $\left\lceil
w_{1}\right\rceil<n/2$ of vertices, and we let $S_{1}=G$. This defines an
$\alpha$-expanding Path-of-Sets System of length $1$ and width $w_{1}$.

We now assume that we are given an integer $\ell>1$, and an
$\alpha_{\ell-1}$-expanding Path-of-Sets System
$\Sigma=({\mathcal{S}},{\mathcal{M}},A_{1},B_{\ell-1})$ of length $\ell-1$ and
width $w_{\ell-1}$, where $G_{\Sigma}\subseteq G$. We assume that
${\mathcal{S}}=(S_{1},\ldots,S_{\ell-1})$. We compute an
$\alpha_{\ell}$-expanding Path-of-Sets System
$\Sigma^{\prime}=({\mathcal{S}}^{\prime},{\mathcal{M}}^{\prime},A^{\prime}_{1},B^{\prime}_{\ell})$
of length $\ell$ and width $w_{\ell}$. We will denote
${\mathcal{S}}^{\prime}=(S_{1}^{\prime},\ldots,S_{\ell}^{\prime})$, and for
each $1\leq i\leq\ell^{\prime}$, the corresponding vertex sets $A_{i}$ and
$B_{i}$ in $S^{\prime}_{i}$ are denoted by $A^{\prime}_{i}$ and
$B^{\prime}_{i}$, respectively.

For all $1\leq i<\ell-1$, we set $S^{\prime}_{i}=S_{i}$. We also let
$A^{\prime}_{1}\subseteq A_{1}$ be any subset of $w_{\ell}$ vertices, and for
$1\leq i<\ell-2$, we let
${\mathcal{M}}^{\prime}_{i}\subseteq{\mathcal{M}}_{i}$ be any subset of
$w_{\ell}$ edges; the endpoints of these edges lying in $B_{i}$ and $A_{i+1}$
are denoted by $B^{\prime}_{i}$ and $A^{\prime}_{i+1}$ respectively. It
remains to define $S^{\prime}_{\ell-1},S^{\prime}_{\ell}$, the matchings
${\mathcal{M}}^{\prime}_{\ell-2}$ and ${\mathcal{M}}^{\prime}_{\ell-1}$ (that
implicitly define the sets
$B_{\ell-2}^{\prime},A_{\ell-1}^{\prime},B_{\ell-1}^{\prime},A_{\ell}^{\prime}$
of vertices), and the set $B^{\prime}_{\ell}$ of vertices.

We apply Theorem 3.5.1 to graph $S_{\ell-1}$, and compute, in time
$\operatorname{poly}(n)\cdot\left(\frac{d}{\alpha_{\ell-1}}\right)^{O(\log(d/\alpha_{\ell-1}))}$
a partition $(V^{\prime},V^{\prime\prime})$ of $V(S_{\ell-1})$, such that
$|V^{\prime}|,|V^{\prime\prime}|\geq\frac{\alpha_{\ell-1}|V(S_{\ell-1})|}{256d}$,
and each graph $G[V^{\prime}],G[V^{\prime\prime}]$ is an
$\alpha^{*}$-expander, for
$\alpha^{*}\geq\left(\frac{\alpha_{\ell-1}}{d}\right)^{c_{x}}$.

One of the two subsets, say $V^{\prime}$, must contain at least half of the
vertices of $A_{\ell-1}$. We set $S^{\prime}_{\ell-1}=S_{\ell-1}[V^{\prime}]$
and $S^{\prime}_{\ell}=S_{\ell-1}[V^{\prime\prime}]$. Recall that:
$|V^{\prime}|,|V^{\prime\prime}|\geq\frac{\alpha_{\ell-1}|V(S_{\ell-1})|}{256d}\geq\frac{\alpha_{\ell-1}w_{\ell-1}}{128d}$.
Since graph $S_{\ell-1}$ is an $\alpha_{\ell-1}$-expander, there are at least
$\frac{\alpha_{\ell-1}^{2}w_{\ell-1}}{128d}$ edges connecting $V^{\prime}$ to
$V^{\prime\prime}$. Since maximum vertex degree in $G$ is at most $d$, there
is a matching ${\mathcal{M}}$, between vertices of $V^{\prime}$ and vertices
of $V^{\prime\prime}$, with
$|{\mathcal{M}}|\geq\frac{\alpha_{\ell-1}^{2}w_{\ell-1}}{128d^{2}}$. We claim
that $|{\mathcal{M}}|\geq w_{\ell}$. In order to see this, it is enough to
prove that $w_{\ell}\leq\frac{\alpha_{\ell-1}^{2}w_{\ell-1}}{128d^{2}}$. Since
$w_{\ell}=\left\lceil\alpha_{\ell}n\right\rceil$, this is equivalent to
proving that:

$\alpha_{\ell}\leq\frac{\alpha_{\ell-1}^{3}}{256d^{2}}.$

This is easy to verify from the definition of $\alpha_{\ell}$ and the fact
that $c_{x}\geq 3$. We let ${\mathcal{M}}^{\prime}_{\ell-1}$ be any subset of
${\mathcal{M}}$ containing $w_{\ell}$ edges. The endpoints of the edges of
${\mathcal{M}}^{\prime}_{\ell-1}$ lying in $V^{\prime}$ and $V^{\prime\prime}$
are denoted by $B^{\prime}_{\ell-1}$ and $A^{\prime}_{\ell}$ respectively. We
let $B_{\ell}^{\prime}$ be any subset of $w_{\ell}$ vertices of
$V^{\prime\prime}\setminus A_{\ell}^{\prime}$. Finally, we let
$A_{\ell-1}^{\prime}$ any subset of $w_{\ell}$ vertices of $(V^{\prime}\cap
A_{\ell-1})\setminus B^{\prime}_{\ell-1}$;
${\mathcal{M}}^{\prime}_{\ell-2}\subseteq{\mathcal{M}}_{\ell-2}$ the subset of
edges whose endpoints lie in $A^{\prime}_{\ell-1}$; and $B^{\prime}_{\ell-2}$
the set of endpoints of the edges of ${\mathcal{M}}^{\prime}_{\ell-2}$ lying
in $B_{\ell-2}$. This completes the construction of the Path-of-Sets System
$\Sigma^{\prime}$. It is immediate to verify that it has length $\ell$, width
$w_{\ell}$, and that $G_{\Sigma^{\prime}}\subseteq G$. It remains to prove
that it is $\alpha_{\ell}$-expanding, or equivalently, that
$S^{\prime}_{\ell-1}$ and $S^{\prime}_{\ell}$ are $\alpha_{\ell}$-expanders.
Recall that Theorem 3.5.1 guarantees that both these graphs are
$\alpha^{*}$-expanders, where
$\alpha^{*}\geq\left(\frac{\alpha_{\ell-1}}{d}\right)^{c_{x}}$. It is now
enough to verify that $\alpha^{*}\geq\alpha_{\ell}$, which is immediate to do
from the definition of $\alpha_{\ell}$:

$\alpha^{*}\geq\left(\frac{\alpha_{\ell-1}}{d}\right)^{c_{x}}=\frac{\left(\alpha^{{c_{x}}^{\ell-2}}/d^{c_{x}^{2\ell-4}}\right)^{c_{x}}}{d^{c_{x}}}=\frac{\alpha^{{c_{x}}^{\ell-1}}}{d^{c_{x}^{2\ell-3}}\cdot
d^{c_{x}}}\geq\frac{\alpha^{{c_{x}}^{\ell-1}}}{d^{c_{x}^{2\ell-2}}}=\alpha_{\ell}$

Lastly, the running time of the algorithm is dominated by partitioning
$S_{\ell-1}$, and is bounded by
$\operatorname{poly}(n)\cdot\left(\frac{d}{\alpha_{\ell-1}}\right)^{O(\log(d/\alpha_{\ell-1}))}\leq\operatorname{poly}(n)\cdot\left(\frac{d}{\alpha_{\ell}}\right)^{O(\log(d/\alpha_{\ell}))}$,
as required.

We apply Corollary 3.5.7 to the input graph $G$, with the parameter $\ell=48$,
obtaining a sub-graph $G_{\Sigma}\subseteq G$, and an
$\alpha^{\prime}$-expanding Path-of-Sets System $\Sigma$ of length $48$ and
width $w^{\prime}=\left\lceil\alpha^{\prime}n\right\rceil$, where
$\alpha^{\prime}=(\alpha/d)^{O(1)}$. The running time of the algorithm is
$\operatorname{poly}(n)\cdot\left(\frac{d}{\alpha}\right)^{O(\log(d/\alpha))}$.

####  3.5.2 From Expanding Path-of-Sets System to Strong Path-of-Sets System

The goal of this subsection is to prove the following theorem:

######  Theorem 3.5.8.

There is an efficient algorithm, that, given a parameter $\ell>0$, and an
$\alpha$-Expanding Path-of-Sets System $\Sigma$ of width $w$ and length
$4\ell$, where $0<\alpha<1$, such that the corresponding graph $G_{\Sigma}$
has maximum vertex-degree at most $d$, computes a Strong Path-of-Sets System
$\Sigma^{\prime}$, of width $w^{\prime}=\Omega(\alpha^{3}w/d^{4})$ and length
$\ell$, such that the maximum vertex degree in the corresponding graph
$G_{\Sigma^{\prime}}$ is at most $d$, and $G_{\Sigma^{\prime}}$ is a minor of
$G_{\Sigma}$. Moreover, the algorithm computes a model of
$G_{\Sigma^{\prime}}$ in $G_{\Sigma}$.

We use the following simple claim, whose proof is deferred to Section B.3.4.

######  Claim 3.5.9.

There is an efficient algorithm, that, given an $\alpha$-expander $G$, whose
maximum vertex degree is at most $d$, where $0<\alpha<1$, together with two
disjoint subsets $A,B$ of its vertices of cardinality $z$ each, computes a
collection ${\mathcal{P}}$ of $\left\lceil\alpha z/d\right\rceil$ disjoint
paths, connecting vertices of $A$ to vertices of $B$ in $G$.

We will also use the following theorem, whose proof is similar to some
arguments that appeared in [CC16b], and is deferred to Section B.3.5.

######  Theorem 3.5.10.

There is an efficient algorithm, that, given an $\alpha$-Expanding Path-of-
Sets System $\Sigma=({\mathcal{S}},{\mathcal{M}},A_{1},B_{3})$ of width $w$
and length $3$, where $0<\alpha<1$, and the corresponding graph $G_{\Sigma}$
has maximum vertex degree at most $d$, computes subsets $\hat{A}_{1}\subseteq
A_{1},\hat{B}_{3}\subseteq B_{3}$ of $\Omega(\alpha^{2}w/d^{3})$ vertices
each, such that $\hat{A}_{1}\cup\hat{B}_{3}$ is well-linked in $G_{\Sigma}$.

We are now ready to complete the proof of Theorem 3.5.8.

Proof of Theorem 3.5.8. We construct a Strong Path-of-Sets System
$\Sigma^{\prime}=({\mathcal{S}}^{\prime},{\mathcal{M}}^{\prime},A_{1}^{\prime},B_{\ell}^{\prime})$
of length $\ell$ and width $w^{\prime}$, denoting
${\mathcal{S}}^{\prime}=(S_{1}^{\prime},\ldots,S_{\ell}^{\prime})$. For all
$1\leq i\leq\ell$, the corresponding vertex sets $A_{i}$ and $B_{i}$ are
denoted by $A^{\prime}_{i}$ and $B^{\prime}_{i}$, respectively.

For all $1\leq i\leq\ell$, we let $\Sigma_{i}$ be the $\alpha$-expanding Path-
of-Sets System of width $w$ and length $3$ obtained by using the clusters
$S_{4i-3},S_{4i-2}$, $S_{4i-1}$, and the matchings ${\mathcal{M}}_{4i-3}$ and
${\mathcal{M}}_{4i-2}$. In order to define the new Path-of-Sets System, for
each $1\leq i\leq\ell$, we set $S^{\prime}_{i}=G_{\Sigma_{i}}$. We apply
Theorem 3.5.10 to $\Sigma_{i}$, to obtain subsets $\hat{A}_{i}\subseteq
A_{4i-3}$, $\hat{B}_{i}\subseteq B_{4i-1}$ of $\Omega(\alpha^{2}w/d^{3})$
vertices each, such that $\hat{A}_{i}\cup\hat{B}_{i}$ are well-linked in
$S^{\prime}_{i}$.

In order to complete the construction of the Path-of-Sets System
$\Sigma^{\prime}$, we let $A_{1}^{\prime}\subseteq\hat{A}_{1}$ be any subset
of $w^{\prime}$ vertices, and we define
$B^{\prime}_{\ell}\subseteq\hat{B}_{\ell}$ similarly. It remains to define,
for each $1\leq i<\ell$, the matching ${\mathcal{M}}^{\prime}_{i}$. We will
ensure that the endpoints of the resulting matching are contained in
$\hat{B}_{i}$ and $\hat{A}_{i+1}$, respectively, ensuring that the resulting
Path-of-Sets System is strong.

Consider some index $1\leq i<\ell$. Recall that we have computed the sets
$\hat{B}_{i}\subseteq B_{4i-1}$, $\hat{A}_{i+1}\subseteq A_{4i+1}$ of
vertices. We let $E^{\prime}_{i}\subseteq{\mathcal{M}}_{4i-1}$ be the set of
edges incident to the vertices of $\hat{B}_{i}$, and we denote by
$\tilde{A}_{4i}\subseteq A_{4i}$ the set of vertices in $A_{4i}$ that serve as
their endpoints. Similarly, we let
$E^{\prime\prime}_{i}\subseteq{\mathcal{M}}_{4i}$ be the set of edges incident
to the vertices of $\hat{A}_{i+1}$, and we denote by $\tilde{B}_{4i}\subseteq
B_{4i}$ the set of vertices in $B_{4i}$ that serve as their endpoints. From
Claim 3.5.9, there is a set ${\mathcal{Q}}_{i}$ of disjoint paths in $S_{4i}$,
connecting vertices of $\tilde{A}_{4i}$ to vertices of $\tilde{B}_{4i}$, of
cardinality $w^{\prime}=\Omega(\alpha^{3}w/d^{4})$. By extending the paths in
${\mathcal{Q}}_{i}$ to include the edges of $E^{\prime}_{i}\cup
E^{\prime\prime}_{i}$ incident to them, we obtain a collection
${\mathcal{Q}}^{\prime}_{i}$ of $w^{\prime}$ disjoint paths in
$S_{4i}\cup{\mathcal{M}}_{4i-1}\cup{\mathcal{M}}_{4i}$, connecting vertices of
$\hat{B}_{i}$ to vertices of $\hat{A}_{i+1}$. We denote the endpoints of the
paths in ${\mathcal{Q}}^{\prime}_{i}$ lying in $\hat{B}_{i}$ by
$B_{i}^{\prime}$, and the endpoints of the paths in
${\mathcal{Q}}^{\prime}_{i}$ lying in $\hat{A}_{i+1}$ by $A^{\prime}_{i+1}$.
The paths in ${\mathcal{Q}}^{\prime}_{i}$ naturally define the matching
${\mathcal{M}}^{\prime}_{i}$ between the vertices of $B_{i}^{\prime}$ and the
vertices of $A_{i+1}^{\prime}$. This concludes the definition of the Path-of-
Sets System $\Sigma^{\prime}$. It is immediate to verify that it is a strong
Path-of-Sets System of length $\ell$ and width $w^{\prime}$, and to obtain a
model of $G_{\Sigma^{\prime}}$ in $G_{\Sigma}$. Note that graph
$G_{\Sigma^{\prime}}$ has maximum vertex degree at most $d$. $\Box$

Recall that in Part 1 of the algorithm, we have obtained a sub-graph
$G_{\Sigma}\subseteq G$, and an $\alpha^{\prime}$-expanding Path-of-Sets
System $\Sigma$ of length $48$ and width
$w^{\prime}=\left\lceil\alpha^{\prime}n\right\rceil$, where
$\alpha^{\prime}=(\alpha/d)^{O(1)}$. Applying Theorem 3.5.8 to $\Sigma$, we
obtain a Strong Path-of-Sets System $\Sigma^{\prime}$ of length $12$ and width

$w^{\prime\prime}=\Omega\left(\frac{(\alpha^{\prime})^{3}w^{\prime}}{d^{4}}\right)=\Omega\left(\frac{(\alpha^{\prime})^{4}}{d^{4}}n\right)=\left(\frac{\alpha}{d}\right)^{O(1)}\cdot
n.$

We have also computed a model of $G_{\Sigma^{\prime}}$ in $G$, and established
that the maximum vertex degree in $G_{\Sigma^{\prime}}$ is at most $d$. For
convenience, we let $c^{\prime}$ be a constant, such that
$w^{\prime\prime}\geq\frac{\alpha^{c^{\prime}}}{d^{c^{\prime}}}n$.

####  3.5.3 From Strong Path-of-Sets System to Path-of-Expanders System

The goal of this subsection is to prove the following theorem:

######  Theorem 3.5.11.

There is an efficient algorithm, that, given a Strong Path-of-Sets System
$\Sigma$ of width $w$ and length $12$, such that the corresponding graph
$G_{\Sigma}$ has at most $n$ vertices and has maximum vertex degree at most
$d$, computes a Path-of-Expanders System $\Pi$ of width
$\hat{w}=\Omega\left(\frac{w^{4}}{d^{2}n^{3}}\right)$ and expansion
$\hat{\alpha}\geq\Omega\left(\frac{w^{2}}{n^{2}d}\right)$, whose corresponding
graph $G_{\Pi}$ has maximum vertex degree at most $d+1$ and is a minor of
$G_{\Sigma}$. Moreover, the algorithm computes a model of $G_{\Pi}$ in
$G_{\Sigma}$.

Before we prove Theorem 3.5.11, we complete the proof of Theorem 3.3.2 using
it.

Proof of Theorem 3.3.2. Recall that our input is an $\alpha$-expander $G$, for
some $0<\alpha<1$, with $|V(G)|=n$, such that the maximum vertex degree in $G$
is at most $d$. Our goal is to provide an algorithm that computes a Path-of-
Expanders System $\Pi$ of expansion
$\tilde{\alpha}\geq\left(\frac{\alpha}{d}\right)^{\hat{c}_{1}}$ and width
$\tilde{w}\geq n\cdot\left(\frac{\alpha}{d}\right)^{\hat{c}_{2}}$, such that
the maximum vertex degree in $G_{\Pi}$ is at most $d+1$, and to compute a
minor of $G_{\Pi}$ in $G$.

Recall that in Step 2 we have constructed a Strong Path-of-Sets System
$\Sigma^{\prime}$ of length $12$ and width
$w^{\prime\prime}\geq\frac{\alpha^{c^{\prime}}}{d^{c^{\prime}}}n$, for some
constant $c^{\prime}$, such that $G_{\Sigma^{\prime}}$ has maximum vertex
degree at most $d$. We have also computed a model of $G_{\Sigma^{\prime}}$ in
$G$. Our last step is to apply Theorem 3.5.11 to $\Sigma^{\prime}$. As a
result, we obtain a Path-of-Expanders System $\Pi$ of width
$\hat{w}=\Omega\left(\frac{(w^{\prime\prime})^{4}}{d^{2}n^{3}}\right)$ and
expansion
$\hat{\alpha}\geq\Omega\left(\frac{(w^{\prime\prime})^{2}}{n^{2}d}\right)$,
whose corresponding graph $G_{\Pi}$ has maximum vertex degree at most $d+1$.
We also obtain a model of $G_{\Pi}$ in $G_{\Sigma}$. Substituting the value
$w^{\prime\prime}\geq\frac{\alpha^{c^{\prime}}}{d^{c^{\prime}}}n$, we get that
the width of the Path-of-Expanders System $\Pi$ is
$\Omega\left(\frac{\alpha^{4c^{\prime}}}{d^{2+4c^{\prime}}}\right)\cdot n$,
and that its expansion is
$\Omega\left(\frac{\alpha^{2c^{\prime}}}{d^{2c^{\prime}+1}}\right)$. By
appropriately setting the constants $\hat{c}_{1}$ and $\hat{c}_{2}$, we ensure
that the width of the Path-of-Expanders System is at least
$n\cdot\left(\frac{\alpha}{d}\right)^{\hat{c}_{2}}$ and its expansion is at
least $\left(\frac{\alpha}{d}\right)^{\hat{c}_{1}}$. This completes the proof
of Theorem 3.3.2. $\Box$

In the remainder of this section, we prove Theorem 3.5.11. We can assume
w.l.o.g. that $w^{4}\geq 2^{14}n^{3}d^{2}$, since otherwise it is sufficient
to produce a Path-of-Expanders System of width $1$, which is trivial to do. We
denote the input Strong Path-of-Sets System by
$\Sigma=({\mathcal{S}},{\mathcal{M}},A_{1},B_{12})$, where
${\mathcal{S}}=(S_{1},\ldots,S_{12})$, and we let $G_{\Sigma}$ be its
corresponding graph. For convenience, we denote by
${\mathcal{I}}_{\text{even}}$ and ${\mathcal{I}}_{\text{odd}}$ the sets of all
even and all odd indices in $\left\\{1,\ldots,12\right\\}$, respectively.

Our algorithm consists of three steps. In the first step, for every index
$i\in{\mathcal{I}}_{\text{even}}$, we find a large set ${\mathcal{P}}_{i}$ of
disjoint paths connecting $A_{i}$ to $B_{i}$ in $S_{i}$, and a subgraph
$T_{i}\subseteq S_{i}$ that is an $\hat{\alpha}$-expander, such that the paths
in ${\mathcal{P}}_{i}$ are disjoint from $T_{i}$. In the second step, for each
such index $i\in{\mathcal{I}}_{\text{even}}$, we compute another set
${\mathcal{Q}}_{i}$ of disjoint paths in $S_{i}$, and a large enough subset
${\mathcal{P}}^{\prime}_{i}\subseteq{\mathcal{P}}_{i}$ of paths, such that
every path in ${\mathcal{Q}}_{i}$ connects a vertex on a distinct path of
${\mathcal{P}}^{\prime}_{i}$ to a distinct vertex of $T_{i}$. In the third and
the final step we compute the Path-of-Expanders System $\Pi$ and a model of
$G_{\Pi}$ in $G_{\Sigma}$.

###### Step 1.

In this step, we prove the following lemma.

######  Lemma 3.5.12.

There is an efficient algorithm, that, given an index
$i\in{\mathcal{I}}_{\text{even}}$, computes a set ${\mathcal{P}}_{i}$ of
$\left\lfloor\frac{w^{2}}{16nd}\right\rfloor$ paths in $S_{i}$, and a subgraph
$T_{i}\subseteq S_{i}$, such that:

  * •

graph $T_{i}$ is an $\hat{\alpha}$-expander, and it contains at least $w/2$
vertices of $A_{i}$;

  * •

the paths in ${\mathcal{P}}_{i}$ are disjoint from each other; they are also
disjoint from $T_{i}$ and internally disjoint from $A_{i}\cup B_{i}$;

  * •

every path in ${\mathcal{P}}_{i}$ connects a vertex of $A_{i}$ to a vertex of
$B_{i}$; and

  * •

every path in ${\mathcal{P}}_{i}$ has length at most $2n/w$.

###### Proof.

For convenience, we omit the subscript $i$ in this proof. We are given a graph
$S$ that contains at most $n$ vertices and has maximum vertex degree at most
$d$, and two disjoint subsets $A,B$ of $V(S)$ of cardinality $w$ each, such
that each of $A\cup B$ is well-linked in $S$. Therefore, there is a set
${\mathcal{P}}$ of $w$ disjoint paths in $S$, connecting vertices of $A$ to
vertices of $B$, such that the paths in ${\mathcal{P}}$ are internally
disjoint from $A\cup B$. We say that a path in ${\mathcal{P}}$ is _short_ if
it contains at most $2n/w$ vertices, and otherwise it is long. Since
$|V(S)|\leq n$, at most $w/2$ paths in ${\mathcal{P}}$ can be long, and the
remaining paths must be short. Let
${\mathcal{P}}^{\prime}\subseteq{\mathcal{P}}$ be any subset of
$\left\lfloor\frac{w^{2}}{16nd}\right\rfloor$ paths in ${\mathcal{P}}$. It is
now sufficient to show an algorithm that computes an $\hat{\alpha}$-expander
$T\subseteq S$, such that $T$ is disjoint from the paths in
${\mathcal{P}}^{\prime}$. In order to do so, we let $E^{\prime}$ be the set of
all edges lying on the paths in ${\mathcal{P}}^{\prime}$, so
$|E^{\prime}|\leq|{\mathcal{P}}^{\prime}|\cdot\frac{2n}{w}\leq\left\lfloor\frac{w^{2}}{16nd}\right\rfloor\cdot\frac{2n}{w}\leq\frac{w}{8}$.

We start with $T=S\setminus E^{\prime}$, and then iteratively remove edges
from $T$, until we obtain a connected component of the resulting graph that is
an $\hat{\alpha}$-expander, containing at least $w/2$ vertices of $A$. Notice
that the original graph $T$ is not necessarily connected. We also maintain a
set $E^{\prime\prime}$ of edges that we remove from $T$, initialized to
$E^{\prime\prime}=\emptyset$. Our algorithm is iterative. In every iteration,
we apply Theorem 3.2.2 to the current graph $T$, to obtain a cut
$(Z,Z^{\prime})$ in $T$. If the sparsity of the cut is at least
$\frac{w}{16n}$, that is,
$|E_{T}(Z,Z^{\prime})|\geq\frac{w}{16n}\min\left\\{|Z|,|Z^{\prime}|\right\\}$,
then we terminate the algorithm. Theorem 3.2.2 then guarantees that the
expansion of $T$ is $\Omega\left(\frac{w^{2}}{n^{2}d}\right)$, that is, $T$ is
a $\hat{\alpha}$-expander. Otherwise,
$|E_{T}(Z,Z^{\prime})|<\frac{w}{16n}\min\left\\{|Z|,|Z^{\prime}|\right\\}$.
Assume w.l.o.g. that $|Z\cap A|\geq|Z^{\prime}\cap A|$. We then add the edges
of $E_{T}(Z,Z^{\prime})$ to $E^{\prime\prime}$, set $T=T[Z]$, and continue to
the next iteration. Note that the number of edges added to $E^{\prime\prime}$
during this iteration is at most $\frac{|Z^{\prime}|w}{16n}$.

Clearly, the graph $T$ we obtain at the end of the algorithm is an
$\hat{\alpha}$-expander, and it is disjoint from all paths in
${\mathcal{P}}^{\prime}$. It now only remans to show that $T$ contains at
least $w/2$ vertices of $A$. Assume for contradiction that this is false.

Assume that the algorithm performs $r$ iterations, and for each $1\leq j\leq
r$, let $(Z_{j},Z^{\prime}_{j})$ be the cut computed by the algorithm in
iteration $j$, where $|Z_{j}\cap A|\geq|Z^{\prime}_{j}\cap A|$. But then for
all $1\leq j\leq r$, $|Z^{\prime}_{j}\cap A|\leq w/2$ must hold. Let
$n_{j}=|Z^{\prime}_{j}\cap A|$. Since the vertices of $A$ are well-linked in
$S$, $\delta_{S}(Z^{\prime}_{j})\geq n_{j}$. Therefore:

$\sum_{j=1}^{r}|\delta_{S}(Z^{\prime}_{j})|\geq\sum_{j=1}^{r}n_{j}\geq w/2,$

since we have assumed that the final graph $T$ has fewer than $w/2$ vertices
of $A$. On the other hand, all edges in
$\bigcup_{j=1}^{r}\delta_{S}(Z^{\prime}_{j})$ are contained in $E^{\prime}\cup
E^{\prime\prime}$, and so:

$\sum_{j=1}^{r}|\delta_{S}(Z^{\prime}_{j})|\leq 2|E^{\prime}\cup
E^{\prime\prime}|.$

Recall that $|E^{\prime}|\leq\frac{w}{8}$, and it is easy to verify that
$|E^{\prime\prime}|\leq\frac{w}{16n}\cdot n=\frac{w}{16}$. Therefore,
$\sum_{j=1}^{r}|\delta_{S}(Z^{\prime}_{j})|<\frac{w}{2}$, a contradiction.

###### Step 2.

For every index $i\in{\mathcal{I}}_{\text{even}}$, let
$A^{\prime}_{i}\subseteq A_{i}$ be the subset of vertices that serve as
endpoints for the paths in ${\mathcal{P}}_{i}$. The goal of this step is to
prove the following lemma.

######  Lemma 3.5.13.

There is an efficient algorithm, that, given an index
$i\in{\mathcal{I}}_{\text{even}}$, computes a subset
${\mathcal{P}}^{\prime}_{i}\subseteq{\mathcal{P}}_{i}$ of $\hat{w}$ paths,
and, for each path $P\in{\mathcal{P}}^{\prime}_{i}$, a path $Q_{P}$ in
$S_{i}$, that connects a vertex of $P$ to a vertex of $T_{i}$, such that the
paths in set ${\mathcal{Q}}_{i}=\left\\{Q_{P}\mid
P\in{\mathcal{P}}^{\prime}_{i}\right\\}$ are disjoint from each other,
internally disjoint from $T_{i}$, and internally disjoint from the paths in
${\mathcal{P}}^{\prime}_{i}$.

###### Proof.

We fix an index $i\in{\mathcal{I}}_{\text{even}}$, and for convenience omit
the subscript $i$ for the remainder of the proof. Recall that we are given a
set $A^{\prime}\subseteq A$ of $\left\lfloor\frac{w^{2}}{16nd}\right\rfloor$
vertices, that serve as endpoints of the paths in ${\mathcal{P}}$. Recall that
$T$ contains at least $w/2$ vertices of $A$. We let $A^{\prime\prime}\subseteq
A$ be any set of $\left\lfloor\frac{w^{2}}{16nd}\right\rfloor$ vertices of $A$
lying in $T$. Since the set $A$ of vertices is well-linked in $S$, there is a
set ${\mathcal{Q}}$ of $\left\lfloor\frac{w^{2}}{16nd}\right\rfloor$ node-
disjoint paths, connecting the vertices of $A^{\prime}$ to the vertices of
$A^{\prime\prime}$ in $S$. We say that a path in ${\mathcal{Q}}$ is _short_ if
it contains fewer than $\frac{64n^{2}d}{w^{2}}$ vertices, and otherwise we say
that it is _long_. Since $S$ contains at most $n$ vertices, and the paths in
${\mathcal{Q}}$ are disjoint, at most $\frac{w^{2}}{64nd}$ paths of
${\mathcal{Q}}$ are long. We let $\hat{{\mathcal{Q}}}\subseteq{\mathcal{Q}}$
be the set of all short paths, so
$|\hat{{\mathcal{Q}}}|\geq\frac{w^{2}}{64nd}$, and we let $\hat{A}\subseteq
A^{\prime}$ be the set of vertices that serve as endpoints of the paths in
$\hat{{\mathcal{Q}}}$. We also let $\hat{{\mathcal{P}}}\subseteq{\mathcal{P}}$
the set of paths originating from the vertices in $\hat{A}$. We are now ready
to compute the set ${\mathcal{P}}^{\prime}$ of paths, and the corresponding
paths $Q_{P}$ for all $P\in{\mathcal{P}}^{\prime}$.

We start with ${\mathcal{P}}^{\prime}=\emptyset$, and then iterate. While
$\hat{{\mathcal{P}}}\neq\emptyset$, let $P$ be any path in
$\hat{{\mathcal{P}}}$, and let $a\in\hat{A}$ be the vertex from which it
originates. Let $Q$ be the path of $\hat{{\mathcal{Q}}}$ originating at $a$.
We prune the path $Q$ as needed, so that it connects a vertex of $P$ to a
vertex of $T$, but is internally disjoint from $P$ and $T$. Let $Q^{\prime}$
be the resulting path. We then add $P$ to ${\mathcal{P}}^{\prime}$, and we let
$Q_{P}=Q^{\prime}$. Next, we delete from $\hat{{\mathcal{P}}}$ all paths that
intersect $Q^{\prime}$ (since the length of $Q^{\prime}$ is at most
$\frac{64n^{2}d}{w^{2}}$, we delete at most $\frac{64n^{2}d}{w^{2}}$ paths
from $\hat{{\mathcal{P}}}$), and for every path $P^{*}$ that we delete from
$\hat{{\mathcal{P}}}$, we delete from $\hat{{\mathcal{Q}}}$ the path sharing
an endpoint with $P^{*}$ (so at most $\frac{64n^{2}d}{w^{2}}$ paths are
deleted from $\hat{{\mathcal{Q}}}$). Similarly, we delete from
$\hat{{\mathcal{Q}}}$ every path that intersects $P$ (since the length of $P$
is at most $2n/w$, we delete at most $\frac{2n}{w}\leq\frac{64n^{2}d}{w^{2}}$
paths from $\hat{{\mathcal{Q}}}$), and for every path $Q^{*}$ that we delete
from $\hat{{\mathcal{Q}}}$, we delete from $\hat{{\mathcal{P}}}$ the path
sharing an endpoint with $Q^{*}$ (again, at most $\frac{64n^{2}d}{w^{2}}$
paths are deleted from $\hat{{\mathcal{P}}}$). Overall, we delete at most
$\frac{128n^{2}d}{w^{2}}$ paths from $\hat{{\mathcal{P}}}$, and at most
$\frac{128n^{2}d}{w^{2}}$ paths from $\hat{{\mathcal{Q}}}$. The paths that
remain in both sets form pairs – that is, for every path
$P^{*}\in\hat{{\mathcal{P}}}$, there is a path $Q^{*}\in\hat{{\mathcal{Q}}}$
originating at the same vertex of $A$, and vice versa. Furthermore, and all
paths in $\hat{{\mathcal{P}}}\cup\hat{{\mathcal{Q}}}$ are disjoint from the
paths in ${\mathcal{P}}^{\prime}\cup\left\\{Q_{P}\mid
P\in{\mathcal{P}}^{\prime}\right\\}$.

At the end of the algorithm, we obtain a subset
${\mathcal{P}}^{\prime}\subseteq{\mathcal{P}}$ of paths, and for each path
$P\in{\mathcal{P}}^{\prime}$, a path $Q_{P}$ in $S$, connecting a vertex of
$P$ to a vertex of $T$, such that the paths in set
${\mathcal{Q}}^{\prime}=\left\\{Q_{P}\mid P\in{\mathcal{P}}^{\prime}\right\\}$
are disjoint from each other, internally disjoint from $T$, and internally
disjoint from the paths in ${\mathcal{P}}^{\prime}$. It now only remains to
show that $|{\mathcal{P}}^{\prime}|\geq\hat{w}$.

Recall that we start with $|\hat{{\mathcal{P}}}|\geq\frac{w^{2}}{64nd}$. In
every iteration, we add one path to ${\mathcal{P}}^{\prime}$, and delete at
most $\frac{128n^{2}d}{w^{2}}$ paths from $\hat{{\mathcal{P}}}$. Since we have
assumed that $w^{4}\geq 2^{14}n^{3}d^{2}$, we get that
$\frac{256n^{2}d}{w^{2}}\leq\frac{w^{2}}{64nd}$. It is then easy to verify
that at the end of the algorithm,
$|{\mathcal{P}}^{\prime}|\geq\left\lfloor\frac{|\hat{{\mathcal{P}}}|}{256n^{2}d/w^{2}}\right\rfloor\geq\Omega\left(\frac{w^{4}}{n^{3}d^{2}}\right)=\hat{w}$.

###### Step 3.

In this step we complete the construction of the Path-of-Expanders System
$\Pi$. We will also define a minor $G^{\prime}$ of $G_{\Sigma}$ and compute a
model of $G_{\Pi}$ in $G^{\prime}$; it is then easy to obtain a model of
$G_{\Pi}$ in $G_{\Sigma}$.

Consider some index $i\in{\mathcal{I}}_{\text{even}}$, and the sets
${\mathcal{P}}^{\prime}_{i},{\mathcal{Q}}_{i}$ of paths computed in Step 2.
Let $P\in{\mathcal{P}}^{\prime}_{i}$ be any such path, and assume that it
connects a vertex $a_{P}\in A_{i}$ to a vertex $b_{P}\in B_{i}$. Let $v_{P}\in
P$ be the endpoint of $Q_{P}$ lying on $P$, and let $c_{P}$ be its other
endpoint. Finally, let $e_{P}$ be the edge of ${\mathcal{M}}_{i-1}$ incident
to $a_{P}$ and let $b^{\prime}_{P}\in B_{i-1}$ be its other endpoint.
Similarly, if $i\neq 12$, let $e^{\prime}_{P}$ be the edge of
${\mathcal{M}}_{i}$ incident to $b_{P}$, and let $a^{\prime}_{P}\in A_{i+1}$
be its other endpoint (see Figure 3.9(a)).

(a) Paths $P$ (shown in blue) and $Q_{P}$ (shown in red) before edge
contractions

(b) After edge contractions

Figure 3.9: The contractions of the edges on paths $P$ and $Q_{P}$.

We contract the edge $e_{P}$ and all edges lying on the sub-path of $P$
between $a_{P}$ and $v_{P}$, so that $v_{P}$ and $b^{\prime}_{P}$ merge. The
resulting vertex is denoted by $b^{\prime}_{P}$. We also suppress all inner
vertices on the path $Q_{P}$, obtaining an edge $\hat{e}_{P}$, connecting
$b^{\prime}_{P}$ to $c_{P}$. Finally, if $i\neq 12$, then we contract all
edges on the sub-path of $P$ between $v_{P}$ and $b_{P}$, obtaining an edge
$\hat{e}^{\prime}_{P}=(b_{P},a^{\prime}_{P})$. We let
$\hat{E}_{i}=\left\\{\hat{e}_{P}\mid P\in{\mathcal{P}}^{\prime}_{i}\right\\}$
and we let $\hat{E}_{i}^{\prime}=\left\\{\hat{e}_{P}^{\prime}\mid
P\in{\mathcal{P}}^{\prime}_{i}\right\\}$ be the sets of these newly defined
edges. Notice that the edges of $\hat{E}_{i}$ connect a subset of $\hat{w}$
vertices of $B_{i-1}$ (that we denote by $\hat{B}_{i-1}$) to a subset of
$\hat{w}$ vertices of $T_{i}$ (that we denote by $\hat{C}_{i})$, and for
$i\neq 12$, the edges of $\hat{E}_{i}^{\prime}$ connect every vertex of
$\hat{B}_{i-1}$ to some vertex of $A_{i+1}$; we denote the set of endpoints of
these edges that lie in $A_{i+1}$ by $\hat{A}_{i+1}$.

Once we perform this procedure for every path
$P\in{\mathcal{P}}^{\prime}_{i}$, for all $i\in{\mathcal{I}}_{\text{even}}$,
we delete from the resulting graph all edges and vertices except those lying
in graphs $S_{i}$ for $i\in{\mathcal{I}}_{\text{odd}}$, graphs $T_{i}$ for
$i\in{\mathcal{I}}_{\text{even}}$, and the edges in
$\hat{E}_{i}\cup\hat{E}_{i}^{\prime}$ for $i\in{\mathcal{I}}_{\text{even}}$.
The resulting graph, denoted by $G^{\prime}$, is a minor of $G$, and it is
easy to verify that its maximum vertex degree is at most $d+1$.

We now define a Path-of-Expanders System
$\Pi=(\tilde{\Sigma},\tilde{\mathcal{M}},\tilde{A}_{1},\tilde{B}_{6},\tilde{\mathcal{T}},\tilde{\mathcal{M}}^{\prime})$,
where the clusters of $\tilde{\Sigma}$ are denoted by
$\tilde{S}_{1},\ldots,\tilde{S}_{6}$; for each $1\leq i\leq 6$ the
corresponding sets $A_{i},B_{i},C_{i}$ of vertices are denoted by
$\tilde{A}_{i}$, $\tilde{B}_{i}$ and $\tilde{C}_{i}$ respectively; the
matching ${\mathcal{M}}^{\prime}_{i}$ is denoted by
$\tilde{\mathcal{M}}^{\prime}_{i}$ and the expander $T_{i}$ is denoted by
$\tilde{T}_{i}$. For all $1\leq i<6$, we also denote the matching
${\mathcal{M}}_{i}$ by $\tilde{\mathcal{M}}_{i}$.

For each $1\leq i\leq 6$, we let the cluster $\tilde{S}_{i}$ of
$\tilde{\Sigma}$ be $S_{2i-1}$, and we let the expander $\tilde{T}_{i}$ be
$T_{2i}$. We also set $C_{i}=\hat{C}_{2i}$, and
$\tilde{\mathcal{M}}^{\prime}_{i}=\hat{E}_{2i}$. If $i>1$, then we let
$\tilde{A}_{i}=\hat{A}_{2i-1}$, and we let $\tilde{A}_{1}$ be any subset of
$\hat{w}$ vertices of $A_{1}$. Similarly, if $i<6$, then we let
$\tilde{B}_{i}=\hat{B}_{2i-1}$, and we let $\tilde{B}_{6}$ be any subset of
$\hat{w}$ vertices of $B_{6}$. Finally, for $i<6$, we let
$\tilde{\mathcal{M}}_{i}=\hat{E}_{2i}^{\prime}$. It is immediate to verify
that we have obtained a Path-of-Expanders System of width $\hat{w}$ and
expansion $\hat{\alpha}$, and a model of $G_{\Pi}$ in $G^{\prime}$. It is now
immediate to obtain a model of $G_{\Pi}$ in $G_{\Sigma}$. This completes the
proof of Theorem 3.5.11.

###  3.6 Efficiently Finding Models of all Not-So-Large Graphs in Expanders

The goal of this section is to provide the proof of Theorem 3.1.2. Notice that
Theorem 3.1.2 provides slightly weaker dependence on $n$ in the minor size
than Theorem 3.1.1, but it has several advantages: its proof is much simpler,
the algorithm’s running time is polynomial in $n,d$ and $\alpha$, and it
provides a better dependence on $\alpha$ and $d$ in the bound on the minor
size. Our algorithm also has an additional useful property: if it fails to
find the required model, then with high probability it certifies that the
input graph is not an $\alpha$-expander by exhibiting a cut of sparsity less
than $\alpha$.

Let $G=(V,E)$ be the given $n$-vertex $\alpha$-expander with maximum vertex
degree at most $d$. As in the proof of Theorem 3.1.1, given a graph $H$ with
$n^{\prime}$ vertices and $m^{\prime}$ edges, we can construct another graph
$H^{\prime}$, whose maximum vertex-degree is at most $3$ and
$|V(H^{\prime})|\leq n^{\prime}+2m^{\prime}\leq
2\left\lfloor\frac{n}{\tilde{c}^{*}\log^{2}n}\cdot\frac{\alpha^{3}}{d^{5}}\right\rfloor$,
such that $H$ is a minor of $H^{\prime}$. It is now enough to provide an
efficient algorithm that computes a model of $H^{\prime}$ in $G$. For
convenience of notation, we denote $H^{\prime}$ by $H=(U,F)$, and we denote
$U=\left\\{u_{1},\ldots,u_{|U|}\right\\}$. We can assume that $n>c_{0}$ for a
large enough constant $c_{0}$ by appropriately setting the constant
$\tilde{c}^{*}$, as otherwise it is enough to show that every graph of size
$1$ is a minor of $G$, which is trivial.

Our algorithm consists of a number of iterations. We say that a partition
$(V^{\prime},V^{\prime\prime})$ of $V$ is _good_ iff
$|V^{\prime}|,|V^{\prime\prime}|\geq n/(4d)$; and
$G[V^{\prime}],G[V^{\prime\prime}]$ are both connected graphs. We start with
an arbitrary good partition $(V_{1},V_{2})$ of $V$, obtained by using the
algorithm from Observation 3.4.1 with $r=2$. Assume without loss of generality
that $|V_{1}|\geq|V_{2}|$. We now try to compute a model of $H$ in $G$, by
first embedding the vertices of $H$ into connected sub-graphs of $G[V_{2}]$,
and then routing the edges of $H$ in $G[V_{1}]$. We show an efficient
algorithm, that with high probability returns one of the following:

  * •

either a good partition $(V^{\prime}_{1},V^{\prime}_{2})$ such that
$|E(V^{\prime}_{1},V^{\prime}_{2})|<|E(V_{1},V_{2})|$ (in this case, we
proceed to the next iteration); or

  * •

a model of $H$ in $G$ (in this case, we terminate the algorithm and return the
model).

Clearly, we terminate after $|E|$ iterations, succeeding with high
probability. We now describe a single iteration in detail. Recall that we are
given a good partition $(V_{1},V_{2})$ of $V$ with $|V_{1}|\geq|V_{2}|$. Since
$G$ is an $\alpha$-expander, we have $|E(V_{1},V_{2})|\geq\alpha n/(4d)$ (note
that, if this is not the case, we have found a cut $(V_{1},V_{2})$ of sparsity
less than $\alpha$). Since the maximum vertex-degree in $G$ is bounded by $d$,
we can efficiently find a matching ${\mathcal{M}}\subseteq E(V_{1},V_{2})$ of
cardinality at least $\alpha n/(8d^{2})$. We denote the endpoints of the edges
in ${\mathcal{M}}$ lying in $V_{1}$ and $V_{2}$ by $Z$ and $Z^{\prime}$,
respectively. Let $\rho:=3\cdot\left\lceil
4cd^{2}\log^{2}n/\alpha^{2}\right\rceil$, where $c$ is the constant from Lemma
3.4.12.

Recall that $U$ is the set of vertices in the graph $H$. We apply Observation
3.4.1 to the graph $G[V_{2}]$, together with $R=Z^{\prime}$ and parameter
$r=|U|$, to obtain a collection
${\mathcal{W}}=\left\\{W_{1},\ldots,W_{|U|}\right\\}$ of disjoint connected
subgraphs of $G[V_{2}]$, such that for all $1\leq i\leq|U|$,

$|V(W_{i})\cap
Z^{\prime}|\geq\left\lfloor\frac{|Z^{\prime}|}{d|U|}\right\rfloor\geq\left\lfloor\frac{\alpha
n}{8d^{3}|U|}\right\rfloor\geq\left\lfloor\frac{\alpha
n}{8d^{3}}\cdot\frac{\tilde{c}^{*}d^{5}\log^{2}n}{2n\alpha^{3}}\right\rfloor=\left\lfloor\frac{\tilde{c}^{*}d^{2}\log^{2}n}{16\alpha^{2}}\right\rfloor$

Here, we have used the fact that $|U|\leq
2\left\lfloor\frac{n}{\tilde{c}^{*}\log^{2}n}\cdot\frac{\alpha^{3}}{d^{5}}\right\rfloor$.
By appropriately setting the constant $\tilde{c}^{*}$ in the bound on $|U|$,
we can ensure that for all $1\leq i\leq|U|$, $|V(W_{i})\cap Z^{\prime}|\geq
3\rho$.

Recall that we are given a graph $H=(U,F)$ with maximum vertex-degree $3$ and
that we have denoted $U=\left\\{u_{1},\ldots,u_{|U|}\right\\}$. For $1\leq
i\leq|U|$, we think of the graph $W_{i}$ as representing the vertex $u_{i}$ of
$H$. For each $1\leq i\leq|U|$, and for each edge $e\in\delta_{H}(u_{i})$, we
select an arbitrary subset $Z^{\prime}_{i}(e)\subseteq V(W_{i})\cap
Z^{\prime}$ of $\rho$ vertices, such that all resulting sets
$\left\\{Z^{\prime}_{i}(e)\mid e\in\delta_{H}(u_{i})\right\\}$ of vertices are
mutually disjoint. Let $E_{i}(e)\subseteq{\mathcal{M}}$ be the subset of edges
of ${\mathcal{M}}$ that have an endpoint in $Z^{\prime}_{i}(e)$, so
$|E_{i}(e)|=\rho$. We let $Z_{i}(e)$ be the set of vertices of $Z$ that serve
as endpoints of the edges in $E_{i}(e)$. Notice that all resulting sets
$\left\\{Z_{i}(e)\mid 1\leq i\leq|U|,e\in\delta_{H}(u_{i})\right\\}$ are
mutually disjoint, and each of them contains $\rho^{\prime}$ vertices.

We apply the algorithm of Lemma 3.4.12 to the graph $G[V_{1}]$, together with
the parameter $\alpha/2$ and the family $\left\\{Z_{i}(e)\mid 1\leq
i\leq|U|,e\in\delta_{H}(u_{i})\right\\}$ of vertex subsets, that we order
appropriately.

###### Case 1. The algorithm returns a cut.

In this case, we obtain a cut $(X,Y)$ in $G[V_{1}]$ of sparsity less than
$\alpha/2$ by computing a good partition $(V^{\prime}_{1},V^{\prime}_{2})$ of
$V$ with $|E(V^{\prime}_{1},V^{\prime}_{2})|~{}<~{}|E(V_{1},V_{2})|$. We need
the following simple observation, that we prove after completing the proof of
Theorem 3.1.2 assuming it.

######  Observation 3.6.1.

There is an efficient algorithm, that given a connected graph $G=(V,E)$ and a
cut $(X,Y)$ in $G$, produces a cut $(X^{*},Y^{*})$, whose sparsity is less
than or equal to that of $(X,Y)$, such that both $G[X^{*}]$ and $G[Y^{*}]$ are
connected.

We apply Observation 3.6.1 to graph $G[V_{1}]$ and cut $(X,Y)$, obtaining a
new cut $(X^{*},Y^{*})$ of sparsity less than $\alpha/2$, such that both
$G[X^{*}]$ and $G[Y^{*}]$ are connected. For convenience, we denote the cut
$(X^{*},Y^{*})$ by $(X,Y)$, and we assume without loss of generality that
$|Y|\leq|X|$. Notice that $|Y|\leq|V_{1}|/2\leq|V|/2$. Since $G$ is an
$\alpha$-expander, $|\delta_{G}(Y)|\geq\alpha|Y|$ (note that, if this is not
the case, then have found a cut $(Y,V\backslash Y)$ of sparsity less than
$\alpha$.).

Since $\delta_{G}(Y)=E(X,Y)\cup E(Y,V_{2})$, we get that
$|E(Y,V_{2})|\geq\alpha|Y|/2$, and $|E(X,Y)|<|E(Y,V_{2})|$. In particular,
$E(Y,V_{2})\neq\emptyset$. We now define a new cut
$(V^{\prime}_{1},V^{\prime}_{2})$ of $G$, where $V^{\prime}_{2}=V_{2}\cup Y$
and $V^{\prime}_{1}=X$. We claim that $(V^{\prime}_{1},V^{\prime}_{2})$ is a
good partition of $V(G)$. It is immediate to verify that
$|V^{\prime}_{1}|,|V^{\prime}_{2}|\geq n/(4d)$, and that
$G[V^{\prime}_{1}]=G[X]$ is connected. Moreover, since $G[Y]$ is connected and
$E(Y,V_{2})\neq\emptyset$, $G[V^{\prime}_{2}]=G[V_{2}\cup Y]$ is also
connected. Lastly, we claim that
$|E(V^{\prime}_{1},V^{\prime}_{2})|<|E(V_{1},V_{2})|$. Indeed, since
$|E(X,Y)|<|E(V_{2},Y)|$:

$|E(V^{\prime}_{1},V^{\prime}_{2})|=|E(V_{1},V_{2})|-|E(V_{2},Y)|+|E(Y,X)|<|E(V_{1},V_{2})|.$

Therefore, we have computed a good partition $(V^{\prime}_{1},V^{\prime}_{2})$
of $V(G)$, with $|E(V^{\prime}_{1},V^{\prime}_{2})|<|E(V_{1},V_{2})|$ as
required.

###### Case 2. The algorithm returns paths.

In this case, we have obtained, for every edge $e=(u_{i},u_{j})\in F$, a path
$Q(e)$ in $G[V_{1}]$, connecting a vertex of $Z_{i}(e)$ to a vertex of
$Z_{j}(e)$, such that, with high probability, the paths in $\left\\{Q(e)\mid
e\in F\right\\}$ are mutually disjoint. If the paths in $\left\\{Q(e)\mid e\in
F\right\\}$ are not mutually disjoint, the algorithm fails. We assume from now
on that the paths in $\left\\{Q(e)\mid e\in F\right\\}$ are mutually disjoint.
We extend each path $Q(e)$ to include the two edges of ${\mathcal{M}}$ that
are incident to its endpoints, so that $Q(e)$ now connects a vertex of
$Z^{\prime}_{i}(e)$ to a vertex of $Z^{\prime}_{j}(e)$.

We are now ready to define the model of $H$ in $G$. For every $1\leq
i\leq|U|$, we let $f(u_{i})=W_{i}$, and for every edge $e\in F$, we let
$f(e)=Q(e)$. It is immediate to verify that this mapping indeed defines a
valid model of $H$ in $G$. This completes the proof of Theorem 3.1.2 assuming
Observation 3.6.1 that we prove next.

Proof of Observation 3.6.1. We start with the cut $(X,Y)$ and perform a number
of iterations. In every iteration, we modify the cut $(X,Y)$ so that the
number of connected components in $G\setminus E(X,Y)$ strictly decreases,
while ensuring that the cut sparsity does not increase. We now describe the
execution of an iteration. Let $(X,Y)$ be the current cut. Let
${\mathcal{C}}_{X}$ and ${\mathcal{C}}_{Y}$ be the sets of all connected
components of $G[X]$ and $G[Y]$ respectively. If
$|{\mathcal{C}}_{X}|=|{\mathcal{C}}_{Y}|=1$, then we return the cut $(X,Y)$,
and terminate the algorithm. We assume from now on that this is not the case.

Assume w.l.o.g. that $|X|\leq|Y|$. Let $\rho_{X}:=\frac{|E(X,Y)|}{|X|}$ and
$\rho_{Y}:=\frac{|E(X,Y)|}{|Y|}$. We consider the following two cases.

###### Case 1:

The first case happens when $|{\mathcal{C}}_{X}|>1$. Recall that
$|E(X,Y)|=\rho_{X}|X|$. Thus, there is a connected component
$C\in{\mathcal{C}}_{X}$ such that $|E(C,Y)|\geq\rho_{X}|C|$. Consider a new
partition $(X^{\prime},Y^{\prime})$, obtained by setting
$X^{\prime}=X\backslash C$ and $Y^{\prime}=Y\cup C$. Notice that the number of
connected components in $G\setminus E(X^{\prime},Y^{\prime})$ decreases by at
least one. The sparsity of the new cut is:

$\frac{|E(X^{\prime},Y^{\prime})|}{\min\left\\{|X^{\prime}|,|Y^{\prime}|\right\\}}=\frac{|E(X^{\prime},Y^{\prime})|}{|X^{\prime}|}=\frac{|E(X,Y)|-|E(C,Y)|}{|X|-|C|}\leq\frac{\rho_{X}|X|-\rho_{X}|C|}{|X|-|C|}=\rho_{X}.$

###### Case 2:

If Case 1 does not happen, then $|{\mathcal{C}}_{Y}|>1$ must hold. As before,
there is a connected component $C\in{\mathcal{C}}_{Y}$ such that
$|E(C,Y)|\geq\rho_{Y}|C|$. Consider the new partition
$(X^{\prime},Y^{\prime})$ by setting $X^{\prime}=X\cup C$ and
$Y^{\prime}=Y\backslash C$. Notice that the number of connected components in
$G\setminus E(X^{\prime},Y^{\prime})$ decreases by at least one. In order to
bound the sparsity of the new cut, we consider two cases. If
$|X^{\prime}|\geq|Y^{\prime}|$, then the sparsity of the new cut is

$\frac{|E(X^{\prime},Y^{\prime})|}{|Y^{\prime}|}=\frac{|E(X,Y)|-|E(C,Y)|}{|Y|-|C|}\leq\frac{\rho_{Y}|Y|-\rho_{Y}|C|}{|Y|-|C|}=\rho_{Y}\leq\rho_{X}.$

Otherwise, the sparsity of the new cut is

$\frac{|E(X^{\prime},Y^{\prime})|}{|X^{\prime}|}=\frac{|E(X,Y)|-|E(C,Y)|}{|X|+|C|}<\frac{|E(X,Y)|}{|X|}=\rho_{X}.$

It is immediate to verify that the algorithm is efficient, and that it
produces the cut $(X^{*},Y^{*})$ with the required properties. $\Box$

##  Chapter 4 Longest Increasing Subsequence and Non-Crossing Matching

###  4.1 Introduction

In this work, we initiate the study of bipartite non-crossing matching (NCM)
problem in the framework that we refer to as ‘hybrid model’. In the NCM
problem, we are given a bipartite graph $G=(L,R,E)$ where $L$ and $R$ are
ordered sets of vertices and $E\subseteq L\times R$ is the set of edges. A
matching $M$ in $G$ is _non-crossing_ , if, for every pair of edges
$(u,v),(u^{\prime},v^{\prime})\in M$, if $u<u^{\prime}$, then $v<v^{\prime}$
holds. Our choice of hybrid model is motivated by its close relationship with
the well-studied longest increasing subsequence (LIS) problem in the streaming
model that we establish. In the hybrid model, we assume that the access to the
graph $G=(L,R,E)$ is provided to an algorithm as follows. We are given
(offline) access to vertices $L$ and $R$, while the edges of $G$ are revealed
over the course of $|L|$ rounds. In the $i^{th}$ round, the algorithm is
revealed a superset of edges incident on the $i^{th}$ vertex of $L$. It then
selects a subset of these ‘advice-edges’ to _query_ , and then receives the
set of ‘real-edges’ among its queried edge-slots. At the end of processing the
last vertex of $L$, the algorithm reports its estimate on the cardinality of
the maximum non-crossing matching in $G$. The aim in this model is to minimize
the number of queries per vertex, as a fraction of the number of advice-edges
incident on it, while disregarding the space complexity. Our choice of this
access model for the NCM problem, is motivated precisely by the fact that it
is the query complexity in this model that sheds light on space complexity of
the LIS problem in the streaming model.

We note that the initial study of the NCM problem in the classical setting was
motivated by its applications in VLSI design [MOP93]. Variants of the NCM
problem have also been studied in computational geometry, where the
(potentially non-bipartite) graph is embedded into a plane, and the goal is to
find its non-crossing matching maximizing certain objective functions.

A closely related model to the hybrid model is the query model, where the
algorithm may directly query the adjacency matrix or adjacency list of the
input graph. The problem of estimating the size of a (standard) matching has
been well-studied in the query model, and it is known that $\tilde{O}(n)$
queries suffice to achieve an $O(1)$-approximation of maximum matching size
whenever the maximum matching size is $\tilde{\Omega}(n)$, where $n$ is the
number of vertices in $G$ [ORRR12, KMNFT20, Beh22]. These algorithms
implicitly rely on the robustness of matchings: the decision to include any
edge in a matching solution can only lower the optimum solution value by at
most one. In fact, even $O(1)$-approximation to the size of maximal matching
leads to $O(1)$-approximation of the maximum matching size. In contrast,
inclusion of a single edge can potentially reduce the optimal non-crossing
matching solution value by a factor of $\Omega(n)$, showing a factor
$\Omega(n)$ gap between optimal and maximal non-crossing matching sizes. This
lack of robustness makes the task of designing a sublinear-query algorithm for
NCM size estimation much harder, even in query model.

Before describing the relation between the space complexity of the LIS problem
in the streaming model and the query complexity of the NCM problem in the
hybrid model, we summarize known result for the former. Liben-Nowell, Van, and
Zhu [LVZ06] showed that an exact computation of the LIS length in the
streaming model, even by a randomized algorithm, requires $\Omega(\sqrt{N})$
space where $N$ is the stream length. This was soon afterwards strengthened to
an $\Omega(N)$ space lower bound for an exact computation of LIS length even
by a randomized algorithm in independent works by Gopalan et al. [GJKK07], and
by Sun and Woodruff [SW07]. We note that the $\Omega(N)$ space lower bound
holds even for instances where the input is a permutation of $[1..N]$.

The focus then shifted to the design of space-efficient algorithms for
approximating LIS length. The first non-trivial result in this direction was
obtained by Gopalan et al. [GJKK07] who gave an $O(\sqrt{N/\epsilon})$ space
one-pass deterministic streaming algorithm for approximating the LIS length to
within a $(1+\epsilon)$-factor for any $\epsilon>0$. Moreover, they
conjectured that the space-complexity of their algorithm is optimal. This
conjecture was shown to be true independently by Gál and Gopalan [GG07], and
by Ergün and Jowhari [EJ08] who established an essentially matching space
lower bound for one-pass deterministic streaming algorithms. We note that the
result of Gál and Gopalan [GG07] also implies a deterministic space lower
bound of $\Omega\left(\sqrt{N/(\alpha-1)}\right)$ for any $\alpha>1$. This
bound is tight, since the deterministic algorithm of [GJKK07] can be easily
adapted to provide $\alpha$-approximation to LIS length for any $\alpha>1$ in
space $O\left(\sqrt{N/(\alpha-1)}\right)$. Together, these results give a
complete understanding of the tradeoff between space complexity and
approximation factor for deterministic one-pass streaming algorithms for
estimating LIS length.

The corresponding picture for randomized algorithms is far from being resolved
though. Saks and Seshadhri [SS13] gave an additive approximation error
randomized one-pass streaming algorithm, that, for any $\delta>0$, achieves a
$(\frac{\delta N}{1+\delta})$ additive approximation to LIS length in
$O\left((\log^{2}N)/\delta\right)$ space. In the regime when the LIS length is
$\omega\left(\sqrt{N}\log^{2}N\right)$, this bound implies a multiplicative
approximation algorithm that has better space complexity than [GJKK07]. In
particular, for any sequence $S$, setting
$\delta=\epsilon\frac{\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)}{N}$ gives a
$(1+\epsilon)$-approximation to LIS length in
${O}\left(\frac{N\log^{2}N}{\epsilon\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)}\right)$
space. On the other hand, [LVZ06] showed that LIS length can be computed
exactly in ${O}\left(\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)\right)$
space. However, the regime where
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)\approx\sqrt{N}$ remains a
bottleneck for the current state-of-the-art for streaming algorithms for LIS –
all known algorithms require ${\Omega}\left(N^{1/2-o(1)}\right)$ space in this
regime for even an $N^{o(1)}$-approximation to the LIS length. At the same
time, known lower bound results do not even rule out the possibility that a
poly-logarithmic space randomized algorithm may achieve an
$\tilde{O}(1)$-approximation to LIS length [SW07]. It is worth emphasizing
that the ${\Omega}\left(N^{1/2-o(1)}\right)$ space requirements for current
known algorithms holds even when the input sequence is a permutation of
$[1..N]$, which is the setting of the LIS problem that we focus on.

We show that the goals of understanding the randomized space complexity of LIS
and NCM problems are closely intertwined, and under some natural conditions,
progress on the current state-of-the-art for one problem will have significant
implications for the other. Note that a trivial exact algorithm for the NCM
problem in the hybrid model is to query all the advice-edges. We show that an
NCM algorithm in the hybrid model with a slightly better query complexity than
this naive algorithm and even a moderately high factor of approximation
implies an $N^{o(1)}$-approximation streaming algorithm for LIS with space
complexity bounded by $N^{1/2-\epsilon}$, where $N$ is the LIS stream length
and $\epsilon$ is some absolute constant. Specifically, we show a low space
complexity randomized LIS algorithm in the streaming model, that, without
reduction to the NCM problem, achieves factor $N^{o(1)}$-approximation with
low space complexity, except for input instances that satisfy some stringent
technical properties. For the latter case, we reduce LIS instances satisfying
these technical properties to the NCM problem in the hybrid model, where the
input instance $G=(L,R,E_{\mathsf{advice}},E)$ satisfies $|L|=|R|$ and
$\mathsf{OPT}_{\mbox{{\scriptsize{NCM}}}}(G)$ is relatively large.

We also show a converse connection, namely, that the existence of a
$(1+\epsilon)$-approximation randomized algorithm for the LIS problem in
streaming model with space complexity $N^{1/2-\delta}$ would imply a
randomized algorithm for the NCM problem in the hybrid model with per-vertex
query complexity of $(d(G)|L|)^{1/2-\delta}$ that achieves
${O}(1)$-approximation in the regime where $|L|=|R|$ and the optimal solution
value is close to $|L|$, where the input instance is
$G~{}=~{}(L,R,E_{\mathsf{advice}},E)$ and $d(G)$ is the maximum number of
edge-slots of $E_{\mathsf{advice}}$ that are incident to a single vertex of
$L$. This converse connection, however, requires a technical restriction,
namely, that the streaming LIS algorithm is comparison-based. To our
knowledge, all known LIS streaming algorithms are comparison-based. Thus, if
one can rule out the existence of an algorithm for NCM in the hybrid model
with this bound on its per-vertex query complexity and approximation
guarantee, even in the above-mentioned regime, it would also eliminate the
possibility of the existence of an algorithm for LIS problem in the streaming
model with space complexity significantly lower than $\sqrt{N}$. As noted
earlier, our current state of knowledge for LIS neither rules out such a
result (for a randomized algorithm) nor gives an algorithm to achieve this.
Any progress in either direction would fundamentally improve our understanding
of the LIS problem.

In the next subsection, we formally define our models and then give a
technical overview of our main results.

####  4.1.1 Our Results and Informal Overview of Techniques

All the algorithms that we consider in this work are randomized algorithms
succeeding with probability at least $2/3$ unless stated otherwise. Before
presenting our results, we define the Longest Increasing Subsequence (LIS) and
Non-Crossing Matching (NCM) problems, and various models of computation that
we analyze.

###### Longest Increasing Subsequence.

The Longest Increasing Subsequence (LIS) problem takes as input a sequence
$S=(a_{1},\ldots,a_{N})$ of $N$ elements from an ordered universe
${\mathcal{U}}=\left\\{1,\ldots,M\right\\}$. We say that a subsequence
$S^{\prime}=(a_{i_{1}},\ldots,a_{i_{k}})$ is an _increasing subsequence_ of
$S$ iff $1\leq i_{1}<\ldots<i_{k}\leq N$ and $a_{i_{1}}<\ldots<a_{i_{k}}$. Let
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)$ be the length of the longest
increasing subsequence of $S$, and denote it by
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}$ or $\mathsf{OPT}$ when the sequence
$S$ is clear from the context. Given such a sequence $S$, the objective of the
LIS problem is to produce an estimate $k^{\prime}$ of
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)$. We say that a randomized
algorithm $\mathsf{Alg}$ is an $\alpha$-approximation algorithm for LIS, if,
given as input a sequence $S$, with probability at least $2/3$ it produces an
estimate $k^{\prime}$ such that
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)/\alpha\leq
k^{\prime}\leq\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)$. For some
$\alpha^{\prime}\geq\beta^{\prime}$, we say that $\mathsf{Alg}$ solves
_$(\alpha^{\prime},\beta^{\prime})$ -gap LIS_ problem iff it distinguishes
between the two cases by reporting _yes_ with probability at least $2/3$ when
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)\geq\alpha^{\prime}$ and reporting
_no_ with probability at least $2/3$ when
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)<\beta^{\prime}$. In this work,
unless stated otherwise, we will restrict ourselves to the case where the
input sequence $S$ is a permutation of the universe
${\mathcal{U}}=\left\\{1,\ldots,N\right\\}$.

######  LIS in the Streaming Model.

We assume that the universe ${\mathcal{U}}=\left\\{1,\ldots,M\right\\}$ is
known to us in advance, and each of its element can be stored in a single unit
of space. In the standard one-pass streaming model, an algorithm with limited
memory is presented the elements of $S=(a_{1},\ldots,a_{N})$ one by one, in
this sequential order. At the end of the stream, it has to output an estimate
$k^{\prime}$ of $\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)$. We do not place
any constraints on the operations it is allowed to perform.

###### Non-Crossing Matching Problem.

The input to the Non-Crossing Matching (NCM) problem is a bipartite graph
$G=(L,R,E)$ where $L$ and $R$ are ordered sets of vertices. We say that a
matching $M$ in $G$ is _non-crossing_ , if, for every pair of edges
$(u,v),(u^{\prime},v^{\prime})\in M$, where $u<u^{\prime}$, it holds that
$v<v^{\prime}$. Given such an instance $G$, the goal in the NCM problem is to
produce an estimate $k^{\prime}$ of the size of the largest non-crossing
matching, denoted by $\mathsf{OPT}_{\mbox{{\scriptsize{NCM}}}}(G)$ or
$\mathsf{OPT}$ when $G$ is clear from context. We say that a randomized
algorithm $\mathsf{Alg}$ is an $\alpha$-approximation algorithm for NCM if
with probability at least $2/3$ it produces an estimate $k^{\prime}$ on the
size of the largest non-crossing matching in $G$ such that
$\mathsf{OPT}_{\mbox{{\scriptsize{NCM}}}}(G)/\alpha\leq
k^{\prime}\leq\mathsf{OPT}_{\mbox{{\scriptsize{NCM}}}}(G)$. For some
$\alpha^{\prime}\geq\beta^{\prime}$, we say that $\mathsf{Alg}$ solves
_$(\alpha^{\prime},\beta^{\prime})$ -gap NCM_ problem iff it distinguishes
between the two cases by reporting _yes_ with probability at least $2/3$ when
$\mathsf{OPT}_{\mbox{{\scriptsize{NCM}}}}(G)\geq\alpha^{\prime}$ and reporting
_no_ with probability at least $2/3$ when
$\mathsf{OPT}_{\mbox{{\scriptsize{NCM}}}}(G)<\beta^{\prime}$.

######  NCM Problem in the Hybrid Model.

In the hybrid model, an algorithm $\mathsf{Alg}$ is given access to an NCM
problem instance $G=(L,R,E)$ along with a superset
$E_{\mathsf{advice}}\supseteq E$ of edge-slots, that we call ‘advice’ edges.
We will denote the resulting instance by $G=(L,R,E_{\mathsf{advice}},E)$ and
say that its _size_ is $|G|:=|L|\cdot|R|$. We denote by $d(G)$, the maximum
number of edge-slots of $E_{\mathsf{advice}}$ incident to a single vertex of
$L$. We assume that the vertex-sets $L$, $R$ along with $d(G)$ are known to
$\mathsf{Alg}$ beforehand, but the sets $E$ and $E_{\mathsf{advice}}$ of edge-
slots are unknown. The algorithm $\mathsf{Alg}$ is revealed the sets $E$ and
$E_{\mathsf{advice}}$ over the course of $|L|$ rounds. In the $i^{th}$ round,
the algorithm $\mathsf{Alg}$ receives the set of the advice edges
$E_{\mathsf{advice}}(u_{i})$ incident on $u_{i}$, where $u_{i}$ is the
$i^{th}$ vertex of $L$. It then selects a subset
$E^{\prime}_{\mathsf{advice}}(u_{i})$ of these edge-slots to query and
receives the set $E^{\prime}_{\mathsf{advice}}(u_{i})\cap E$ of ‘real edges’
among its queried edge-slots. At the end of processing the last vertex of $L$,
the algorithm outputs its estimate $k^{\prime}$ of
$\mathsf{OPT}_{\mbox{{\scriptsize{NCM}}}}(G)$. We say that the algorithm
$\mathsf{Alg}$ has a per-vertex query complexity $q$ iff for all $u\in L$,
$|E^{\prime}_{\mathsf{advice}}(u)|\leq q$. In the hybrid model, the goal is to
optimize the per-vertex query complexity, and we ignore both, the space
complexity and the time complexity of our algorithm.

###### From Query-Efficient NCM to Space-Efficient LIS.

We start by discussing our algorithm for the LIS problem in the Streaming
model, which uses as a blackbox, the algorithm for the NCM problem in the
hybrid model. To establish this relation between NCM and LIS problems, we
prove the following theorem:

######  Theorem 4.1.1.

Suppose there exists a constant $\delta>0$ and an algorithm
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ for the
$(\gamma|L|,\gamma|L|/|G|^{o(1)})$-gap NCM problem in the hybrid model for the
special case where the input instance $G~{}=~{}(L,R,E_{\mathsf{advice}},E)$
has $|L|=|R|$ and $d(G)\geq|G|^{10^{-9}}$, for all
$(d(G))^{10^{-3}}\leq\gamma\leq 1$, with per-vertex query complexity
$\left(d(G)\right)^{1-\delta}$. Then there is a constant
$\epsilon=\epsilon(\delta)>0$ and a factor $N^{o(1)}$-approximation algorithm
$\mathsf{Alg}_{\mbox{{\scriptsize{LIS}}}}$ for the LIS problem in the
streaming model with space complexity $N^{1/2-\epsilon}$, where $N$ is the
size of the input stream.

Before we give a brief overview of our techniques behind Theorem 4.1.1, we
discuss some of its implications. For the ease of notation, assume in this
section that $N$ is a large enough integral power of $2$. Consider an instance
$G=(L,R,E_{\mathsf{advice}},E)$ for the NCM Problem in the hybrid model, and
let $d=d(G)$ be the maximum number of edge-slots of $E_{\mathsf{advice}}$
incident to a single vertex of $L$. Note that there is a trivial
$1$-approximation algorithm that performs $d$ queries per vertex. Indeed, we
can query all the advice-edges $E_{\mathsf{advice}}$ and incur the per-vertex
query complexity of $d$. Suppose there exists an algorithm that improves this
bound by a relatively modest factor of $d^{\delta}$, for some constant
$\delta>0$, even at the cost of a ‘large’ factor of $(|G|)^{o(1)}$ in the
approximation guarantee in the special case where $|L|=|R|$ and
$d\geq|G|^{10^{-9}}$. Consider a special case where the input instance
$G=(L,R,E_{\mathsf{advice}},E)$ for the NCM Problem in the hybrid model is
guaranteed to have $\mathsf{OPT}_{\mbox{{\scriptsize{NCM}}}}(G)\geq
d^{10^{-3}}\geq|G|^{10^{-12}}$. Assume that there is an algorithm
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ in the hybrid model that solves
$(\gamma|L|,\gamma|L|/|G|^{o(1)})$-gap NCM problem with per-vertex query
complexity $(d(G))^{1\delta}$, for all $(d(G))^{10^{-3}}\leq\gamma\leq 1$ and
some constant $\delta>0$, where the input instance is $G$. We then show that
there are non-trivial consequences for the LIS problem in the streaming model.
Specifically, we demonstrate that the long-standing space complexity upper
bound barrier of $N^{1/2-o(1)}$ for achieving $N^{o(1)}$-approximation
algorithm for the LIS problem in the streaming model, where $N$ is the input
stream length, can be broken in this case. 111 We note that for such an
algorithm $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ to exist, $\delta\leq
10^{-3}$ must hold. Indeed, consider an input instance
$G=(L,R,E_{\mathsf{advice}},E)$ of the NCM problem in the hybrid model where
$|L|=|R|$ and $d(G)=|G|^{10^{-9}}$. It is immediate to verify that to
distinguish between the cases where $E$ is a non-crossing matching of size
$d^{10^{-3}}$ from the case where $E=\emptyset$, one must query at least
$\Omega\left(|L|d/d^{10^{-3}}\right)=\Omega\left(|L|\cdot
d^{(1-10^{-3})}\right)$ edge-slots of $E_{\mathsf{advice}}$, which translates
to per-vertex query complexity of $\Omega\left(d^{(1-10^{-3})}\right)$.  As
mentioned earlier, we do not put any restriction on the space complexity of
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ in the hybrid model. To obtain this
‘space-agnostic’ reduction, we use an intrinsic ‘self-reducibility’ property
of the LIS problem that we outline below.

###### Self-reducibility Property and Hierarchical Decomposition.

Consider an instance $S$ of the LIS problem and a parameter $Z$ that is an
integral power of $2$. We assume that $S$ is a permutation of the range
$H^{*}=(1,\ldots,N)$, where $N$ is known to us in advance, and is an integral
power of $2$. We prove the existence of two parameters, $X(Z)$ and $Y(Z)$,
also integral powers of $2$, and an increasing subsequence $S^{*}$ of $S$ with
size comparable to $\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)$, such that
the following property holds. Notice that $S^{*}$ can also be naturally
thought of as an increasing subsequence of the range $H^{*}$. Consider the
partition of $S$ into _stream-blocks_ , where each stream-block is a
contiguous subsequence in $S$ of length exactly $X(Z)$. Similarly, consider
the partition of the range $H^{*}$ into _range-blocks_ , where each range-
block is a contiguous subsequence in $H^{*}$ of length exactly $Y(Z)$. Then
each block of these partitions either contributes exactly $Z$ elements to
$S^{*}$ or none at all. Consider a pair $(B,B^{\prime})$ of blocks, where $B$
is a stream-block and $B^{\prime}$ is a range-block. From the above
discussion, for each such pair $(B,B^{\prime})$ of blocks, either $S^{*}$
contains exactly $Z$ elements of $B$ with values in $B^{\prime}$, or there are
zero such elements. Consider a pair $(B,B^{\prime})$ that contributes elements
to $S^{*}$. We refer to such pairs as _yes-pairs_. Our algorithm ensures that
each yes-pair $(B,B^{\prime})$ is statistically similar to every other yes-
pair in terms of the number of their common elements ($B\cap B^{\prime}$) and
the ‘distance’ at which the elements of $S^{*}$ appear in the resulting common
subsequence $B\cap B^{\prime}$. This ‘regularity property’ will prove
advantageous in subsequent analysis.

We can think of these partitions as naturally giving rise to a NCM instance
$G=(L,R,E_{\mathsf{advice}},E)$ in the hybrid model. For each stream-block of
the partition of the stream $S$, there is a unique vertex in $L$. Similarly,
for each range-block of the partition of the range $H^{*}$, there is a unique
vertex in $R$. For each pair of blocks that are potential candidates for
contributing elements to $S^{*}$, by the virtue of having the ‘correct’ number
of shared elements; we add the corresponding pair of vertices to the set
$E_{\mathsf{advice}}$ of advice-edges. If these blocks indeed share an
increasing subsequence of size comparable to $Z$ (which may contain elements
that do not lie in $S^{*}$), we add the corresponding pair of vertices to the
set $E$ of edges. Here, we are glossing over the simulation of this reduction
while accessing $S$ in the streaming model with limited memory.

Consider a pair $(B,B^{\prime})$ of a stream-block and a range-block. We view
each such pair $(B,B^{\prime})$ as a fresh LIS problem instance, where the
input stream is the sequence $B\cap B^{\prime}$ of elements of $B$ with their
values in the range-block $B^{\prime}$. The range of this new LIS problem
instance is $B^{\prime}$, which is in turn, a subset of the range $H^{*}$ of
the original input stream $S$. Moreover, if $(B,B^{\prime})$ is a yes-pair, we
have $\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B\cap B^{\prime})\geq Z$. On
the other hand, if it is a no-pair, we do not have any constraint on
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(B\cap B^{\prime})$. Notice that we
can recursively apply our partitioning process to these resulting instances.
We refer to this property as the ‘self-reducibility property,’ and the
resulting hierarchical family of partitions as a ‘hierarchical decomposition.’

Naively, this is an existential result: that there exists a large increasing
subsequence $S^{*}$ of $S$ and a hierarchical decomposition that obeys the
regularity properties outlined above w.r.t. the subsequence $S^{*}$. As
mentioned earlier, we show that these regularity properties, and hence, the
relevant parameters of the hierarchical decomposition, depend solely on the
‘level’ at which they appear, and it suffices to consider a relatively small
set of such parameters. We show that we can efficiently ‘guess’ such a
hierarchical decomposition (but not the increasing subsequence $S^{*}$), even
before processing the input sequence $S$, with a small enough overhead in
space complexity. We can thus assume from now on, that the algorithm is given
a hierarchical decomposition for which there is a large enough increasing
subsequence $S^{*}$ of $S$ that satisfies the above-mentioned regularity
properties.

###### Space-efficient LIS Algorithm.

We note that existing algorithms can be combined in order to achieve a
constant-factor approximation for LIS in space ${N^{1/2-\epsilon+o(1)}}$,
except for the case where
$N^{1/2-\epsilon}\leq\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)\leq
N^{1/2+\epsilon}$. We thus focus here on the interesting regime where such a
result is not known, namely, where
$N^{1/2-\epsilon}\leq\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)\leq
N^{1/2+\epsilon}$. We define four technical conditions, that describe the
interplay between the parameters of our hierarchical decomposition, and show a
structural theorem that if
$N^{1/2-\epsilon}\leq\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)\leq
N^{1/2+\epsilon}$, at least one of them must hold. Thus, it suffices to
consider four special cases of the problem, each restricted to instances
satisfying one of these conditions. Intuitively, three our of these four
special cases can be dealt with directly, without exploiting the algorithm
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ for the NCM problem in the hybrid
model. We reduce the last special case to the NCM problem in the hybrid model.
We proceed to provide a brief overview of these conditions, and the efficient
LIS algorithm in the streaming model for each of these resulting special
cases.

The first special case occurs when the size of the stream-blocks is relatively
small at some level of our hierarchical decomposition. In this case, we
present a simple algorithm that samples elements of $S$ as they arrive in the
streaming model while gradually narrowing down on the pairs of stream-blocks
and range-blocks that share a prescribed number of elements and hence can
possibly contribute elements to $S^{*}$. For each of these promising pairs, we
employ one of the existing LIS algorithms to compute the size of their largest
shared increasing subsequence. Using the self reducibility property, we show
that these computations suffice to compute an estimate to the size of $S^{*}$.
In this special case, we obtain $O(1)$-approximation to
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)$, directly, without exploiting
the algorithm $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$.

The second special case occurs when there is some level in our hierarchical
decomposition, such that the contribution of the yes-pairs to $S^{*}$ is
miniscule compared to the number of elements they share. Our algorithm for
this case, that also obtains $O(1)$-approximation to
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)$, is similar to that for the
first special case, but with minor technical differences. As in first special
case, this algorithm does not exploit
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$.

The first two special cases deal with situations where the relevant condition
occurs at a unique level. However, the third special case is more complex and
involves an interplay of parameters across multiple levels. Unlike the
previous cases, this condition may occur independently across a large number
of levels, necessitating the need to apply the following approach recursively
on all such occurrences. Informally, this case arises when a significant
proportion of block-pairs at a single level seem promising, making it
challenging to determine the ones to pursue. Exploiting the statistical
properties of our hierarchical decomposition, we show that for this challenge
to arise, there must be a large enough increasing subsequence (which may be
unrelated to both, $S^{*}$ and the optimum longest increasing subsequence of
$S$) that uses elements from these promising pairs. Our algorithm then pursues
as many of these pairs as possible; when this number exceeds a carefully
crafted threshold, we prune some of these searches by falling back on this
existential guarantee. Unfortunately, the resulting increasing subsequence may
not adhere to our hierarchical decomposition. Nevertheless, we can still
obtain an $N^{o(1)}$-approximation to
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)$ in this special case directly,
without exploiting the algorithm $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$.

Recall that we can view each level of partition in our hierarchical
decomposition as a NCM problem instance. The fourth and final special case
arises when a large fraction these instances are so tiny, that we can execute
the algorithm $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ on them with a
negligible space overhead. This is precisely the point where the self-
reducibility property is most useful: it allows us to create NCM problem
instances $G$, that are tiny, of size roughly $\operatorname{poly}\log\log N$,
so that even if $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ uses space
$2^{\operatorname{poly}(|G|)}$, this space overhead can be bounded by
$N^{o(1)}$. Similar to the third special case, this phenomenon occurs on a
large number of levels, and we need to execute multiple instances of
$\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ recursively across multiple levels.
Assuming that each execution of $\mathsf{Alg}_{\mbox{{\scriptsize{NCM}}}}$ on
the input instance $G$ achieves factor $|G|^{o(1)}$-approximation, we achieve
factor $N^{o(1)}$-approximation to
$\mathsf{OPT}_{\mbox{{\scriptsize{LIS}}}}(S)$ in this special case.

###### From Space-Efficient LIS to Query-Efficient NCM.

Ideally, we would like a similar relation in the opposite direction: that is,
an $N^{o(1)}$-approximation LIS algorithm in the streaming model with space
complexity $N^{1/2-\epsilon}$, for some small absolute constant $\epsilon>0$,
should imply an algorithm for the
$\left(\gamma|L|,\gamma|L|/|G|^{o(1)}\right)$-gap NCM problem in the hybrid
model with query complexity $(d(G))^{1-\delta}$, for a constant $\delta$ that
depends solely on $\epsilon$, when the input instance
$G=(L,R,E_{\mathsf{advice}},E)$ satisfies $|L|=|R|$ and
$d(G)\geq|G|^{10^{-9}}$ for all $(d(G))^{10^{-3}}\leq\gamma\leq 1$.
Unfortunately, we can only show the reduction from a special case of the NCM
problem in the hybrid model, where the problem instance
$G=(L,R,E_{\mathsf{advice}},E)$ satisfies even stricter restrictions to the
LIS problem in the comparison-based streaming model that we define next.

######  LIS in the Comparison-Based Streaming Model.

In contrast to the standard streaming model, the comparison-based streaming
model only allows an algorithm to gain information about the elements in the
stream by _comparing_ them, without using any information about their
_absolute values_. Consider the input LIS instance $S$ of $N$ elements in the
streaming model. A (randomized) $s$-space comparison-based streaming algorithm
maintains a ‘memory-state’ $\Gamma$ along with an array $I$ consisting of at
most $s$ elements from the stream observed so far. While processing the $i$-th
element $a_{i}$ from the stream $S$, the algorithm is allowed to compare
elements of $I$ with each other and the element $a_{i}$ with elements of $I$.
Based solely on the current memory state $\Gamma$ and these comparisons, the
algorithm updates its memory state. It may then choose to add $a_{i}$ to $I$
and/or discard some elements from $I$, while ensuring that $|I|\leq s$ holds.
Note that are no restrictions on the algorithm’s time complexity or the size
of its memory state $\Gamma$, except for the number of elements $I$ that it
may save. To our knowledge, all the previously known LIS streaming algorithms
are comparison-based. We provide a formal description of this model in Section
4.3.

We are now ready to state the relation between the LIS problem and NCM problem
in the reverse direction.

######  Theorem 4.1.2.

Suppose there are constants $0<\epsilon<1/3$ and $\delta>0$, such that there
exists a factor $(1+\epsilon)$-approximation algorithm for the LIS problem in
the comparison-based streaming model with space-complexity $N^{1/2-\delta}$,
where $N$ is the length of the input stream $S$. Then there is an algorithm
for the $(\gamma|L|,\epsilon\gamma|L|)$-gap NCM problem in the hybrid model
for the special case where the input instance
$G~{}=~{}(L,R,E_{\mathsf{advice}},E)$ has $|L|=|R|$ and
$\gamma>1/(2-3\epsilon)$, that achieves per-vertex query complexity of
$\left(2d(G)|L|\right)^{1/2-\delta}$.