$\frac{|C|}{\operatorname{spars}_{(h,s)}(C,A)}=|D|\leq|A|$ so we have that

$\displaystyle\frac{\phi}{\operatorname{spars}_{(h,s)}(C,A)}\cdot|C|\leq|A|.$

Thus, it follows that
$|\bar{C}|\geq\frac{\phi}{\operatorname{spars}_{(h,s)}(C,A)}\cdot|C|-|C|$ and
so we can arbitrarily increase the length of edges to turn $C$ into a
$C^{\prime}$ satisfying
$\frac{\phi}{\operatorname{spars}_{(h,s)}(C,A)}\cdot|C|=|C^{\prime}|$.555We
ignore rounding to multiples of $\frac{1}{h}$ here for simplicity of
presentation.

Lastly, any such $C^{\prime}$ is $(h,s)$-length $\phi$-sparse since
$C^{\prime}$ $hs$-separates $D$ and so

$\displaystyle\operatorname{spars}_{(h,s)}(C^{\prime},A)\geq\frac{|C^{\prime}|}{|D|}=\frac{\phi\cdot|C|}{|D|\cdot\mathrm{spars}_{(h,s)}(C,A)}=\phi.$

∎

We now prove the main theorem of this section. See 11.2

###### Proof.

The proof is immediate from Lemma 11.2 and the fact that the union of sparse
moving cuts is itself a sparse cut as per 1.2 and so smaller than the largest
sparse moving cut.

More formally, let $(C_{1},C_{2},\ldots)$ be the largest $(h,s)$-length
$\phi$-sparse moving cut sequence w.r.t. $A$ in $G$ of largest weighted size
as defined in Definition 11.1 and let $C_{0}$ be the $(h,s)$-length
$\phi$-sparse cut of largest size w.r.t. $A$ in $G$. Our goal is to show

$\displaystyle\sum_{i\geq
1}\frac{\phi}{\operatorname{spars}_{(h,s)}(C_{i},A)}\cdot|C_{i}|\leq|C_{0}|.$
(13)

Let $\mathcal{C}:=\sum_{i\geq 1}C_{i}$ be the union of our moving cut
sequence. By 1.2 we know that

$\displaystyle\operatorname{spars}_{(h^{\prime},s^{\prime})}(\mathcal{C},A)\leq
s^{3}\cdot\log^{3}N\cdot
N^{O(1/s)}\cdot\frac{\sum_{i}|C_{i}|}{\sum_{i}|C_{i}|/\operatorname{spars}_{(h,s)}(C_{i},A)}.$
(14)

Furthermore, by Lemma 11.2 we know that there exists an
$(h^{\prime},s^{\prime})$-length $\phi^{\prime}$-sparse moving cut
$\mathcal{C}^{\prime}$ such that

$\displaystyle\frac{\phi^{\prime}}{\operatorname{spars}_{(h^{\prime},s^{\prime})}(\mathcal{C},A)}\cdot|\mathcal{C}|\leq|\mathcal{C}^{\prime}|.$
(15)

Thus, combining Equation 14 and Equation 15 we get

$\displaystyle\frac{\sum_{i}|C_{i}|/\operatorname{spars}_{(h,s)}(C_{i},A)}{s^{3}\cdot\log^{3}N\cdot
N^{O(1/s)}\cdot\sum_{i}|C_{i}|}\cdot\phi^{\prime}\cdot|\mathcal{C}|\leq|\mathcal{C}^{\prime}|$

and so using our definition of $\phi^{\prime}$ and the fact that
$|\mathcal{C}|=\sum_{i\geq 1}|C_{i}|$ we get

$\displaystyle\sum_{i\geq
1}\frac{\phi}{\operatorname{spars}_{(h,s)}(C_{i},A)}\cdot|C_{i}|\leq|\mathcal{C}^{\prime}|.$

However, since $C_{0}$ is the largest $(h^{\prime},s^{\prime})$-length
$\phi^{\prime}$-sparse cut we know that $|\mathcal{C}^{\prime}|\leq|C_{0}|$,
giving our desired inequality (Equation 13). ∎

###  11.2 Largest Cut (1) at Most Largest Expander’s Complement (4)

We now show $\text{LC}\leq\text{LEC}$. The basic idea is to argue that if the
largest length-constrained sparse cut were too large then it would cut into
the length-constrained expanding part of our graph, contradicting its
sparsity. We formalize this argument with the notion of projected down demand.

######  Theorem 11.3.

Given graph $G$ and node-weighting $A$ and parameters $h,s,\phi$, we have that

$\displaystyle\text{LC}(\phi,h,s)\leq\text{LEC}(\phi^{\prime},h,s)$

where $\phi^{\prime}=3\phi$.

####  11.2.1 Projected Down Demands

The following formalizes the projected down demand.

######  Definition 11.3 (Projected Down Demand).

Suppose we are given graph $G$, node-weighting $A$, $A$-respecting demand $D$
and $\hat{A}\preceq A$ where $\bar{A}:=A-\hat{A}$ is the complement of
$\hat{A}$. Then, let $D^{+}$ be any demand such that
$\sum_{v}D^{+}(u,v)=\min(\bar{A}(u),\sum_{v}D(u,v))$ for every $u$ and
$D^{+}\preceq D$. Symmetrically, let $D^{-}$ be any demand such that
$\sum_{v}D(v,u)=\min(\bar{A}(u),\sum_{v}D(v,u))$ and $D^{-}\preceq D$. Then we
define the demand $D$ projected down to $\hat{A}$ on $(u,v)$ as

$\displaystyle
D^{\downharpoonright\hat{A}}(u,v):=\max(0,D(u,v)-D^{+}(u,v)-D^{-}(u,v)).$

The following establishes the basic properties of
$D^{\downharpoonright\hat{A}}$.

######  Lemma 11.4.

Given graph $G$, node-weighting $A$, $\hat{A}\preceq A$ where
$\bar{A}:=A-\hat{A}$, we have that $D^{\downharpoonright\hat{A}}$ is
$\hat{A}$-respecting, $|D^{\downharpoonright\hat{A}}|\geq|D|-2|\bar{A}|$ and
$D^{\downharpoonright\hat{A}}\preceq D$.

###### Proof.

To see that $D^{\downharpoonright\hat{A}}$ is $\hat{A}$-respecting, fix a
vertex $u$. Casing on the minimizer of $\min(\bar{A}(u),\sum_{v}D(u,v))$ we
have the following.

  * •

If $\sum_{v}D^{+}(u,v)=\bar{A}(u)$ (where $D^{+}$ is defined in Definition
11.3) then by the fact that $D$ is $A$-respecting we have

$\displaystyle\sum_{v}D^{\downharpoonright\hat{A}}(u,v)$
$\displaystyle\leq\sum_{v}D(u,v)-\sum_{v}D^{+}(u,v)$ $\displaystyle\leq
A(v)-\bar{A}(u)$ $\displaystyle=\hat{A}(u).$

  * •

On the other hand, if $\sum_{v}D^{+}(u,v)=\sum_{v}D(u,v)$ then by the non-
negativity of node-weightings we have

$\displaystyle\sum_{v}D^{\downharpoonright\hat{A}}(u,v)$
$\displaystyle\leq\sum_{v}D(u,v)-\sum_{v}D^{+}(u,v)$ $\displaystyle=0$
$\displaystyle=\hat{A}(u).$

In either case we have
$\sum_{v}D^{\downharpoonright\hat{A}}(u,v)\leq\hat{A}(u)$. A symmetric
argument using $D^{-}$ (where $D^{-}$ is defined in Definition 11.3) shows
that $\sum_{v}D^{\downharpoonright\hat{A}}(v,u)\leq\hat{A}(u)$ and so
$D^{\downharpoonright\hat{A}}(u,v)$ is $\hat{A}$-respecting.

To see that $|D^{\downharpoonright\hat{A}}|\geq|D|-2|\bar{A}|$, observe that
by definition, $|D^{\downharpoonright\hat{A}}|\geq|D|-|D^{+}|-|D^{-}|$. But,
also by definition, $|D^{+}|,|D^{-}|\leq|\bar{A}|$, giving the claim.

Lastly, observe that $D^{\downharpoonright\hat{A}}\preceq D$ trivially by
construction. ∎

####  11.2.2 Proof Of Largest Cut At Most Largest Expander’s Complement

Having formalized the projected down demand, we can now formally prove the
main theorem of this section. See 11.3

###### Proof.

The basic idea of the proof is to argue that the largest sparse cut cannot be
larger than the size of the complement of the largest expanding subset because
if it were then it would cut into the the largest expanding subset itself;
this contradicts the fact that no sparse cut can cut too much into an
expanding subset. The projected down demand (Definition 11.3) allows us to
formalize this idea.

More formally, let $C_{0}$ be the $(h,s)$-length $\phi$-sparse cut of largest
size w.r.t. $A$ in $G$ and let $\bar{A}$ be the complement of the largest
$(h,s)$-length $\phi^{\prime}$-expanding subset $\hat{A}\preceq A$ as in
Definition 11.1.

Let $D$ be the demand that witnesses the $(h,s)$-length $\phi$-sparsity of
$C_{0}$; that is, it is the minimizing $A$-respecting demand in Definition
5.13. We may assume, without loss of generality, that $C_{0}$ $hs$-separates
all of $D$; that is, $\mathrm{sep}_{hs}(C_{0},D)=|D|$. Let
$D^{\downharpoonright\hat{A}}$ be the projected down demand (as in Definition
11.3). Recall that by Lemma 11.4 we know that $D^{\downharpoonright\hat{A}}$
is $\hat{A}$-respecting, $|D^{\downharpoonright\hat{A}}|\geq|D|-2|\bar{A}|$
and $D^{\downharpoonright\hat{A}}\preceq D$.

However, since $C_{0}$ $hs$-separates all of $D$ and
$D^{\downharpoonright\hat{A}}\preceq D$ we know that $C_{0}$ must
$hs$-separate all of $D^{\downharpoonright\hat{A}}$ and so applying this and
$|D^{\downharpoonright\hat{A}}|\geq|D|-2|\bar{A}|$ we have

$\displaystyle\operatorname{spars}_{s\cdot
h}(C_{0},D^{\downharpoonright\hat{A}})=\frac{|C_{0}|}{\mathrm{sep}(C_{0},D^{\downharpoonright\hat{A}})}=\frac{|C_{0}|}{|D^{\downharpoonright\hat{A}}|}\leq\frac{|C_{0}|}{|D|-2|\bar{A}|}$
(16)

where, as a reminder, $\operatorname{spars}$ is defined in Definition 5.10 and
Definition 5.13.

On the other hand, since $D^{\downharpoonright\hat{A}}$ is
$\hat{A}$-respecting and $\hat{A}$ is $(h,s)$-length $\phi^{\prime}$-expanding
by definition, we know that no cut can be too sparse w.r.t. $\hat{A}$ and, in
particular, we know that

$\displaystyle
3\phi=\phi^{\prime}\leq\operatorname{spars}_{(h,s)}(C_{0},\hat{A})\leq\operatorname{spars}_{s\cdot
h}(C_{0},D^{\downharpoonright\hat{A}})$ (17)

Combining Equation 16 and Equation 17 and solving for
$\phi^{\prime}\cdot|\bar{A}|$ we have

$\displaystyle\frac{3\phi\cdot|D|-|C_{0}|}{2}\leq\phi^{\prime}\cdot|\bar{A}|.$

However, recall that $C_{0}$ is an $(h,s)$-length $\phi$-sparse cut witnessed
by $D$ and, in particular, this means that $\frac{1}{\phi}|C_{0}|\geq|D|$.
Applying this we conclude that

$\displaystyle|C_{0}|\leq\phi^{\prime}\cdot|\bar{A}|.$

as required. ∎

###  11.3 Largest Expander’s Complement (4) at Most Weighted Sparse Cut
Sequence (3)

We now argue that $\text{LEC}\leq\text{LWSC}$. The basic idea is to use our
characterization of length-constrained expanders in terms of expander power
embeddings (as developed in Section 7 and formalized by the neighborhood
router demand). In particular, any demand of the neighborhood router demand
not separated by the largest cut sequence must be efficiently routable after
applying any expander decomposition since the resulting graph is a length-
constrained expander. By 7.1 this implies the existence of a large expanding
subset and so the complement of the largest expanding expanding complement
must be small. Formally we show the following.

######  Theorem 11.4.

Given graph $G$ and node-weighting $A$, we have that

$\displaystyle\text{LEC}(\phi,h,s)\leq\text{LWSC}(\phi^{\prime},h^{\prime},s^{\prime})$

where $\phi^{\prime}=\phi\cdot\Omega\left(2^{O(k)}\cdot
N^{O(1/k^{\prime})}\cdot\log^{2}N\right)$, $h^{\prime}=h\cdot k^{\prime}$ and
$s^{\prime}=s\cdot O\left(\frac{k}{k^{\prime}}\cdot\log N\right)$.

It will be useful for us to abstract out this argument as we will later use it
to argue that $\text{LEC}\leq\text{SED}$. The following formalizes the fact
which we abstract out.

######  Lemma 11.5.

Given graph $G$, node-weighting $A$ and parameters $k,k^{\prime}\geq 1$, let
$\bar{A}$ be the largest $(h,s)$-length $\phi$-expanding subset’s complement
(as defined in Definition 11.1). Furthermore, let $C^{*}$ be an
$(h^{\prime},s^{\prime})$-length $\phi^{\prime}$-expander decomposition where
$\phi^{\prime}=\phi\cdot\Omega\left(2^{O(k)}\cdot
N^{O(1/k^{\prime})}\cdot\log^{3}N\right)$, $h^{\prime}=h\cdot k^{\prime}$ and
$s^{\prime}=s\cdot O\left(\frac{k}{k^{\prime}}\cdot\log N\right)$. Then

$\displaystyle\operatorname{spars}_{(h^{\prime},s^{\prime})}(C^{*},A)\cdot|\bar{A}|\leq|C^{*}|\cdot
O\left(2^{O(k)}\cdot N^{O(1/k^{\prime})}\cdot\log^{2}N\right).$

###### Proof.

Let $G^{\prime}:=G-C^{*}$ be $G$ with $C^{*}$ applied. Observe that
$G^{\prime}$ must be an $(h^{\prime},s^{\prime})$-length
$\phi^{\prime}$-expander since $C^{*}$ is an expander decomposition.

Next, let $D_{A,k,k^{\prime}}$ be the neighborhood router demand, as defined
in Section 7.1. Recall that by Lemma 7.1 we know $D_{A,k,k^{\prime}}$ is
$A$-respecting and $h^{\prime}$-length. Let $D_{A,k,k^{\prime}}^{\prime}$ be
$D_{A,k,k^{\prime}}$ restricted to be $h^{\prime}s^{\prime}$-length in
$G^{\prime}$. That is, $D_{A,k,k^{\prime}}^{\prime}$ on $u$ and $v$ is defined
as

$\displaystyle D_{A,k,k^{\prime}}^{\prime}(u,v)$
$\displaystyle:=\begin{cases}D_{A,k,k^{\prime}}(u,v)&\text{if
$d_{G^{\prime}}(u,v)\leq h^{\prime}s^{\prime}$}\\\
0&\text{otherwise}.\end{cases}$

Observe that $D_{A,k,k^{\prime}}^{\prime}$ is trivially $A$-respecting since
$D_{A,k,k^{\prime}}$ is $A$-respecting. Also, $D_{A,k,k^{\prime}}^{\prime}$ is
$h^{\prime}s^{\prime}$-length by construction. Additionally, observe that by
construction we have

$\displaystyle|D_{A,k,k^{\prime}}^{\prime}|\geq|D_{A,k,k^{\prime}}|-\mathrm{sep}_{h^{\prime}s^{\prime}}\left(C^{*},A\right).$

Since $G^{\prime}$ is an $(h^{\prime},s^{\prime})$-length
$\phi^{\prime}$-expander and $D_{A,k,k^{\prime}}^{\prime}$ is $A$-respecting
and $h^{\prime}s^{\prime}$-length, we know that $D_{A,k,k^{\prime}}^{\prime}$
can be routed in $G^{\prime}$ with congestion at most $O(\frac{\log
N}{\phi^{\prime}})$ and dilation $O(h^{\prime}s^{\prime})$ by Theorem 5.17.
Letting
$\epsilon=\frac{\mathrm{sep}_{h^{\prime}s^{\prime}}(C^{*},A)}{|D_{A,k,k^{\prime}}|}$,
it follows that a $1-\epsilon$ fraction of $D_{A,k,k^{\prime}}$ can be routed
with congestion at most $O(\frac{\log N}{\phi^{\prime}})$ and dilation at most
$O(h^{\prime}s^{\prime})$. Applying 7.1 and the fact that
$|D_{A,k,k^{\prime}}|\geq\Omega\left(\frac{1}{N^{O(1/k^{\prime})}\cdot\log
N}\cdot|A|\right)$ by Lemma 7.1, we have that that there is a node weighting
$A^{\prime}\preceq A$ of size at least

$\displaystyle|A^{\prime}|\geq|A|\cdot\left(1-\frac{\mathrm{sep}_{h^{\prime}s^{\prime}}(C^{*},A)}{|D_{A,k,k^{\prime}}|}\cdot
O\left(2^{O(k)}\cdot N^{O(1/k^{\prime})}\cdot\log N\right)\right)$
$\displaystyle\geq|A|-\mathrm{sep}_{h^{\prime}s^{\prime}}(C^{*},A)\cdot
O\left(2^{O(k)}\cdot N^{O(1/k^{\prime})}\cdot\log^{2}N\right)$

such that $A^{\prime}$ is $(h,s)$-length $\phi$-expanding in $G^{\prime}$.

Let $\bar{A}$ be the complement of the largest $(h,s)$-length $\phi$-expanding
subset of $A$ as in Definition 11.1. Then, observing that
$|\bar{A}|\leq|A|-|A^{\prime}|$ and
$\mathrm{sep}_{h^{\prime}s^{\prime}}(\mathcal{C},A)=\frac{|\mathcal{C}|}{\operatorname{spars}_{(h^{\prime},s^{\prime})}(\mathcal{C},A)}$
then gives:

$\displaystyle|\bar{A}|\leq|\mathcal{C}|\cdot O\left(\frac{2^{O(k)}\cdot
N^{O(1/k^{\prime})}\cdot\log^{2}N}{\operatorname{spars}_{(h^{\prime},s^{\prime})}(\mathcal{C},A)}\right)$

as required. ∎

Applying the above helper lemma allows us to conclude the main fact of this
section. See 11.4

###### Proof.

The basic idea is to observe that the union of the largest sequence of sparse
cuts is an expander decomposition and then apply Lemma 11.5.

More formally, let $\bar{A}$ be the largest $(h,s)$-length $\phi$-expanding
subset’s complement (as defined in Definition 11.1). Also, let
$(C_{1},C_{2},\ldots)$ be the $(h^{\prime},s^{\prime})$-length
$\phi^{\prime}$-sparse moving cut sequence of largest weighted size as defined
in Definition 11.1, let $\mathcal{C}:=\sum_{i}C_{i}$.

Observe that $\mathcal{C}$ must be an $(h^{\prime},s^{\prime})$-length
$\phi^{\prime}$-expander decomposition since otherwise there would be a cut
that could be appended to $(C_{1},C_{2},\ldots)$ to increase its size,
contradicting its maximality. It follows by Lemma 11.5 that

$\displaystyle\operatorname{spars}_{(h^{\prime},s^{\prime})}(\mathcal{C},A)\cdot|\bar{A}|\leq|\mathcal{C}|\cdot
O\left(2^{O(k)}\cdot N^{O(1/k^{\prime})}\cdot\log^{2}N\right).$ (18)

Let $D$ be the $A$-respecting demand witnessing the sparsity of $\mathcal{C}$
so that

$\displaystyle\operatorname{spars}_{(h^{\prime},s^{\prime})}(\mathcal{C},A)=\frac{|\mathcal{C}|}{\mathrm{sep}_{h^{\prime}s^{\prime}}(\mathcal{C},D)}.$

Observe that by definition of $\mathcal{C}$ and since
$\operatorname{spars}_{(h^{\prime},s^{\prime})}(C_{i},D)\geq\operatorname{spars}_{(h^{\prime},s^{\prime})}(C_{i},A)$
we get

$\displaystyle\mathrm{sep}_{(h^{\prime}s^{\prime})}(\mathcal{C},D)=\sum_{i}\mathrm{sep}_{h^{\prime}s^{\prime}}(C_{i},D)=\sum_{i}\frac{|C_{i}|}{\operatorname{spars}_{(h^{\prime},s^{\prime})}(C_{i},D)}\leq\sum_{i}\frac{|C_{i}|}{\operatorname{spars}_{(h^{\prime},s^{\prime})}(C_{i},A)}$

and so it follows that

$\displaystyle\operatorname{spars}_{(h^{\prime},s^{\prime})}(\mathcal{C},A)\geq\frac{|\mathcal{C}|}{\sum_{i}|C_{i}|/\operatorname{spars}_{(h^{\prime},s^{\prime})}(C_{i},A)}.$

Combining this bound on
$\operatorname{spars}_{(h^{\prime},s^{\prime})}(\mathcal{C},A)$ and Equation
18 we get

$\displaystyle|\bar{A}|\leq\sum_{i}\frac{|C_{i}|}{\operatorname{spars}_{(h^{\prime},s^{\prime})}(C_{i},A)}\cdot
O\left(2^{O(k)}\cdot N^{O(1/k^{\prime})}\cdot\log^{2}N\right).$

Multiplying both sides by $\phi$ we get

$\displaystyle\phi\cdot|\bar{A}|\leq\sum_{i}\frac{\phi^{\prime}}{\operatorname{spars}_{(h^{\prime},s^{\prime})}(C_{i},A)}\cdot|C_{i}|.$

as required. ∎

The remaining inequalities we show are mostly trivial.

###  11.4 Largest Expander’s Complement (4) at Most Smallest Expander
Decomposition (5)

We now leverage the helper lemma from the previous section (Lemma 11.5) to
show $\text{LEC}\leq\text{SED}$.

######  Theorem 11.5.

Given graph $G$ that is $(h^{\prime},s^{\prime})$-length $\phi_{G}$-expanding
w.r.t. node-weighting $A$ and parameters $h,s,\phi$, we have that

$\displaystyle\frac{\phi_{G}}{\phi^{\prime}}\cdot\text{LEC}(\phi,h,s)\leq\text{SED}(\phi^{\prime},h^{\prime},s^{\prime}).$

where $\phi^{\prime}=\phi\cdot\Omega\left(2^{O(k)}\cdot
N^{O(1/k^{\prime})}\cdot\log^{2}N\right)$, $h^{\prime}=h\cdot k^{\prime}$ and
$s^{\prime}=s\cdot O\left(\frac{k}{k^{\prime}}\cdot\log N\right)$.

###### Proof.

The proof is immediate from our previous helper lemma, Lemma 11.5.

In particular, let $C^{*}$ be the smallest $(h^{\prime},s^{\prime})$-length
$\phi^{\prime}$-expander decomposition and let $\bar{A}$ be the largest
$(h,s)$-length $\phi$-expanding subset’s complement (as in Definition 11.1).
By Lemma 11.5 we know that

$\displaystyle\operatorname{spars}_{(h^{\prime},s^{\prime})}(C^{*},A)\cdot|\bar{A}|\leq|\mathcal{C}|\cdot
O\left(2^{O(k)}\cdot N^{O(1/k^{\prime})}\cdot\log^{2}N\right).$

Since $G$ is $(h^{\prime},s^{\prime})$-length $\phi_{G}$-expanding we know
$\operatorname{spars}_{(h^{\prime},s^{\prime})}(C^{*},A)\geq\phi_{G}$ and so

$\displaystyle\phi_{G}\cdot|\bar{A}|\leq|\mathcal{C}|\cdot
O\left(2^{O(k)}\cdot N^{O(1/k^{\prime})}\cdot\log^{2}N\right).$

Multiplying both sides by $\phi$ and applying the definition of
$\phi^{\prime}$ then gives

$\displaystyle\frac{\phi_{G}}{\phi^{\prime}}\cdot\phi|\bar{A}|\leq|\mathcal{C}|.$

as required. ∎

###  11.5 Largest Cut (1) at Most Largest Cut Sequence (2)

Showing $\text{LC}\leq\text{LSC}$ is trivial since the first moving cut of any
sparse length-constrained cut sequence cut could be the largest sparse length-
constrained cut.

######  Theorem 11.6.

Given graph $G$ and node-weighting $A$ and parameters $h,s,\phi$, we have that

$\displaystyle\text{LC}(\phi,h,s)\leq\text{LSC}(\phi,h,s).$

###### Proof.

Any cut sequence $(C_{1},C_{2},\ldots)$ that begins with $C$ will satisfy
$|C|\leq\sum_{i}|C_{i}|$ and since $C$ can always be chosen as the first cut
in an $(h,s,\phi)$-sequence this gives the theorem. ∎

###  11.6 Largest Cut Sequence (2) at Most Largest Weighted Cut Sequence (3)

Likewise $\text{LSC}\leq\text{LWSC}$ is trivial since the largest weighted
sequence of sparse length-constrained cuts always has as a candidate the
largest (unweighted) sequence of sparse length-constrained cuts.

######  Theorem 11.7.

Given graph $G$ and node-weighting $A$ and parameters $h,s,\phi$, we have that

$\displaystyle\text{LSC}(\phi,h,s)\leq\text{LWSC}(\phi,h,s).$

###### Proof.

The proof is immediate from the fact that the weighted size of a sequence of
$(h,s)$-length $\phi$-sparse cuts is always larger than its actual size

Specifically, let $(C_{1},C_{2},)$ be the largest sequence of $(h,s)$-length
$\phi$-sparse cuts and let $(C_{1}^{\prime},C_{2}^{\prime},\ldots)$ be the
sequence of of $(h,s)$-length $\phi$-sparse cuts of largest weighted size (as
in Definition 11.1). Observe that since each $C_{i}$ is $\phi$-sparse we know
that for each $C_{i}$ we have $\operatorname{spars}_{(h,s)}(C_{i},A)\leq\phi$
and since $(C_{1}^{\prime},C_{2}^{\prime},\ldots)$ is the $(h,s)$-length
$\phi$-sparse cut sequence of largest size we have

$\displaystyle\sum_{i}|C_{i}|\leq\sum_{i}\frac{\phi}{\operatorname{spars}_{(h,s)}(C_{i},A)}\cdot|C_{i}|\leq\sum_{i}\frac{\phi}{\operatorname{spars}_{(h,s)}(C_{i}^{\prime},A)}\cdot|C_{i}^{\prime}|$

as required. ∎

###  11.7 Smallest Expander Decomposition (5) at Most Largest Cut Sequence (2)

Lastly, $\text{SED}\leq\text{LSC}$ is trivial since the largest sequence of
length-constrained sparse cuts is itself a length-constrained expander
decomposition.

######  Theorem 11.8.

Given graph $G$ and node-weighting $A$ and parameters $h,s,\phi$, we have that

$\displaystyle\text{SED}(\phi,h,s)\leq\text{LSC}(\phi,h,s).$

###### Proof.

Let $(C_{1},C_{2},\ldots)$ be the largest sequence of $(h,s)$-length
$\phi$-sparse cuts and let $C^{*}$ be the smallest $(h,s)$-length
$\phi$-expander decomposition.

From the maximality of the sequence $(C_{1},C_{2},\ldots)$, it must hold that
$G-\sum_{i}C_{i}$ is an $(h,s)$-length $\phi$-expander, as otherwise we can
find another moving cut and append it to the sequence, contradicting the
maximality of the sequence $(C_{1},C_{2},\ldots)$. Therefore, the moving cut
$\mathcal{C}=\sum_{i}C_{i}$ is an $(h,s)$-length $\phi$-expander decomposition
of $G$ for $A$. But since $C^{*}$ is the smallest such expander decomposition
we then know that $|C^{*}|\leq|\mathcal{C}|=\sum_{i}|C_{i}|$ as required. ∎

###  11.8 Proof of Equivalence of Distance Measures (11.1)

We conclude this section by stringing together our proven inequalities to show
the equivalence of our various graph quantities.

See 11.1

###### Proof.

We string together our inequalities as follows.

$\text{LC}(\phi,h,s)\leq\text{LEC}(\phi_{1},h,s)$ by 11.3

$\text{LEC}(\phi_{1},h_{1},s_{1})\leq\text{LSC}(\phi_{2},h_{2},s_{2})$ by
11.4, 11.2 and 11.6.

$\text{LSC}(\phi_{2},h_{2},s_{2})\leq\text{LC}(\phi_{3},h_{3},s_{3})$ by 11.7
and 11.2.

For our second set of inequalities we additionally have the following.

$\frac{\phi_{G}}{\phi_{4}}\cdot\text{LEC}(\phi,h,s)\leq\text{SED}(\phi_{4},h_{4},s_{4})$
by 11.5.

$\text{SED}(\phi_{4},h_{4},s_{4})\leq\text{LSC}(\phi_{4},h_{4},s_{4})$ by
11.8.

$\text{LSC}(\phi_{4},h_{4},s_{4})\leq\text{LC}(\phi_{5},h_{5},s_{5})$ again by
11.7 and 11.2.

$\text{LC}(\phi_{5},h_{5},s_{5})\leq\text{LSC}(\phi_{5},h_{5},s_{5})$ by 11.6.
∎

##  12 Algorithm: Sparse Flows and Cutmatches

Our algorithm to compute large length-constrained sparse cuts from cut
strategies will be based on the previously-studied idea of a (length-
constrained) cutmatch. Informally, a cutmatch matches two node sets over flow
paths and finds a cut certifying that the unmatched nodes cannot be matched
without significant additional congestion. In the rest of this section we give
new algorithms for efficiently computing cutmatches with sparse flows; towards
this, we give the first efficient algorithms for near-optimal length-
constrained flows with support size $\tilde{O}(m)$. As our algorithms
parallelize, we give our results as parallel algorithms in this section.

To define our cutmatch algorithm guarantees we will make use of the following
notion of batching.

######  Definition 12.1 ($b$-Batchable).

Given a graph $G=(V,E)$ with edge lengths $\ell$ and vertex subsets
$V_{1},V_{2},\ldots\subseteq V$, we say that
$\mathcal{V}=\\{V_{1},V_{2},\ldots\\}$ is $b$-batchable for length $h$ if
$\mathcal{V}$ can be partitioned into “batches”
$\mathcal{V}_{1},\mathcal{V}_{2},\ldots,\mathcal{V}_{b}$ so that if $u\in
V_{i}\in\mathcal{V}_{j}$ and $v\in V_{i^{\prime}}\in\mathcal{V}_{j}$ and
$i\neq i^{\prime}$ then $u$ and $v$ are at least $2h$ apart in $G$. We say
that pairs of vertex subsets $\\{(S_{i},T_{i})\\}_{i}$ are $b$-batchable if
$\\{S_{i}\cup T_{i}\\}_{i}$ is $b$-batchable.

A cutmatch is defined as follows.

######  Definition 12.2 (Multi-Commodity $h$-Length Cutmatch, [HHS23]).

Given a graph $G=(V,E)$ with lengths $\ell$, an $h$-length $\phi$-sparse
cutmatch of congestion $\gamma$ between disjoint and equal-size node-weighting
pairs $\\{(A_{i},A_{i}^{\prime})\\}_{i}$ consists of, for each $i$, a
partition of the support of the node-weightings $M_{i}\sqcup
U_{i}=\mathrm{supp}(A_{i})$ and $M_{i}^{\prime}\sqcup
U_{i}^{\prime}=\mathrm{supp}(A_{i}^{\prime})$ where $M_{i},M_{i}^{\prime}$ and
$U_{i},U_{i}^{\prime}$ are the “matched” and “unmatched” parts respectively
and

  * •

An integral $h$-length flow $F=\sum_{i}F_{i}$ in $G$ with lengths $\ell$ of
congestion $\gamma$ according to $U$ where, for each $i$, each $u$ sends at
most $A_{i}(u)$ according to $F_{i}$ (with equality iff $u\in M_{i}$) and each
$u^{\prime}\in M_{i}^{\prime}$ receives at most $A_{i}^{\prime}(u^{\prime})$
flow according to $F_{i}$ (with equality iff $u^{\prime}\in M_{i}^{\prime}$);

  * •

A moving cut $C$ in $G$ where $U_{i}$ and $U_{i}^{\prime}$ are at least
$h$-far according to lengths $\\{\ell_{e}+h\cdot C(e)\\}_{e}$ and $C$ has size
at most

$\displaystyle|C|\leq\phi\cdot\left(\left(\sum_{i}|A_{i}|\right)-\mathrm{val}(F)\right).$

The below summarizes our new cutmatch algorithms. Previously, [HHS23] gave the
same result but with support size $\tilde{O}(b\cdot\operatorname{poly}(h)\cdot
m)$.

######  Theorem 12.3.

Suppose we are given a graph $G=(V,E)$ on $m$ edges with lengths $\ell$,
$h\geq 1$ and $\phi\leq 1$. There is an algorithm that, given node-weighting
pairs $\\{(A_{i},B_{i})\\}_{i}$ whose supports are $b$-batchable for length
$h$, outputs a multi-commodity $h$-length $\phi$-sparse cutmatch $(F,C)$ of
congestion $\gamma$ where $\gamma=\tilde{O}(\frac{1}{\phi})$. Furthermore,
$|\mathrm{supp}(F)|\leq\tilde{O}(m+b+\sum_{i}|\mathrm{supp}(A_{i}\cup
B_{i})|)$ and this algorithm has depth $b\cdot\operatorname{poly}(h,\log N)$
and work
$\tilde{O}\left(|\mathrm{supp}(F)|\cdot\operatorname{poly}(h)\right)$.

Our cutmatch algorithm will be based on new length-constrained flow algorithms
whose guarantees are summarized by the below. See 1.3

###  12.1 Rounding Flows to Blaming Flows

In order to achieve sparse flows and cutmatches we introduce the following
sense of blaming flows. The utility of the following sense of blaming is that
each time an edge is $\gamma$-blamed, a $\gamma$-fraction of its capacity is
used up so if we compute a series of $\gamma$-blaming flows the total support
size of these flows should be at most (about) $m/\gamma$.

######  Definition 12.4 (Blaming Flow).

Given flow $F$ we say that $F$ is $\gamma$-blaming if for each $P$ in the
support of $F$ there is a unique edge $e\in P$ that $P$ “blames” such that
$F(e)\geq\gamma\cdot U_{e}$.

The following algorithm shows how to convert arbitrary flows into blaming
flows

######  Lemma 12.5.

Given a feasible (possibly fractional) $h$-length flow $F$ on graph $G=(V,E)$
one can compute a feasible integral flow $\hat{F}$ where
$\mathrm{supp}(\hat{F})\subseteq\mathrm{supp}(F)$ and

  1. 1.

Blaming: $\hat{F}$ is $\frac{1}{2}$-blaming;

  2. 2.

Approximate:
$\mathrm{val}(\hat{F})\geq\Omega\left(\frac{1}{h\cdot\log^{2}N}\right)\cdot\mathrm{val}(F)$;

in $\tilde{O}(|\mathrm{supp}(\hat{F})|/|E|+\log|\mathrm{supp}(\hat{F})|)$
parallel time with $m$ processors.

###### Proof.

The basic idea of the algorithm is as follows. By a standard bucketing trick
we can assume that every flow path in the support of $F$ has the same value
$2^{j^{*}}$ and that the minimum capacity edge used by every flow path has the
same capacity of $2^{i^{*}}$. We then create an instance of maximal
independent set (MIS) whose vertices are our flow paths to select a subset of
flow paths $I\subseteq\mathrm{supp}(F)$ so that each capacity $2^{i^{*}}$ edge
used by $F$ has at most one flow path in $I$ going over it; sending
$2^{i^{*}}$ flow along each flow path of $I$ gives our result.

More formally, we begin by rounding our flow values and capacities down to
powers of $2$. Specifically let $U^{\prime}$ be the capacity which gives edge
$e$ value

$\displaystyle U_{e}^{\prime}:=2^{\lfloor\log_{2}(U_{e})\rfloor}$

Likewise, let $F^{\prime}$ be the flow which gives path $P$ flow value

$\displaystyle F^{\prime}(P):=2^{\lfloor\log_{2}(F(P))-1\rfloor}$

Observe that by the feasibility of $F$ for capacities $U$ and the extra $-1$
in the exponent in our definition of $F^{\prime}(P)$ we know that $F^{\prime}$
is feasible in $G$ for capacities $U^{\prime}$. Furthermore, we know by
definition of $F^{\prime}$ that

$\displaystyle\mathrm{val}(F^{\prime})\geq\mathrm{val}(F)/2.$ (19)

Next, we partition paths of $F^{\prime}$ by the smallest capacity edge that
they use and their flow value. Specifically, for each $i$ and $j\leq i$, let
$\mathcal{P}_{i,j}:=\\{P\in\mathrm{supp}(F^{\prime}):\min_{e\in
P}U_{e}^{\prime}=2^{i}\text{ and }F^{\prime}(P)=2^{j}\\}$ be all paths in the
support of $F^{\prime}$ with minimum capacity edge of capacity $2^{i}$ and
flow value $2^{j}$. Let $F_{i,j}^{\prime}$ be the flow which matches
$F^{\prime}$ on paths in $\mathcal{P}_{i,j}$, namely $F_{i,j}^{\prime}$ on
path $P$ is defined as

$\displaystyle F_{i,j}^{\prime}(P):=\begin{cases}F^{\prime}(P)=2^{j}&\text{if
$P\in\mathcal{P}_{i,j}$}\\\ 0&\text{otherwise}.\end{cases}$

Let
$i^{*},j^{*}:=\operatorname*{arg\,max}_{i,j}\mathrm{val}(F_{i,j}^{\prime})$ be
the index of the maximum such flow. We let

$\displaystyle F^{*}:=F_{i^{*},j^{*}}^{\prime}$

for ease of notation. By our assumption of polynomial capacities, the fact
that $F^{\prime}=\sum_{i,j}F_{i,j}^{\prime}$ and Equation 19 we know that

$\displaystyle\mathrm{val}(F^{*})\geq\Omega\left(\mathrm{val}(F^{\prime})/\log^{2}N\right)\geq\Omega\left(\mathrm{val}(F)/\log^{2}N\right).$
(20)

Furthermore, we know that $F^{*}$ is feasible in $G$ with capacities
$U^{\prime}$ and therefore feasible in $G$ with capacities $U$.

In what remains we will show how to round $F^{*}$ to another flow $\hat{F}$
which is both integral and blaming to at a negligible loss in cost. Each path
in the support of $\hat{F}$ will blame some edge of capacity $2^{i^{*}}$
according to $U^{\prime}$.

We will construct $\hat{F}$ by solving an appropriate instance of maximal
independent set (MIS) based on $F^{*}$. By construction every path in the
support of $F^{*}$ has flow value $2^{j^{*}}$ and uses an edge of capacity
$2^{i^{*}}$. Our goal will be to construct an instance of MIS which allows us
to select paths so that for each edge of capacity $2^{i^{*}}$ that is used by
some path in $\mathrm{supp}(F^{*})$ we select exactly one path. We will the
increase said paths flow value to $2^{i^{*}}$; likewise we will select
$2^{i-{i^{*}}}$ many paths for an edge of capacity $i>{i^{*}}$ in $G$.
Specifically, consider the following instance of MIS on graph
$H=(V_{H},E_{H})$.

  * •

MIS Vertices: For each path in $P\in\mathrm{supp}(F^{*})$ we have $1$ vertex.
In other words, $V_{H}:=\mathrm{supp}(F^{*})$.

  * •

MIS Edges: For each edge $e\in G$ in our original graph such that $F^{*}(e)>0$
we construct edges $E_{e}$ where $E_{H}:=\sqcup_{e\in E}E_{e}$ is the union of
all such edges. $E_{e}$ is constructed as follows. Let
$\mathcal{P}_{e}=\\{P_{0},P_{1},\ldots\\}$ be all paths in
$\mathrm{supp}(F^{*})$ which include $e$ ordered arbitrarily and for
$l\in\left[\lceil|\mathcal{P}_{e}|/2^{{i^{*}}-j^{*}}\rceil\right]$ let
$\mathcal{P}_{e}^{(l)}:=\\{P_{(l-1)\cdot 2^{i^{*}-j^{*}}},\ldots P_{(l)\cdot
2^{i^{*}-j^{*}}}\\}$ be the $l$th set of contiguous $2^{i^{*}-j^{*}}$ such
paths. For each $l$ and each $P,P^{\prime}\in\mathcal{P}_{e}^{(l)}$ we include
the edge $\\{P,P^{\prime}\\}$ in $E_{e}$; in other words, we add a clique for
each $\mathcal{P}_{e}^{(l)}$.

Let $I\subseteq\mathrm{supp}(F^{*})$ be an MIS in $H$. Then, we define
$\hat{F}$ as the flow corresponding to $I$ where each flow value is rounded up
from $2^{j^{*}}$ to $2^{i^{*}}$; that is, $\hat{F}$ on path $P$ is defined as

$\displaystyle\hat{F}(P):=\begin{cases}2^{i^{*}}&\text{if $P\in I$}\\\
0&\text{otherwise}.\end{cases}$

We now argue that $\hat{F}$ satisfies the required properties. We have
$\mathrm{supp}(\hat{F})\subseteq\mathrm{supp}(F)$ since
$\mathrm{supp}(\hat{F})\subseteq\mathrm{supp}(F^{*})\subseteq\mathrm{supp}(F^{\prime})=\mathrm{supp}(F)$.

$\hat{F}$ must be integral since $i^{*}\geq 1$ since we have assumed $U_{e}$
is integral for every $e$.

We next argue that $\hat{F}$ is feasible for capacities $U$. Even stronger, we
observe that $\hat{F}$ is feasible for $U^{\prime}$. In particular, applying
the fact that $I$ includes at most one element from each
$\mathcal{P}_{e}^{(l)}$ and $l\leq|\mathcal{P}_{e}|/2^{i^{*}-j^{*}}$ we have
the total flow that $\hat{F}$ sends over edge $e$ is

$\displaystyle\hat{F}(e)$ $\displaystyle=\sum_{l}\sum_{P\in
I\cap\mathcal{P}_{e}^{(l)}}2^{i^{*}}$ $\displaystyle\leq\sum_{l}2^{i^{*}}$
$\displaystyle\leq|\mathcal{P}_{e}|\cdot 2^{j^{*}}$ $\displaystyle=F^{*}(e)$
$\displaystyle\leq F^{\prime}(e)$ $\displaystyle\leq U_{e}^{\prime}.$

Thus, $\hat{F}$ is feasible for $U^{\prime}$ and since $U_{e}^{\prime}\leq
U_{e}$ for every edge $e$, $\hat{F}$ is also feasible for $U$.

Next, we claim that $\hat{F}$ is $\frac{1}{2}$-blaming. By definition of
$F^{*}$ we know that, for each $P\in\mathrm{supp}(F^{*})$, there is an edge
$e\in P$ such that $U_{e}^{\prime}=2^{i^{*}}$. As
$\mathrm{supp}(\hat{F})\subseteq\mathrm{supp}(F^{*})$ and $\hat{F}$ sends
$2^{i^{*}}$ over each path in its support, it follows that for each
$P\in\mathrm{supp}(\hat{F})$ there is a some $e\in P$ such that
$U^{\prime}_{e}=2^{i^{*}}$. Since $\hat{F}(P)=2^{i^{*}}$ and $\hat{F}$ is
feasible for $U^{\prime}$, it follows that this edge for each
$P\in\mathrm{supp}(\hat{F})$ is unique and $\hat{F}(e)=2^{i^{*}}$. Thus, we
have $P\in\mathrm{supp}(\hat{F})$ blame this unique edge $e$; since
$U^{\prime}_{e}\leq\frac{1}{2}\cdot U_{e}$, it follows that $\hat{F}$ is
$\frac{1}{2}$-blaming.

Lastly, we argue that $\hat{F}$ has approximately the same value as $F$. Since
every path in $F^{*}$ consists of at most $h$-many edges, observe that the
maximum degree in $H$ is at most $h\cdot 2^{i^{*}-j^{*}}$ so
$|I|\geq\frac{1}{h\cdot 2^{i^{*}-j^{*}}}\cdot|\mathrm{supp}(F^{*})|$.
Combining this with the fact that
$|\mathrm{supp}(F^{*})|=\mathrm{val}(F^{*})/2^{j^{*}}$ we have

$\displaystyle|I|$ $\displaystyle\geq\frac{1}{h\cdot
2^{i^{*}-j^{*}}}\cdot|\mathrm{supp}(F^{*})|$ $\displaystyle=\frac{1}{h\cdot
2^{i^{*}}}\cdot\mathrm{val}(F^{*}).$ (21)

Applying Equation 21 and the definition of $\hat{F}$ we get

$\displaystyle\mathrm{val}(\hat{F})$ $\displaystyle=2^{i^{*}}\cdot|I|$
$\displaystyle=\frac{1}{h}\cdot\mathrm{val}(F^{*})$ (22)

Combining Equation 22 and Equation 20 we get

$\displaystyle\mathrm{val}(\hat{F})\geq\Omega\left(\frac{1}{h\cdot\log^{2}N}\right)\cdot\mathrm{val}(F)$

as required.

It remains to argue the runtime of our algorithm. Computing $\hat{F^{*}}$ in
the stated time is trivial to do by inspecting each path in the support of $F$
in parallel. Likewise, computing $\hat{F}$ from $I$ is trivial to do in the
stated time. The only non-trivial step is to construct $H$ and compute $I$.
Constructing $H$ can be done in the stated time as it consists of
$|\mathrm{supp}(F^{*})|\leq|\mathrm{supp}(F)|$-many vertices and each
$\mathcal{P}_{e}^{(l)}$ and its corresponding clique can be computed in
parallel. Computing $I$ can then be done by any number of a standard number of
parallel MIS algorithms running in deterministic parallel time
$O(\log|V_{H}|)=O(\log|\mathrm{supp}(F)|)$ rounds; see e.g. [Lub85]. ∎

###  12.2 Blaming Flow Sequences

Our algorithm will ultimately compute a sequence of blaming flows, defined as
follows.

######  Definition 12.6 (Blaming Flow Sequence).

Given flow $F$ we say that $F$ is decomposable into a $\gamma$-blaming flow
sequence $F_{1},F_{2},\ldots$ if $F$ can be expressed as
$F=F_{1}+F_{2}+\ldots$ where $F_{i}$ is $\gamma$-blaming in $G$ with
capacities $U^{(i)}:=\\{U_{e}-\sum_{j<i}F_{j}(e)\\}_{e}$.

Given a flow $F$ that can be decomposed into a blaming flow sequence we will
refer to the number of times $F$ blames an edge $e$ by which we mean the
number of flows in $F_{1},F_{2},\ldots$ that have in their support a path that
blames $e$.

The following will imply the sparsity of a sequence of blaming flows.

######  Lemma 12.7.

Let $F$ be decomposable into a $\gamma$-blaming flow sequence
$F_{1},F_{2},\ldots$ of integral flows on graph $G=(V,E)$ with capacities $U$.
Then each edge is blamed at most $O(\frac{\log N}{\gamma})$ times by $F$.

###### Proof.

Each time an edge is blamed its capacity is reduced by a $1-\gamma$
multiplicative factor and by our assumption of polynomial-size capacities such
a reduction can happen at most $\frac{1}{\gamma}\cdot\log N$ times.

More formally, fix an edge $e$ suppose (without loss of generality) that
$F_{1}^{\prime},F_{2}^{\prime},\ldots,F_{k}^{\prime}$ is a subsequence of
$F_{1},F_{2},\ldots$ where each $F_{i}^{\prime}$ has in its support a path
that blames $e$. We have that the capacity of $e$ in the graph in which
$F_{i+1}^{\prime}$ contains a path blaming $e$ is at most

$\displaystyle U_{e}\cdot(1-\gamma)^{i}$

By our assumption that $U_{e}\leq N$ we then have that $i\leq O(\log N)$ as
required. ∎

###  12.3 Blaming Near-Lightest Path Blockers

The sequence of blaming flows computed by our algorithm will be a so-called
“near-lighted path blocker” as previously introduced by [HHS23]. Towards
defining these, it will be useful to treat a moving cut $C$ as assigning
“weights” to edges of our input graph. Given a moving cut $C$ and path $P$ we
let

$\displaystyle C(P):=\sum_{e\in P}C(e)$

be the total weight of the path and let

$\displaystyle d_{C}^{(h)}(u,v):=\min_{u-v\text{ path }P:\ell(P)\leq h}C(P)$

give the minimum weight of a length at most $h$ path connecting $u$ and $v$.
For vertex sets $W,W^{\prime}\subseteq V$ we define
$d_{C}^{(h)}(W,W^{\prime}):=\min_{w\in W}\min_{w^{\prime}\in
W^{\prime}}d_{C}^{(h)}(w,w^{\prime})$ analogously. Then, we have our
definition of near-lightest path blockers below.

######  Definition 12.8 ($h$-length $(1+\epsilon)$-Lightest Path Blockers,
[HHS23] Definition 11.1).

Let $G=(V,E)$ be a graph with lengths $\ell$, weights $C$ and capacities $U$.
Fix $\epsilon>0$, $h\geq 1$, $\lambda\leq d^{(h)}_{C}(S,T)$ and $S,T\subseteq
V$. Let $F$ be an $h$-length integral $S$-$T$ flow. $F$ is an $h$-length
$(1+\epsilon)$-lightest path blocker if:

  1. 1.

Near-Lightest: $P\in\mathrm{supp}(F)$ has weight at most
$(1+2\epsilon)\cdot\lambda$;

  2. 2.

Near-Lightest Path Blocking: If $S$-$T$ path $P^{\prime}$ has length at most
$h$ and weight at most $(1+\epsilon)\cdot\lambda$ then there is some $e\in
P^{\prime}$ where $F(e)=U_{e}$.

Previous work showed how to compute near-lightest path blockers.

######  Theorem 12.1.

[[HHS23] Theorem 11.1] One can compute $h$-length $(1+\epsilon)$-lightest path
blocker $F$ in deterministic parallel time
$\tilde{O}\left(\operatorname{poly}(\frac{1}{\epsilon},h)\right)$ with $m$
processors where
$|\mathrm{supp}(F)|\leq\tilde{O}\left(\operatorname{poly}(\frac{1}{\epsilon},h)\cdot|E|\right)$.

By repeatedly making near-lightest path blockers blaming, we can compute a
near-lightest path blockers which is also blaming.

######  Theorem 12.2.

One can compute an $h$-length $(1+\epsilon)$-lightest path blocker $F$ in
deterministic parallel time
$\tilde{O}\left(\operatorname{poly}(\frac{1}{\epsilon},h)\right)$ with $m$
processors which is decomposable into a $\frac{1}{2}$-blaming flow sequence.

###### Proof.

Our algorithm simply repeatedly takes lightest path blockers, rounds them to
be blaming, reduces capacities and iterates.

More formally, we do the following. We initialize our output
$(1+\epsilon)$-lightest path blocker $F$ to be the empty flow. Then, we
compute a $(1+\epsilon)$-lightest path blocker $F^{\prime}$ using 12.3. We
then apply Lemma 12.5 to round this flow to flow $\hat{F}$ which is
$\frac{1}{2}$-blaming. We update $F$ to $F+\hat{F}$ and decrement the capacity
of each edge $e$ by $\hat{F}(e)$. We iterate this until $F$ is near-lightest
path blocking.

We first claim that the above algorithm must only iterate
$\tilde{O}(\operatorname{poly}(h))$ times. This is proven in Theorem 11.1 of
[HHS23]. Our runtime and the fact that $\hat{F}$ is a $(1+\epsilon)$-lightest
path blocker and decomposable into a $\frac{1}{2}$-blaming flow sequence is
immediate by construction and the guarantees of 12.3 and Lemma 12.5. ∎

###  12.4 Sparse Flows and Cutmatches via Blaming Near-Lightest Path Blockers

We now use our near-lightest path blockers to compute sparse flows and
cutmatches. Specifically, we adopt Algorithm 1 which was shown by [HHS23] to
compute a near-optimal flow.

######  Theorem 12.3.

[[HHS23] Theorem 11.1] Algorithm 1 returns a feasible $h$-length
$\\{(S_{i},T_{i})\\}_{i}$ flow, moving cut pair $(F,C)$ that is
$(1\pm\epsilon)$-approximate in deterministic parallel time
$\tilde{O}\left(\operatorname{poly}(\frac{1}{\epsilon},h\right)$ with $m$
processors. Also, $F=\eta\cdot\sum_{j=1}^{k}F_{j}$ where
$\eta=\tilde{\Theta}(\epsilon^{2})$,
$k=\tilde{O}\left(\frac{h}{\epsilon^{4}}\right)$ and each $F_{j}$ is an
integral $h$-length $S_{i}$-$T_{i}$ flow for some $i$.

We observe that if we use blaming flows for our near-lightest path blockers in
Algorithm 1 then the resulting flow is sparse.

######  Lemma 12.9.

If each lightest path blocker in Algorithm 1 is decomposable into a
$\gamma$-blaming flow sequence then the flow $F$ returned by Algorithm 1
satisfies
$\mathrm{supp}(F)\leq\tilde{O}\left(\frac{1}{\gamma}\cdot|E|\right)$.

###### Proof.

Consider one edge $e$. Next, consider one shortest path blocker $\hat{F}$
computed by Algorithm 1. By Lemma 12.7 if $\hat{F}$ blames $e$ at least once
then it blames it at most $O\left(\frac{\log N}{\gamma}\right)$ times.
Furthermore, if $\hat{F}$ $\gamma$-blames $e$ at least once then $e$ has its
cut value increases by a $(1+\epsilon_{0})^{\gamma}$ multiplicative factor.
Since each edge has its cut value initialized to $\frac{1}{m^{O(1)}}$ it
follows that the total number of computed shortest path blockers that blame
$e$ is at most $\tilde{O}(1)$ and since each such shortest path blocker blames
$e$ at most $O\left(\frac{\log N}{\gamma}\right)$ times it follows that the
total number of paths in the support of all shortest path blockers computed by
Algorithm 1 and therefore in the support of $F$ is
$\mathrm{supp}(F)\leq\tilde{O}\left(\frac{1}{\gamma}\cdot|E|\right)$. ∎

Algorithm 1 Multi-Commodity Length-Constrained Flows and Moving Cuts

Input: graph $G=(V,E)$ with lengths $\ell$, capacities $U$, length constraint
$h$ and $\kappa$-batchable source, sink pairs $\\{(S_{i},T_{i})\\}_{i}$ where
$S_{i},T_{i}\subseteq V$ for every $i$ and an $\epsilon\in(0,1)$.

Output: $(1\pm\epsilon)$-approximate $h$-length multi-commodity flow $F$ and
moving cut $C$.

Let $\epsilon_{0}=\frac{\epsilon}{6}$, let
$\zeta=\frac{1+2\epsilon_{0}}{\epsilon_{0}}+1$ and let
$\eta=\frac{\epsilon_{0}}{(1+\epsilon_{0})\cdot\zeta}\cdot\frac{1}{\log m}$.

Initialize $C(e)\leftarrow\left(\frac{1}{m}\right)^{\zeta}$ for all $e\in E$.

Initialize $\lambda\leftarrow\left(\frac{1}{m}\right)^{\zeta}$.

Initialize $F(P)\leftarrow 0$ for every path $P$.

while $\lambda<1$ do:

for $j\in[\kappa]$ and each batch $(\mathcal{S}_{j},\mathcal{T}_{j})$ do

for each $(S_{i},T_{i})$ with $S_{i}\in\mathcal{S}_{j}$ and
$T_{i}\in\mathcal{T}_{j}$ in parallel do

for $\Theta\left(\frac{h\log_{1+\epsilon_{0}}n}{\epsilon_{0}}\right)$
repetitions do

Compute any $S_{i}$-$T_{i}$ $h$-length $(1+\epsilon_{0})$-lightest path
blocker $\hat{F}$.

Length-Constrained Flow (Primal) Update: $F\leftarrow F+\eta\cdot\hat{F}$.

Moving Cut (Dual) Update:
$C(e)\leftarrow(1+\epsilon_{0})^{\hat{F}(e)/U_{e}}\cdot C(e)$ for every $e\in
E$.

$\lambda\leftarrow(1+\epsilon_{0})\cdot\lambda$

return $(F,C)$.

We conclude with our sparse flow and cutmatch algorithms. See 1.3

###### Proof.

The proof is immediate from combining 12.2, Lemma 12.9 and 12.3. ∎

[HHS23] showed how to compute cutmatches using flow algorithms. Combining our
sparse flows (1.3) with the cutmatch algorithms of [HHS23] (which just call
batchable multicommodity length-constrained flow, cut algorithms as a
blackbox) immediately gives our sparse cutmatches as described in Theorem
12.3.

##  13 Algorithm: Demand-Size-Large Sparse Cuts from EDs

In the previous section we developed the theory of length-constrained expander
decompositions. We now put this theory to use by giving new algorithms for
length-constrained expander decompositions. Our algorithms will make use of a
well-studied “spiral” paradigm from the classic setting where we compute a
length-constrained expander decomposition by repeatedly computing large sparse
cuts [SW19]. In particular, we will show that one can compute expander
decompositions from large length-constrained sparse cuts (Lemma 14.1) which
one can compute from expander decompositions (13.4) and so on. In order to
prevent this argument from becoming circular we argue that it “spirals” in
that the expander decompositions we must compute get smaller and smaller each
time we go around the circle of dependencies.

In this section we show how to compute large length-constrained sparse cuts
using length-constrained expander decompositions.

The following is our notion of size which is analogous to the volume of a cut
in the non-length-constrained setting.

######  Definition 13.1 ($(h,s)$-Separated Demand-Size).

Given length-constrained cut $C$ and node-weighting $A$, we define the
$(h,s)$-length demand-size of $C$ with respect to $A$ as the size of the
largest $A$-respecting $h$-length demand which is $(hs)$-separated by $C$. We
denote this “demand-size” by $A_{(h,s)}(C)$.

######  Definition 13.2 (Demand-Size Largest Sparse Cut, LDSC).

We call the $(h,s)$-length $\phi$-sparse cut $C$ the demand-size largest
$(h,s)$-length $\phi$-sparse cut for node-weighting $A$ if it its demand-size
is maximum among all $(h,s)$-length $\phi$-sparse cuts. We notate the size of
this cut as

$\displaystyle\text{LDSC}(\phi,h,s):=A_{(h,s)}(C)$

######  Definition 13.3 (Approximately Demand-Size-Largest Sparse Length-
Constrained Cut).

Length-constrained cut $C$ is an $\alpha$-approximate demand-size-largest
$(\leq h,s)$-length $\phi$-sparse cut for node-weighting $A$ with length
approximation $\alpha_{s}$ and sparsity approximation $\alpha_{\phi}$ if it is
an $(h^{\prime\prime},s)$-length $\phi$-sparse cut for some
$h^{\prime\prime}\leq\alpha_{s}\cdot h$ and for all $h^{\prime}\leq
h/\alpha_{s}$ we have

$\displaystyle
A_{(h^{\prime\prime},s)}(C)\geq\frac{1}{\alpha}\cdot\text{LDSC}(\phi/\alpha_{\phi},h^{\prime},s\cdot\alpha_{s}).$

For the below result, recall the definition of a length-constrained expansion
witness (Definition 5.33).

######  Lemma 13.4.

For any parameter $\epsilon>0$, there exists an algorithm that, given a graph
$G$ on $n$ vertices and $m$ edges, a node weighting $A$, a length bound and
slack $h$ and $s$, a recursion size parameter $L$, and a conductance parameter
$\phi$, computes a $\alpha$-approximate demand-size-largest $(\leq
h,s)$-length $\phi$-sparse cut with sparsity approximation $\alpha_{\phi}$ and
length slack approximation $\alpha_{s}$ with respect to $A$ where

$\displaystyle\alpha=\frac{\tilde{O}(N^{O(\epsilon)})}{\epsilon^{3}}\qquad\qquad\alpha_{\phi}=\frac{s^{3}N^{O(1/s)}}{\epsilon}\qquad\qquad\alpha_{s}=\max\left(2,\frac{1}{\epsilon^{2}}\cdot(s)^{1+O(1/\epsilon)}\right)$

with work

$\displaystyle\textnormal{{W}}_{\textnormal{sparse-cut}}(A,m)\leq
m\cdot\tilde{O}\left(\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}\cdot
N^{O(\epsilon)}+\frac{1}{\epsilon}\cdot L\cdot
N^{O(\epsilon)}\cdot\operatorname{poly}(h)\right)+\frac{\tilde{O}(1)}{\operatorname{poly}(\epsilon)}\sum_{i}\textnormal{{W}}_{\textnormal{ED}}(A_{i},m_{i})$

and depth

$\displaystyle\textnormal{{D}}_{\textnormal{sparse-
cut}}(A,m)\leq\tilde{O}\left(\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}\cdot
N^{O(\epsilon)}+\frac{1}{\epsilon}\cdot L\cdot
N^{O(\epsilon)}\cdot\operatorname{poly}(h)\right)+\frac{\tilde{O}(1)}{\operatorname{poly}(\epsilon)}\max_{i}\textnormal{{D}}_{\textnormal{ED}}(A_{i},m_{i})$

where $\textnormal{{W}}_{\textnormal{ED}}(A_{i},m_{i})$ and
$\textnormal{{D}}_{\textnormal{ED}}(A_{i},m_{i})$ are the work and depth to
compute an $(h,2^{1/\epsilon})$-length $\phi$-expander decomposition with cut
slack $N^{\operatorname{poly}(\epsilon)}$ for node-weighting $A_{i}$ in an
$m_{i}$-edge graph and for all $i$ each $A_{i}\preceq A$ and
$|A_{i}|\leq\frac{|A|}{L}$ and $\\{m_{i}\\}_{i}$ are non-negative integers
satisfying

$\displaystyle\sum_{i}m_{i}\leq\frac{1}{\epsilon}\cdot\tilde{O}(m+n^{1+O(\epsilon)}+L^{2}\cdot
N^{O(\epsilon)}).$

Furthermore, if the graph is $(\leq h\cdot\frac{1}{\epsilon}\cdot
s^{O(1/\epsilon)},s)$-length $\phi$-expanding then the algorithm also returns
a $(\leq h,s_{w})$-length $\phi_{w}$-expansion witness where
$s_{w}=\frac{1}{\epsilon^{2}}\cdot s^{O(1/\epsilon)}$ and
$\phi_{w}=\tilde{O}(\phi\epsilon/N^{O(\epsilon)})$.

Observe that applying our previous relations we can get a simple lower bound
on the demand-size of the largest-demand-size length-constrained sparse cut.

######  Lemma 13.5.

Given graph $G$ and node-weighting $A$ and parameters $h,s,\phi$, we have that

$\displaystyle\text{LDSC}(\phi,h,s)\leq\text{LEC}(\phi^{\prime},h^{\prime},s)$

where $\phi^{\prime}=\tilde{O}(\phi\cdot s^{3}\cdot N^{O(1/s)})$ and
$h^{\prime}=2h$.

###### Proof.

See Definition 11.1 for a definition of the relevant graph quantities below.
Let $C$ be the $(h,s)$-length $\phi$-sparse cut of largest demand-size.
Observe that $\text{LDSC}(\phi,h,s)\leq\frac{1}{\phi}\text{LWSC}(\phi,h,s)$
since we can use $C$ in the largest weighted sparse cut sequence and so
$\phi\cdot A_{(h,s)}(C)$ is a lower bound on $\text{LWSC}(\phi,h,s)$.
Continuing, by 11.2 we have

$\displaystyle\text{LWSC}(\phi,h,s)\leq\text{LC}(\phi^{\prime\prime},h^{\prime},s^{\prime})$

where $\phi^{\prime\prime}=\tilde{O}(\phi\cdot s^{3}\cdot N^{O(1/s)})$,
$h^{\prime}=2h$ and $s^{\prime}=(s-2)/2$. Lastly, by 11.3 we have

$\displaystyle\text{LC}(\phi^{\prime\prime},h^{\prime},s^{\prime})\leq\text{LEC}(3\phi^{\prime\prime},h^{\prime},s^{\prime}).$

Combining the above and observing that
$\text{LEC}(3\phi^{\prime\prime},h^{\prime},s^{\prime})\leq\text{LEC}(3\phi^{\prime\prime},h^{\prime},s)$
gives the lemma. ∎

We will use the above lower bound to argue that our algorithm returns an
approximately demand-size largest sparse cut as described below.

###  13.1 (Preliminary) Algorithm: Cut Strategies from Expander Decompositions

We describe the cut matching games and describing prior work on computing
expander decompositions from cut strategies. The cut-matching game was first
proposed and studied in [KKOV07, KRV09], and later on it has found a wide
range of applications in graph algorithms. We use a slightly generalized
version of it as follows.

##### Cut Strategies.

A cut strategy is an algorithm which given a graph $G$ and node-weighting $A$
produces a set of node-weightings $\\{(A^{(j)},B^{(j)})\\}_{j}$ where for each
$j$ we have $A^{(j)}+B^{(j)}\preccurlyeq A$ and $|A^{(j)}|=|B^{(j)}|$ and
$A\preceq\sum_{j}A^{(j)}+B^{(j)}$.

##### Matching Strategies.

A matching strategy is an algorithm which given a graph $G$ and the node-
weighting pairs $\\{(A^{(j)},B^{(j)})\\}_{j}$ produced by a cut player outputs
a set of edges
$M^{(j)}\subseteq\mathrm{supp}(A^{(j)})\times\mathrm{supp}(B^{(j)})$ for each
$j$ between the vertices in the support of $A^{(j)}$ and $B^{(j)}$ and
capacities $U$ subject to the constraint that for every vertex $u$ we have
$U(\delta_{M^{(j)}}(u))\leq A^{(j)}(u),B^{(j)}(u)$.

##### Cut Matching Games.

A cut matching game is a procedure for using cut and matching strategies to
produce good routers by a sequence of interactions between cut and matching
strategies. Namely, given a set of vertices $V$ and a node-weighting $A$ on
$V$, it produces a series of graphs $G_{0},\dots,G_{r}$ where
$G_{0}=(V,\emptyset)$ is the empty graph and we call $G_{r}$ the output of the
cut matching game. The graph $G_{i}$ is $G_{i-1}$ plus the output of the
matching player when given the output of the cut player when given $G_{i-1}$.
That is, if $\\{(A^{(j)}_{i},B^{(j)}_{i})\\}_{j}$ is the output of the cut
player when given $G_{i-1}=(V,E_{i-1})$ and $\\{M^{(j)}_{i}\\}_{j}$ is the
output of the matching player when given
$\\{(A^{(j)}_{i},B^{(j)}_{i})\\}_{j}$, then
$G_{i}=(V,E_{i-1}\cup\bigcup_{j}M_{i}^{(j)})$.

We will be interested in the following parameters of a cut matching game.

  * •

Rounds of Interaction: We call $r$ the number of rounds of interaction.

  * •

Cut Batch Size: We call the maximum number of pairs the cut strategy plays in
each round of interaction $\max_{i}|\\{(A_{i}^{(j)},B_{i}^{(j)})\\}_{j}|$ the
cut batch size of the cut matching game. In typical cut matching games
[KKOV07, KRV09] the cut batch size is $1$; we will be interested in
potentially larger batch sizes.

  * •

Matching Perfectness: If each set of edges the matching player plays for a
batch always has total capacity at least a $1-\alpha$ fraction of the total
node-weighting then we say that the cut matching game is $(1-\alpha)$-perfect.
That is, a cut matching game is $(1-\alpha)$-perfect if for every $i$ we have

$\displaystyle\sum_{j}U\left(M_{i}^{(j)}\right)\geq(1-\alpha)\cdot\sum_{j}|A_{i}^{(j)}|=(1-\alpha)\cdot\sum_{j}|B_{i}^{(j)}|.$

We use the following result from [HHG22] which shows both the existence of
high quality cut matching games and how to compute them assuming we can
compute length-constrained expander decompositions.

######  Theorem 13.6 ([HHG22]).

For every $\epsilon>0$ there is a cut strategy with cut batch size
$N^{O(\epsilon)}$ which when used in a cut matching game with $1/\epsilon$
rounds of interaction against any $(1-\alpha)$-perfect matching strategy
results in a $G_{r}$ that is a $1/\epsilon$-step and
$N^{O(\epsilon)}$-congestion router for some $A^{\prime}\preceq A$ of size
$|A^{\prime}|\geq(1-O(\frac{\alpha}{\epsilon}))\cdot|A|$.

This cut-strategy on a node-weighting $A$ in a graph with $m$ edges can be
computed in work

$\displaystyle\textnormal{{W}}_{\textnormal{cut-
strat}}(A,m)\leq\frac{\tilde{O}(1)}{\operatorname{poly}(\epsilon)}\cdot\textnormal{{W}}_{\textnormal{ED}}(A,m)$

and depth

$\displaystyle\textnormal{{D}}_{\textnormal{cut-
strat}}(A,m)\leq\frac{\tilde{O}(1)}{\operatorname{poly}(\epsilon)}\cdot\textnormal{{D}}_{\textnormal{ED}}(A,m)$

where $\textnormal{{W}}_{\textnormal{ED}}(A,m)$ and
$\textnormal{{D}}_{\textnormal{ED}}$ are the work and depth respectively for
computing an $(h,2^{1/\epsilon})$-length $\phi$-expander decomposition with
cut slack $N^{\operatorname{poly}(\epsilon)}$ for node-weighting $A$ in an
$m$-edge graph. Likewise, $A^{\prime}$ can be computed in the same work and
depth and is vertex induced: i.e. for each vertex $u$ if $A^{\prime}(u)\neq 0$
then $A^{\prime}(u)=A(u)$.

###  13.2 Algorithm: Demand-Size-Large Sparse Cuts from Cut Strategies

The following is our main result for this section and shows how to compute
large sparse length-constrained cuts using cut strategies. Below, we let
$\textnormal{{W}}_{\textnormal{cut-strat}}$ and
$\textnormal{{D}}_{\textnormal{cut-strat}}$ give the work and depth to compute
the cut strategy given by Theorem 13.6.

######  Theorem 13.7.

For any parameter $\epsilon>0$, there exists an algorithm that, given a graph
$G$ on $n$ vertices and $m$ edges, a node weighting $A$, a length bound and
slack $h$ and $s$, a recursion size parameter $L$, and a conductance parameter
$\phi$, computes a $\alpha$-approximate demand-size-largest $(\leq
h,s)$-length $\phi$-sparse cut with sparsity approximation $\alpha_{\phi}$ and
length slack approximation $\alpha_{s}$ with respect to $A$ where

$\displaystyle\alpha=\frac{\tilde{O}(N^{O(\epsilon)})}{\epsilon^{3}}\qquad\qquad\alpha_{\phi}=\frac{s^{3}N^{O(1/s)}}{\epsilon}\qquad\qquad\alpha_{s}=\max\left(2,\frac{1}{\epsilon^{2}}\cdot(s)^{1+O(1/\epsilon)}\right)$

with work

$\displaystyle\textnormal{{W}}_{\textnormal{sparse-cut}}(A,m)\leq
m\cdot\tilde{O}\left(\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}\cdot
N^{O(\epsilon)}+\frac{1}{\epsilon}\cdot L\cdot
N^{O(\epsilon)}\cdot\operatorname{poly}(h)\right)+\frac{1}{\epsilon}\sum_{i}\textnormal{{W}}_{\textnormal{cut-
strat}}(A_{i},m_{i})$

and depth

$\displaystyle\textnormal{{D}}_{\textnormal{sparse-
cut}}(A,m)\leq\tilde{O}\left(\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}\cdot
N^{O(\epsilon)}+\frac{1}{\epsilon}\cdot L\cdot
N^{O(\epsilon)}\cdot\operatorname{poly}(h)\right)+\frac{1}{\epsilon}\max_{i}\textnormal{{D}}_{\textnormal{cut-
strat}}(A_{i},m_{i})$

where for all $i$ each $A_{i}\preceq A$ and $|A_{i}|\leq\frac{|A|}{L}$ and
$\\{m_{i}\\}_{i}$ are non-negative integers satisfying

$\displaystyle\sum_{i}m_{i}\leq\frac{1}{\epsilon}\cdot\tilde{O}(m+n^{1+O(\epsilon)}+L^{2}\cdot
N^{O(\epsilon)}).$

and $\textnormal{{W}}_{\textnormal{cut-strat}}$ and
$\textnormal{{D}}_{\textnormal{cut-strat}}$ are the work and depth to compute
the cut strategy described in Theorem 13.6 on an $m_{i}$-edge graph for node-
weighting $A_{i}$. Furthermore, if the graph is $(\leq
h\cdot\frac{1}{\epsilon}\cdot s^{O(1/\epsilon)},s)$-length $\phi$-expanding
then the algorithm also returns a $(\leq h,s_{w})$-length $\phi_{w}$-expansion
witness where $s_{w}=\frac{1}{\epsilon^{2}}\cdot s^{O(1/\epsilon)}$ and
$\phi_{w}=\tilde{O}(\phi\epsilon/N^{O(\epsilon)})$.

Having shown in the previous section how to compute sparse cutmatches, we now
use these cutmatches to compute large length-constrained cuts using the cut
strategies from cut matching games. That is, we prove Theorem 13.7.

We begin by describing the algorithm for Theorem 13.7.

##### Step 1: Create Clusters for Cut Matching Games.

We do the following for each $h^{\prime}\leq h$ which is a power of $2$.
First, apply Theorem 5.32 to $G$ to compute a neighborhood cover
${\mathcal{N}}_{h^{\prime}}$ with covering radius $h_{cov}=h^{\prime}$,
separation factor $2s$, cluster diameter
$h_{\mathrm{diam}}=\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}\cdot h^{\prime}$
and width $\omega=N^{O(\epsilon)}\log N$.

Modify ${\mathcal{N}}_{h^{\prime}}$ as follows. Since we would like to only
run our cut strategy on clusters whose node-weightings are a small fraction of
the total size of $A$, we must further break up the node-weighting in each
cluster in our neighborhood cover. Specifically, for each cluster
$S\in{\mathcal{N}}$ we let $A_{S}$ be the restriction of node-weighting $A$ on
$S$ (i.e. $A_{S}(u)$ is $A(u)$ if $u\in S$ and $0$ otherwise). Then if
$|A_{S}|\leq|A|/L$ we do nothing. However, if $|A_{S}|>|A|/L$ then we break
$A_{S}$ into sub-node-weightings $A_{S}^{(1)},A_{S}^{(2)},\ldots,A_{S}^{(L)}$
so that $\sum_{i}A_{S}^{(i)}=A$ where each of these has equal size and size at
most $|A|/L$. We remove $S$ from ${\mathcal{N}}_{h^{\prime}}$ and add a copy
of $S$ for each of $A_{S}^{(1)},A_{S}^{(2)},\ldots$ to
$\mathcal{N}_{h^{\prime}}$. If we don’t break up $A_{S}$ then we say that
$A_{S}$ corresponds to cluster $S$; if we do then we say that each of
$A_{S}^{(1)},A_{S}^{(2)},\ldots$ correspond to each respective copy of $S$.
For ease of notation, if we do not break up $A_{S}$ then we let
$A_{S}^{(1)}:=A_{S}$.

Observe that (by e.g. iterating over vertices and greedily constructing
$A^{(i)}_{S}$), we can ensure that the total support size across the node-
weightings of all clusters of $\mathcal{N}[h^{\prime}]$ is

$\displaystyle\sum_{S\in\mathcal{N}_{h^{\prime}}}\sum_{i}|\mathrm{supp}(A_{S}^{(i)})|\leq\omega\cdot(n+L^{2})\leq\tilde{O}(n^{1+O(\epsilon)}+N^{O(\epsilon)}L^{2}).$
(23)

We let $\mathcal{N}$ be the union of all clusters of all
$\mathcal{N}_{h^{\prime}}$. We next partition $\mathcal{N}$ on the basis of
cluster diameter. Specifically, for
$h^{\prime\prime}\leq\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}\cdot h$ which
is a power of $2$, we let $\mathcal{N}[h^{\prime\prime}]$ be all clusters of
$\mathcal{N}$ whose diameter is in $(h^{\prime\prime}/2,h^{\prime\prime}]$.
Observe that clusters of $\mathcal{N}[h^{\prime\prime}]$ have diameter at most
$h^{\prime\prime}$ but may contain clusters in
$\mathcal{N}_{h^{\prime\prime\prime}}$ for
$h^{\prime\prime\prime}>h^{\prime\prime}$ since
$\mathcal{N}_{h^{\prime\prime\prime}}$ may contain clusters with diameter much
smaller than $h^{\prime\prime\prime}$. For each
$S\in\mathcal{N}[h^{\prime\prime}]$, we let $S^{+}$ be all nodes within
distance $s\cdot h^{\prime\prime}$ of some vertex in $S$.

##### Step 2: Run Cut Matching Games.

First, let

$\displaystyle\phi^{\prime}:=\phi/\tilde{O}\left(N^{O(\epsilon)}\right)$ (24)

be the (relaxed) sparsity with respect to which we will run compute our
cutmatches.

Next, we do the following for each $h^{\prime\prime}\leq
h\cdot\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}$ which is a power of $2$.
More or less, we simultaneously implement a cut matching game for the node-
weightings corresponding to clusters in $\mathcal{N}[h^{\prime\prime}]$. For
each $S\in\mathcal{N}[h^{\prime\prime}]$ with corresponding node-weightings
$A_{S}^{(1)},A_{S}^{(2)},\ldots$, we initialize graph $G_{Si}=(S,\emptyset)$
to the empty graph. Then, repeat the following $1/\epsilon$ times.

  1. 1.

Run Cut Strategies: For each $S\in\mathcal{N}[h^{\prime\prime}]$ and each
node-weighting $A_{S}^{(i)}$ corresponding to $S$, apply the the cut strategy
(from Theorem 13.6) to $G_{Si}$. Let $\\{(A_{Si,k},B_{Si,k})\\}_{k}$ be the
output pairs of node-weightings from the cut strategy for cluster $S$.

  2. 2.

Compute a Cutmatch: For all pairs $\\{(A_{Si,k},B_{Si,k})\\}_{S,i,k}$ just
computed, compute a $(h^{\prime\prime}\cdot s)$-length $\phi^{\prime}$-sparse
cutmatch $(F,C)$ of congestion $\tilde{O}(1/\phi^{\prime})$ by invoking
Theorem 12.3 (we will reason about the batch size in our analysis). We let
$F=\sum_{S,i,k}F_{Si,k}$ be the relevant decomposition of this flow.

  3. 3.

Update Graphs: For each pair $(A_{Si,k},B_{Si,k})$, with corresponding flow
$F_{Si,k}$, let $E_{Si,k}$ be the edge set which for each path $P$ in the
support of $F_{Si,k}$ with flow value $F_{Si,k}(P)$ from node $u$ to node $v$
has an edge from $u$ to $v$ of capacity $F_{Si,k}(P)$. Add to $G_{Si}$ the
edge set $\bigcup_{k}E_{Si,k}$.

##### Step 3: Glue Broken Up Clusters.

Lastly, we glue together our broken-up clusters. Specifically, we again do the
following for each $h^{\prime\prime}\leq
h\cdot\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}$ which is a power of $2$. Let
$S$ be a cluster we broke up with diameter in
$(h^{\prime\prime}/2,h^{\prime\prime}]$ whose node-weighting we broke up into
$A_{S}^{(1)},A_{S}^{(2)},\ldots$. Let $\\{A_{S}^{(i)},A_{S}^{(j)}\\}_{i\neq
j}$ be all relevant pairs for this cluster and let
$\\{A_{S}^{(i)},A_{S}^{(j)}\\}_{i\neq j,S}$ be all pairs across all clusters
whose node-weightings we broke up; here, $S$ ranges over all clusters whose
node-weightings we broke up. Then, we compute a $(\phi^{\prime}/L)$-sparse
$h^{\prime\prime}s$-length cutmatch $(F,C)$ of congestion
$\tilde{O}(L/\phi^{\prime})$ on the pairs
$\\{A_{S}^{(i)},A_{S}^{(j)}\\}_{i\neq j,S}$ by invoking Theorem 12.3; here,
the $S$ in these pairs again ranges over all clusters whose node-weightings we
broke up.

##### Algorithm Output.

We return as our cut $C^{*}$ (and corresponding length $h^{\prime\prime}\leq
h\cdot\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}$) the largest cut (by demand-
size) of any cutmatch we computed above in step 2 or step 3 (among all $O(\log
N/\epsilon)$ cutmatches). If the size of $C^{*}$ is $0$ then we return as our
$(\leq h,s_{w})$-length $\phi_{w}$-expansion witness the neighborhood covers
$\\{\mathcal{N}_{h^{\prime}}\\}_{h^{\prime}}$, the roouter for cluster $S$
gotten by taking the union of the routers computed for
$A_{S}^{(1)},A_{S}^{(2)},\ldots$ from step 2 and the matchings corresponding
to step 3 and the embedding given by all flows we compute for our cutmatches
in step 2 and step 3. Recall that $s_{w}=\frac{1}{\epsilon^{2}}\cdot
s^{O(1/\epsilon)}$ and $\phi_{w}=\tilde{O}(\phi\epsilon/N^{O(\epsilon)})$.

We conclude with our proof of Theorem 13.7.

See 13.7

###### Proof.

We use the algorithm described directly above.

##### Runtime Analysis.

We begin by analyzing the runtime of the above algorithm. We begin with step 1
wherein we build our neighborhood covers. Since $\mathrm{diam}(S)\leq
h\cdot\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}$, by Theorem 5.32 we can
compute each of our $O(\log h)\leq O(\log N)$-many neighborhood covers which
form $\mathcal{N}$ in work at most

$\displaystyle m\cdot\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}\cdot
N^{O(\epsilon)}\cdot\log N$ (25)

and depth at most

$\displaystyle\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}\cdot
N^{O(\epsilon)}\cdot\log N$ (26)

Likewise, since each of the clusterings of each $\mathcal{N}_{h^{\prime}}$ are
disjoint and each $\mathcal{N}_{h^{\prime}}$ has width $N^{O(\epsilon)}\log
N$, we can break up all of our clusters in work at most

$\displaystyle m\cdot N^{O(\epsilon)}\log^{2}N.$ (27)

and depth at most

$\displaystyle N^{O(\epsilon)}\log^{2}N.$ (28)

Thus, combining Equations 25 and 27, the total work of step 1 is

$\displaystyle
m\cdot\tilde{O}\left(\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}\cdot
N^{O(\epsilon)}\right)$ (29)

and the total depth of step 1 is

$\displaystyle\tilde{O}\left(\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}\cdot
N^{O(\epsilon)}\right)$ (30)

We now discuss step 2. We first discuss how we compute our cutmatches in step
2. Towards this, we first discuss the batch sizes used when invoking Theorem
12.3 for a given $h^{\prime}$ in a given one of the $1/\epsilon$-many
iterations. First, observe that for a given $S\in\mathcal{N}[h^{\prime}]$, we
have that $\\{(A_{Si,k},B_{Si,k})\\}_{i,k}$ is $N^{O(\epsilon)}$-batchable
since, by Theorem 13.6, the batch size of our cut strategy is
$N^{O(\epsilon)}$. Furthermore, since $\mathcal{N}_{h^{\prime}}$ has width
$N^{O(\epsilon)}\log N$ before we break up clusters and since we duplicate a
given cluster at most $L$-many times when breaking up clusters, it follows
that each $\mathcal{N}[h^{\prime}]$ is $N^{O(\epsilon)}L\log^{2}N$-batchable.
Thus, we therefore have that $\\{(A_{Si,k},B_{Si,k})\\}_{Si,k}$ is
$\tilde{O}(L\cdot N^{O(\epsilon)})$-batchable.

It follows by Theorem 12.3 that in one iteration of step 2, we can compute all
of our cutmatches for all clusters in $\mathcal{N}[h^{\prime}]$ in work

$\displaystyle m\cdot\tilde{O}\left(L\cdot
N^{O(\epsilon)}\cdot\operatorname{poly}(h)\right)$

and depth at most

$\displaystyle\tilde{O}\left(L\cdot
N^{O(\epsilon)}\cdot\operatorname{poly}(h)\right)$

and so we can compute our cutmatches for all clusters in $\mathcal{N}$ across
all $1/\epsilon$ iterations in work at most

$\displaystyle m\cdot\tilde{O}\left(\frac{1}{\epsilon}\cdot L\cdot
N^{O(\epsilon)}\cdot\operatorname{poly}(h)\right).$ (31)

and depth at most

$\displaystyle\tilde{O}\left(\frac{1}{\epsilon}\cdot L\cdot
N^{O(\epsilon)}\cdot\operatorname{poly}(h)\right).$ (32)

Next, we analyze the time to compute our cut strategy cuts in step 2. To do
so, we first bound the total number of edges across all $G_{S}$. Specifically,
observe that since we have constructed our clusters so that if $A_{S}^{(i)}$
is a node-weighting corresponding to cluster $S\in\mathcal{N}[h^{\prime}]$,
then we have
$\sum_{S\in\mathcal{N}[h^{\prime}],i}\mathrm{supp}(A_{S}^{(i)})\leq\tilde{O}(n^{1+O(\epsilon)}+N^{O(\epsilon)}L^{2})$
(see Equation 23). Furthermore, since in step 2 the pairs
$\\{(A_{Si,k},B_{Si,k})\\}_{k}$ for fixed cluster $S$ and $i$ are
$N^{O(\epsilon)}$-batchable (by Theorem 13.6), it follows that for a fixed
$S\in\mathcal{N}[h^{\prime}]$ and fixed $i$ we have

$\displaystyle\sum_{k}|\mathrm{supp}(A_{Si,k}\cup B_{Si,k}))|\leq
N^{O(\epsilon)}\cdot\mathrm{supp}(A_{S}^{(i)})$

and so

$\displaystyle\sum_{S,i}\sum_{k}|\mathrm{supp}(A_{Si,k}\cup
B_{Si,k})|\leq\sum_{S,i}N^{O(\epsilon)}\cdot\mathrm{supp}(A_{S}^{(i)})\leq\tilde{O}(n^{1+O(\epsilon)}+N^{O(\epsilon)}L^{2})$

Thus, plugging this bound on $\sum_{S,i,k}|\mathrm{supp}(A_{Si,k}\cup
B_{Si,k})|$ into the guarantees of Theorem 12.3 and the fact that our pairs
are $L\cdot N^{O(\epsilon)}$-batchable, we have that each time we compute a
cutmatch in step 2, the total number of edges we add across all $G_{S}$ for
$S\in\mathcal{N}[h^{\prime}]$ for a fixed $h^{\prime}$ is at most

$\displaystyle\tilde{O}(m+L\cdot
N^{O(\epsilon)}+n^{1+O(\epsilon)}+N^{O(\epsilon)}L)=\tilde{O}(m+n^{1+O(\epsilon)}+L^{2}\cdot
N^{O(\epsilon)}).$

Since we have $1/\epsilon$ iterations, it follows that the number of edges
across all $G_{S}$ for $S\in\mathcal{N}[h^{\prime}]$ is never more than

$\displaystyle\frac{1}{\epsilon}\cdot\tilde{O}(m+n^{1+O(\epsilon)}+L^{2}\cdot
N^{O(\epsilon)}).$

It follows that the work and depth to compute all cut strategies for all
$S\in\mathcal{N}[h^{\prime}]$ for all $1/\epsilon$-many iterations and all
$h^{\prime}\leq h\cdot\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}$ a power of
$2$ in step 2 are respectively

$\displaystyle\frac{1}{\epsilon}\cdot\sum_{i}\textnormal{{W}}_{\textnormal{cut-
strat}}(A_{i},m_{i})$ (33)

and

$\displaystyle\frac{1}{\epsilon}\cdot\max_{i}\textnormal{{D}}_{\textnormal{cut-
strat}}(A_{i},m_{i})$ (34)

where $|A_{i}|\leq|A|/L$ for all $i$ and
$\sum_{i}m_{i}\leq\tilde{O}(m+n^{1+O(\epsilon)}+L^{2}\cdot N^{O(\epsilon)})$.

Combining the work and depth to compute cutmatches (work Equation 31 and depth
Equation 32) and cut strategies (work Equation 33 and depth Equation 34) in
step 2, we have that the $1/\epsilon$-many iterations of step 2 for all
$h^{\prime}\leq h\cdot\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}$ a power of
$2$ can be implemented in work

$m\cdot\tilde{O}\left(\frac{1}{\epsilon}\cdot L\cdot
N^{O(\epsilon)}\cdot\operatorname{poly}(h)\right)+\frac{1}{\epsilon}\cdot\sum_{i}\textnormal{{W}}_{\textnormal{cut-
strat}}(A_{i},m_{i})$ (35)

and depth

$\tilde{O}\left(\frac{1}{\epsilon}\cdot L\cdot
N^{O(\epsilon)}\cdot\operatorname{poly}(h)\right)+\frac{1}{\epsilon}\cdot\max_{i}\textnormal{{D}}_{\textnormal{cut-
strat}}(A_{i},m_{i})$ (36)

where $|A_{i}|\leq|A|/L$ for all $i$ and
$\sum_{i}m_{i}\leq\frac{1}{\epsilon}\cdot\tilde{O}(m+n^{1+O(\epsilon)}+L^{2}\cdot
N^{O(\epsilon)})$.

Lastly, we analyze the runtime of step 3. Since each $\mathcal{N}[h^{\prime}]$
is $\tilde{O}(L\cdot N^{O(\epsilon)})$-batchable and by definition of how we
broke up clusters, we have that all pairs
$\\{A_{S}^{(i)},A_{S}^{(j)}\\}_{i\neq j,S}$ in step 3 are $\tilde{O}(L\cdot
N^{O(\epsilon)})$-batchable. Thus, applying Theorem 12.3, we have that all
cumatches of step 3 can be computed in work

$\displaystyle m\cdot\tilde{O}\left(L\cdot
N^{O(\epsilon)}\cdot\operatorname{poly}(h)\right).$ (37)

and depth

$\displaystyle\tilde{O}\left(L\cdot
N^{O(\epsilon)}\cdot\operatorname{poly}(h)\right).$ (38)

The work and depth of our algorithm then follows by combining the running time
of

  * •

step 1 work (Equation 29) and depth (Equation 30)

  * •

step 2 work (Equation 35) and depth (Equation 36)

  * •

step 3 work (Equation 37) and depth (Equation 38).

Correctness Analysis: Upper Bound on Largest Sparse Cut Size. The basic idea
will be to argue that most vertices are successfully “embedded” which in turn
gives us a large expanding subset which will allow us to upper bound the
demand-size of the largest sparse cut by Lemma 13.5. Fix an
$h^{\prime\prime}\leq h\cdot\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}$. We
fix a suitably large constant $c\in(0,1)$.

Cut Matching Game Success. Consider a node-weighting $A_{S}^{(i)}$ with
corresponding cluster $S\in\mathcal{N}[h^{\prime\prime}]$. Let $B_{S}^{(i)}$
be the (expanding) node-weighting returned by our cut matching game in step 2
as described by Theorem 13.6. We say that a vertex $u$ succeeded for the cut
matching game for $A_{S}^{(i)}$ if $B_{S}^{(i)}(u)=A_{S}^{(i)}(u)$. We say
that $A_{S}^{(i)}$ succeeded for the cut matching game if $|B_{S}^{(i)}|\geq
c\cdot|A_{S}^{(i)}|$. If $S$ is a cluster whose node-weighting we didn’t break
up then we say that $S$ succeeded for its cut matching games if $A_{S}^{(1)}$
succeeded. If $S$ is a cluster whose node-weighting we broke up into
$A_{S}^{(1)},A_{S}^{(2)},\ldots$ then we say that $S$ succeeded for its cut
matching games if at least a $c$ fraction of the cut matching games of
$A_{S}^{(1)},A_{S}^{(2)},\ldots$ succeeded. We say that a vertex $u$ succeeds
for the cut matching games of $S$ if $\sum_{i}B_{S}^{(i)}(u)\geq c\cdot
A_{S}(u)$.

Cutmatching Success. Next, suppose $S\in\mathcal{N}[h^{\prime\prime}]$ is a
cluster whose node-weighting $A_{S}$ we broke up into
$A_{S}^{(1)},A_{S}^{(2)},\ldots$ so that for each $i$ and $j$ the pair
$(A_{S}^{(i)},A_{S}^{(j)})$ is a pair for our cutmatching in step 3. We let
$F_{Sij}$ be the flow returned for the pair $(A_{S}^{(i)},A_{S}^{(j)})$ of the
cutmatching returned in step 3. We say that the pair $(i,j)$ succeeded for the
cutmatching if $\mathrm{val}(F_{Sij})\geq c|A_{S}^{(i)}|=c|A_{S}^{(j)}|$.
Likewise, we say that the cutmatching succeeded for $A_{S}^{(i)}$ if, among
all $j$, at least a $c$ fraction of the $(i,j)$ succeeded for the cutmatching.
We let $I_{S}$ be the indices of all $A_{S}^{(i)}$ which succeeded for the
cutmatching. Lastly, we say that the cutmatching succeeded for $S$ if, among
all $i$, at least a $c$ fraction of $A_{S}^{(i)}$ succeeded for the cut
matching; i.e. $|I_{S}|\geq cL$.

Towards defining the node-weighting we will claim is length-constrained
expanding, we define the node-weighting $\hat{B}_{S}$ for each
$S\in\mathcal{N}[h^{\prime\prime}]$.

  * •

Specifically, for each cluster $S$ whose node-weighting we did not break up
and which succeeded for the cut matching game, we let
$\hat{B}_{S}:=B_{S}^{(1)}$.

  * •

If $S$ is a cluster whose node-weighting $A_{S}$ we broke up into
$A^{(1)}_{S},A^{(2)}_{S},\ldots$, which succeeded for both the cut matching
game and cutmatching and $V_{S}$ are the vertices which succeeded for the cut
matching games of $S$, then we let $\hat{B}_{S}$ be $A_{S}$ restricted to
$V_{S}$.

  * •

If $S$ did not succeed for both the cut matching game and cutmatching, then we
just let $\hat{B}_{S}$ be uniformly $0$.

We now argue that any demand $D$ that decomposes as $D=\sum_{S}D_{S}$ where
$D_{S}$ is $\hat{B}_{S}$-respecting can be efficiently routed; here, we sum
over clusters of $\mathcal{N}[h^{\prime\prime}]$ without multiplicity. To do
so we will first route within routers given by our cut matching game (from
step 2), then route across clusters using the cutmatches (from step 3) and
then again route according to our cut matching game (from step 2). We describe
this more formally below.

Routing Within Clusters. We first describe how to route what we call a _cut
matching game demand_. Let $A_{S}^{(i)}$ be a node-weighting whose cut
matching game succeeded and let $B_{S}^{(i)}$ be the corresponding expanding
node-weighting returned by the cut matching game. Likewise, let $D_{Si}$ be a
demand that is $B_{S}^{(i)}$-respecting. We call $D=\sum_{S,i}D_{Si}$ a cut
matching game demand. By the guarantees of Theorem 13.6 we know that the
result of our cut matching game on $S$ is a $1/\epsilon$-step and
$N^{O(\epsilon)}$-congestion router for $B_{S}^{(i)}$. Since each edge of the
output of our cut matching game for cluster $S$ corresponds to a path of
length $h^{\prime\prime}\cdot s$ in $G[S^{+}]$ and each of the $1/\epsilon$
cutmatches we compute has congestion $\tilde{O}(1/\phi^{\prime})$ by Theorem
12.3, it follows that $D$ can be routed over
$(h^{\prime\prime}s/\epsilon)$-length paths with congestion at most
$\tilde{O}(\frac{N^{O(\epsilon)}}{\phi^{\prime}\cdot\epsilon})$.

Routing Across Clusters. We next describe how to route what we call a
_cutmatching demand_ between indices. Specifically, consider any function $D$
that decomposes as $\sum_{S}D_{S}$ (where our sum is over clusters whose node-
weightings we broke up) such that for each $S$ we have:

  1. 1.

$(i,j)\in\mathrm{supp}(D_{S})$ only if $A_{S}^{(i)}$ and $A_{S}^{(j)}$
succeeded for the succeeded for the respective cut matching games and the
cutmatching for $S$ and;

  2. 2.

$\sum_{j}D_{S}(i,j)\leq|B_{S}^{(i)}|$ and
$\sum_{j}D_{S}(j,i)\leq|B_{S}^{(i)}|$ for every $i$.

Then, given any such $D$, we claim there is a $2h^{\prime\prime}s$-length flow
$\hat{F}=\sum_{S,i,j}\hat{F}_{Sij}$ with congestion
$\tilde{O}(1/\phi^{\prime})$ wherein each $\hat{F}_{Sij}$ routes $D_{S}(i,j)$
flow from $\mathrm{supp}(B_{S}^{(i)})$ to $\mathrm{supp}(B_{S}^{(j)})$ so that
no vertex $u$ sends or receives more than $B_{S}^{(i)}(u)$ and
$B_{S}^{(j)}(u)$ flow respectively according to $\hat{F}_{Sij}$.

To construct $\hat{F}$, first consider two pairs $(i,k)$ and $(k,j)$ that both
succeed for the cutmatching where both $A_{S}^{(i)}$ and $A_{S}^{(j)}$
succeeded for their cut matching game. Observe that, by definition of a pair
succeeding for the cutmatching, we know that $\mathrm{val}(F_{Sik})\geq
c|A_{S}^{(k)}|$ and $\mathrm{val}(F_{Skj})\geq c|A_{S}^{(k)}|$. Likewise, we
know that since both $A_{S}^{(i)}$ and $A_{S}^{(j)}$ succeeded for their cut
matching game it holds that $B_{S}^{(i)}\geq c|A_{S}^{(i)}|$ and
$B_{S}^{(j)}\geq c|A_{S}^{(j)}|$.

Thus, it follows by scaling and concatenating flow paths of $F_{Sik}$ and
$F_{Skj}$ that it is possible to construct a flow $\hat{F}_{Sikj}$ which, for
a fixed $S$, $i$ and $j$, is a $2h^{\prime\prime}s$-length flow that routes
$D_{S}(i,j)$ flow from $i$ to $j$ and incurs congestion on edge $e$ at most
$\sum_{S}\frac{D_{S}(i,j)}{|A_{S}^{(i)}|}\cdot O(F_{Sik}(e)+F_{Skj}(e))$.

Next, let $I_{Sij}$ be all $k$ such that the pair $(i,k)$ and the pair $(k,j)$
both succeeded for the cutmatching and $i$ and $j$ succeeded for the cut
matching game. Likewise, let

$\displaystyle\hat{F}_{Sij}:=\Theta(1)\sum_{k\in I_{Sij}}\hat{F}_{Sikj}/L$

for an appropriate hidden constant. Since $i$ and $j$ both succeeded for the
cutmatching we know that $|I_{Sij}|\geq\Omega(L)$ so this is a
$2h^{\prime\prime}s$-length flow that routes at least $D_{S}(i,j)$ from $i$ to
$j$ and on edge $e$ incurs congestion at most

$\displaystyle\frac{D_{S}(i,j)}{|A_{S}^{(i)}|}\sum_{k\in
I_{Sij}}O(F_{Sik}(e)+F_{Skj}(e))/L.$

Let

$\displaystyle\hat{F}:=\sum_{S}\sum_{i,j}\hat{F}_{Sij}.$

be all such flows pairs for all $S$, $i$ and $j$.

This $2h^{\prime\prime}s$-length flow routes, simultaneously for every $S$,
$i$ and $j$, $D_{S}(i,j)$ flow from $i$ to $j$ for cluster $S$ and on edge $e$
incurs congestion at most

$\displaystyle\sum_{S,i,j}\frac{D_{S}(i,j)}{|A_{S}^{(i)}|}\sum_{k\in
I_{ij}}\frac{O(F_{Sik}(e)+F_{Skj}(e))}{L}$
$\displaystyle=\sum_{S,i,k}\frac{O(F_{Sik}(e))}{L}\sum_{j}\frac{D_{S}(i,j)}{|A_{S}^{(i)}|}+\sum_{S,j,k}\frac{O(F_{Skj}(e))}{L}\sum_{i}\frac{D_{S}(i,j)}{|A_{S}^{(j)}|}$
$\displaystyle\leq\sum_{S,i,j}\frac{O(F_{Sij}(e))}{L}$
$\displaystyle=\frac{F(e)}{L}$
$\displaystyle\leq\tilde{O}\left(\frac{1}{\phi^{\prime}}\right)$

where, above, we use the fact that $F$ has congestion
$\tilde{O}(L/\phi^{\prime})$ as given in the definition of step 3.

Routing Across and Within Clusters. Next, we describe how to route an
arbitrary demand $D$ which decomposes as $D=\sum D_{S}$ where $D_{S}$ is
$\hat{B}_{S}$ respecting. First, a minor technical detail to deal with the
fact that a vertex can appear in multiple copies of a cluster: observe that
since $D_{S}$ is $\hat{B}_{S}$-respecting, it is possible to decompose $D_{S}$
into $D_{S}=\sum_{ij}D_{Sij}$ where for each $i$ we have $\sum_{j}D_{Sij}$ and
$\sum_{j}D_{Sji}$ are both $B_{S}^{(i)}$-respecting. Using this decomposition,
we construct our demand $D_{2}$ between indices. Namely, we let
$D_{S}^{\prime}$ for indices $i,j\in I_{S}$ be

$\displaystyle D^{\prime}_{S}(i,j):=\sum_{u,v}D_{Sij}(u,v)$

and let $D_{2}:=\sum_{S}D^{\prime}_{S}$.

First, observe that $D_{2}$ is a cutmatching demand by construction and so by
the above discussion can be routed over $2h^{\prime\prime}s$-length paths by a
flow $\hat{F}=\sum_{S,i,j}\hat{F}_{Sij}$ with congestion at most
$\tilde{O}(1/\phi^{\prime})$ where each node $u$ sends and receives at most
$\hat{B}_{S}^{(i)}(u)$ flow according to $\hat{F}_{Sij}$. For a given vertex
$u$, we let $w_{Sij}(u)$ be the amount of flow that $u$ sends according to
$\hat{F}_{Sij}$. We use these values to construct two cut matching game
demands $D_{1}$ and $D_{3}$ such that concatenating the routing paths of
$D_{1}$, $D_{2}$ and $D_{3}$ give a routing for $D$.

We first describe $D_{1}$. Let

$\displaystyle D_{Si}(u,j):=\sum_{v}D_{Sij}(u,v)$

be the amount of demand that vertex $u$ sends to $\hat{B}_{S}^{(j)}$ according
to $D_{S}$ according to the portion of $u$’s node-weighting that is in
$\hat{B}_{S}^{(i)}$. Next, consider the demand $\hat{D}_{Si}$ wherein vertex
$u$ sends each of its demands $D_{Si}(u,j)$ to each node $v$ proportional to
$w_{Sij}(v)$. Specifically, let

$\displaystyle\hat{D}_{Sij}(u,v):=D_{Si}(u,j)\cdot\frac{w_{Sij}(v)}{\mathrm{val}(\hat{F}_{Sij})}.$

and

$\displaystyle\hat{D}_{Si}:=\sum_{j}\hat{D}_{Sij}.$

Lastly, let $D_{1}$

$\displaystyle D_{1}:=\sum_{S}\hat{D}_{Si}$

First, we claim that $D_{1}$ is a cut matching game demand. To do so, we must
show that $\hat{D}_{Si}$ is $B_{S}^{(i)}$-respecting. To see this, observe
that the demand that a vertex $u$ sends according to $\hat{D}_{Si}$ is

$\displaystyle\sum_{v}\hat{D}_{Si}(u,v)$
$\displaystyle=\sum_{v}\sum_{j}D_{Si}(u,j)\cdot\frac{w_{Sij}(v)}{\mathrm{val}(\hat{F}_{Sij})}$
$\displaystyle=\sum_{j}D_{Si}(u,j)\sum_{v}\frac{w_{Sij}(v)}{\mathrm{val}(\hat{F}_{Sij})}$
$\displaystyle=\sum_{j}\sum_{v}D_{Sij}(u,v)$ $\displaystyle\leq
B^{(i)}_{S}(u)$

where in the last step we used the fact that $\sum_{j}D_{Sij}$ is
$B_{S}^{(i)}$-respecting. Symmetrically, one can show that
$\sum_{v}\hat{D}_{Si}(v,u)\leq B^{(i)}_{S}(u)$ which shows that $D_{1}$ is
indeed a cut matching game demand. It follows by the above discussion that we
can route $D_{1}$ over $h^{\prime\prime}s/\epsilon$-length paths with
congestion at most
$\tilde{O}(\frac{N^{O(\epsilon)}}{\phi^{\prime}\cdot\epsilon})$.

Next, we claim that it is possible to concatenate the routing paths of $D_{1}$
and $D_{2}$ to get a flow $F=\sum_{S,i,j}F_{Sij}$ in which $F_{Sij}$ routes
from each vertex $u$ a flow of value $D_{Si}(u,j)$ to $B_{S}^{(j)}$.

We describe $F_{Sij}$. Recall that $D_{1}=\sum_{i,j}\hat{D}_{Sij}$ and let
$\hat{F}=\hat{F}_{Sij}$ be the aforementioned flow which routes $D_{2}$. We
will construct $F_{Sij}$ by concatenating paths of the portion of the flow for
$D_{1}$ which routes $\hat{D}_{Sij}$ and $F_{Sij}$. Specifically, notice that
according to $\hat{D}_{Sij}$ the total flow from vertices to a vertex $v$ must
be

$\displaystyle\frac{w_{Sij}(v)}{\mathrm{val}(\hat{F}_{Sij})}\sum_{u}D_{Si}(u,j)=\frac{w_{Sij}(v)}{\mathrm{val}(\hat{F}_{Sij})}\sum_{u,w}D_{Sij}(u,w)=w_{Sij}(v).$

and since by definition the flow from vertex $v$ according to $F_{Sij}$ is
just $w_{Sij}(v)$, we have that we can concatenate the flow paths of these two
flows at each vertex $v$. Next, observe that for a given vertex $u$ this flow
sends

$\displaystyle\sum_{v}\hat{D}_{Sij}(u,v)=\sum_{v}D_{Si}(u,j)\cdot\frac{w_{Sij}(v)}{\mathrm{val}(\hat{F}_{Sij})}=D_{Si}(u,j)$

flow from $u$ to $B_{S}^{(j)}$ as required. Lastly, observe that $F$ has
length $O(h^{\prime\prime}s/\epsilon)$ and congestion at most
$\tilde{O}(\frac{N^{O(\epsilon)}}{\phi^{\prime}\cdot\epsilon})$. $D_{3}$ can
be constructed symmetrically to $D_{1}$ and concatenated to $F$ for a flow
with the same guarantees but one in which each vertex $u$ sends to vertex $v$
flow $\sum D_{Sij}(u,v)$ flow. Summarizing, we shown how to route our initial
demand $D$ that decomposes as $D=\sum_{S}D_{S}$ where $D_{S}$ is
$\hat{B}_{S}$-with the above length and congestion.

Constructing a Length-Constrained Expanding Node-Weighting. Finally, we use
the above routing to demonstrate the existence of a large length-constrained
expanding subset.

Specifically, say that a vertex $v$ is _$h^{\prime}$ -length embedded_ if for
every cluster $S\in\mathcal{N}_{h^{\prime}}\cap\mathcal{N}[h^{\prime\prime}]$
for all $h^{\prime\prime}\leq
h\cdot\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}$ which contains $v$, $v$
succeeds for the cut matching games of $S$ (of which there are either $1$ or
$L$), $S$ succeeded for its cut matching games and cut matching. We let
$B_{h^{\prime}}$ be $A$ restricted to all _$h^{\prime}$ -length embedded_
vertices. Clearly $B_{h^{\prime}}$ is $A$-respecting.

We claim that $B_{h^{\prime}}$ has large $h^{\prime}$-length expansion.
Consider an $h^{\prime}$-length $B_{h^{\prime}}$-respecting demand $D$. Since
$\mathcal{N}_{h^{\prime}}$ is a neighborhood cover with covering radius
$h^{\prime}$, for each pair $(u,v)\in\mathrm{supp}(D)$, we know there must be
some cluster $S\in\mathcal{N}_{h^{\prime}}$ such that $u,v\in S$. It follows
that we can decompose $D$ as $D=\sum_{h^{\prime\prime}}D_{h^{\prime\prime}}$
where every pair in the support of $D_{h^{\prime\prime}}$ is contained in some
cluster in $S\in\mathcal{N}[h^{\prime\prime}]\cap\mathcal{N}_{h^{\prime}}$
wherein both $u$ and $v$ succeeded for the cut matching games of $S$ and $S$’s
cut matching games and cutmatching succeeded.

Such a demand $D_{h^{\prime\prime}}$ is exactly the sort of demand we argued
we can route above and so it follows that we can route each
$D_{h^{\prime\prime}}$ and therefore $D$ (at an increase of $O(\log N)$ in
congestion) over length $O(h^{\prime\prime}s/\epsilon)\leq
h^{\prime}\cdot\frac{1}{\epsilon^{2}}\cdot(s)^{1+O(1/\epsilon)}$ paths with
congestion at most
$\tilde{O}(\frac{N^{O(\epsilon)}}{\phi^{\prime}\cdot\epsilon})$. Thus,
applying our choice of $\phi^{\prime}$ (Equation 24), we have $B_{h^{\prime}}$
is $(h^{\prime},\frac{1}{\epsilon^{2}}\cdot(s)^{1+O(1/\epsilon)})$-length
$\tilde{O}(\phi\cdot\epsilon)$-expanding.

Letting $\bar{B}_{h^{\prime}}:=A-B_{h^{\prime}}$, it follows by Lemma 13.5
that

$\displaystyle\text{LDSC}\left(\phi\frac{\epsilon}{s^{3}N^{O(1/s)}},\frac{h^{\prime}}{2},\frac{1}{\epsilon^{2}}\cdot(s)^{1+O(1/\epsilon)}\right)\leq\text{LEC}\left(\phi\epsilon,h^{\prime},\frac{1}{\epsilon^{2}}\cdot(s)^{1+O(1/\epsilon)}\right)\leq|\bar{B}_{h^{\prime}}|.$

In other words, (up to appropriate slacks) the above upper bounds the demand-
size of the demand-size-largest $(h^{\prime},s)$-length $\phi$-sparse cut for
any $h^{\prime}\leq h$ in terms of $|\bar{B}_{h^{\prime}}|$.

Letting $\bar{B}^{*}$ be the $\bar{B}_{h^{\prime}}$ of smallest size, we have
the following upper bound for all $h^{\prime}$ on the demand-size of the
demand-size-largest length-constrained
$\phi^{\prime}\frac{\epsilon}{N^{O(\epsilon)}}$-sparse cut.

$\displaystyle\text{LDSC}\left(\phi\frac{\epsilon}{s^{3}N^{O(1/s)}},\frac{h^{\prime}}{2},\frac{1}{\epsilon^{2}}\cdot(s)^{1+O(1/\epsilon)}\right)\leq|\bar{B}^{*}|.$
(39)

Correctness Analysis: Sparsity of Each of Our Candidate Cuts. Consider a fixed
$h^{\prime\prime}\leq h\cdot\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}$ that
is a power of $2$. Let $(F,C)$ be one of the $1/\epsilon+1$ cutmatches we
compute (in either step 2 or step 3) in this iteration. We argue that $C$ has
$(h^{\prime\prime},s)$-length sparsity at most $\phi$.

To do so we begin by constructing a large $h^{\prime\prime}$-length demand
$D_{h^{\prime\prime}}$ which is $h^{\prime\prime}s$-separated in
$G+h^{\prime}\cdot C_{h^{\prime}}$. Let the pairs for $(F,C)$ be
$\\{(A_{i},A_{i}^{\prime})\\}_{i}$ where the support of each such pair is in
some cluster in $\mathcal{N}[h^{\prime\prime}]$ and with matched and unmatched
parts $\\{(M_{i},M_{i}^{\prime})\\}_{i}$ and
$\\{(U_{i},U_{i}^{\prime})\\}_{i}$ respectively. Throughout this proof we will
assume without loss of generality that for all $i$ $A_{i}(U_{i})\leq
A_{i}^{\prime}(U_{i}^{\prime})$. For each pair $(A_{i},A_{i}^{\prime})$, let
$D_{i}$ be an $h^{\prime\prime}$-length demand with
$\mathrm{supp}(D_{i})\subseteq\mathrm{supp}(U_{i})\times\mathrm{supp}(U_{i}^{\prime})$
where each $u\in U_{i}$ sends $A_{i}(u)$ to nodes in $U_{i}^{\prime}$ so that
no node $v\in U_{i}^{\prime}$ receives more than $A_{i}^{\prime}(v)$ demand.
The definition of a cutmatch (Definition 12.2) ensures that in
$G+h^{\prime\prime}\cdot C_{h^{\prime\prime}}$ all pairs of this demand are at
least $(h^{\prime\prime}s)$-far.

Similarly, if we are in step 2 we let

$\displaystyle D_{h^{\prime\prime}}:=\sum_{i}D_{i}/\tilde{O}(N^{O(\epsilon)})$

and if we are in step 3 we let

$\displaystyle D_{h^{\prime\prime}}:=\sum_{i}D_{i}/\tilde{O}(L\cdot
N^{O(\epsilon)})$

be this demand summed and scaled appropriately across all pairs. Observe that
$C_{h^{\prime\prime}}$ still clearly $(h^{\prime\prime}s)$-separates this
demand. Furthermore, observe that this demand is $h^{\prime\prime}$-length by
since each pair in the support is contained in a cluster in
$\mathcal{N}[h^{\prime\prime}]$. Also, observe that above demand is
$A$-respecting by virtue of the width of each of our neighborhood covers being
$N^{O(\epsilon)}$ and by definition of how we break up node-weightings; this
holds regardless of whether the cutmatch is computed in step 2 or step 3.
Lastly, observe that the size of this demand is

$\displaystyle|D_{h^{\prime\prime}}|$
$\displaystyle=\sum_{i}A_{i}(U_{i})/\tilde{O}(N^{O(\epsilon)})$
$\displaystyle=\sum_{i}\frac{|A_{i}|-A_{i}(M_{i})}{\tilde{O}(N^{O(\epsilon)})}$
$\displaystyle\geq\frac{\sum_{i}|A_{i}|-\mathrm{val}(F)}{\tilde{O}(N^{O(\epsilon)})}$
(40)

On the other hand, by the definition of a cutmatch (Definition 12.2), we have
that the size of $C$ is at most

$\displaystyle|C|\leq\phi^{\prime\prime}\cdot\left(\left(\sum_{i}|A_{i}|\right)-\mathrm{val}(F)\right).$
(41)

where $\phi^{\prime\prime}=\phi^{\prime}/L$ if we are in step 3 and
$\phi^{\prime\prime}=\phi^{\prime}$ otherwise.

Combining Equations 13.2 and 41, the definition of $\phi^{\prime}$ (Equation
24), we have that $C_{h^{\prime\prime}}$ is an $h^{\prime\prime}$-length cut
with sparsity at most

$\displaystyle\phi^{\prime}/\tilde{O}(N^{O(\epsilon)})\leq\phi.$

Correctness Analysis: Output Cut is Demand-Size Large. It remains to argue
that the demand-size of the cut $C^{*}$ returned by our algorithm is
sufficiently large. Recall that, if $C^{*}$ was computed when we were
considering diameter $h^{\prime\prime}\leq
h\cdot\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}$, then we know that the
$(h^{\prime\prime},s)$-length sparsity of $C^{*}$ is at most $\phi$.

We claim that the $(h^{\prime\prime},s)$-length demand-size of $C^{*}$ with
respect to $A$ (Definition 13.1) is

$\displaystyle
A_{(h^{\prime\prime},s)}(C^{*})\geq|\bar{B}^{*}|\cdot\frac{\epsilon^{3}}{\tilde{O}(N^{O(\epsilon)})}.$
(42)

Furthermore, by Equation 39 for any $h^{\prime}\leq h$, the largest
$(\frac{h^{\prime}}{2},\frac{1}{\epsilon^{2}}\cdot(s)^{1+O(1/\epsilon)})$-length
demand-size of a
$(\frac{h^{\prime}}{2},\frac{1}{\epsilon^{2}}\cdot(s)^{1+O(1/\epsilon)})$-length
$\phi\cdot\frac{\epsilon}{s^{3}N^{O(1/s)}}$-sparse cut is at most
$|\bar{B}^{*}|$. It follows that $C_{h^{\prime}}$ is a
$\frac{\epsilon^{3}}{\tilde{O}(N^{O(\epsilon)})}$-approximate $(\leq
h,s)$-length $\phi$-sparse cut with length slack approximation
$\alpha_{s}=\max\left(2,\frac{1}{\epsilon^{2}}\cdot(s)^{1+O(1/\epsilon)}\right)$
and sparsity approximation $\alpha_{\phi}=\frac{\epsilon}{s^{3}N^{O(1/s)}}$
(see, again, Definition 13.3 for a definition of this notion of
approximation).

It remains to argue that Equation 42 holds. We let
$\bar{B}_{h^{\prime}}=\bar{B}^{*}$ for the remainder of this proof; that is,
for the remainder of this proof we let $h^{\prime}\leq h$ be the length with
respect to which $B_{h^{\prime}}=A-\bar{B}_{h^{\prime}}$ is length-constrained
expanding.

A vertex $u$ can fail to be $h^{\prime}$-length embedded if there is a cluster
$S\in\mathcal{N}_{h^{\prime}}\cap\mathcal{N}[h^{\prime\prime}]$ for some
$h^{\prime\prime}\leq
h^{\prime}\cdot\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}$ which contains $u$
and with corresponding node-weighting $A_{S}$ for which

  1. 1.

Cut Matching Games Fails for Vertex. $u$ fails the cut matching game for $S$;
in other words, there is some cluster $S\in\mathcal{N}[h^{\prime\prime}]$
containing $u$ such that $\sum_{i}B_{S}^{(i)}(u)<cA_{S}(u)$. Let
$W^{(1)}_{h^{\prime\prime}}$ be all such nodes.

  2. 2.

Cut Matching Game Fails for Cluster. $u$ succeeds the cut matching game for
$S$ but $S$ does not succeed the cut matching game; i.e it is not the case
that a constant fraction of $A_{S}^{1},A_{S}^{(2)},\ldots$ succeed. Let
$W^{(2)}_{h^{\prime\prime}}$ be all such nodes.

  3. 3.

Cutmatching Fails. $S$ is a cluster whose node-weighting we broke up which did
not succeed for the cutmatching. Let $W^{(3)}_{h^{\prime\prime}}$ be all such
nodes not in $W^{(2)}_{h^{\prime\prime}}$ or $W^{(1)}_{h^{\prime\prime}}$.

Likewise, let $W^{(i)}:=\bigcup_{h^{\prime\prime}}W^{(i)}_{h^{\prime\prime}}$
for $i\in[1,3]$. It follows that

$\displaystyle|B_{h^{\prime}}|=A-A(W^{(1)})-A(W^{(2)})-A(W^{(1)}).$

and so

$\displaystyle|\bar{B}^{*}|=A(W^{(1)})+A(W^{(2)})+A(W^{(3)}).$

Likewise, by averaging there is some $h^{\prime\prime}$ such that

$\displaystyle
A(W^{(1)})+A(W^{(2)})+A(W^{(3)})\leq\tilde{O}\left(A(W^{(1)}_{h^{\prime\prime}})+A(W^{(2)}_{h^{\prime\prime}})+A(W^{(3)}_{h^{\prime\prime}})\right).$

Furthermore, observe that by how defined what it means for a cluster to
succeed we have $A(W^{(2)}_{h^{\prime\prime}})\leq
O(A(W_{h^{\prime\prime}}^{O(1)}))$ for an appropriate hidden constant. Thus,
we have

$\displaystyle|\bar{B}^{*}|\leq\tilde{O}\left(A(W^{(1)}_{h^{\prime\prime}})+A(W^{(3)}_{h^{\prime\prime}})\right).$

We case on which of $A(W^{(1)}_{h^{\prime\prime}})$ and
$A(W^{(3)}_{h^{\prime\prime}})$ are larger.

  1. 1.

Suppose $A(W^{(1)}_{h^{\prime\prime}})\geq A(W^{(3)}_{h^{\prime\prime}})$ so
that $|\bar{B}^{*}|\leq\tilde{O}\left(A(W^{(1)}_{h^{\prime\prime}})\right)$.
For a $u$ and $i$, say that $u$ fails the cut matching game for $S$ and $i$ if
$B_{S}^{(i)}(u)\leq c^{\prime\prime}\cdot A_{S}^{(i)}(u)$ for a fixed constant
$c^{\prime\prime}\in[0,1)$. Let $W^{(1)}_{Si}$ be all nodes that fail the cut
matching game for $S$ and $i$. Observe that, by choosing $c^{\prime\prime}$
appropriately, we have

$\displaystyle\sum_{S,i}A_{S}^{(i)}(W^{(1)}_{Si})\geq\Omega\left(A(W^{(1)}_{h^{\prime\prime}})\right).$

and so it suffices to bound $\sum_{S,i}A_{S}^{(i)}(W^{(1)}_{Si})$.

Let $(F^{(l)},C^{(l)})$ be the cutmatch we compute in iteration
$l\in[1/\epsilon]$ for pairs $\\{(A_{Si,k}^{(l)},B_{Si,k}^{(l)})\\}_{S,i,k}$
and let $F^{(l)}=\sum_{S,i,k}F_{Si,k}^{(l)}$ be the decomposition of this flow
(one sub-flow for each pair).

Let $\alpha_{Si}$ be the smallest matching played by the cut matching game we
run on $A_{S}^{(i)}$. It follows that, for a fixed $S$ and $i$, there must be
some iteration $l_{Si}$ among our $1/\epsilon$ cutmatches

$\displaystyle\sum_{k}\mathrm{val}(F_{Si,k}^{(l_{Si})})=(1-\alpha_{Si})\cdot\sum_{k}|A_{Si,k}^{(l_{Si})}|.$

Likewise, we know by the guarantees of Theorem 13.6 that

$\displaystyle\left(1-\frac{\alpha_{Si}}{\epsilon}\right)\cdot|A_{S}^{(i)}|\leq|B_{S}^{(i)}|\leq|A_{S}^{(i)}|-\Omega\left(A_{S}^{(i)}(W_{Si}^{(1)})\right).$

and so rearranging we have

$\displaystyle\epsilon\cdot
A_{S}^{(i)}(W_{Si}^{(1)})\leq\alpha_{Si}\cdot|A_{S}^{(i)}|.$

Let $F=\sum_{l}F^{(l)}$, let $C=\sum_{l}C^{(l)}$ and let
$D_{h^{\prime\prime}}=\epsilon\sum_{l}D_{h^{\prime\prime}}^{(l)}$ where
$D_{h^{\prime\prime}}^{(l)}$ is the demand for this cutmatch as described in
our sparsity analysis. Note that $C$ is the cut our algorithm considers from
step 2 for this value of $h^{\prime\prime}$. Thus, $D_{h^{\prime\prime}}$ is
$A$-respecting, $C$ $h^{\prime\prime}s$-separates $D_{h^{\prime\prime}}$ and
$D_{h^{\prime\prime}}$ has size at least

$\displaystyle|D_{h^{\prime\prime}}|\geq\epsilon\cdot\sum_{l}\sum_{S,i,k}\frac{|A_{Si,k}|-\mathrm{val}(F_{Si,k}^{(l)})}{\tilde{O}(N^{O(\epsilon)})}$
$\displaystyle\geq\epsilon\cdot\sum_{S,i}\frac{\alpha_{Si}\cdot\sum_{k}|A_{Si,k}^{(l_{Si})}|}{\tilde{O}(N^{(\epsilon)})}\geq\epsilon\cdot\sum_{S,i}\frac{\alpha_{Si}\cdot|A_{S}^{(i)}|}{\tilde{O}(N^{(\epsilon)})}$

where in the last inequality we applied the fact that the total size of the
node-weighting of all pairs played by a cut strategy on node-weighting $A$ is
at least $|A|$ (by definition of a node-weighting).

Combining the above we get that this demand has size at least

$\displaystyle|D_{h^{\prime\prime}}|\geq\epsilon\cdot\sum_{S,i}\frac{\alpha_{Si}\cdot|A_{S}^{(i)}|}{\tilde{O}(N^{(\epsilon)})}\geq\epsilon^{2}\cdot\sum_{S,i}\frac{A_{S}^{(i)}(W_{Si}^{1})}{\tilde{O}(N^{(\epsilon)})}\geq\frac{\epsilon^{2}}{\tilde{O}(N^{(\epsilon)})}\cdot
A(W^{(1)}_{h^{\prime\prime}})\geq\frac{\epsilon^{2}}{\tilde{O}(N^{(\epsilon)})}\cdot|\bar{B}^{*}|,$

demonstrating that in this case we have
$|D_{h^{\prime\prime}}|\geq\frac{\epsilon^{2}}{\tilde{O}(N^{(\epsilon)})}\cdot|\bar{B}^{*}|$.
By an averaging argument, there must be some $C^{(l)}$ which separates at
least an $\epsilon$ fraction of $D_{h^{\prime\prime}}$, demonstrating that one
of the $C^{(l)}$ has demand-size at least
$\frac{\epsilon^{3}}{\tilde{O}(N^{(\epsilon)})}\cdot|\bar{B}^{*}|$.

  2. 2.

Suppose $A(W^{(1)}_{h^{\prime\prime}})<A(W^{(3)}_{h^{\prime\prime}})$ so that
$|\bar{B}^{*}|\leq\tilde{O}\left(A(W^{(3)}_{h^{\prime\prime}})\right)$. Let
$(F,C)$ be the cutmatch returned in step 3 when we are using diameter
$h^{\prime\prime}$. We claim that $A_{(h,s)}(C)$ is large. Namely, let
$D_{h^{\prime\prime}}$ be the $A$-respecting demand which is
$h^{\prime\prime}s$-separated and of size as described above which by Section
13.2 has size at least

$\displaystyle\sum_{S,i,j}\frac{|A_{S}^{(i)}|-\mathrm{val}(F_{Sij})}{\tilde{O}(L\cdot
N^{O(\epsilon)})}.$

Let $\mathcal{S}^{(3)}$ be all clusters of $\mathcal{N}[h^{\prime\prime}]$
that did not succeed for the cutmatching (without multiplicity). If a cluster
$S\in\mathcal{S}^{(3)}$ then we know that, for at least a constant fraction of
$i$, a constant fraction of the pairs $(i,j)$ did not succeed, i.e.
$\mathrm{val}(F_{Sij})<c|A_{S}^{(i)}|$. Thus, we have that, among all $L^{2}$
pairs, a constant fraction did not succeed for $S$ and so for any
$S\in\mathcal{S}^{(3)}$ we have

$\displaystyle\sum_{i,j}|A_{S}^{(i)}|-\mathrm{val}(F_{Sij})\geq(1-c^{\prime})L\cdot|A_{S}|$

for some constant $c^{\prime}>0$.

Since each vertex of $W_{h^{\prime\prime}}^{(3)}$ appears in at least one
cluster of $\mathcal{S}^{(3)}$, we have

$\displaystyle\sum_{S\in\mathcal{S}^{(3)}}|A_{S}|\geq
A(W_{h^{\prime\prime}}^{(3)})$

Thus, we have that this demand has size

$\displaystyle\frac{\sum_{i}|A_{i}|-\mathrm{val}(F)}{\tilde{O}(N^{O(\epsilon)})}$

Combining the above, we have that the demand $D_{h^{\prime\prime}}$ has size
at least

$\displaystyle\sum_{S,i,j}\frac{|A_{S}^{(i)}|-\mathrm{val}(F_{Sij})}{\tilde{O}(L\cdot
N^{O(\epsilon)})}$
$\displaystyle\geq\sum_{S\in\mathcal{S}^{(3)}}\frac{\sum_{i,j}|A_{S}^{(i)}|-\mathrm{val}(F_{Sij})}{\tilde{O}(L\cdot
N^{O(\epsilon)})}$
$\displaystyle\geq\frac{(1-c^{\prime})}{N^{O(\epsilon)}}\sum_{S\in\mathcal{S}^{(3)}}|A_{S}|$
$\displaystyle\geq\frac{1}{\tilde{O}(N^{O(\epsilon)}))}\cdot
A(W_{h^{\prime\prime}}^{(3)}).$

Thus, in this case we have
$|D_{h^{\prime\prime}}|\geq|\bar{B}^{*}|/\tilde{O}(N^{O(\epsilon)})$ and so
the demand-size of $C$ is at least this

In either of the above cases we have that one of the cuts we compute for
$h^{\prime\prime}$ has demand-size at least
$|\bar{B}^{*}|\cdot\frac{\epsilon^{3}}{\tilde{O}(N^{O(\epsilon)})}$ as
required.

Correctness Analysis: Witnesses. Lastly, we argue about the returned witness
(as defined in Definition 5.33).

  * •

Neighborhood Cover. Clearly, $\mathcal{N}$ is a neighborhood cover satisfying
the required properties

  * •

Routers. Recall that each $B_{h^{\prime}}$ as described above is
$(h^{\prime},\frac{1}{\epsilon^{2}}\cdot(s)^{1+O(1/\epsilon)})$-length
$\tilde{O}(\phi\cdot\epsilon)$-expanding. Since each cut considered by our
algorithm has $(h^{\prime\prime},s)$-length sparsity at most $\phi$ for some
$h^{\prime\prime}\leq h\cdot\frac{1}{\epsilon}\cdot s^{O(1/\epsilon)}$, it
follows that if any of these cuts has non-zero size then our graph is not a
$(h^{\prime\prime},s)$-length $\phi$-expander. Thus, each of our cutmatches’
cuts must always have a cut of size $0$ and so each router we compute for
cluster $S$ must be a $1/\epsilon$-step and $N^{O(\epsilon)}$ congestion
router. Thus, if $S$ is a cluster whose node-weighting we broke up into
$A_{S}^{(1)},A_{S}^{(2)},\ldots$ then the union of the routers we compute for
$A_{S}^{(1)},A_{S}^{(2)},\ldots$ using our cut matching game along with the
corresponding matching edges from step 3 is a $(s_{0}=(2/\epsilon+1))$-step
router with congestion $\kappa_{0}=N^{O(\epsilon)}$.

  * •

Embedding of Routers. Observe that the sum of the flows we compute across all
cutmatches for clusters of $\mathcal{N}_{h^{\prime}}$ have length at most
$h^{\prime}\cdot\frac{1}{\epsilon}\cdot s^{O(1/\epsilon)}=h^{\prime}\cdot
s_{1}$ and congestion at most
$\kappa_{1}=\tilde{O}(N^{O(\epsilon)}/(\phi\epsilon))$.

Lastly, observe that the overall for our witness we get

$\displaystyle s_{0}\cdot s_{1}=(2/\epsilon+1)\cdot\frac{1}{\epsilon}\cdot
s^{O(1/\epsilon)}=O\left(\frac{1}{\epsilon^{2}}\cdot
s^{O(1/\epsilon)}\right)=s_{w}$

and

$\displaystyle\kappa_{0}\cdot\kappa_{1}=N^{O(\epsilon)}\cdot\tilde{O}(N^{O(\epsilon)}/(\phi\epsilon))=\tilde{O}(N^{O(\epsilon)}/(\phi\epsilon))=1/\phi_{w}$

∎

Combining Theorem 13.6 and Theorem 13.7 immediately gives 13.4, restated below
for convenience. See 13.4

##  14 Algorithm: EDs from Demand-Size-Large Sparse Cuts

We now show how to compute expander decompositions from demand-size large
length-constrained sparse cuts. Specifically, we show the following. Recall
the definition of an $\alpha$-approximate $(\leq h,s)$-length $\phi$-sparse
cut with length approximation $\alpha_{s}$ and sparsity approximation
$\alpha_{\phi}$ from Definition 13.3.

######  Lemma 14.1.

Fix $\alpha,\alpha_{\phi},\alpha_{s}>1$ and let
$\textnormal{{W}}_{\textnormal{sparse-cut}}(A,m)$ be the time to compute an
$\alpha$-approximate $(\leq h^{\prime},s^{\prime})$-length
$\phi^{\prime}$-sparse cut with sparsity approximation $\alpha_{\phi}$ and
length approximation $\alpha_{s}$ w.r.t. node-weighting $A$ in a graph with
$m^{\prime}\leq m$ edges for $h^{\prime}\leq h$, $s^{\prime}\leq s$ and
$\phi^{\prime}\geq\phi$.

Then, for every $\epsilon,\epsilon^{\prime}>0$, one can compute a $(\leq
h,s)$-length $\phi$-expander decomposition for $A$ with cut slack

$\displaystyle\kappa=\tilde{O}\left(\alpha\cdot
N^{O(\epsilon^{\prime})}\right)\cdot\tilde{O}\left(\alpha_{\phi}\cdot s\cdot
N^{O(1/\sqrt{s})}\ \right)^{O(1/\epsilon^{\prime})},$

length slack

$\displaystyle s=\alpha_{s}^{O(1/\epsilon^{\prime})},$

work

$\displaystyle\textnormal{{W}}_{\textnormal{ED}}(A,m)\leq\tilde{O}\left(\frac{N^{O(\epsilon^{\prime})}}{\epsilon^{\prime}}\cdot\alpha\right)\cdot\textnormal{{W}}_{\textnormal{sparse-
cut}}(A,m)$

and depth

$\displaystyle\textnormal{{D}}_{\textnormal{ED}}(A,m)\leq\tilde{O}\left(\frac{N^{O(\epsilon^{\prime})}}{\epsilon^{\prime}}\cdot\alpha\right)\cdot\textnormal{{D}}_{\textnormal{sparse-
cut}}(A,m).$

We begin by describing the algorithm we use to prove the above. We give
pseudo-code in Algorithm 2. The algorithm runs in
$\frac{1}{\epsilon^{\prime}}$ top-level iterations we call epochs. In epoch
$\mathsf{epoch}$ the algorithm repeatedly cuts an $\alpha$-approximate demand-
size-largest $(\leq h_{\mathsf{epoch}},s_{\mathsf{epoch}})$-length
$\phi_{\mathsf{epoch}}$-sparse cut for the target node weighting $A$ in the
current graph with sparsity slack $\alpha_{\phi}$ and length slack
$\alpha_{s}$. For the next epoch the algorithm adjusts its target values for
sparsity and length by decreasing $\phi_{\mathsf{epoch}}$ by about
$1/\alpha_{\phi}$, $h_{\mathsf{epoch}}$ by about $1/\alpha_{s}$ and increasing
$s_{\mathsf{epoch}}$ by about $\alpha_{s}$.

The proof shows that, at the end of an epoch $\mathsf{epoch}$, no demand-size-
large $(h_{\mathsf{epoch}}^{\prime},s_{\mathsf{epoch}}^{\prime})$-length
$\phi_{\mathsf{epoch}}^{\prime}$-sparse cuts exist for $A$ anymore for
$h_{\mathsf{epoch}}^{\prime}$, $s_{\mathsf{epoch}}^{\prime}$ and
$\phi_{\mathsf{epoch}}$ each slightly more relaxed than $h_{\mathsf{epoch}}$,
$s_{\mathsf{epoch}}$ and $\phi_{\mathsf{epoch}}$. More specifically, for
$h_{\mathsf{epoch}}^{\prime}\leq h_{\mathsf{epoch}}/\alpha_{s}$,
$s_{\mathsf{epoch}}^{\prime}=s_{\mathsf{epoch}}\cdot\alpha_{s}$ and
$\phi_{\mathsf{epoch}}^{\prime}=\phi_{\mathsf{epoch}}/\alpha_{\phi}$.
Initially, no such cut of demand-size strictly more than $|A|$ exists
(trivially) and in each epoch we improve the quality of this upper bound on
the demand-size-largest cut by an $N^{\epsilon^{\prime}}$ factor so that after
$1/\epsilon^{\prime}$ iterations no such cut exists (for appropriately relaxed
length, length slack and sparsity). Generally speaking, the trick is to make
sure that our upper bound on $|A|$ improves faster than we must relax our
length, length slack and sparsity.

Algorithm 2 Length-Constrained Expander Decompositions (from Large Sparse
Cuts)

Input: Edge-capacitated graph $G_{0}$, parameters
$\epsilon,\epsilon^{\prime}\in(0,1)$, node-weighting $A$ on $G$, length bound
$h$, and conductance bound $\phi>0$, an algorithm for demand-size-largest
sparse cut.

Output: $(\leq h,s)$-length $\phi$-expander decomposition

Initialize Graph and Number of Iterations: $G=G_{0}$ and $l=\Theta(\log
N\cdot\alpha\cdot N^{O(\epsilon^{\prime})})$

Initialize Length:
$h_{0}=\alpha_{s}\cdot(2\alpha_{s})^{1/\epsilon^{\prime}}\cdot h$

Initialize Length Slack: $s_{0}=2\cdot\alpha_{s}^{1/\epsilon^{\prime}}$

Initialize Sparsity:
$\phi_{0}=\phi\cdot\alpha_{\phi}\cdot\prod_{\mathsf{epoch}\in[1/\epsilon^{\prime}]}\left(\tilde{O}(\alpha_{\phi}\cdot
s_{\mathsf{epoch}}^{3}\cdot N^{O(1/s_{\mathsf{epoch}})})\right)$

for $\mathsf{epoch}=1,2,\ldots 1/\epsilon^{\prime}$ do

Update Length: $h_{\mathsf{epoch}}=\frac{1}{2\alpha_{s}}\cdot
h_{\mathsf{epoch}-1}$

Update Length Slack: $s_{\mathsf{epoch}}=\alpha_{s}\cdot s_{\mathsf{epoch}-1}$

Update Sparsity: $\phi_{\mathsf{epoch}}=\frac{1}{\tilde{O}(\alpha_{\phi}\cdot
s_{\mathsf{epoch}}^{3}\cdot
N^{O(1/s_{\mathsf{epoch}})})}\cdot\phi_{\mathsf{epoch}-1}$

for $j=1,2,\ldots,l$ do

Let $C$ be an $\alpha$-approximate demand-size-largest $(\leq
h_{\mathsf{epoch}},s_{\mathsf{epoch}})$-length $\phi_{\mathsf{epoch}}$-sparse
cut

for $A$ and length $h_{\mathsf{epoch}}^{\prime\prime}$ in $G$ with length and
sparsity approximation $\alpha_{s}$ and $\alpha_{\phi}$.

Update Graph: $G=G+s_{\mathsf{epoch}}\cdot
h^{\prime\prime}_{\mathsf{epoch}}\cdot C$.

return $\sum_{C}C$

We will use the following notion of the demand-size of a sequence of cuts and
the subsequent relation. Below, recall the definition of LDSC from Definition
13.2.

######  Definition 14.2 (LDSCS).

Fix a graph $G$, node-weighting $A$ and parameters $h$, $s$ and $\phi$. LDSCS
is the demand-size of the demand-size-largest sequence of $(h,s)$-length
$\phi$-sparse moving cuts. Specifically,

$\displaystyle\text{LDSCS}(\phi,h,s):=\sum_{i}A_{(h,s)}(C_{i})$

where above $A_{(h,s)}(C_{i})$ is computed after applying all $C_{j}$ for
$j<i$ and $(C_{1},C_{2},\ldots)$ is the $(h,s)$-length $\phi$-expanding moving
cut sequence maximizing $\sum_{i}A_{(h,s)}(C_{i})$.

######  Lemma 14.3.

Given graph $G$ and node-weighting $A$, we have that

$\displaystyle\text{LDSCS}(\phi,h,s)\leq\text{LDSC}(\phi^{\prime},h^{\prime},s^{\prime})$

where $h^{\prime}=2h$, $s^{\prime}=\frac{(s-2)}{2}$ and
$\phi^{\prime}=s^{3}\cdot\log^{3}N\cdot N^{O(1/s)}\cdot\phi$.

###### Proof.

Let $(C_{1},C_{2},\ldots)$ be a sequence of $(h,s)$-length $\phi$-sparse cuts
such that $\sum_{i}A_{(h,s)}(C_{i})=\text{LDSCS}(\phi,h,s)$ where
$\phi_{i}\leq\phi$ is the minimum value for which $C_{i}$ is
$\phi_{i}$-sparse. Let $D_{1},D_{2},\ldots$ be the demands witnessing these
cuts so that for all $i$ we have

$\displaystyle|C_{i}|/\phi=|D_{i}|.$

Let $C=\sum_{i}C_{i}$. By 1.2 we know that $C$ is an
$(h^{\prime},s^{\prime})$-length $\phi^{\prime}$-sparse cut for $A$ and so
there must be some $h^{\prime}$-length demand $D$ which is
$h^{\prime}s^{\prime}$-separated by $C$ and $D$ has size at least

$\displaystyle\frac{|C|}{\phi^{\prime}}=|C|\frac{\sum_{i}|C_{i}|/\phi_{i}}{\sum_{i}|C_{i}|}=\sum_{i}|D_{i}|$

In other words, the demand-size of $C$ is at least $\sum_{i}|D_{i}|$, as
required. ∎

######  Lemma 14.4.

At the end of the $\mathsf{epoch}$th epoch of Algorithm 2, we have that for
every $h^{\prime}_{\mathsf{epoch}}\leq h_{\mathsf{epoch}}/\alpha_{s}$ that the
demand-size-largest $(h^{\prime}_{\mathsf{epoch}},s_{\mathsf{epoch}})$-length
$(\phi_{\mathsf{epoch}}/\alpha_{\phi})$-sparse cut has
$(h^{\prime}_{\mathsf{epoch}},s_{\mathsf{epoch}}\cdot\alpha_{s})$-length
demand-size at most
$|A|\cdot\left(\frac{1}{N^{O(\epsilon^{\prime})}}\right)^{\mathsf{epoch}}$. In
other words, we have for every $h^{\prime}_{\mathsf{epoch}}\leq
h_{\mathsf{epoch}}/\alpha_{s}$ that

$\displaystyle\text{LDSC}(\phi_{\mathsf{epoch}}/\alpha_{\phi},h^{\prime}_{\mathsf{epoch}},s_{\mathsf{epoch}}\cdot\alpha_{s})\leq|A|\cdot\left(\frac{1}{N^{O(\epsilon^{\prime})}}\right)^{\mathsf{epoch}}.$

###### Proof.

We prove this by induction. Let $\gamma:=1/N^{O(\epsilon^{\prime})}$ for
convenience of notation. The base case when $\mathsf{epoch}=0$ is trivial as
the demand-size of any cut is trivially at most $|A|$. Next, suppose
$\mathsf{epoch}>0$ and assume for the sake of contradiction that our inductive
hypothesis does not hold and so there is some $\hat{h}_{\mathsf{epoch}}\leq
h_{\mathsf{epoch}}/\alpha_{s}$ such that at the end of the $\mathsf{epoch}$th
epoch we have

$\displaystyle\text{LDSC}(\phi_{\mathsf{epoch}}/\alpha_{\phi},\hat{h}_{\mathsf{epoch}},s_{\mathsf{epoch}}\cdot\alpha_{s})>|A|/\gamma^{\mathsf{epoch}}.$
(43)

Consider a cut $C$ we compute in an epoch, $\mathsf{epoch}$, with
corresponding length $h^{\prime\prime}_{\mathsf{epoch}}$. Unpacking the
definition of approximate demand-size largest sparse cuts (Definition 13.3),
we have that $C$ is an
$(h^{\prime\prime}_{\mathsf{epoch}},s_{\mathsf{epoch}})$-length
$\phi_{\mathsf{epoch}}$-sparse cut for $A$ where
$h^{\prime\prime}_{\mathsf{epoch}}\leq\alpha_{s}\cdot h_{\mathsf{epoch}}$ and,
for any $h^{\prime}_{\mathsf{epoch}}\leq h_{\mathsf{epoch}}/\alpha_{s}$ and,
in particular, for $\hat{h}_{\mathsf{epoch}}$ we have

$\displaystyle
A_{(h^{\prime\prime}_{\mathsf{epoch}},s_{\mathsf{epoch}})}(C)\geq\frac{1}{\alpha}\cdot\text{LDSC}(\phi_{\mathsf{epoch}}/\alpha_{\phi},\hat{h}_{\mathsf{epoch}},s_{\mathsf{epoch}}\cdot\alpha_{s})$

at the moment when $C$ is computed. Combining the above with Equation 43 and
the fact that
$\text{LDSC}(\phi_{\mathsf{epoch}}/\alpha_{\phi},\hat{h}_{\mathsf{epoch}},s_{\mathsf{epoch}}\cdot\alpha_{s})$
can only be smaller at the end of our epoch than in the middle of it , we get

$\displaystyle
A_{(h^{\prime\prime}_{\mathsf{epoch}},s_{\mathsf{epoch}})}(C)>\frac{1}{\alpha}\cdot|A|/\gamma^{\mathsf{epoch}}$
(44)

Let $h^{\prime\prime}_{\mathsf{epoch}}\leq h_{\mathsf{epoch}}\cdot\alpha_{s}$
be a value that could correspond to a cut in the $\mathsf{epoch}$th iteration.
Notice that, by our definition $h_{\mathsf{epoch}}=\frac{1}{2\alpha_{s}}\cdot
h_{\mathsf{epoch}-1}$, we have that

$\displaystyle 2h^{\prime\prime}_{\mathsf{epoch}}\leq 2\alpha_{s}\cdot
h_{\mathsf{epoch}}=h_{\mathsf{epoch}-1}.$ (45)

We may assume these values are, without loss of generality, powers of $2$ and
so after we compute $\Theta(\log N\cdot\alpha\cdot\gamma)$-many cuts, we know
that there must be some $h^{\prime\prime}_{\mathsf{epoch}}$ such that
$\mathcal{C}_{h^{\prime\prime}_{\mathsf{epoch}}}$ contains at least
$(\alpha\cdot\gamma)$-many cuts. We let $(C_{1},C_{2},\ldots)$ be these cuts.
Applying Equation 44 to each of our $C_{i}$s, we get

$\displaystyle\sum_{i}A_{(h^{\prime\prime}_{\mathsf{epoch}},s_{\mathsf{epoch}})}(C_{i})>|A|/\gamma^{\mathsf{epoch}-1}.$
(46)

$(C_{1},C_{2},\ldots)$ is an
$(h_{\mathsf{epoch}}^{\prime\prime},s_{\mathsf{epoch}})$-length
$\phi_{\mathsf{epoch}}$-sparse sequence of moving cuts and so forms a
candidate for the demand-size-largest such sequence.

It therefore follows that at the end of the $\mathsf{epoch}$th epoch we have

$\displaystyle\sum_{i}A_{(h^{\prime\prime}_{\mathsf{epoch}},s_{\mathsf{epoch}})}(C_{i})$
$\displaystyle\leq\text{LDSCS}(\phi_{\mathsf{epoch}},h^{\prime\prime}_{\mathsf{epoch}},s_{\mathsf{epoch}})$
$\displaystyle\leq\text{LDSC}\left(\phi_{\mathsf{epoch}}\cdot\tilde{O}(s_{\mathsf{epoch}}^{3}\cdot
N^{O(1/s_{\mathsf{epoch}})}),2h^{\prime\prime}_{\mathsf{epoch}},s_{\mathsf{epoch}}\right)$
$\displaystyle=\text{LDSC}\left(\phi_{\mathsf{epoch}-1},2h^{\prime\prime}_{\mathsf{epoch}},s_{\mathsf{epoch}-1}\cdot\alpha_{s}\right)$
$\displaystyle\leq\text{LDSC}\left(\phi_{\mathsf{epoch}-1},h_{\mathsf{epoch}-1},s_{\mathsf{epoch}-1}\right)$
$\displaystyle\leq|A|/\gamma^{\mathsf{epoch}-1}.$

where, above, the second inequality follows from Lemma 14.3, the third from
the definition of $\phi_{\mathsf{epoch}-1}$ and $s_{\mathsf{epoch}-1}$, the
fourth from Equation 45 and the fact that $\text{LDSC}(\phi,h,s)$ is monotone
increasing in $h$ (as long as $s\geq 2$) and monotone decreasing in $s$ and
the fifth from our inductive hypothesis. However, the above contradicts
Equation 46. ∎

We conclude with our proof of Lemma 14.1. See 14.1

###### Proof.

We use Algorithm 2.

First, we claim that the returned cuts $\sum_{C}C$ are indeed an $(\leq
h,s)$-length expander decomposition for sparsity $\phi$ with cut slack
$\kappa$.

Let $\mathsf{epoch}$ be $1/\epsilon^{\prime}$. By our choice of how we
initialize $h_{0}$, $\phi_{0}$, observe that after our
$1/\epsilon^{\prime}$-many epochs we have that
$h_{\mathsf{epoch}}=\alpha_{s}\cdot h$,
$s_{\mathsf{epoch}}=2\cdot\alpha_{s}^{2/\epsilon^{\prime}}$ and
$\phi_{\mathsf{epoch}}=\alpha_{\phi}\cdot\phi$. Letting
$s=2\cdot\alpha_{s}^{2/\epsilon^{\prime}}$ and applying Lemma 14.4 to the
final epoch of our algorithm, we therefore have that, after applying
$\sum_{C}C$ to our graph, for every $h^{\prime}\leq
h_{\mathsf{epoch}}/\alpha_{s}\leq h$ that the $(h,s)$-length demand-size of
the demand-size-largest $(h,s)$-length
$\phi_{\mathsf{epoch}}/\alpha_{\phi}=\phi$-sparse cut is at most

$\displaystyle|A|\cdot\left(\frac{1}{N^{O(\epsilon^{\prime})}}^{1/\epsilon^{\prime}}\right)\leq
m\cdot\left(\frac{1}{N^{O(\epsilon^{\prime})}}\right)^{1/\epsilon^{\prime}}<1$

where, above, we applied the fact that $|A|\leq m$ (since it must be degree-
respecting). Since the demand-size of a cut is integral, it follows that for
all $h^{\prime}\leq h$ no $(h,s)$-length $\phi$-sparse cut exists and so
$\sum_{C}C$ is indeed a $(\leq h,s)$-length $\phi$-expander decomposition
(Definition 5.20).

We next consider the cut slack of this expander decomposition. Observe that
each cut $C$ that we compute in the epoch $\mathsf{epoch}$ is, by
construction, a ($(\leq h_{\mathsf{epoch}},s_{\mathsf{epoch}})$-length)
$\phi_{\mathsf{epoch}}$-sparse cut for $|A|$ and so has size at most

$\displaystyle\phi_{\mathsf{epoch}}\cdot|A|$
$\displaystyle\leq\phi\cdot\alpha_{\phi}\cdot\left(\tilde{O}(\alpha_{\phi}\cdot
s_{\mathsf{epoch}}^{3}\cdot
N^{O(1/s_{\mathsf{epoch}})})\right)^{1/\epsilon^{\prime}}\cdot|A|$
$\displaystyle\leq\phi\cdot\alpha_{\phi}\cdot\left(\tilde{O}(\alpha_{\phi}\cdot
s^{3}\cdot N^{O(1/s_{0})})\right)^{1/\epsilon^{\prime}}\cdot|A|$
$\displaystyle\leq\phi\cdot\alpha_{\phi}^{O(1/\epsilon^{\prime})}\cdot
s^{O(1/\epsilon^{\prime})}\cdot
N^{O(1/(\epsilon^{\prime}\cdot\sqrt{s}))}\cdot\left(\tilde{O}(1)\right)^{1/\epsilon^{\prime}}\cdot|A|$

Furthermore, applying the fact that, although we compute
$l=\tilde{O}(\alpha\cdot N^{O(\epsilon^{\prime})})$ total such cuts in one
iteration, the size of these cuts is geometrically increasing, so the entire
size of $\sum_{C}C$ is dominated by the sum of the cuts we compute in the last
iteration. Namely, we have

$\displaystyle\sum_{C}|C|\leq\phi|A|\cdot\left(\tilde{O}\left(\alpha\cdot
N^{O(\epsilon^{\prime})}\right)\cdot\alpha_{\phi}^{O(1/\epsilon^{\prime})}\cdot
s^{O(1/\epsilon^{\prime})}\cdot
N^{O(1/(\epsilon^{\prime}\cdot\sqrt{s}))}\cdot\left(\tilde{O}(1)\right)^{1/\epsilon^{\prime}}\right)$

giving our bound on the cut slack.

Lastly, the work and depth of our algorithm is trivial since we compute
$\tilde{O}(\frac{N^{O(\epsilon^{\prime})}}{\epsilon^{\prime}}\cdot\alpha)$-many
cuts.

∎

##  15 Algorithm: Length-Constrained EDs from “The Spiral”

We conclude by combining our algorithm which computes length-constrained
expander decompositions using demand-size-large length-constrained sparse cuts
(Lemma 14.1) with our algorithm that computes large length-constrained sparse
cuts using length-constrained expander decompositions (13.4). This forms a
“spiral” of mutual recursion where each time we go around the spiral we make
substantial progress on the size of the problem on which we are working (in
terms of node-weighting size). We first state (and prove) our result with a
maximally general tradeoff of parameters ($\epsilon$ and $\epsilon^{\prime}$).
We next simplify this presentation by choosing these parameters to get our
final theorem.

######  Theorem 15.1.

There exists an algorithm that, given edge-capacitated graph $G$, parameters
$\epsilon,\epsilon^{\prime}\in(0,1)$, node-weighting $A$ on $G$, length bound
$h$, and conductance bound $\phi>0$, computes an $(\leq h,s)$-length witnessed
$\phi$-expander decomposition for $A$ in $G$ with cut and length slack

$\displaystyle\kappa=N^{O(\epsilon^{\prime})}\cdot\tilde{O}\left(\frac{N^{O(\epsilon)}}{\operatorname{poly}(\epsilon)}\right)^{O(1/\epsilon^{\prime})}\qquad\qquad
s=(1/\epsilon)^{O(1/\epsilon^{\prime})}$

with work

$\displaystyle\textnormal{{W}}_{\textnormal{ED}}(A,m)\leq
m\cdot\tilde{O}\left(\frac{N^{O(\epsilon+\epsilon^{\prime})}}{\operatorname{poly}(\epsilon,\epsilon^{\prime})}\right)\left(\tilde{O}(1/\epsilon)^{O(1/(\epsilon\epsilon^{\prime}))}+\operatorname{poly}(h)\right).$

and depth

$\displaystyle\textnormal{{D}}_{\textnormal{ED}}(A,m)\leq\tilde{O}\left(\frac{N^{O(\epsilon+\epsilon^{\prime})}}{\operatorname{poly}(\epsilon,\epsilon^{\prime})}\right)\left(\tilde{O}(1/\epsilon)^{O(1/(\epsilon\epsilon^{\prime}))}+\operatorname{poly}(h)\right).$

###### Proof.

Applying 13.4 with $L=N^{\epsilon^{\prime}}$ we have that one can compute an
$\alpha$-approximate $(\leq h,s)$-length demand-size largest cut with sparsity
and length approximation $\alpha_{\phi}$ and $\alpha_{s}$ where

$\displaystyle\alpha=\tilde{O}\left(\frac{N^{O(\epsilon)}}{\epsilon^{3}}\right)\qquad\qquad\alpha_{\phi}=\frac{s^{3}N^{O(1/s)}}{\epsilon}\qquad\qquad\alpha_{s}=\max\left(2,\frac{1}{\epsilon^{2}}\cdot(s)^{1+O(1/\epsilon)}\right)$

with work at most

$\displaystyle\textnormal{{W}}_{\textnormal{sparse-cut}}(A,m)\leq
m\cdot\tilde{O}\left(\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}\cdot
N^{O(\epsilon)}+\frac{1}{\epsilon}\cdot
N^{O(\epsilon+\epsilon^{\prime})}\cdot\operatorname{poly}(h)\right)+\frac{1}{\epsilon}\sum_{i}\textnormal{{W}}_{\textnormal{ED}}(A_{i},m_{i})$

where $|A_{i}|\leq\frac{|A|}{N^{\epsilon^{\prime}}}$ for all $i$ and
$\\{m_{i}\\}_{i}$ are non-negative integers satisfying

$\displaystyle\sum_{i}m_{i}\leq\frac{1}{\epsilon}\cdot\tilde{O}(m+n^{1+O(\epsilon)}+N^{O(\epsilon)}).$
(47)

Likewise, applying Lemma 14.1, we have that we can compute a $(\leq
h,s)$-length $\phi$-expander decomposition for $A$ with cut slack

$\displaystyle\kappa=\tilde{O}\left(\alpha\cdot
N^{O(\epsilon^{\prime})}\right)\cdot\tilde{O}\left(\alpha_{\phi}\cdot s\cdot
N^{O(1/\sqrt{s})}\ \right)^{O(1/\epsilon^{\prime})},$

length slack

$\displaystyle s=\alpha_{s}^{O(1/\epsilon^{\prime})},$

with work

$\displaystyle\textnormal{{W}}_{\textnormal{ED}}(A,m)\leq\tilde{O}\left(\frac{N^{O(\epsilon^{\prime})}}{\epsilon^{\prime}}\cdot\alpha\right)\cdot\textnormal{{W}}_{\textnormal{sparse-
cut}}(A,m)$

where $\alpha$, $\alpha_{\phi}$ and $\alpha_{s}$ are the approximation factors
of our approximate demand-size-largest sparse cut algorithm.

We now combine the above recursions into a single recursion to compute a
$(\leq h,s_{i})$-length $\phi$-expander decomposition for $A$. We will index
each level of our recursion by $i$. Observe that at the $i$th level of our
recursion, we have that

$\displaystyle
s_{i}=\alpha_{s,i}^{O(1/\epsilon^{\prime})}=\frac{1}{\epsilon^{2}}\cdot
s_{i-1}^{1+O(1/\epsilon)}$

Furthermore, since each time we recurse we reduce our node-weighting’s size by
a multiplicative $N^{\epsilon^{\prime}}$, the depth of our recursion is at
most $1/\epsilon^{\prime}$ and so we have that $s_{i}$ is always at most

$\displaystyle
s_{i}\leq\left(\frac{1}{\epsilon}\right)^{O(1/\epsilon^{\prime})}$

It follows that our cut slack in the $i$th level of our recursion is

$\displaystyle\kappa_{i}$ $\displaystyle=\tilde{O}\left(\alpha\cdot
N^{O(\epsilon^{\prime})}\right)\cdot\tilde{O}\left(\alpha_{\phi}\cdot
s_{i}\cdot N^{O(1/\sqrt{s_{i}})}\ \right)^{O(1/\epsilon^{\prime})}$
$\displaystyle=\tilde{O}\left(\frac{N^{O(\epsilon+\epsilon^{\prime})}}{\operatorname{poly}(\epsilon)}\right)\cdot\tilde{O}\left(\frac{s_{i}^{3}N^{O(1/s_{i})}}{\epsilon}\cdot
s_{i}\cdot N^{O(1/\sqrt{s_{i}})}\ \right)^{O(1/\epsilon^{\prime})}$
$\displaystyle=\tilde{O}\left(\frac{N^{O(\epsilon+\epsilon^{\prime})}}{\operatorname{poly}(\epsilon)}\right)\cdot\tilde{O}\left(\frac{1}{\operatorname{poly}(\epsilon)}\cdot
N^{O(1/s_{i}+1/\sqrt{s_{i}})}\right)^{O(1/\epsilon^{\prime})}$
$\displaystyle=N^{O(\epsilon^{\prime})}\cdot\tilde{O}\left(\frac{N^{O(\epsilon)}}{\operatorname{poly}(\epsilon)}\right)^{O(1/\epsilon^{\prime})}.$

where in the last line we used the fact that $1/\sqrt{s_{i}}+1/s_{i}\geq
1/\epsilon$ for every value of $s_{i}$ we consider.

We next bound the work of our algorithm. Letting $m_{j}$ be the total number
of edges at the $j$th level of our recursion and applying our bound on
$\sum_{i}m_{i}$ from Equation 47 we have

$\displaystyle
m_{j+1}\leq\frac{1}{\epsilon}\cdot\tilde{O}(m_{j}+n^{1+O(\epsilon)}+N^{O(\epsilon)})$

Applying the fact that our recurrence has depth at most $1/\epsilon^{\prime}$,
we get that the maximum number of edges across an entire level of recursion
$j$ is at most

$\displaystyle m_{j}$ $\displaystyle\leq
m\cdot\tilde{O}\left(\frac{1}{\epsilon}\right)^{1/\epsilon^{\prime}}+\frac{1}{\epsilon^{\prime}}\left(n^{1+O(\epsilon)}+N^{O(\epsilon)}\right)$
$\displaystyle=m\cdot\tilde{O}\left(\frac{1}{\epsilon}\right)^{1/\epsilon^{\prime}}+\frac{N^{O(\epsilon)}}{\epsilon^{\prime}}$
(48)

where, above, $m$ is the number of edges in our original graph. On the other
hand, we have that (apart from the recursive calls), the entire work of our
algorithm at a single level of recursion is at most

$\displaystyle m_{j}\cdot\tilde{O}\left(\frac{\alpha\cdot
N^{O(\epsilon^{\prime})}}{\epsilon^{\prime}}\right)\left(\frac{1}{\epsilon}\cdot(s)^{O(1/\epsilon)}\cdot
N^{O(\epsilon)}+\frac{1}{\epsilon}\cdot
N^{O(\epsilon+\epsilon^{\prime})}\cdot\operatorname{poly}(h)\right)$
$\displaystyle\leq
m_{j}\cdot\tilde{O}\left(\frac{N^{O(\epsilon+\epsilon^{\prime})}}{\operatorname{poly}(\epsilon,\epsilon^{\prime})}\right)\left((s)^{O(1/\epsilon)}+\operatorname{poly}(h)\right)$
$\displaystyle\leq
m_{j}\cdot\tilde{O}\left(\frac{N^{O(\epsilon+\epsilon^{\prime})}}{\operatorname{poly}(\epsilon,\epsilon^{\prime})}\right)\left((1/\epsilon)^{O(1/(\epsilon\epsilon^{\prime}))}+\operatorname{poly}(h)\right)$
(49)

Combining Section 15 and Section 15 we get that the total work on a single
level of recursion (again, excluding recursive calls) is at most

$\displaystyle\left(m\cdot\tilde{O}\left(\frac{1}{\epsilon}\right)^{1/\epsilon^{\prime}}+\frac{N^{O(\epsilon)}}{\epsilon^{\prime}}\right)\cdot\tilde{O}\left(\frac{N^{O(\epsilon+\epsilon^{\prime})}}{\operatorname{poly}(\epsilon,\epsilon^{\prime})}\right)\left((1/\epsilon)^{O(1/(\epsilon\epsilon^{\prime}))}+\operatorname{poly}(h)\right)$
$\displaystyle=m\cdot\tilde{O}\left(\frac{N^{O(\epsilon+\epsilon^{\prime})}}{\operatorname{poly}(\epsilon,\epsilon^{\prime})}\right)\left(\tilde{O}(1/\epsilon)^{O(1/(\epsilon\epsilon^{\prime}))}+\operatorname{poly}(h)\right)$

Summing over our $1/\epsilon^{\prime}$-many recursive levels of our algorithm
then gives our work bound. The argument for depth is analogous (and, in fact,
easier because we do not have to control the total number of edges over each
level of recursion using Equation 47).

∎

Lastly, we give the simplified version of the above theorem with witnesses.

See 1.1

###### Proof.

We first apply Theorem 15.1 with $\epsilon^{\prime}_{0}=\epsilon$ and
$\epsilon_{0}=\epsilon^{2}$ where $\epsilon^{\prime}_{0}$ and $\epsilon_{0}$
are the parameters described in Theorem 15.1. Likewise, let $c$ be an upper-
bound on the exponent of the poly-log in the $\tilde{O}$ notations and the
exponent of all $\operatorname{poly}$ notation of Theorem 15.1. It follows
that we can compute a $(\leq h,s)$-length $\phi$-expander decomposition for
$A$ in $G$ with cut and length slack

$\displaystyle\kappa=\frac{N^{O(\epsilon)}}{(\epsilon)^{c\cdot
O(1/\epsilon)}}\cdot\log^{c\cdot O(1/\epsilon)}N\qquad\qquad
s=(1/\epsilon^{2})^{O(1/\epsilon)}$

with work

$\displaystyle\textnormal{{W}}_{\textnormal{ED}}(A,m)\leq
m\cdot\tilde{O}\left(\frac{N^{O(\operatorname{poly}(\epsilon))}}{\operatorname{poly}(\epsilon)}\right)\left((1/\epsilon)^{O(1/\epsilon^{3})}\cdot\log^{c\cdot
O(1/\epsilon)}N+\operatorname{poly}(h)\right).$

and depth

$\displaystyle\textnormal{{D}}_{\textnormal{ED}}(A,m)\leq\tilde{O}\left(\frac{N^{O(\operatorname{poly}(\epsilon))}}{\operatorname{poly}(\epsilon)}\right)\left((1/\epsilon)^{O(1/\epsilon^{3})}\cdot\log^{c\cdot
O(1/\epsilon)}N+\operatorname{poly}(h)\right).$

We begin by reasoning about our cut slack. Notice that, for a suitable large
hidden constant in the $\Omega$ we have that if

$\displaystyle\epsilon\geq\Omega\left(\sqrt{\frac{c\cdot\log\log n}{\log
N}}\right)$

then we have that

$\displaystyle\frac{c\cdot O(1/\epsilon)\cdot\log\log N}{\log N}\leq\epsilon$
(50)

Similarly, we have that if

$\displaystyle\epsilon\geq\Omega\left(\left({\frac{c}{\log
n}}\right)^{1/3}\right)$

then

$\displaystyle\frac{\log(1/\epsilon)\cdot c\cdot O(1/\epsilon)}{\log
N}\leq\frac{c\cdot O(1/\epsilon^{2})}{\log N}\leq\epsilon$

Thus, our cut slack is

$\displaystyle\kappa=N^{O(\epsilon)+\frac{c\cdot O(1/\epsilon)\cdot\log\log
N}{\log N}+\frac{\log(1/\epsilon)\cdot c\cdot O(1/\epsilon)}{\log N}}\leq
N^{O(\epsilon)}$

Likewise, our length slack is

$\displaystyle
s=(1/\epsilon^{2})^{O(1/\epsilon)}=\exp(O(1/\epsilon)\cdot\log(1/\epsilon^{2}))\leq\exp(O(1/\epsilon^{2}))=\exp(\operatorname{poly}(1/\epsilon)).$

Lastly, observe that if

$\displaystyle\epsilon\geq\Omega\left(\frac{1}{\log N}\right)^{(1/5)}$

and

$\displaystyle\epsilon\geq\Omega\left(\log\log n/\log n\right)$

then we have

$\displaystyle\frac{O(1/\epsilon^{3})\cdot\log(1/\epsilon)}{\log
N}+\frac{c\cdot O(1/\epsilon)\cdot\log\log N}{\log
N}\leq\frac{O(1/\epsilon^{4})}{\log N}+\frac{O(1/\epsilon)\cdot\log\log
N}{\log N}\leq O(\epsilon)$

and so our work is

$\displaystyle\textnormal{{W}}_{\textnormal{ED}}(A,m)$ $\displaystyle\leq
m\cdot\tilde{O}\left(\frac{N^{O(\operatorname{poly}(\epsilon))}}{\operatorname{poly}(\epsilon)}\right)\left((1/\epsilon)^{O(1/\epsilon^{3})}\cdot\log^{c\cdot
O(1/\epsilon)}N+\operatorname{poly}(h)\right)$
$\displaystyle=m\cdot\tilde{O}\left(\frac{N^{O(\operatorname{poly}(\epsilon))}}{\operatorname{poly}(\epsilon)}\right)\left(N^{\frac{O(1/\epsilon^{3})\cdot\log(1/\epsilon)}{\log
N}+\frac{c\cdot O(1/\epsilon)\cdot\log\log N}{\log
N}}+\operatorname{poly}(h)\right)$
$\displaystyle=m\cdot\tilde{O}\left(\frac{N^{O(\operatorname{poly}(\epsilon))}}{\operatorname{poly}(\epsilon)}\right)\left(N^{O(\epsilon)}+\operatorname{poly}(h)\right)$
$\displaystyle=m\cdot\tilde{O}\left(\frac{N^{O(\operatorname{poly}(\epsilon))}}{\operatorname{poly}(\epsilon)}\right)\cdot\operatorname{poly}(h)$
$\displaystyle\leq
m\cdot\tilde{O}\left(N^{O(\operatorname{poly}(\epsilon))}\cdot\operatorname{poly}(h)\right)$

Where in the last line we used the fact that $\epsilon\geq 1/\log^{O(1)}N$.
The final result comes from letting $\epsilon$ above be smaller by a suitable
large constant (to get the cut slack from $N^{O(\epsilon)}$ to
$n^{\epsilon}$). Our depth bound is symmetric.

Lastly, we discuss how to compute our witness. The basic idea is to slightly