# New Structures and Algorithms for
Length-Constrained Expander Decompositions

Bernhard Haeupler D Ellis Hershkowitz Zihan Tan ETH Zürich & Brown University
DIMACS, Carnegie Mellon University Rutgers University

###### Abstract

Expander decompositions form the basis of one of the most flexible paradigms
for close-to-linear-time graph algorithms. Length-constrained expander
decompositions generalize this paradigm to better work for problems with
lengths, distances and costs. Roughly, an $(h,s)$-length $\phi$-expander
decomposition is a small collection of length increases to a graph so that
nodes within distance $h$ can route flow over paths of length $hs$ with
congestion at most $1/\phi$.

In this work, we give a close-to-linear time algorithm for computing length-
constrained expander decompositions in graphs with general lengths and
capacities. Notably, and unlike previous works, our algorithm allows for one
to trade off off between the size of the decomposition and the length of
routing paths: for any $\epsilon>0$ not too small, our algorithm computes in
close-to-linear time an $(h,s)$-length $\phi$-expander decomposition of size
$m\cdot\phi\cdot n^{\epsilon}$ where
$s=\exp(\operatorname{poly}(1/\epsilon))$. The key foundations of our
algorithm are: (1) a simple yet powerful structural theorem which states that
the union of a sequence of sparse length-constrained cuts is itself sparse and
(2) new algorithms for efficiently computing sparse length-constrained flows.

###### Contents

  1. 1 Introduction
    1. 1.1 Length-Constrained Expanders and Expander Decompositions
    2. 1.2 Our Contributions
      1. 1.2.1 Overcoming Challenge 1: Union of Sparse Length-Constrained Cuts is Sparse
      2. 1.2.2 Overcoming Challenge 2: Sparse Flows for the Spiral
  2. 2 Applications of Our Work
  3. 3 Additional Related Work
    1. 3.1 Applications of Expander Decompositions
    2. 3.2 Parallel Work on Well-Connected Graphs
    3. 3.3 Routing in Expanders
  4. 4 Notation and Conventions
  5. 5 Preliminaries
    1. 5.1 Classic Expanders and Expander Robustness
    2. 5.2 Length-Constrained Cuts (Moving Cuts)
    3. 5.3 Length-Constrained Expanders
    4. 5.4 At Most Length-Constrained Expanders
    5. 5.5 Length-Constrained Expander Decompositions
    6. 5.6 Routers, Power Graphs and Expander Power Graph Robustness
    7. 5.7 Neighborhood Covers
    8. 5.8 Length-Constrained Expansion Witnesses
  6. 6 Main Result Restated: Length-Constrained ED Algorithm
  7. 7 Length-Constrained Expanders as Embedded Expander Powers
    1. 7.1 Formalizing the Embedding via the Neighborhood Router Demand
    2. 7.2 Proving Length-Constrained Expanders are Embedded Expander Powers
  8. 8 Robustness of Length-Constrained Expanders
  9. 9 Union of Sparse (Classic) Cut Sequence is Sparse
    1. 9.1 Warmup: When the Source Component is Not a Witness Component
    2. 9.2 Proving the General Case for (Classic) Cuts
  10. 10 Union of Sparse Moving Cut Sequence is Sparse
    1. 10.1 Low Arboricity Demand Matching Graph via Parallel Greedy Spanners
    2. 10.2 Matching-Dispersed Demand
    3. 10.3 Proving Union of Sparse Moving Cuts is a Sparse Moving Cut
  11. 11 Equivalence of Distances to Length-Constrained Expander
    1. 11.1 Weighted Sparse Cut Sequence () at Most Largest Cut ()
    2. 11.2 Largest Cut () at Most Largest Expander’s Complement ()
      1. 11.2.1 Projected Down Demands
      2. 11.2.2 Proof Of Largest Cut At Most Largest Expander’s Complement
    3. 11.3 Largest Expander’s Complement () at Most Weighted Sparse Cut Sequence ()
    4. 11.4 Largest Expander’s Complement () at Most Smallest Expander Decomposition ()
    5. 11.5 Largest Cut () at Most Largest Cut Sequence ()
    6. 11.6 Largest Cut Sequence () at Most Largest Weighted Cut Sequence ()
    7. 11.7 Smallest Expander Decomposition () at Most Largest Cut Sequence ()
    8. 11.8 Proof of Equivalence of Distance Measures (11.1)
  12. 12 Algorithm: Sparse Flows and Cutmatches
    1. 12.1 Rounding Flows to Blaming Flows
    2. 12.2 Blaming Flow Sequences
    3. 12.3 Blaming Near-Lightest Path Blockers
    4. 12.4 Sparse Flows and Cutmatches via Blaming Near-Lightest Path Blockers
  13. 13 Algorithm: Demand-Size-Large Sparse Cuts from EDs
    1. 13.1 (Preliminary) Algorithm: Cut Strategies from Expander Decompositions
    2. 13.2 Algorithm: Demand-Size-Large Sparse Cuts from Cut Strategies
  14. 14 Algorithm: EDs from Demand-Size-Large Sparse Cuts
  15. 15 Algorithm: Length-Constrained EDs from “The Spiral”
  16. 16 Maintaining Extra Properties (1.1 with Linkedness)
    1. 16.1 Proof of Theorem 16.1
    2. 16.2 Achieving Linkedness in 1.1

##  1 Introduction

Over the past few decades, expander decompositions have come to form the
foundation of one of the most powerful and flexible paradigms for close-to-
linear-time algorithms [CGL+20, vdBLN+20, Li21, SW19]. Informally, expander
decompositions separate a graph into expanders, allowing algorithms to make
use of the structure of expanders on arbitrary graphs. One of the key
properties of expanders—and, indeed, a way in which they are often defined— is
that any (reasonable) multi-commodity flow demand can be routed with low
congestion [GKS17, GL18, GRST21, BFU92, PU87, KR96, Val90, LR99, LMR94].
However, while this property makes the expander decomposition paradigm very
useful for algorithms dealing with flows, congestion and cuts, it is less
useful for quantities like lengths, distances and costs.

###  1.1 Length-Constrained Expanders and Expander Decompositions

Motivated by this, [HRG22] introduced the idea of length-constrained
expanders. Informally, a length-constrained expander is a graph in which any
(reasonable) multi-commodity flow can be routed over _short_ paths. More
formally, a demand $D:V\times V\to\mathbb{Z}_{\geq 0}$ is _$h$ -length_ if
$D(u,v)>0$ implies that $u$ and $v$ are at distance at most $h$ and _unit_ if
no vertex sends or receives more than its degree in demand. Then, an
$(h,s)$-length $\phi$-expander is a graph where any $h$-length unit demand can
be routed by a multi-commodity flow with congestion
$\tilde{O}(\frac{1}{\phi})$ _over length $hs$-length paths_. $s$ is called the
_length slack_. If $hs\ll O(\frac{\log n}{\phi})$, a graph which is an
$(h,s)$-length $\phi$-expander may not be a $\phi$-expander. For example, a
path is an $(h,1)$-length $\Omega(1)$-expander for constant $h$ but not an
$\Omega(1)$-expander; henceforth, we use _classic expander_ to refer to (non-
length-constrained) expanders.

In order to better bring the expander decomposition machinery to bear on
problems that deal with lengths, distances and costs, [HRG22] introduced the
idea of an $(h,s)$-length $\phi$-expander decomposition: a collection of
$(\kappa\cdot\phi m)$ total edge length increases that make the input graph an
$(h,s)$-length $\phi$-expander. Here, $\kappa$ is called the _cut slack_.

Length-constrained expander decompositions greatly extend the problems for
which the expander decomposition paradigm is suitable. For instance, length-
constrained expander decompositions give a simple tree-like way of routing
demands that is $n^{o(1)}$-competitive with respect to _both_ congestion and
flow path length [HRG22]. Furthermore, these routings are oblivious: the flow
for each pair is fixed without knowledge of the demand. In turn, these
routings give (1) compact routing tables that allow nodes to perform
$n^{o(1)}$-competitive point-to-point communication and (2) universally-
optimal distributed algorithms in the CONGEST model of distributed
computation, bypassing $\Omega(\sqrt{n}/\log n)$ lower bounds [PR00, DSHK+11]
on networks with $n^{o(1)}$ time algorithms.

###  1.2 Our Contributions

In this work, we provide a deeper theory of length-constrained expanders and
significantly more powerful close-to-linear time algorithms for computing
length-constrained expander decompositions.

We begin by describing our new algorithm for computing length-constrained
expander decompositions. Our algorithm is based on the notion of
$(h,s)$-length $\phi$-sparse cuts which generalizes the classic notion of
$\phi$-sparse cuts (a.k.a. moving cuts) [HRG22]. An $(h,s)$-length
$\phi$-sparse cut is a collection of length increases such that there is a
large $h$-length unit “witness” demand whose support pairs are made at least
$hs$-far apart by these length increases. Our algorithm will simply repeatedly
cut length-constrained sparse cuts where “cutting” such a cut just consists of
applying its length increases to the graph.111For the case of length-
constrained expanders, “cutting” necessarily involves increasing lengths
(possibly fractionally) rather than (integrally) deleting edges since the
length-constrained setting is known to exhibit large flow-cut integrality gaps
[HWZ20].

It is known that a graph is a length-constrained expander iff it contains no
length-constrained sparse cuts [HRG22] and so, if one repeatedly cuts
$(h,s)$-length $\phi$-sparse cuts until none exist, the union of all such cuts
gives a length-constrained expander decomposition. Of course, if these cuts
are always very small in size (e.g. only a single edge has its length
increased) then such an algorithm would have no hope of running in close-to-
linear time. In order to avoid this, we require that our cuts be
(approximately) largest among all length-constrained sparse cuts (for a
suitable notion of “large”). Summarizing, we have the following (conceptually
simple) rough outline of our algorithm:

> Until none exist:
> Cut a $(\approx h,\approx s)$-length $(\approx\phi)$-sparse (approximately)
> largest cut.

The only technical caveat to the above outline is what is hidden by the
“$\approx$”s above. Specifically, our algorithm proceeds in epochs in order to
deal with the slacks that occur in the length-constrained setting where after
each epoch we relax the cuts we look for by appropriately increasing the
length slack $s$ and decreasing the length $h$ and sparsity $\phi$. A more
formal version of the above algorithm is given in Algorithm 2.

Appropriately instantiating the above approach gives us the main result of our
work. We state the formal result below; some of the precise definitions are
left to Sections 4 and 5. Informally, though, the “node-weighting” $A$
specifies the subset of our graph we would like to be $(h,s)$-length expanding
and our decomposition is “witnessed” in the sense that it comes with an
embedding which shows how to route with low congestion over low length paths
in the graph after applying the decomposition. We discuss $(\leq h,s)$-length
below and make use of standard work-depth models of parallel computation (see,
e.g. [Ble96]); for sequential algorithms work is equivalent to time.

######  Theorem 1.1.

There is a constant $c>1$ such that given graph $G$ with edge lengths and
capacities, $\epsilon\in\left(\frac{1}{\log^{1/c}N},1\right)$, node-weighting
$A$, length bound $h\geq 1$, and conductance $\phi>0$, one can compute a
witnessed $(\leq h,s)$-length $\phi$-expander decomposition for $A$ in $G$
with cut and length slack respectively

$\displaystyle\kappa=n^{\epsilon}\qquad\qquad
s=\exp(\operatorname{poly}(1/\epsilon))$

and work and depth respectively

$\displaystyle\textnormal{{W}}_{\textnormal{ED}}(A,m)\leq
m\cdot\tilde{O}\left(n^{O(\operatorname{poly}(\epsilon))}\cdot\operatorname{poly}(h)\right)\qquad\textnormal{{D}}_{\textnormal{ED}}(A,m)\leq\tilde{O}\left(n^{O(\operatorname{poly}(\epsilon))}\cdot\operatorname{poly}(h)\right).$

The above improves over the previous algorithms for length-constrained
expander decompositions of [HRG22] in several major ways.222We also note that
our algorithm is considerably conceptually simpler than that of [HRG22] which
relied on an intricate “expander gluing” framework.

  1. 1.

Trading Off Between Slacks: Our algorithm allows one to trade off between
length slack and cut slack. In particular, by increasing the cut slack
$\kappa$, one can decrease the length slack $s$ and vice-versa. Notably, for
suitably small constant parameter, the above allows us to achieve length slack
$s=O(1)$ and cut slack $N^{\epsilon}$ in work
$m^{1+\epsilon}\cdot\operatorname{poly}(h)$ and depth
$m^{\epsilon}\cdot\operatorname{poly}(h)$ for any small constant $\epsilon$.
The previous approach of [HRG22] computed length-constrained expander
decompositions with $\kappa=s=\exp(\log^{1-\delta}n)$ for a fixed $\delta$
slightly less than $1$ and so could not produce such decompositions.
Crucially, all of the applications of our results (discussed in Section 2)
will make use of a constant length slack of $s=O(1)$.

  2. 2.

General Lengths and Capacities: Our algorithm is the first (close-to-linear
time) algorithm for computing length-constrained expander decompositions on
graphs with general lengths and general edge lengths. The algorithm of [HRG22]
only worked if one assumed that both the capacity and length of every edge is
$1$. Even in the classic setting, efficient algorithms for expander
decompositions for general capacities are significantly more difficult than
those in the unit capacity setting [Li21]. All of our applications will make
use of general lengths and capacities and implementing the above approach for
general lengths and capacities—particularly, for general capacities—presents
significant difficulties; discussed below.

  3. 3.

Stronger Routing Guarantees: The routing guarantees provided by our algorithm
are significantly stronger than those of [HRG22] in two ways. First, our
decomposition is what we call a $(\leq h,s)$-length expander decomposition (as
opposed to an $(h,s)$-length expander decomposition). In particular, after
applying our decomposition we provide the guarantee that any $h$-length demand
can be routed by a low congestion multi-commodity flow where the flow paths
between vertices $u$ and $v$ at distance $d\leq h$ have length at most $d\cdot
s$ as opposed to $h\cdot s$ as in $(h,s)$-length expander decompositions.
Notably, if $d\ll h$ (i.e. the two vertices are very close initially) then we
route between $u$ and $v$ over paths whose length is proportional to $d$
rather than proportional to $h$.

Second, the expander decomposition output by our algorithm is “strong” in the
sense that after applying the decomposition to graph $G$ to get $G^{\prime}$,
any $h$-length demand in $G^{\prime}$ can be routed with low congestion over
low-length paths in $G^{\prime}$; that of [HRG22] was “weak” in that
$h$-length demands could only be routed over low-length paths _in $G$_.

Showing that the above approach works requires overcoming two significant
challenges:

> Challenge 1: How can we show that cutting large length-constrained sparse
> cuts
> quickly yields a length-constrained expander decomposition?

and

> Challenge 2: How can we efficiently compute large length-constrained sparse
> cuts?

In what follows, we discuss these challenges and how we overcome them.

####  1.2.1 Overcoming Challenge 1: Union of Sparse Length-Constrained Cuts is
Sparse

We discuss how we show that cutting large length-constrained sparse cuts
quickly yields a length-constrained expander decomposition.

##### The Classic Approach.

Repeatedly cutting large sparse cuts in order to compute classic expander
decompositions is a well-studied approach [SW19]. In the classic setting the
“largness” of a cut is its balance, namely, the volume of the side of the cut
with smaller volume.333The volume of a set of vertices is the sum of their
degrees.

In the classic setting, this approach hinges on the fact that the “union of
sparse cuts is itself a sparse cut.” In particular, if $C_{1},C_{2},\ldots$
are a series of cuts where each $C_{i}$ is a $\phi$-sparse cut after $C_{j}$
for $j<i$ has been cut, then $\bigcup_{i}C_{i}$ is itself a $O(\log
n\cdot\phi)$-sparse cut.

Thus, if each $C_{i}$ is a $\phi$-sparse cut whose size is within an $\alpha$
factor of the largest $O(\log n\cdot\phi)$-sparse cut and we cut about
$\alpha$ of these cuts then we know that after cutting all of these cuts we
must have substantially reduced the size of the largest $O(\log
n\cdot\phi)$-sparse cut (otherwise $\bigcup_{i}C_{i}$ would be a $O(\log
n\cdot\phi)$-sparse cut whose size is larger than the largest such cut).

The above union of cuts fact in the classic setting is easily shown. In
particular, because we are measuring the size of the cut in terms of the
smaller volume side and each time we apply a cut the smaller volume side has
at most half of the total volume, we get a depth of $O(\log n)$, leading to
the $O(\log n)$ in the above sparsity. In the interest of completeness, we
give a proof of this fact in Section 9.

##### Issues in the Length-Constrained Setting.

However, showing a comparable fact for the length-constrained setting is
significantly more challenging. In particular, there is no clear notion of the
“side” of a cut in the length-constrained setting since we are applying length
increases, not fully deleting edges. Thus, a proof of the sparsity of the
union of sparse length-constrained cuts cannot appeal to a tidy recursion
where each time one recurses, one side of the cut reduces by a constant.
Further, it is not even clear what the appropriate notion of the “size” of a
cut is in this setting since, again, there is no “smaller side” whose volume
we can measure.

In fact, given the definition of an $(h,s)$-length $\phi$-sparse cut, one
might not think that the union of a sequence of $(h,s)$-length $\phi$-sparse
cuts should be sparse. In particular, recall that an $(h,s)$-length cut
$C_{i}$ is $\phi$-sparse iff there is some large witnessing demand $D_{i}$
that is $h$-length and unit such that after $C_{i}$ is applied every pair in
the support of $D_{i}$ is at least $hs$-far apart. However, if we take the
union of $(C_{1},C_{2},\ldots)$ as $C_{1}+C_{2}+\ldots$, then we cannot
witness the sparsity of $C_{1}+C_{2}+\ldots$ by $D_{1}+D_{2}+\ldots$: the
resulting demand can be arbitrarily far from being unit!

##### Result.

Nonetheless, for the length-constrained setting we show that, somewhat
surprisingly, the union of a sequence of $(h,s)$-length $\phi$-sparse cuts is
itself an $(h,s)$-length $O(\phi\cdot n^{O(1/s)})$-sparse cut (with some slack
in $h$ and $s$). More generally, we show that, the union of cuts in a sequence
of length-constrained sparse cuts is at least as sparse as the (appropriately-
weighted) average sparsity of its constituent cuts. The following gives our
formal result (we again defer some of the technical definitions to later
sections).

######  Theorem 1.2 (Union of Sparse Moving Cuts is a Sparse Moving Cut).

Let $(C_{1},\ldots,C_{k})$ be a sequence of moving cuts where $C_{i}$ is an
$(h,s)$-length $\phi_{i}$-sparse cut in $G-\sum_{j<i}C_{j}$ w.r.t. node-
weighting $A$. Then the moving cut $\sum_{i}C_{i}$ is an
$(h^{\prime},s^{\prime})$-length $\phi^{\prime}$-sparse cut w.r.t. $A$ 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\frac{\sum_{i}|C_{i}|}{\sum_{i}|C_{i}|/\phi_{i}}$.

##### Techniques.

Our result for the length-constrained setting is based on an intriguing
connection to parallel algorithms for greedy spanner constructions. In
particular, we show that the witnessing demands in a sequence of
$(h,s)$-length $\phi$-sparse cuts are analogous to a parallel process for
greedily computing a spanner. Recent work [HHT23] showed that such parallel
processes produce a graph with low—namely about $n^{O(1/s)}$—arboricity. We
then make use of the low arboricity of such graphs to decompose the demands of
a sequence of length-constrained sparse cuts into forests and then use each
tree in this forest to “disperse” the corresponding demand. The result is a
demand that can be used to witness the sparsity of the union of
$(C_{1},C_{2},\ldots)$: in particular, it is of approximately the same size as
the sum of the $D_{i}$ and still separated by the union of
$(C_{1},C_{2},\ldots)$ but it is actually unit, unlike the sum of the $D_{i}$.
These results are discussed in Section 10.

By making use of the above union of cuts fact for the length-constrained
setting and defining an appropriate notion of the size of a length-constrained
cut—a notion we call the “demand-size” of a cut—we are able to extend the
above approach to the length-constrained setting. In particular, we show that
that repeatedly cutting an $(h,s)$-length $\phi$-sparse cut which is
approximately demand-size-largest quickly yields a length-constrained expander
decomposition.

####  1.2.2 Overcoming Challenge 2: Sparse Flows for the Spiral

Having discussed how it suffices to show that repeatedly cutting large and
sparse length-constrained cuts quickly yields a length-constrained expander,
we now discuss how to compute these cuts.

##### Classic Approach.

In the classic setting, a well-studied means of cutting large sparse cuts is
by what we call “the spiral.” In particular, it is known that one can compute
large sparse cuts using “cut matching games.” Cut matching games, in turn, can
be efficiently computed by computing expander decompositions. By the above-
mentioned arguments, expander decompositions can be computed using large
sparse cuts. In order to avoid a cycle of dependencies, one turns this cycle
into a “spiral.” In particular, the algorithm is set up so that each time one
goes around the cycle of dependencies the input size significantly decreases.

##### Issues in the Length-Constrained Setting.

A recent work of [HHG22] provided a cut matching game that is suitable for our
purposes and so, in light of our discussion above, one might hope to implement
a similar approach in the length-constrained setting. However, here, the fact
that we are interested in general capacities significantly complicates our
problem.

In particular, in the spiral we recurse on graphs produced by cut matching
games. Each edge of these graphs, in turn, corresponds to a flow path in the
flow decomposition of a flow we computed on our input graph. Thus, if we want
to guarantee that when we recurse the input size has significantly gone down,
it must be the case that the flows we construct for our cut matching game have
low support size; i.e. the flow can be decomposed into a small number of flow
paths.

This is easy to do in the classic setting but, to our knowledge, prior to our
work no such result was known for the length-constrained setting for general
capacities. In the length-constrained setting, the relevant notion of flow is
$h$-length flows (i.e. flows whose flow paths have length at most $h$). Prior
work [HHS23] showed that one can compute $h$-length multi-commodity flows but
with support size $\tilde{O}\left(b\cdot\operatorname{poly}(h)\cdot m\right)$
where, roughly, $b$ is the number of commodities. Using this result would lead
to a multiplicative blowup of $\operatorname{poly}(h)$ in the total number of
edges of our graphs which, unfortunately, cannot be made to work with the
spiral.

##### Result.

To solve the above issue, we give the first sparse flow algorithms for the
length-constrained setting, improving the above sparsity to $\tilde{O}(|E|+b)$
and, notably, so that it does not depend on $h$. Specifically, we show the
following (again, see later sections for relevant technical definitions).

######  Theorem 1.3.

Given a graph $G=(V,E)$ with capacities $U$, lengths $\ell$, length constraint
$h\geq 1$, $0<\epsilon<1$ and $b$-batchable source, sink pairs
$\\{(S_{i},T_{i})\\}_{i}$, one can compute a feasible $h$-length flow cut pair
$(F,C)$ of $\\{(S_{i},T_{i})\\}_{i}$ that is $(1\pm\epsilon)$-approximate in
(deterministic) depth
$\tilde{O}(b\cdot\operatorname{poly}(\frac{1}{\epsilon},h))$ and work
$m\cdot\tilde{O}(b\cdot\operatorname{poly}(\frac{1}{\epsilon},h))$ where

$\displaystyle|\mathrm{supp}(F)|\leq\tilde{O}(|E|+b).$

Furthermore, $F=\eta\cdot\sum_{j=1}^{k}F_{j}$ where
$\eta=\tilde{\Theta}(\epsilon^{2})$,
$k=\tilde{O}\left(\kappa\cdot\frac{h}{\epsilon^{4}}\right)$ and $F_{j}$ is an
integral $h$-length $S_{i}$-$T_{i}$ flow for some $i$.

##### Techniques.

In order to show the above result, we make use of a novel “blaming” argument.
The rough idea is to construct a near-optimal flow where each path in the
support of the flow can uniquely point to an edge whose capacity was mostly
used up when flow along this flow path was added to our solution. We discuss
and prove the above result in Section 12.

Combining the above flow algorithms with the spiral and our union of cuts fact
shows that the above strategy quickly yields a length-constrained expander
decomposition. As a corollary, we get efficient algorithms for large length-
constrained sparse cuts (since these algorithms form a sub-routine of the
spiral). While we feel the above are the main contributions of our work, we
note that building up to them requires developing several new ideas and
techniques for the length-constrained setting, including proofs of the
robustness of length-constrained expanders to edge deletions and the
equivalence of several notions of a graph’s “distance” from being a length-
constrained expander.

##  2 Applications of Our Work

In this section we discuss applications of our work; both those in subsequent
work and some corollaries of our results. We note that the first two results
directly use the algorithms from this work.

##### Application 1: $O(1)$-Approx. MC Flow in Close-To-Linear Time
(Subsequent Work).

A recent work of [HHL+24] gave the first close-to-linear time algorithms to
compute an $O(1)$-approximate $k$-commodity flow in almost-linear-time. These
algorithms run in time $O((m+k)^{1+\epsilon})$ for arbitrarily small constant
$\epsilon>0$ [HHL+24]. Roughly speaking, these algorithms make use of the
“boosting” framework of Garg and Könemann [GK07] wherein solving multi-
commodity flow is, by way of multiplicative-weights-type techniques, reduced
to problems on graphs with arbitrary capacities and lengths. Thus, the fact
that our algorithms work for arbitrary capacities and lengths are crucial for
this later work. Likewise, this work also makes use of our sparse flow
algorithms. Lastly, we note that this work uses the fact that our algorithms
can output length-constrained expander decompositions with $s=O(1)$ to compute
“low-step multi-commodity flow emulators” which are, roughly, low-diameter
graphs which represent all multi-commodity flows.

##### Application 2: Distance Oracles (Subsequent Work)

Another recent work [HLS24] makes use of our algorithms for length-constrained
expander decompositions to give new distance oracle results. Specifically,
this work shows that in a graph with general edge lengths one can maintain a
data structure with $n^{\epsilon}$ worst-case update time which can answer
distance queries between vertices that are $\exp(1/\epsilon)$-approximate in
$\operatorname{poly}(1/\epsilon)\cdot\log\log n$ time. Crucially, this work
makes use of the fact that our algorithms for length-constrained expander
decompositions can trade off between cut and length slack (the $\epsilon$ in
their work and ours are roughly analogous). The previous best result along
these lines is that of Chuzhoy and Zhang [CZ23] which gave a $(\log\log
n)^{2^{O(1/\epsilon^{3})}}$-approximate fully-dynamic deterministic all-pair-
shortest-path distance oracle with _amortized_ $n^{\epsilon}$ update time
using the below-mentioned well-connected graphs.

##### Application 3: Capacitated Length-Constrained Oblivious Routing.

Lastly, we note that we obtain the first close-to-linear time algorithms for
length-constrained oblivious routing on graphs with general capacities (with
constant length slack). Specifically, in length-constrained oblivious routing
the goal is to fix for each pair of vertices a flow over $h^{\prime}$-length
paths so that for any demand the induced flow is always congestion-competitive
with the minimum congestion flow over $h$-length paths routing this demand. We
refer to $h^{\prime}/h$ as the length competitiveness of such a routing
scheme. [GHZ21] proved the existence of length-constrained oblivious routing
schemes that simultaneously achieve $\operatorname{poly}\log n$ length and
congestion competitiveness (not using length-constrained expander
decompositions). However, this result did not provide an efficient algorithm
for computing such a scheme. [HRG22] addressed this by observing that one can
use length-constrained expander decompositions to compute length-constrained
oblivious routing schemes in time $m^{1+o(1)}$ that simultaneously achieve
$n^{o(1)}$ length and congestion competitiveness.

Applying the techniques of [HRG22] and our algorithms for length-constrained
expander decompositions, it follows that for any $\epsilon>0$ (not too small
as in 1.1) one can compute in time $m^{1+\epsilon}$ an oblivious length-
constrained routing scheme that achieves length and congestion slack
$\exp(\operatorname{poly}(1/\epsilon))$ and $n^{O(\epsilon)}$ respectively.
Note that setting $\epsilon=1/\sqrt{\log n}$ generalizes the [HRG22]. More
importantly, since our algorithms for length-constrained expander
decompositions work for the general capacities case, so too do our oblivious
routing schemes unlike those of [HRG22]. Furthermore, if $\epsilon=O(1)$ then
we achieve constant length competitiveness with sub-linear congestion
competitiveness. Not only is this the first efficient algorithms for such a
routing scheme, but even the existence of routing schemes with the stated
competitiveness was not known prior to our work.

##  3 Additional Related Work

We give a brief overview of additional related work.

###  3.1 Applications of Expander Decompositions

We start by describing some additional work on the applications of expander
decompositions.

Areas of use include linear systems [ST04], unique games [ABS15, Tre05, RS10],
minimum cut [KT18], and dynamic algorithms [NSWN17]. Some of the long-
standing-open questions which have recently been solved thanks to expander
decompositions include: deterministic approximate balanced cut in near linear
time (with applications to dynamic connectivity and MST) [CGL+20],
subquadratic time algorithms for bipartite matching [vdBLN+20], and
deterministic algorithms for global min-cut in almost linear time [Li21].

###  3.2 Parallel Work on Well-Connected Graphs

A parallel and independent series of works by Chuzhoy [Chu23] and Chuzhoy and
Zhang [CZ23] develops notions similar to $(h,s)$-length $\phi$-expanders,
sparse moving cuts, and cut-matching games for length-constrained expanders.

In particular, the concept of $(\nu,d)$-well-connected graphs (proposed after
the length-constrained expanders of [HRG22]) is similar in spirit to
$(h,s)$-hop $\phi$-expanders when restricted to graphs with diameter less than
$h$. By way of their parameters, both types of graphs provide separate control
over congestion ($\nu$ for well-connected graphs and $\frac{1}{\phi}$ for
length-constrained expanders) and length ($d$ for well-connected graphs and
$hs$ for length-constrained expanders) of routing paths, but there are some
technical differences. Like the focus on small or constant $s$ in this paper
and [HRG22], the well-connected graphs of [Chu23] are particularly interesting
when guaranteeing routing via very short sub-logarithmic paths.

One important difference between well-connected graphs and length-constrained
expanders seems to be that $(h,s)$-length expanders are an expander-like
notion that applies to arbitrary graphs with (potentially) large diameter,
unlike well-connected graphs. In particular, they provide low congestion
($\tilde{O}(\frac{1}{\phi})$) and low length ($hs$) routing guarantees for
every unit demand between $h$-close nodes where $h$ and $hs$ are both
independent and potentially much smaller than the diameter of the entire
graph. On the other hand, well-connected graphs provide routing guarantees
between all nodes and, as such, seem to correspond more closely to what we
call routers in this work; see Definition 5.23. Overall, it is unclear if the
notion of a length-constrained expander decomposition of a general graph that
stands at the center of this paper relates in an immediate way to the notions
of [Chu23] and [CZ23].

###  3.3 Routing in Expanders

As much of our work deals with finding good routes in (length-constrained)
expanders, we briefly review some work on routing in expanders.

As mentioned earlier, expanders admit low congestion good multi-commodity flow
solutions [LR99]. A closely related problem is that of finding edge-disjoint
paths. [PU87] showed given any $\Omega(1)$-expander and $n^{\epsilon}$ pairs
for some small constant $\epsilon>0$, it is possible to find edge-disjoint
paths between these pairs in polynomial time. This was later improved by
[Fri01] to $\Theta(\frac{n}{\log n})$ edge-disjoint paths in regular
expanders. Many other works have studied this problem [BFU92, KR96, Val90,
LMR94].

Along similar lines, [GKS17] introduced the notion of “expander routing” which
allows each node $v$ to exchange $\mathrm{deg}(v)$ messages with nodes of its
choosing in the CONGEST model of distributed computation in about
$n^{o(1)}/\phi$ time on $\phi$-expanders. Using this approach, [GKS17] showed
that a minimum spanning tree (MST) can be constructed in
$\operatorname{poly}(\phi^{-1})\cdot n^{o(1)}$ distributed time in
$\phi$-expanders, bypassing the earlier-mentioned $\Omega(\sqrt{n}/\log n)$
lower bound [PR00, DSHK+11] for small $\phi$ networks. This was later extended
by [GL18] to a much wider class of optimization problems.

What use are expander decompositions for routing in graphs that are not
expanders? [GRST21] showed that expander decompositions can be used to route
arbitrary demands in a tree-like, oblivious and $n^{o(1)}$-congestion-
competitive manner. There is also a great deal of related work on related
“tree flow sparsifiers’; see, e.g. [Rac02].

##  4 Notation and Conventions

Before moving on to a more formal description of our results we introduce the
notation and conventions that we use throughout this work.

##### Graphs.

Let $G=(V,E)$ be a graph with $n:=|V|$ vertices and $m:=|E|$ edges. By
default, $G$ is undirected, and allowed to have self-loops but not parallel
edges. For each vertex $v\in V(G)$, we denote by $\mathrm{deg}_{G}(v)$ the
degree of $v$ in $G$. For $S\subset V$ we let the volume of $S$ be
$\mathrm{vol}(S)=\sum_{v\in S}\mathrm{deg}_{G}(v)$. $E(S,V\setminus S)$ gives
all edges with exactly one endpoint in $S$. We drop $G$ subscript when it is
clearly implied. We use standard graph terminology like adjacency,
connectivity, connected components, as defined in, e.g. [W+01].

##### Edge Values and Path Lengths

We will associate two functions with the edges of graph $G$. We clarify these
here.

  1. 1.

Capacities: We will let $U=\\{U_{e}\\}_{e}$ be the capacities of edges of $E$.
These capacities will specify a maximum amount of flow (either length-
constrained or not) that is allowed over each edge. Throughout this work we
imagine each $U_{e}$ is in $\mathbb{Z}_{\geq 0}$.

  2. 2.

Lengths: We will let $\ell=\\{\ell_{e}\\}_{e}$ be the _lengths_ of edges in
$E$. These lengths will be input to our problem and determine the lengths with
respect to which we are computing length-constrained expanders and length-
constrained expander decompositions. Throughout this work we imagine each
$\ell_{e}$ is in $\mathbb{Z}_{>0}$. We will let $d_{\ell}(u,v)$ or
$d_{G}(u,v)$ or just $d(u,v)$ when $G$ or $\ell$ are clear from context give
the minimum value of a path in $G$ that connects $u$ and $v$ where the value
of a path $P$ is $\ell(P):=\sum_{e\in P}\ell(e)$. We let
$\mathrm{ball}(v,h):=\\{u:d_{G}(v,u)\leq h\\}$ be all vertices within distance
$h$ from $v$ according to $\ell_{G}$. Prior works primarily used length-
constrained expanders in the context of unit-length graphs and talked about
$h$-hop expanders and $h$-hop expander decompositions. We deal with general
lengths and use “length” instead of “hop” where appropriate.

##### Polynomial Size Objects ($N$).

All objects (e.g. graphs with self-loops) defined in this paper are assumed to
be of size polynomial in $n$, i.e., for a fixed large enough constant
$c_{\max}$ we assume that all objects are of size at most $N<n^{c_{\max}}$
where $n$ is the number of vertices in the underlying graph. This polynomial
bound on object sizes in this paper also allows us to treat logarithmic upper
bounds in the sizes of these objects as essentially interchangeable, e.g., for
any constant bases $b,b^{\prime}$ we have that
$\log_{b}n\leq\log_{b^{\prime}}n^{c_{\max}}=\Theta(\log_{b^{\prime}}N)$.
Throughout the paper we therefore use $O(\log N)$ without any explicitly
chosen basis to denote such quantities. That is, all $O$-notation depends on
$c_{\max}$. We use $\tilde{O}$, $\tilde{\Omega}$ and $\tilde{\Theta}$ notation
to hide $\operatorname{poly}(N)$ factors.

##### Graph Arboricity.

Give graph $G$, a _forest cover_ of $G$ consists of sub-graphs
$F_{1},F_{2},\ldots,F_{k}$ of $G$ which are forests such that for $j\neq i$ we
have $F_{i}$ and $F_{j}$ are edge-disjoint and every edge of $G$ occurs in
some $F_{i}$. $k$ is called the size of the forest cover and the _arboricity_
$\alpha$ of graph $G$ is the minimum size of a forest cover of $G$.

##### Flows.

A _(multicommodity) flow_ $F$ in $G$ is a function that assigns to each simple
path $P$ in $G$ a flow value $F(P)\geq 0$. We say $P$ is a _flow-path_ of $F$
if $F(P)>0$. The value of $F$ is $\mathrm{val}(F)=\sum_{P}F(P)$. We let
$F(e):=\sum_{P\ni e}F(P)$ be the total flow through edge $e$. The _congestion
of $F$ on an edge $e$_ is defined to be

$\displaystyle\mathrm{cong}_{F}(e):=\sum_{P:e\in P}F(P)/U_{e},$

i.e., the total flow value of all paths going through $e$ divided by the
capacity of $e$. The _congestion_ of $F$ is

$\displaystyle\mathrm{cong}(F):=\max_{e\in E(G)}\mathrm{cong}_{F}(e).$

The _length_ (a.k.a. dilation) of $F$ is

$\displaystyle\text{dil}(F)=\max_{P:F(P)>0}\ell(P),$

i.e., the maximum length of all flow-paths of $F$. The _(maximum) step_ of $F$
is

$\displaystyle\mathrm{step}_{F}=\max_{P:F(P)>0}|P|,$

i.e., the maximum number of edges in all flow-paths of $F$. Given
$S,T\subseteq V$ we say that $F$ is an $S$-$T$ flow if each path in its
support is from a vertex in $S$ to a vertex in $T$. Given source, sink pairs
$\\{S_{i},T_{i}\\}_{i}$, we say that $F$ is an $\\{S_{i},T_{i}\\}_{i}$ flow if
each path in its support is from a vertex in some $S_{i}$ to a vertex in
$T_{i}$. We say that $F$ is feasible (with respect to capacities $U$) if
$\mathrm{cong}(F)\leq 1$.

##### Demands.

A _demand_ $D:V\times V\rightarrow\mathbb{R}_{\geq 0}$ assigns a non-negative
value $D(v,w)\geq 0$ to each ordered pair of vertices in $V$. The size of a
demand is written as $|D|$ and is defined as $\sum_{v,w}D(v,w)$. A demand $D$
is called _$h$ -length_ constrained (or simply _$h$ -length_ for short) if it
assigns positive values only to pairs that are within distance at most $h$,
i.e., $D(v,w)>0$ implies that $d_{G}(v,w)\leq h$. We call a demand integral if
all $D(v,w)$ are integers and empty if $|D|=0$. Given a flow $F$, the _demand
routed by $F$_ is denoted by $D_{F}$ where, for each $u,v\in V$,__
$D_{F}(u,v)=\sum_{P\text{ is a }(u,v)\text{-path}}F(P)$ is the value of
$(u,v)$-flow of $F$. We say that a _demand $D$ is routable in $G$ with
congestion $\eta$ and dilation $h$_ iff there exists a flow $F$ in $G$ where
$D_{F}=D$, $\mathrm{cong}_{F}\leq\eta$ and $\text{dil}(F)\leq h$. We say that
demand $D$ is routable with dilation inflation $s$ if there is a flow $F$ that
routes $D$ and for every $u$ and $v$ in the support of $F$, every path in the
support of $F$ has length at most $s\cdot d(u,v)$. We say that an $\alpha$
fraction of $D$ is routable if there exists a flow $F$ with
$\mathrm{val}(F)\geq\alpha\cdot|D|$ where the flow $F$ sends from $u$ to $v$
is at most $D(u,v)$ for every $u,v\in V$.

##### Graph Embeddings.

We will adopt the convention of an embedding of one graph into another being a
mapping of each edge to a flow. Specifically, an $h$-length embedding of edge-
capacitated graph $H=(V,E)$ into edge-capacitated graph $G$ is defined as
follows. Let $D_{H}$ be the demand that for each edge $e=\\{u,v\\}$ with
capacity $U_{e}$ sends $U_{e}$ demand from $u$ to $v$ and vice versa. Then an
$h$-length embedding of $H$ into $G$ is an $h$-length flow in $G$ that routes
$D_{H}$.

##  5 Preliminaries

In this section we review key definitions and theorems from previous work of
which we make use.

###  5.1 Classic Expanders and Expander Robustness

We summarize some (mostly standard) definitions of cut sparsity and classic
expanders. As this work will mostly deal with cuts understood as a collection
of edges (rather than a collection of vertices), we provide edge-centric
definitions. We begin with such a definition for cuts and cut sparsity.

######  Definition 5.1 (Classic Cut).

Given connected graph $G=(V,E)$, a (classic) cut is a set of edges $C\subseteq
E$ such that $G-C:=(V,E\setminus C)$ contains at least $2$ connected
components

######  Definition 5.2 ((Classic Edge) Cut Sparsity).

Given graph $G$, the sparsity of (classic) cut $C$ is

$\displaystyle\phi(C):=|C|/\sum_{S_{C}\in\mathcal{S}_{C}}\mathrm{vol}(S_{C})$

where $\mathcal{S}_{C}$ is all connected components of $G-C$ except for the
connected component of maximum volume. We refer to $\mathcal{S}_{C}$ as the
witness components of $C$.

Notice that the above definition of cut sparsity is equivalent to the vertex
cut definition provided in Section 1 provided $C$ separates the graph into two
components.

The following formalizes classic expanders.

######  Definition 5.3 (Classic Expander).

A graph $G=(V,E)$ is a $\phi$-expander if the sparsity of every cut
$C\subseteq E$ is at least $\phi$.

For the sake of comparison to our results in the length-constrained setting,
we give the following result summarizing the robustness of expanders to edge
deletions.

######  Theorem 5.4 (Theorem 1.3 of [SW19]).

Let $G=(V,E)$ be a $\phi$-expander with $m$ edges, let $D\subseteq E$ be a
collection of edges and let $G^{\prime}=(V,E\setminus D)$ be $G$ with $D$
deleted. Then there is a set $P\subseteq V$ such that:

  1. 1.

$G^{\prime}[V\setminus P]$ is $\frac{\phi}{6}$-expanding;

  2. 2.

$\mathrm{vol}(P)\leq\frac{8}{\phi}\cdot|D|$.

###  5.2 Length-Constrained Cuts (Moving Cuts)

We now recall formal definitions of length-constrained cuts from [HWZ20] which
will allow us to define length-constrained expanders and length-constrained
expander decompositions.

The following is the length-constrained analogue of a cut.

######  Definition 5.5 (Length-Constrained Cut (a.k.a. Moving Cut) [HWZ20]).

An $h$-length moving cut (a.k.a. $h$-length cut)
$C:E\mapsto\\{0,\frac{1}{h},\frac{2}{h},\dots,1\\}$ assigns to each edge $e$ a
fractional cut value between zero and one which is a multiple of
$\frac{1}{h}$. The _size_ of $C$ is defined as $|C|=\sum_{e}U_{e}\cdot C(e)$.
The length increase associated with the $h$-length moving cut $C$ is denoted
with $\ell_{C,h}$ and defined as assigning an edge $e$ the length
$\ell_{C,h}(e)=h\cdot C(e)$. Any moving cut which only assigns cut values
equal to either $0$ or $1$ is called a pure moving cut.

We can understand length-constrained cuts as cutting in one of two ways.
First, we can consider them as cutting apart vertex sets for which they cover
all $h$-length paths between these vertex sets.

######  Definition 5.6 (Length-Constrained $S$-$T$ and $\\{S_{i},T_{i}\\}_{i}$
Cuts).

Given vertex subsets $S,T\subseteq V$, we say that $h$-length cut $C$ is an
$h$-length $S$-$T$ cut if each $h$-length $S$-$T$ path $P$ satisfies $C(P)\geq
1$. Likewise, given vertex subset pairs $\\{S_{i},T_{i}\\}_{i}$ we say that
$C$ is an $h$-length $\\{S_{i},T_{i}\\}_{i}$ cut if it is an $S_{i}$-$T_{i}$
cut for each $i$.

By strong duality the size of the minimum size $h$-length $\\{S_{i},T_{i}\\}$
cut is equal to the value of the maximum value feasible $\\{S_{i},T_{i}\\}$
flow; see e.g. [HHS23].444Really, strong duality requires that $C$ assigns
general values to edges (not just values that are multiples of $\frac{1}{h}$);
this nuance can be ignored in this work as we are only interested in
approximately optimal cuts. As such, we will say that a pair of $h$-length
$\\{S_{i},T_{i}\\}_{i}$ flow and cut $(F,C)$ is $(1\pm\epsilon)$-approximate
for $\epsilon\geq 0$ if the cut certifies the value of the length-constrained
flow up to a $(1-\epsilon)$; i.e. if
$(1-\epsilon)\cdot|C|\leq\mathrm{val}(F)$.

Second, if we interpret length-constrained cuts as length increases, then we
can understand them as cutting apart vertices that are made sufficiently far
apart (i.e. separated). Specifically, consider the following is the result of
applying a length-constrained cut in a graph.

######  Definition 5.7 ($G-C$).

For a graph $G$ with length function $l_{G}$ and moving cut $C$, we denote
with $G-C$ the graph $G$ with length function $l_{G-C}=l_{G}+\ell_{C,h}$. We
refer to $G-C$ as the _graph $G$ after cutting_ $C$ or _after applying the
moving cut_ $C$.

Then, the following gives the appropriate length-constrained analogue of
disconnecting two vertices or a demand by making the demand pairs sufficiently
far apart (i.e. separated).

######  Definition 5.8 ($h$-Length Separation).

Let $C$ be an $h$-length moving cut. We say two node $v,v^{\prime}\in V$ are
$h$-length separated by $C$ if their distance in $G-C$ is larger than $h$,
i.e., if $d_{G-C}(v,v^{\prime})>h$.

Observe that if $C$ is an $h$-length $\\{u\\}$-$\\{v\\}$ cut then it always
$h$-length separates $u$ and $v$. However, $C$ might $h$-length separate nodes
$u$ and $v$ even if it is not an $h$-length $\\{u\\}$-$\\{v\\}$ cut; e.g. in
the case where $u$ and $v$ are nearly $h$-far in $G$.

######  Definition 5.9 ($h$-Length Separated Demand).

For any demand $D$ and any $h$-length moving cut $C$, we define the amount of
$h$-length separated demand as the sum of demands between vertices that are
$h$-length separated by $C$. We denote this quantity with
$\mathrm{sep}_{h}(C,D)$, i.e.,

$\mathrm{sep}_{h}(C,D)=\sum_{u,v:d_{G-C}(u,v)>h}D(u,v).$

Using demand separation, we can carry over cut sparsity to the length-
constrained setting.

######  Definition 5.10 ($h$-Length Sparsity of a Cut $C$ for Demand $D$).

For any demand $D$ and any $h$-length moving cut $C$ with
$\mathrm{sep}_{h}(C,D)>0$, the $h$-length sparsity of $C$ with respect to $D$
is the ratio of $C$’s size to how much demand it $h$-length separates i.e.,

$\operatorname{spars}_{h}(C,D)=\frac{|C|}{\mathrm{sep}_{h}(C,D)}.$

Note that if a demand $D$ has any demand between vertices that have length-
distance exceeding $h$ then the empty cut has an $h$-length sparsity for $D$
which is equal to zero. For all other demands, i.e., for any non-empty
$h$-length demand $D$ with $h<h^{\prime}$, the $h^{\prime}$-length sparsity of
any cut $C$ for $D$ is always strictly positive.

###  5.3 Length-Constrained Expanders

We now move on to formally defining length-constrained expanders. Informally,
they are graphs with no sparse length-constrained cuts.

We begin by introducing the notion of node-weightings which will give us a
formal way of defining what it means for a subset of a graph to be a length-
constrained $\phi$-expanding.

######  Definition 5.11 (Node-Weightings).

A _node-weighting_ $A:V\rightarrow\mathbb{R}_{\geq 0}$ of $G$ assigns a value
$A(v)$ to a vertex $v$. The _size_ of $A$ is denoted by $|A|=\sum_{v}A(v)$.
For two node-weightings $A,A^{\prime}$ we define $\min(A,A^{\prime})$,
$A-A^{\prime}$ and $A+A^{\prime}$ as pointwise operations and let
$\mathrm{supp}(A):=\\{v:A(v)>0\\}$.

The following summarizes the demands we consider for a particular node-
weighting.

######  Definition 5.12 (Demand Load and Respect).

The load of a demand $D$, denoted with $\operatorname{load}(D)$, is the node-
weighting which assigns the node $v$ the weight $\max\\{\sum_{w\in
V}D(v,w),\sum_{w\in V}D(w,v)\\}$. We write $A\prec A^{\prime}$ if $A$ is
pointwise smaller than $A^{\prime}$. We say demand $D$ is _$A$ -respecting_ if
$\operatorname{load}(D)\prec A$. We say that $D$ is _degree-respecting_ if $D$
is $\mathrm{deg}_{G}$-respecting.

Having defined node-weightings and their corresponding demands, we can now
define their sparsity.

######  Definition 5.13 ($(h,s)$-Length Sparsity of a Cut w.r.t. a Node-
Weighting).

The $(h,s)$-length sparsity of any $hs$-length moving cut $C$ with respect to
a node-weighting $A$ is defined as:

$\operatorname{spars}_{(h,s)}(C,A)=\min_{A\text{-respecting h-length demand}\
D}\operatorname{spars}_{s\cdot h}(C,D).$

We refer to the minimizing demand $D$ above as the demand _witnessing_ the
sparsity of $C$ with respect to $A$. We can analogously define the length-
constrained conductance of a node-weighting.

######  Definition 5.14 ($(h,s)$-Length Conductance of a Node-Weighting).

The $(h,s)$-length conductance of a node-weighting $A$ in a graph $G$ is
defined as the $(h,s)$-length sparsity of the sparsest $hs$-length moving cut
$C$ with respect to $A$, i.e.,

$\operatorname{cond}_{(h,s)}(A)=\min_{hs\text{-length moving cut
}C}\operatorname{spars}_{(h,s)}(C,A).$

When no node-weighting is mentioned then $(h,s)$-length sparsity and
$(h,s)$-length conductance are defined with respect to the node-weighting
$\mathrm{deg}_{G}$ which gives vertex $v$ value $\mathrm{deg}_{G}(v)$. In
other words, the $(h,s)$-length sparsity of an $hs$-length moving cut $C$ in
$G$ is defined as
$\operatorname{spars}_{(h,s)}(C,G)=\min_{D}\operatorname{spars}_{hs}(C,D)$
where the minimum is taken over all degree-respecting $h$-length demands.
Similarly, the $(h,s)$-length conductance of $G$ is defined as
$\operatorname{cond}_{(h,s)}(G)=\min_{C}\operatorname{spars}_{(h,s)}(C,\mathrm{deg}_{G})$
where the minimum is taken over all $hs$-length moving cuts.

With the above notion of conductance, we can now define when $A$ is length-
constrained expanding and when $G$ is length-constrained expander.

######  Definition 5.15 ($(h,s)$-Length $\phi$-Expanding Node-Weightings).

We say a node-weighting $A$ is $(h,s)$-length $\phi$-expanding in $G$ if the
$(h,s)$-length conductance of $A$ in $G$ is at least $\phi$.

Equivalently to the above, we will sometimes say that $G$ is an $(h,s)$-length
$\phi$-expander for $A$. Applying the above definition to $\mathrm{deg}_{G}$
gives our formal definition of length-constrained $\phi$-expanders.

######  Definition 5.16 ($(h,s)$-Length $\phi$-Expanders).

A graph $G$ is an $(h,s)$-length $\phi$-expander if $\mathrm{deg}_{G}$ is
$(h,s)$-length $\phi$-expanding in $G$.

The above definition of length-constrained expanders characterizes them in
terms of conductance. The below fact from [HRG22] (see their Lemma 3.16)
exactly characterizes length-constrained expanders as those graphs that admit
both low congestion and low dilation routings.

######  Theorem 5.17 (Routing Characterization of Length-Constrained
Expanders, [HRG22]).

Given graph $G$ and node-weighting $A$, for any $h\geq 1$, $\phi<1$ and $s\geq
1$ we have:

  * •

Length-Constrained Expanders Have Good Routings If $A$ is $(h,s)$-length
$\phi$-expanding in $G$, then every $h$-length $A$-respecting demand can be
routed in $G$ with congestion at most $O(\log(N)/\phi)$ and dilation at most
$s\cdot h$.

  * •

Not Length-Constrained Expanders Have a Bad Demand If $A$ is not
$(h,s)$-length $\phi$-expanding in $G$, then some $h$-length $A$-respecting
demand cannot be routed in $G$ with congestion at most $1/2\phi$ and dilation
at most $\frac{s}{2}\cdot h$.

###  5.4 At Most Length-Constrained Expanders

######  Definition 5.18 ($(\leq h,s)$-Length $\phi$-Expanding Node-
Weightings).

We say a node-weighting $A$ is $(\leq h,s)$-length $\phi$-expanding in $G$ if
the $(h^{\prime},s)$-length sparsity of $A$ in $G$ is at least $\phi$ for
every $h^{\prime}\leq h$.

######  Definition 5.19 ($(\leq h,s)$-Length $\phi$-Sparsity of Cut).

We say a node-weighting $A$ is $(\leq h,s)$-length $\phi$-expanding in $G$ if
the $(h^{\prime},s)$-length sparsity of $A$ in $G$ is at least $\phi$ for
every $h^{\prime}\leq h$.

###  5.5 Length-Constrained Expander Decompositions

Having defined length-constrained expanders, we can now define length-
constrained expander decompositions. Informally, these are simply moving cuts
whose application renders the graph a length-constrained expander.

######  Definition 5.20 (Length-Constrained Expander Decomposition).

Given graph $G$, an _$(h,s)$ -length (resp. $(\leq h,s)$-length)
$\phi$-expander decomposition_ for a node-weighting $A$ with cut slack
$\kappa$ and length slack $s$ is an $hs$-length cut $C$ of size at most
$\kappa\cdot\phi|A|$ such that $A$ is $(h,s)$-length (resp. $(\leq
h,s)$-length) $\phi$-expanding in $G-C$.

We will make use of a strengthened version of length-constrained expander
decompositions called “linked” length-constrained expander decompositions.
Informally, this is a length-constrained expander decomposition which renders
$G$ length-constrained expanding even after adding many self-loops. This is a
strengthened version because adding self-loops only makes it harder for a
graph to be a length-constrained expander. The following definition gives the
self-loops we will add for a length-constrained expander decomposition $C$.

######  Definition 5.21 (Self-Loop Set $L^{\ell}_{C}$).

Let $C$ be an $h$-length moving cut of a graph $G=(V,E)$ and let $\ell$ be a
positive integer divisible by $h$. For any vertex $v$, define $C(v)=\sum_{e\ni
v}C(e)$. The self-loop set $L^{\ell}_{C}$ consists of $C(v)\cdot\ell$ self-
loops at $v$. We let $G+L^{\ell}_{C}:=(V,E\cup L^{\ell}_{C})$.

Using the above self-loops, we can now define linked length-constrained
expander decompositions.

######  Definition 5.22 (Linked Length-Constrained Expander Decomposition).

Let $G$ be a graph. An $\ell$-linked $(h,s)$-length (resp. $(\leq
h,s)$-length) $\phi$-expander decomposition of a node-weighting $A$ on $G$
with cut slack $\kappa$ is an $hs$-length moving cut $C$ such that
$|C|\leq\kappa\cdot\phi|A|$ and $A\cup L^{\ell}_{C}$ is $(h,s)$-length (resp.
$(\leq h,s)$-length) $\phi$-expanding in $G+L^{\ell}_{C}-C$.

As before, we say that moving cut $C$ is an $(h,s)$-length $\phi$-expander
decomposition (linked or not) for $G$ if it is an $(h,s)$-length
$\phi$-expander decomposition for the node-weighting $\mathrm{deg}_{G}$.

###  5.6 Routers, Power Graphs and Expander Power Graph Robustness

Having introduced length-constrained expander decompositions in the previous
section, we introduce and discuss the closely related notion of graph routers,
which will be useful for our characterizations of length-constrained expanders
in terms of (classic) expanders.

######  Definition 5.23 (Routers).

Given graph $G$ and node-weighting $A$, we say that $G$ is a _$t$ -step
$\kappa$-router for $A$_ if every $A$-respecting demand can be routed in $H$
via a $t$-step flow with congestion at most $\kappa$.

As with length-constrained expanders, we say $G$ is just a $t$-step
$\kappa$-router if it is a $t$-step $\kappa$-router for $\mathrm{deg}_{G}$.

Observe that, by the flow characterization of length-constrained expanders
(Theorem 5.17), routers are essentially the same object as $(h,s)$-length
$\phi$-expanders with unit length $t=\Theta(hs)$ long routing paths,
congestion $\kappa=\tilde{\Theta}(\frac{1}{\phi})$ congestion, and a diameter
smaller than $h$, which guarantees that any demand is $h$-length and therefore
any degree-respecting demand must be routable. The following formalizes this.

######  Lemma 5.24.

Let $G$ be a graph with unit length edges. Let $A$ be a node-weighting where
$\mathrm{diam}_{G}(\mathrm{supp}(A))\leq h$. Then:

  * •

Expander Implies Router: If $G$ is a $(h,s)$-length $\phi$-expander for $A$,
then $G$ is an $hs$-step $O(\frac{\log N}{\phi})$-router for $A$;

  * •

Router Implies Expander: If $G$ is not a $(h,s)$-length $\phi$-expander for
$A$, then $G$ is not an $(\frac{hs}{2})$-step $\frac{1}{2\phi}$-router for
$A$.

###### Proof.

Since $\mathrm{diam}_{G}(\mathrm{supp}(A))\leq h$, the set of $A$-respecting
demands and the set of $h$-length $A$-respecting demands are identical.
Therefore, by Theorem 5.17, if $G$ is a $(h,s)$-length $\phi$-expander for
$A$, then every $A$-respecting demand can be routed in $G$ with congestion
$O(\log(N)/\phi)$ and $sh$ steps. Otherwise, some $A$-respecting demand cannot
be routed in $G$ with congestion $1/2\phi$ and $(sh)/2$ steps. This completes
the proof by Definition 5.23. ∎

Of particular interest to us will be routers constructed by taking power
graphs, defined as follows.

######  Definition 5.25 ($k$th Power Graph).

Given a graph $G=(V,E)$, we let $G^{k}=(V,E^{k})$ be the graph that has an
edge for each path of length at most $k$. In particular, $\\{u,v\\}\in E^{k}$
iff $d_{G}(u,v)\leq k$.

The following are easy-to-verify routers.

######  Lemma 5.26 (Star is a Router).

Let $G$ be a star where rooted at $r$ with node-weighting $A$ where the set of
leaves of $G$ is $\mathrm{supp}(A)$. The capacity of each star-edge $(r,v)\in
E(G)$ is $A(v)$. Then, $G$ is a $2$-step $1$-router for $A$.

######  Lemma 5.27 (Complete Graph is a Router).

Let $G$ be a complete graph with node-weighting $A$ where
$V(G)=\mathrm{supp}(A)$ and where for each $v,w\in\mathrm{supp}(A)$ and the
capacity of $(v,w)$ is $\frac{A(v)\cdot A(w)}{|A|}$. Then, $G$ is a $2$-step
$2$-router for $A$.

######  Lemma 5.28 (Expander Power is a Router).

Let $G$ be a constant-degree $\Omega(1)$-expander. Then $G$ is a $O(\log
n)$-step $O(\log n)$-router and $G^{k}$ is a $O(\log n/k)$-step $O(\log
n/k)$-router.

Lastly, we observe that power graphs when used as routers are robust to edge
deletions. In particular, the following is immediate from Lemma 5.28 and well-
known results for expanders.

######  Lemma 5.29 (Robustness of Expander Power Routers, Adaptation of
Theorem 2.1 of [SW19].).

Suppose $H=(V,E_{H})$ is an $\Omega(1)$-expander with maximum degree $\Delta$
and $G:=H^{k}=(V,E_{G})$ is the $k$th power graph of $H$. Then for any subset
$D\subseteq E_{G}$, let $G^{\prime}:=(V,E_{G}\setminus D)$ be $G$ with $D$
deleted. Then, there exists a subset of vertices $V^{\prime}\subseteq V$
connected in $G^{\prime}[V^{\prime}]$ where:

  1. 1.

$G^{\prime}[V^{\prime}]$ is a $O(\frac{\log N}{k})$-step $O(\frac{\log
N}{k})$-router;

  2. 2.

$|V^{\prime}|\geq|V|-O(\frac{k\cdot\Delta^{2k}}{\phi})\cdot|D|$.

###  5.7 Neighborhood Covers

Our characterizations of length-constrained expander decompositions in terms
of (classic) expander decompositions will make use of so-called neighborhood
covers. Neighborhood covers are a special kind of clustering.

######  Definition 5.30 (Clustering).

Given a graph $G$ with edge lengths $\ell$, a _clustering_ ${\cal S}$ in $G$
with diameter $h_{\mathrm{diam}}$ is a collection of disjoint vertex sets
$S_{1},\ldots,S_{|{\cal S}|}$, called clusters, where every cluster has
diameter at most $h_{\mathrm{diam}}$ in $G$. A clustering has _absolute
separation_ $h_{\mathrm{sep}}$ or _separation factor_ $s$ if the distance
between any two clusters is at least $h_{\mathrm{sep}}$ or $s\cdot
h_{\mathrm{diam}}$, respectively.

######  Definition 5.31 (Neighborhood Cover).

A neighborhood cover ${\cal N}$ with width $\omega$ and covering radius
$h_{\mathrm{cov}}$ is a collection of $\omega$ many clusterings ${\cal
S}_{1},\ldots,{\cal S}_{\omega}$ such that for every node $v$ there exists a
cluster $S$ in some $\mathcal{S}_{i}$ containing
$\mathrm{ball}(v,h_{\mathrm{cov}})$.

We will say that a neighborhood cover ${\cal N}$ has diameter
$h_{\mathrm{diam}}$ if every clustering has diameter at most
$h_{\mathrm{diam}}$ and absolute separation $h_{\mathrm{sep}}$ or separation-
factor $s$ if this applies to each of its clusterings. Note, however, that two
clusterings in a given neighborhood cover may have different diameters.

We use the following result for neighborhood covers, which can be proved in a
similar way to Lemma 8.15 of [HRG22].

######  Theorem 5.32 ([HRG22]).

For any $h_{\mathrm{cov}},s>1$ and $\epsilon\in(0,1)$ and graph $G$ there
exists a neighborhood cover with covering radius $h_{\mathrm{cov}}$,
separation-factor $s$, diameter $h_{\mathrm{diam}}=\frac{1}{\epsilon}\cdot
O(s)^{O(1/\epsilon)}\cdot h_{\mathrm{cov}}$ and width
$\omega=N^{O(\epsilon)}\log N$. Moreover, there exists an algorithm that
computes such a neighborhood cover in $h_{\mathrm{diam}}\cdot N^{O(\epsilon)}$
depth and $m\cdot h_{\mathrm{diam}}\cdot N^{O(\epsilon)}$ work with high
probability.

###  5.8 Length-Constrained Expansion Witnesses

In this section we define the notion of a witness of $(\leq h,s)$-length
$\phi$-expansion. Below, for node-weighting $A$ and nodes $S$, we let $A_{S}$
be $A$ restricted to nodes in $S$.

######  Definition 5.33 (Length-Constrained Expansion Witness).

A $(\leq h,s)$-length $\phi$-expansion witness for graph $G$ and node-
weighting $A$ consists of the following where $s_{0}\cdot s_{1}\leq s$ and
$\kappa_{0}\cdot\kappa_{1}\leq 1/\phi$:

  * •

Neighborhood Cover: a neighborhood cover $\mathcal{N}_{h^{\prime}}$ of $G$
with covering radius $h^{\prime}$ for each $h^{\prime}\leq h$ a power of $2$;

  * •

Routers: an $s_{0}$-step and $\kappa_{0}$ congestion router $R_{S}$ of $A_{S}$
for each $S\in\bigcup_{h^{\prime}}\mathcal{N}_{h^{\prime}}$;

  * •

Embedding of Routers: an $(h^{\prime}\cdot s_{1})$-length embedding $F_{S}$ of
$R_{S}$ into $G$ for each $S\in\mathcal{N}_{h^{\prime}}$ for each
$\mathcal{N}_{h^{\prime}}$ such that
$\sum_{h^{\prime}}\sum_{S\in\mathcal{N}_{h^{\prime}}}F$ has congestion at most
$\kappa_{1}$.

A witness of $(h,s)$-length $\phi$-expansion is defined identically to the
above but there is only a single neighborhood cover $\mathcal{N}_{h}$ with
covering radius $h$.

It is easy to verify that such a witness indeed witnesses that an input graph
is a length-constrained expander.

######  Lemma 5.34.

If a graph $G$ and node-weighting $A$ have an $(h,s)$-length (resp. $(\leq
h,s)$-length) $\phi$-expansion witness then $G$ is an $(h,s)$-length (resp.
$(\leq h,s)$-length) $\phi$-expander with respect to $A$.

The following gives our definition of a witnessed length-constrained expander
decomposition.

######  Definition 5.35 (Witnessed Length-Constrained Expander
Decompositions).

A witnessed $(h,s)$-length (resp. $(\leq h,s)$-length) $\phi$-expander
decomposition consists of an $(h,s)$-length (resp. $(\leq h,s)$-length)
$\phi$-expander decomposition $C$ along with an $(h,s)$-length (resp. $(\leq
h,s)$-length) $\phi$-expansion witness for $G-C$.

##  6 Main Result Restated: Length-Constrained ED Algorithm

Having formally defined length-constrained expander decompositions in the
previous section, we now restate the guarantees of our algorithm for computing
these decompositions for convenience.

The following gives the main result of our work. See 1.1 The proof of 1.1 uses
several new notions and techniques that we introduce in the subsequent
sections. The final proof of 1.1 is in Section 15. We show that we can
additionally achieve linkedness in Section 16.

##  7 Length-Constrained Expanders as Embedded Expander Powers

Towards understanding whether large sparse length-constrained cuts quickly
yield length-constrained expander decompositions, we begin by providing a new
characterization of length-constrained expander decompositions in terms of
classic expanders. One of the great benefits of such a characterization is
that it will allow us to bring well-studied tools from the classic expander
setting to bear on length-constrained expanders.

##### Challenge.

Achieving such a characterization may seem impossible. Length-constrained
expanders are fundamentally different objects from classic expanders: as
earlier mentioned, many graphs which are length-constrained expanders are not
classic expanders and adding length constraints destroys the structure of many
otherwise well-behaved objects.

##### Basic Version of Result.

We show that, nonetheless, length-constrained expander decompositions are
exactly those graphs that admit low congestion _and dilation_ embeddings of
regular expanders in every local neighborhood. More formally, if $H$ is a
constant-degree $\Omega(1)$-expander, we show that a graph $G$ is an
$(h,s)$-length $\phi$-expander iff it is possible to embed $H$ into every
$h$-neighborhood in $G$ with congestion about $\frac{1}{\phi}$ using paths of
length at most $hs/\Theta(\log n)$.

##### Full Result.

The above characterization has two downsides. First, assuming integer lengths,
such an embedding only makes sense when $hs\geq\Omega(\log n)$. However,
$(h,s)$-length $\Omega(1)$-expanders are only interesting and distinct from
classic $\Omega(1)$-expanders when $hs\ll O(\log n)$. Second, the embedding is
brittle in the sense that if even a small part of the graph is not embeddable
then the entire graph is declared to be not length-constrained expanding.

We address these issues by significantly strengthening this result. First, we
allow for $hs=o(\log n)$ by considering embeddings of the “$k$th power graph”
$H^{k}$ of classic expander $H$ rather than $H$ itself. In particular, this
allows uxs to trade off between congestion and dilation, showing $G$ is an
$(h,s)$-length $\phi$-expander iff $H^{k}$ can be embedded into every
neighborhood with congestion at most about $\frac{1}{\phi\cdot 2^{k}}$ using
paths of length at most $hs\cdot k/\Theta(\log n)$. Observe that, assuming
integer lengths, such an embedding makes sense as long as $hs\cdot
k\geq\Theta(\log n)$. Second, we show that if such embeddings are _mostly_
possible in $G$, then _most_ of $G$ is an $(h,s)$-length $\phi$-expander.

##### Techniques.

The main proof idea for this result is as follows. First, we argue that we can
route in $H^{k}$ with low congestion over paths of length $O(\log n/k)$. Then,
if our embedding exists, we can embed these routes in the expander powers into
the original graph with low dilation and congestion. This gives low congestion
and dilation routes in the original graph, showing it is a length-constrained
expander. We formalize these embeddings with the idea of the “neighborhood
router demand.”

######  Theorem 7.1.

Suppose we are given a graph $G$, node-weighting $A$, $h\geq 1$ and parameters
$k,k^{\prime}\geq 1$. Then:

  * •

Length-Constrained Expander Implies Embedding: If $G$ is an
$(hk^{\prime},s)$-length $\phi$-expander for $A$ then $D_{A,k,k^{\prime}}$ is
routeable with congestion $O(\frac{\log N}{\phi})$ and dilation
$2k^{\prime}\cdot hs$.

  * •

Embedding Implies Length-Constrained Expander: Let $G^{\prime}$ be $G$ with a
moving cut applied. If a $(1-\epsilon)$ fraction of $D_{A,k,k^{\prime}}$ is
routable in $G^{\prime}$ with congestion $\frac{1}{\phi}$ and dilation $hs$
then there is a node-weighting $A^{\prime}\preccurlyeq A$ of size
$|A^{\prime}|\geq|A|\cdot\left(1-\epsilon^{\prime}\right)$ such that
$A^{\prime}$ is $\left(h,s^{\prime}\right)$-length $\phi^{\prime}$-expanding
in $G^{\prime}$ where $\epsilon^{\prime}=O\left(\epsilon\cdot 2^{O(k)}\cdot
N^{O(1/k^{\prime})}\log N\right)$, $s^{\prime}=O\left(s\cdot\frac{\log
N}{k}\right)$ and $\phi^{\prime}=\Omega\left(\phi\cdot 2^{-O(k)}\cdot
N^{-O(1/k^{\prime})}\cdot\log^{-2}N\right)$.

Notice that the above states that if one can embed expander powers into _most_
of a graph then _most_ of the graph is a length-constrained expander. $k$ and
$k^{\prime}$ above correspond to the power of the expanders that we take and
the diameter of neighborhood covers that we use respectively.

###  7.1 Formalizing the Embedding via the Neighborhood Router Demand

We begin by formalizing the aforementioned embedding with what we call the
neighborhood router demand, $D_{A,k,k^{\prime}}$.

(a) Cluster $S_{i,j}$.

(b) Graph $H_{i,j}^{k}$.

(c) Demand $\Delta^{k}\cdot D_{i,j}$.

Figure 1: Our neighborhood router demand for one cluster $S_{i,j}$. 1(a) gives
the cluster $S_{i,j}$ with node $v$ labeled with $A(v)$. 1(b) gives the graph
$H_{i,j}^{k}$ we want to embed into $S_{i,j}$. 1(c) gives the demand $D_{i,j}$
corresponding to this embedding (times $\Delta^{k}$) in dashed blue. Our
neighborhood router demand is then computed by doing this for all such
clusters and scaling down appropriately.

Formally, suppose we are given a graph $G=(V,E)$ and a node-weighting $A$ of
$G$ as well as a length bound $h$ and parameters $k,k^{\prime}\geq 1$. To
compute the neighborhood router demand we first compute a neighborhood cover
$\mathcal{N}=\\{\mathcal{S}_{1},\mathcal{S}_{2}\ldots\\}$ with covering radius
$h$, diameter $k^{\prime}\cdot h$, load $N^{O(1/k^{\prime})}\log N$ and
separation factor $2$; such a neighborhood cover exists by Theorem 5.32.

We now construct a graph $H_{i,j}$ associated with each cluster
$S_{i,j}\in\bigcup_{i}\mathcal{S}_{i}$. The vertex set of $H_{i,j}$ consists
of $A(u)$ copies for each vertex $u\in V$ for $\sum_{u\in S_{i,j}}A(u)$ total
vertices in $H_{i,j}$. We let $\text{copies}_{i,j}(u)$ denote these copies of
$u$ in $H_{i,j}$ and let $V_{i,j}:=\bigcup_{u\in
S_{i,j}}\text{copies}_{i,j}(u)$ be all such copies. Then, we let
$H_{i,j}=(V_{i,j},E_{i,j})$ be a fixed but arbitrary $\Omega(1)$-expander with
max degree $\Delta=O(1)$ with vertex set $V_{i,j}$; such graphs are well-known
to exist by e.g. [ASS08].

Likewise, we let $H_{i,j}^{k}=(V_{i,j},E_{i,j}^{k})$ be the $k$th power graph
of $H_{i,j}$ as defined in Section 5.6. Lastly, for $u,v\in V$ we let

$E_{i,j}^{k}(u,v):=\\{\\{u^{\prime},v^{\prime}\\}\in
E^{\prime}:u^{\prime}\in\text{copies}_{i,j}(u),v^{\prime}\in\text{copies}_{i,j}(v)\\}$

be edges of $H^{k}_{i,j}$ between copies of $u$ and $v$. We then define the
neighborhood router demand associated with cluster $S_{i,j}$ on vertices
$u,v\in V$ as

$\displaystyle D_{i,j}(u,v):=\frac{1}{\Delta^{k}}\cdot|E_{i,j}^{k}(u,v)|.$

See Figure 1 for an illustration of $D_{i,j}$.

Similarly, we define the entire neighborhood router demand as

$\displaystyle
D_{A,k,k^{\prime}}:=\frac{1}{\operatorname{load}_{\mathcal{N}}}\cdot\sum_{i,j}D_{i,j}.$

We verify the basic properties of $D_{A,k,k^{\prime}}$.

######  Lemma 7.1.

$D_{A,k,k^{\prime}}$ is $A$-respecting and $(hk^{\prime})$-length. Furthermore
$|D_{A,k,k^{\prime}}|\geq\frac{1}{N^{O(1/k^{\prime})}\cdot\log N}\cdot|A|$.

###### Proof.

We prove that $D_{A,k,k^{\prime}}$ is $hk^{\prime}$-length and then that it is
$A$-respecting.

  * •

$D_{A,k,k^{\prime}}$ is $hk^{\prime}$-length since each $D_{i,j}(u,v)>1$ only
if $u,v\in S_{i,j}$ for some $i$ and $j$ and each $S_{i,j}$ has diameter at
most $hk^{\prime}$ by our assumption that $\mathcal{N}$ has diameter
$hk^{\prime}$.

  * •

$D_{A,k,k^{\prime}}$ is $A$-respecting: recall that to be $A$-respecting we
must show that for every $v$ we have
$\max\left\\{\sum_{u}D_{A,k,k^{\prime}}(u,v),\sum_{u}D_{A,k,k^{\prime}}(v,u)\right\\}\leq
A(v)$; consider such a $v$; we will show $\sum_{u}D_{A,k,k^{\prime}}(v,u)\leq
A(v)$ (showing $\sum_{u}D_{A,k,k^{\prime}}(u,v)\leq A(v)$ is symmetric);
observe that since each vertex in $H$ has degree at most $\Delta$, we know
that each vertex in $H^{k}_{i,j}$ has degree at most $\Delta^{k}$ and so for
each $i$ and $j$ we have

$\displaystyle\sum_{u}D_{i,j}(v,u)$
$\displaystyle=\sum_{u}\sum_{u^{\prime}\in\text{copies}_{i,j}(u)}\sum_{v^{\prime}\in\text{copies}_{i,j}(v)}\frac{1}{\Delta^{k}}\cdot\mathbbm{1}(\\{u^{\prime},v^{\prime}\\}\in
E(H^{k}_{i,j}))$
$\displaystyle=\sum_{v^{\prime}\in\text{copies}_{i,j}(v)}\frac{1}{\Delta^{k}}\cdot\mathrm{deg}_{H^{k}_{i,j}}(v^{\prime})$
$\displaystyle\leq\sum_{v^{\prime}\in\text{copies}_{i,j}(v)}1$
$\displaystyle\leq A(v)$ (1)

The claim then follows from the fact that no vertex is in more than
$\operatorname{load}\mathcal{N}$-many clusters. Namely, applying Equation 1
and the definition of $\operatorname{load}{\mathcal{N}}$:

$\displaystyle D_{A,k,k^{\prime}}(v,u)$
$\displaystyle=\frac{1}{\operatorname{load}{\mathcal{N}}}\cdot\sum_{i,j}D_{i,j}(v,u)$
$\displaystyle\leq\frac{1}{\operatorname{load}{\mathcal{N}}}\cdot\sum_{i,j}A(v)$
$\displaystyle\leq A(v).$

Lastly, we argue the lower bound on $|D_{A,k,k^{\prime}}|$. Observe that each
time a vertex $u$ is in $S_{i,j}$, it is responsible for $A(u)$ copies in each
$H_{i,j}^{k}$ where each copy has degree $\Omega(1)$ and so contributes at
least $\Omega(A(u)/\operatorname{load}_{\mathcal{N}})$ to
$|D_{A,k,k^{\prime}}|$. ∎

###  7.2 Proving Length-Constrained Expanders are Embedded Expander Powers

Having formally defined the neighborhood router demand, we proceed to show the
main theorem of this section (7.1): the extent to which a graph is a length-
constrained expander is more or less captured by how well the neighborhood
router demand can be routed and, in particular, how well expander powers embed
into the input graph.

See 7.1

###### Proof.

The fact that if $G$ is an $(hk^{\prime},s)$-length $\phi$-expander for $A$
then $D_{A,k,k^{\prime}}$ can be routed with the stated path length and
congestion is immediate from Theorem 5.17 and Lemma 7.1

We now turn to the second point; namely we argue that if a $(1-\epsilon)$
fraction of $D_{A,k,k^{\prime}}$ can be routed with congestion
$\frac{1}{\phi}$ and dilation $hs$ in $G^{\prime}$ then there is a node-
weighting $A^{\prime}\preccurlyeq A$ of size at least
$|A|\cdot(1-\epsilon^{\prime})$ that is $(h,s^{\prime})$-length
$\phi^{\prime}$-expanding in $G^{\prime}$. To argue that such an $A^{\prime}$
exists, by Theorem 5.17 it suffices to show that there is an $A^{\prime}$ of
size at least $|A|\cdot(1-\epsilon^{\prime})$ where every
$A^{\prime}$-respecting $h$-length demand can be routed with congestion at
most $O(\frac{1}{\phi^{\prime}})$ and dilation at most $O(hs^{\prime})$. We
proceed to argue this $A^{\prime}$ exists.

We let $F$ be the flow in $G^{\prime}$ that routes at least a $(1-\epsilon)$
fraction of $D_{A,k,k^{\prime}}$ with congestion $\frac{1}{\phi}$ and dilation
$hs$. The basic idea is to map $F$ into each $H^{k}_{i,j}$, perform (normal)
expander pruning in $H^{k}_{i,j}$ and then map the large expanding subset in
$H^{k}_{i,j}$ back into $G^{\prime}$.

We say that the pair $\\{u,v\\}\subseteq V$ is _unsuccessfully embedded_ if
$F(u,v)<.5\cdot D_{A,k,k^{\prime}}(u,v)$ and let $\bar{E}$ be all
unsuccessfully embedded pairs. For a fixed $S_{i,j}$, this allows us to define
$\bar{E}_{i,j}^{k}$ as the edges of $H^{k}_{i,j}$ corresponding to all
unsuccessfully embedded pairs as follows:

$\displaystyle\bar{E}_{i,j}^{k}:=\bigcup_{\\{u,v\\}\in\bar{E}}E_{i,j}^{k}(u,v).$

We proceed to define our node weights $A^{\prime}\preccurlyeq A$ of size at
least $(1-\epsilon^{\prime})\cdot|A|$. In short, we will find this subset by
applying expander pruning on $H^{k}_{i,j}$ where $\bar{E}_{i,j}^{k}$ gives us
the edges we deleted as input to expander pruning. Specifically, letting
$\hat{H}^{k}_{i,j}$ be $H^{k}_{i,j}$ with $\bar{E}_{i,j}$ deleted, we know by
Lemma 5.29 that there is a subset of vertices $V^{\prime}_{i,j}\subseteq
V_{i,j}$ connected in $\hat{H}^{k}_{i,j}[V^{\prime}_{i,j}]$ satisfying

  1. 1.

$\hat{H}^{k}_{i,j}[V^{\prime}_{i,j}]$ is a $O(\frac{\log N}{k})$-step
$O(\frac{\log N}{k})$-router;

  2. 2.

$|V^{\prime}_{i,j}|\geq|V_{i,j}|-k\cdot 2^{O(k)}\cdot|\bar{E}_{i,j}|$.

This subset $V^{\prime}_{i,j}$ naturally corresponds to a node-weighting
$A_{i,j}^{\prime}$. In particular, we let $A_{i,j}^{\prime}$ on $v$ be:

$\displaystyle A_{i,j}^{\prime}(v):=|\text{copies}_{i,j}(v)\cap
V^{\prime}_{i,j}|$

and then let $A^{\prime}$ on $v$ be defined as:

$\displaystyle A^{\prime}(v):=\min_{i,j}A_{i,j}^{\prime}(v).$

First, we claim that $A^{\prime}\preccurlyeq A$. Observe that for each $v$ we
have:

$\displaystyle A^{\prime}(v)$ $\displaystyle=\min_{i,j}A_{i,j}^{\prime}(v)$
$\displaystyle\leq\max_{i,j}A_{i,j}^{\prime}(v)$
$\displaystyle=\max_{i,j}|\text{copies}_{i,j}(v)\cap V^{\prime}_{i,j}|$
$\displaystyle\leq A(v).$

Next, we claim that $|A^{\prime}|\geq|A|\cdot\left(1-\epsilon\cdot
2^{O(k)}\cdot N^{O(1/k^{\prime})}\cdot\log N\right)$.

Let $\bar{D}_{A,k,k^{\prime}}$ be all the demand that $F$ does not satisfy to
extent at least $.5$; that is, $\bar{D}_{A,k,k^{\prime}}$ on $(u,v)$ is
$\sum_{\\{u,v\\}\in\bar{E}}D_{A,k,k^{\prime}}(u,v)$. Observe that by an
averaging argument and our assumption that at least a $(1-\epsilon)$ fraction
of $D_{A,k,k^{\prime}}$ is routed we know that $|\bar{D}_{A,k,k^{\prime}}|\leq
2\epsilon\cdot|D_{A,k,k^{\prime}}|$. On the other hand, each pair of vertices
$\\{u,v\\}$ in $\bar{E}$ (i.e. each unsuccessfully embedded pair) corresponds
to at most $|E_{i,j}(u,v)|$ edges in $H^{k}_{i,j}$; and so

$\displaystyle\sum_{i,j}|\bar{E}_{i,j}|$
$\displaystyle=\sum_{i,j}\sum_{\\{u,v\\}\in\bar{E}}|E_{i,j}(u,v)|$
$\displaystyle=\sum_{i,j}\Delta^{k}\sum_{\\{u,v\\}\in\bar{E}}D_{i,j}(u,v)$
$\displaystyle=\Delta^{k}\cdot\operatorname{load}_{\mathcal{N}}\cdot\sum_{\\{u,v\\}\in\bar{E}}D_{A,k,k^{\prime}}(u,v)$
$\displaystyle=\Delta^{k}\cdot\operatorname{load}_{\mathcal{N}}\cdot|\bar{D}_{A,k,k^{\prime}}|$
$\displaystyle\leq\Delta^{k}\cdot\operatorname{load}_{\mathcal{N}}\cdot
2\epsilon\cdot|D_{A,k,k^{\prime}}|$ $\displaystyle\leq\epsilon\cdot
2^{O(k)}\cdot N^{O(1/k^{\prime})}\cdot\log N\cdot|D_{A,k,k^{\prime}}|.$ (2)

where in the last line we used our choice of neighborhood cover with load
$N^{O(1/k^{\prime})}\log N$ and the fact that $\Delta=O(1)$.

Thus, combining Equation 2, the fact that
$|V^{\prime}_{i,j}|\geq|V_{i,j}|-k\cdot 2^{O(k)}\cdot|\bar{E}_{i,j}|$ for each
$i$ and $j$ and the fact that $|D_{A,k,k^{\prime}}|\leq|A|$ since
$D_{A,k,k^{\prime}}$ is $A$-respecting (as proved in Lemma 7.1), we have

$\displaystyle|A^{\prime}|$ $\displaystyle=\sum_{v}A^{\prime}(v)$
$\displaystyle=\sum_{v}\min_{i,j}|\text{copies}_{i,j}(v)\cap
V_{i,j}^{\prime}|$
$\displaystyle=\sum_{v}A(v)-\max_{i,j}|\text{copies}_{i,j}(v)\setminus
V_{i,j}^{\prime}|$
$\displaystyle\geq\sum_{v}\left[A(v)-\sum_{i,j}|\text{copies}_{i,j}(v)\setminus
V_{i,j}^{\prime}|\right]$
$\displaystyle=|A|-\sum_{i,j}\left[|V(H^{k}_{i,j})|-|V_{i,j}^{\prime}|\right]$
$\displaystyle\geq|A|-k\cdot 2^{O(k)}\cdot\sum_{i,j}|\bar{E}_{i,j}|$
$\displaystyle\geq|A|\cdot\left(1-\epsilon\cdot 2^{O(k)}\cdot
N^{O(1/k^{\prime})}\cdot\log N\right)$

Lastly, we claim that $A^{\prime}$ is $(h,s^{\prime})$-length
$\phi^{\prime}$-expanding in $G^{\prime}$. Recall that
$s^{\prime}=O\left(s\cdot\frac{\log N}{k}\right)$ and
$\phi^{\prime}=\Omega\left(\phi\cdot 2^{-O(k)}\cdot
N^{-O(1/k^{\prime})}\log^{-2}N\right)$ By Theorem 5.17 it suffices to argue
that every $h$-length $A^{\prime}$-respecting demand can be routed in
$G^{\prime}$ with congestion at most $O\left(\frac{1}{\phi^{\prime}}\right)$
and dilation at most $O(hs^{\prime})$.

Consider an $A^{\prime}$-respecting $h$-length demand $D$ in $G^{\prime}$. As
above, let $F$ be our flow which certifies that at least a $(1-\epsilon)$
fraction of $D_{A,k,k^{\prime}}$ can be routed in $G^{\prime}$. The basic idea
is to route $D$ by treating $F$ as an embedding of each power graph
$H^{k}_{i,j}$ into $G^{\prime}$ and then routing in each $H^{k}_{i,j}$. We
will use this strategy to construct a flow $\hat{F}$ which routes $D$ by
routing it in each $H^{k}_{i,j}$ and then using $F$ to project this routes
back into $G^{\prime}$.

More formally, fix an $S_{i,j}$. We proceed to define a demand
$D^{\prime}_{i,j}$ on $\hat{H}^{k}_{i,j}[V^{\prime}_{i,j}]$. In particular,
for each pair of vertices $u^{\prime},v^{\prime}\in V^{\prime}_{i,j}$ where
$u^{\prime}\in\text{copies}(u)$ and $v^{\prime}\in\text{copies}(v)$ we let

$\displaystyle
D^{\prime}_{i,j}(u^{\prime},v^{\prime}):=\begin{cases}\frac{D(u,v)}{A_{i,j}^{\prime}(u)\cdot
A_{i,j}^{\prime}(v)}&\text{if $A^{\prime}(u)\cdot A^{\prime}(v)\neq 0$}\\\
0&\text{otherwise}\end{cases}$

and so by definition of $A_{i,j}^{\prime}(u)$ we have

$\displaystyle\sum_{u^{\prime}\in\text{copies}_{i,j}(u)}\sum_{v^{\prime}\in\text{copies}_{i,j}(v)}D^{\prime}_{i,j}(u^{\prime},v^{\prime})=D(u,v).$

We next claim that $D_{i,j}^{\prime}$ is degree-respecting in
$\hat{H}^{k}_{i,j}[V^{\prime}_{i,j}]$. To do so we will argue that for any
$u^{\prime}\in V_{i,j}^{\prime}$ we have
$\sum_{v^{\prime}}D^{\prime}_{i,j}(u^{\prime},v^{\prime})\leq 1$; showing a
symmetric upper bound on
$\sum_{v^{\prime}}D^{\prime}_{i,j}(v^{\prime},u^{\prime})$ is symmetric.
$u^{\prime}$ must have degree at least $1$ since we know that
$\hat{H}^{k}_{i,j}[V^{\prime}_{i,j}]$ is connected and so this shows that
$D_{i,j}^{\prime}$ is degree-respecting. To see this observe that applying the
definition of $D_{i,j}^{\prime}$ and the fact that $D$ is
$A^{\prime}$-respecting we have:

$\displaystyle\sum_{v^{\prime}}D^{\prime}_{i,j}(u^{\prime},v^{\prime})$
$\displaystyle=\sum_{v\in
S_{i,j}}\sum_{v^{\prime}\in\text{copies}_{i,j}(v)}D^{\prime}_{i,j}(u^{\prime},v^{\prime})$
$\displaystyle=\frac{1}{A^{\prime}(u)}\cdot\sum_{v}D(u,v)$ $\displaystyle\leq
1;$

Since $D_{i,j}^{\prime}$ is degree respecting and since
$\hat{H}^{k}_{i,j}[V^{\prime}_{i,j}]$ is a $O(\log N/k)$-step $O(\log
N/k)$-router, $D^{\prime}_{i,j}$ can be routed on
$\hat{H}^{k}_{i,j}[V^{\prime}_{i,j}]$ with congestion $O(\log N/k)$ and
$O(\log N/k)$ steps. Let $F^{\prime}_{i,j}$ be the flow on
$\hat{H}^{k}_{i,j}[V^{\prime}_{i,j}]$ that routes $D^{\prime}_{i,j}$ with
congestion $O(\log N/k)$ and $O(\log N/k)$ dilation.

By using $F$ as an embedding, we can see that $F^{\prime}_{i,j}$ naturally
corresponds to a flow $F_{i,j}$ on $G$. Specifically, by assumption an edge of
$\hat{H}^{k}_{i,j}[V^{\prime}_{i,j}]$ is of the form
$\\{u^{\prime},v^{\prime}\\}$ where $u^{\prime}\in\text{copies}_{i,j}(u)$,
$v^{\prime}\in\text{copies}_{i,j}(v)$ and $F(u,v)\geq.5\cdot
D_{A,k,k^{\prime}}(u,v)$. We can therefore project a flow path in the support
of $F_{i,j}^{\prime}$ into $G$ by concatenating the projection of each of its
incident edges $\\{u^{\prime},v^{\prime}\\}$ to the flow paths given by $F$ in
$G$ between $u$ and $v$. Below, we formalize this idea.

Consider a path
$P^{\prime}=(v_{1}^{\prime},v_{2}^{\prime},\ldots,v_{l}^{\prime})$ in the
support of $F_{i,j}^{\prime}$ where
$v_{x}^{\prime}\in\text{copies}_{i,j}(v_{x})$ for each $x\in[l]$. Let
$\mathcal{P}_{x}(P^{\prime})$ be all paths between $v_{x}$ and $v_{x+1}$ in
the support of $F$. By adding paths with multiplicity to
$\mathcal{P}_{x}(P^{\prime})$, we may assume that $F$ sends some equal flow
amount $\rho_{P^{\prime}}$ along each path in $\mathcal{P}_{x}(P^{\prime})$
for every $x$. Then, letting $z$ be $\min_{x}|\mathcal{P}_{x}(P^{\prime})|$
(i.e. the number of paths corresponding to the $v_{x},v_{x+1}$ pair that has
the least flow sent by $F$) we construct a collection of $z$ paths
$\mathcal{P}(P^{\prime})$ in $G$ gotten by selecting one path from each $x$;
that is if use an arbitrary fixed ordering to the paths of
$\mathcal{P}_{x}(P^{\prime})$ and we imagine that the first $z$ paths of
$\mathcal{P}_{x}(P^{\prime})$ are
$\\{P_{x}^{(1)},P_{x}^{(2)},\ldots\,P_{x}^{(z)}\\}$ then
$\mathcal{P}(P^{\prime})$ consists of paths in $G$ and is

$\displaystyle\mathcal{P}(P^{\prime}):=\left\\{P_{1}^{(y)}\oplus
P_{2}^{(y)}\oplus\ldots\oplus P_{l-1}^{(y)}:y\in[z]\right\\}$

where $\oplus$ is path concatenation. Observe that each path in
$\mathcal{P}(P^{\prime})$ is a path in $G$ of length at most $O(h\cdot\log
N/k)$. Let $F_{i,j}^{(P^{\prime})}$ be the flow that sends
$F_{i,j}(P^{\prime})$ flow by sending equal flow along each path in
$\mathcal{P}(P^{\prime})$ in $G$; that is

$\displaystyle F_{i,j}^{(P^{\prime})}(P):=\begin{cases}\frac{1}{z}\cdot
F_{i,j}^{\prime}(P^{\prime})&\text{if $P\in\mathcal{P}(P^{\prime})$}\\\
0&\text{otherwise}\end{cases}$

Lastly, we can construct $F_{i,j}$ as the result of doing this for all flows
in the support of $F^{\prime}_{i,j}$; that is,

$\displaystyle
F_{i,j}:=\sum_{P^{\prime}\in\mathrm{supp}(F^{\prime}_{i,j})}F_{i,j}^{(P^{\prime})}$

We let our final flow $\hat{F}$ to route the demand $D$ that we started with
be the result of doing this for every cluster in our neighborhood cover:

$\displaystyle\hat{F}:=\sum_{i,j}F_{i,j}$

It remains to argue that $\hat{F}$ routes our $A^{\prime}$-respecting
$h$-length demand $D$ with congestion $O\left(\frac{1}{\phi^{\prime}}\right)$
and dilation $O(hs^{\prime})$ in $G^{\prime}$.

We begin by arguing that $\hat{F}$ indeed routes $D$. To see this consider a
pair of vertices $u$ and $v$ in $G^{\prime}$ with $D(u,v)>0$. Since $D$ is
$h$-length, $\mathcal{N}$ has covering radius $h$ and applying a moving cut
only increases the distances between nodes, it follows that there is some $i$
and $j$ for which $u,v\in S_{i,j}$. For this $i$ and $j$ we know that each
$F_{i,j}^{(P^{\prime})}$ sends $F_{i,j}^{\prime}(P^{\prime})$ from a copy of
$u$ to a copy of $v$ and so summing across all $P^{\prime}$ from copies of $u$
to copies of $v$ we can see that

$\displaystyle\hat{F}(u,v)$ $\displaystyle\geq F_{i,j}(u,v)$
$\displaystyle=\sum_{u^{\prime}\in\text{copies}_{i,j}(u)}\sum_{v^{\prime}\in\text{copies}_{i,j}(v)}\sum_{P^{\prime}=(u^{\prime},\ldots,v^{\prime})}F_{i,j}^{(P^{\prime})}(u,v)$
$\displaystyle=\sum_{u^{\prime}\in\text{copies}_{i,j}(u)}\sum_{v^{\prime}\in\text{copies}_{i,j}(v)}\sum_{P^{\prime}=(u^{\prime},\ldots,v^{\prime})}F^{\prime}_{i,j}(P^{\prime})$
$\displaystyle=\sum_{u^{\prime}\in\text{copies}_{i,j}(u)}\sum_{v^{\prime}\in\text{copies}_{i,j}(v)}F^{\prime}_{i,j}(u^{\prime},v^{\prime})$
$\displaystyle=\sum_{u^{\prime}\text{copies}_{i,j}(u)}\sum_{v^{\prime}\in\text{copies}_{i,j}(v)}D^{\prime}_{i,j}(u^{\prime},v^{\prime})$
$\displaystyle=D(u,v)$

Our bound on the dilation of $\hat{F}$ is immediate from the fact that every
path in $\mathcal{P}(P^{\prime})$ for every
$P^{\prime}\in\mathrm{supp}(F_{i,j}^{\prime})$ for every $i$ and $j$ has
length at most $O(h\cdot\log N/k)=O(hs^{\prime})$.

Lastly, we now argue that $\hat{F}$ has congestion at most
$O\left(\frac{1}{\phi^{\prime}}\right)=O\left(\frac{1}{\phi}\cdot
2^{O(k)}\cdot N^{O(1/k^{\prime})}\log^{2}N\right)$. For each
$e^{\prime}=\\{u^{\prime},v^{\prime}\\}\in E(H^{k}_{i,j})$ where
$u^{\prime}\in\text{copies}_{i,j}(u)$ and
$v^{\prime}\in\text{copies}_{i,j}(v)$, let

$\displaystyle F_{e^{\prime}\to
e}:=\frac{1}{|E_{i,j}^{k}(u,v)|}\cdot\sum_{P=(u,\ldots,v)\ni e}F(P)$

be the flow induced on edge $e$ resulting from embedding $e^{\prime}$ into
$e$. Applying the fact that each $F_{i,j}^{\prime}$ has congestion $O(\log
N/k)$, the fact that $F(u,v)\geq.5\cdot D_{A,k,k^{\prime}}(u,v)$ if
$\\{u^{\prime},v^{\prime}\\}\in\hat{H}_{i,j}^{k}[V_{i,j}^{\prime}]$, the
separation factor of our neighborhood cover $\mathcal{N}$ is $2$ (and so our
absolute separation is at least $h$) and $F$ has congestion $\frac{1}{\phi}$,
we have that the congestion of $\hat{F}$ on a given edge $e$ in $G$ is

$\displaystyle\sum_{P\ni e}\hat{F}(P)$
$\displaystyle=\sum_{i,j}\sum_{e^{\prime}\in
E(H^{k}_{i,j}[V_{i,j}^{\prime}])}F_{i,j}^{\prime}(e^{\prime})\cdot
F_{e^{\prime}\to e}$ $\displaystyle\leq O(\log
N/k)\cdot\sum_{i,j}\sum_{e^{\prime}\in
E(H^{k}_{i,j}[V_{i,j}^{\prime}])}F_{e^{\prime}\to e}$ $\displaystyle=O(\log
N/k)\cdot\Delta^{k}\cdot\operatorname{load}_{\mathcal{N}}\cdot F(e)$
$\displaystyle\leq
O\left(\frac{1}{\phi}\cdot\frac{\Delta^{k}\cdot\operatorname{load}_{\mathcal{N}}}{k}\right)$
$\displaystyle\leq O\left(\frac{1}{\phi}\cdot 2^{O(k)}\cdot
N^{O(1/k^{\prime})}\cdot\log^{2}N\right)$

as desired. ∎

##  8 Robustness of Length-Constrained Expanders

In this section we prove that, like (classic) expanders, length-constrained
expanders are robust to edge deletions. In particular, we show that if we
begin with a length-constrained expander and delete a small number of edges,
then, up to various slacks, the remaining graph is mostly still a length-
constrained expander.

The basic strategy for proving this fact will be to use the characterization
of length-constrained expanders in terms of expander power embeddings from
previous section. In particular, we will use this characterization and then
apply the robustness of each of the embedded expander powers.

Formally, we show the following theorem.

######  Theorem 8.1 (Robustness of Length-Constrained Expanders).

Suppose that $G=(V,E,\ell)$ is an $(hk^{\prime},s)$-length $\phi$-expander
with respect to node weighting $A$ for $k^{\prime}\geq 1$, let $C$ be a moving
cut and let $G^{\prime}:=(V,E,\ell+C)$ be $G$ with $C$ applied. Then, for any
integer $k\geq 1$ there exists a node weighting $A^{\prime}\preccurlyeq A$
that is $(h,s^{\prime})$-length $\phi^{\prime}$-expanding in $G^{\prime}$ such
that $|A^{\prime}|\geq|A|-|C|\cdot O\left(\frac{2^{O(k)}\cdot
N^{O(1/k^{\prime})}\cdot\log N}{\phi}\right)$ where
$\phi^{\prime}=\Omega\left(\phi\cdot 2^{-O(k)}\cdot
N^{-O(1/k^{\prime})}\cdot\log^{-2}N\right)$ and
$s^{\prime}=O\left(s\cdot\frac{k^{\prime}}{k}\cdot\log N\right)$.

###### Proof.

Our proof sketch is as follows. Consider the neighborhood router demand. Then,
observe that $C$ can increase the length of only a constant fraction of the
paths in the support of the flow which routes the neighborhood router demand
and conclude by 7.1 that there exists a large expanding subset.

More formally, let $D_{A,k,k^{\prime}}$ be our neighborhood routing demand as
defined in Section 7.1.

By 7.1 since $G$ is an $(hk^{\prime},s)$ $\phi$-expander, it follows that
$D_{A,k,k^{\prime}}$ can be routed in $G$ with congestion at most
$O(\frac{1}{\phi})$ and dilation $2k^{\prime}\cdot hs$. Let $F$ be the flow
that witnesses this routing. Since $F$ has congestion at most
$O(\frac{1}{\phi})$, it follows by an averaging argument that the total flow
across paths in the support of $F$ which have their length increased to at
least $4k^{\prime}\cdot hs$ is at most $O(\frac{1}{\phi})\cdot|C|$. That is,

$\displaystyle\sum_{P\in\mathrm{supp}(F):\ell_{G^{\prime}}(P)>4k^{\prime}\cdot
hs}F(P)\leq O\left(\frac{1}{\phi}\right)\cdot|C|.$

Let $F^{\prime}$ be $F$ restricted to all paths in the support of $F$ with
length at most $4k^{\prime}\cdot hs$ in $G^{\prime}$ so that
$\mathrm{val}(F^{\prime})\geq\mathrm{val}(F)-O\left(\frac{1}{\phi}\right)\cdot|C|$.
Observe that by construction the dilation of $F^{\prime}$ is
$O(k^{\prime}\cdot hs)$.

Furthermore, observe that it follows from the existence of $F^{\prime}$ that
at least a $1-\epsilon$ fraction of $D_{A,k,k^{\prime}}$ can be routed in
$G^{\prime}$ for
$\epsilon=\Omega\left(\frac{|C|}{\mathrm{val}(F)}\cdot\frac{1}{\phi}\right)\geq\Omega\left(\frac{|C|}{|A|}\cdot\frac{1}{\phi}\right)$
with congestion at most $O\left(\frac{1}{\phi}\right)$ and dilation at most
$O(h\cdot sk^{\prime})$. Applying 7.1 tells us that there is a node weighting
$A^{\prime}\preceq A$ where

$\displaystyle|A^{\prime}|$
$\displaystyle\geq|A|\cdot\left(1-O\left(\epsilon\cdot 2^{O(k)}\cdot
N^{O(1/k^{\prime})}\cdot\log N\right)\right)$ $\displaystyle\geq|A|-|C|\cdot
O\left(\frac{2^{O(k)}\cdot N^{O(1/k^{\prime})}\cdot\log N}{\phi}\right)$

and $A^{\prime}$ is $(h,s^{\prime})$-length $\phi^{\prime}$-expanding in
$G^{\prime}$ where $s^{\prime}=O(s\cdot\frac{k^{\prime}}{k}\cdot\log N)$ and
$\phi^{\prime}=\Omega\left(\phi\cdot 2^{-O(k)}\cdot
N^{-O(1/k^{\prime})}\cdot\log^{-2}N\right)$ as required to show our theorem. ∎

##  9 Union of Sparse (Classic) Cut Sequence is Sparse

In this section we prove that the union of a sequence of sparse (classic) cuts
is still a sparse (classic) cut with only an $O(\log n)$ loss in sparsity.
Before proceeding, it may be useful for the reader to recall the definition of
the sparsity of a classic cut in Section 5.1 and, in particular, the
definition of the witness components of a cut.

Formally, we consider the following notion of a sequence of sparse (classic)
cuts.

######  Definition 9.1 (Sequence of (Classic) Cuts).

Given graph $G=(V,E)$, a sequence of (classic) cuts is a sequence of (classic)
cuts $(C_{1},C_{2},\ldots)$ where each $C_{i}$ is a cut all of whose edges are
internal to one connected component $H_{i}$ of $G-\sum_{j<i}C_{j}$. We refer
to $H_{i}$ as the source component of $C_{i}$ and the sparsity of $C_{i}$ in
$H_{i}$ as its sparsity in the sequence.

The following formalizes the idea that the union of (classic) sparse cuts is
sparse. Observe that, in fact, it proves a slightly stronger statement,
namely, that the union of cuts has a sparsity at most the (appropriately
weighted) average of the cuts in the sequence.

######  Theorem 9.1 (Union of Sparse (Classic) Cut Sequence is a Sparse
(Classic) Cut).

Given graph $G=(V,E)$, let $(C_{1},C_{2},\ldots)$ be a sequence of (classic)
cuts where $C_{i}$ has sparsity $\phi_{i}$ in this sequence. Then the cut
$\bigcup_{i}C_{i}$ has sparsity $\phi^{\prime}$ in $G$ where
$\phi^{\prime}\leq O(\log
n)\cdot\frac{\sum_{i}|C_{i}|}{\sum_{i}|C_{i}|/\phi_{i}}$.

Observe that if each $C_{i}$ has sparsity $\phi$ in the sequence then we get
that $\bigcup_{i}C_{i}$ has sparsity $O(\phi\cdot\log n)$. Intuitively, we get
$O(\log n)$ overhead because each time we take a cut we charge to the smaller
side and so an edge can only be charged at most $O(\log n)$ times until its
side is empty. The remainder of this section makes this proof idea formal.

###  9.1 Warmup: When the Source Component is Not a Witness Component

As a simple warmup and helper lemma we observe that the union of two sparse
cuts is still sparse assuming the second cut is not in a witness component of
the first cut.

######  Lemma 9.2.

Let $(C_{1},C_{2})$ be a sequence of two (classic) cuts where $C_{i}$ has
sparsity $\phi_{i}$ in the sequence. Then if the source component of $C_{2}$
is not a witness component of $C_{1}$ we have $C_{1}\cup C_{2}$ has sparsity
at most $\phi^{\prime}$ in $G$ where
$\phi^{\prime}\leq\frac{\sum_{i}|C_{i}|}{\sum_{i}|C_{i}|/\phi_{i}}$.

###### Proof.

Let $C=C_{1}\cup C_{2}$. Let $M_{1}$ be the connected component of $G-C_{1}$
of maximum volume in $G$, (i.e. the one component that is not a witness
component for $C_{1}$ but which is a source component for $C_{2}$). Similarly,
let $M$ be the connected component of $G-C$ of maximum volume in $G$ (i.e. the
one component that is not a witness component for $C$).

Observe that $\mathrm{vol}(M_{2})\leq\mathrm{vol}(M)$ since $M_{2}$ is a
subset of $M$. Letting $m$ be $|E|$, o, it follows that

$\displaystyle m-\mathrm{vol}(M)$
$\displaystyle=m-\mathrm{vol}(M_{1})+\mathrm{vol}(M_{1})-\mathrm{vol}(M)$
$\displaystyle\geq
m-\mathrm{vol}(M_{1})+\mathrm{vol}(M_{1})-\mathrm{vol}(M_{2}).$ (3)

On the other hand, observe that by definition of sparsity and the fact that
the source component of $C_{2}$ is $M_{1}$ we have

$\displaystyle\frac{|C_{1}|}{\phi_{1}}=m-\mathrm{vol}(M_{1})$ (4)

and

$\displaystyle\frac{|C_{2}|}{\phi_{2}}=\mathrm{vol}(M_{1})-\mathrm{vol}(M_{2})$
(5)

and so combining Equations 3, 4 and 5 we get

$\displaystyle m-\mathrm{vol}(M)\geq\sum_{i}\frac{|C_{i}|}{\phi_{i}}.$

Applying this and the definition of sparsity we get

$\displaystyle\phi(C)\leq\frac{\sum_{i}|C_{i}|}{\sum_{i}|C_{i}|/\phi_{i}},$

as required. ∎

As a simple implication of this fact we have that the union of an arbitrary-
length sequence of (classic) sparse cuts is still sparse provided each cut in
the sequence is never applied to the witness component of any previous cut.

######  Lemma 9.3.

Let $(C_{1},C_{2},\ldots)$ be a sequence of (classic) cuts where $C_{i}$ has
sparsity $\phi_{i}$ in the sequence. Then if we have that the source component
of $C_{j}$ is not a witness component of $C_{i}$ for all $i$ and $j>i$ then
$\bigcup_{i}C_{i}$ is a $\phi^{\prime}$-sparse cut in $G$ where
$\phi^{\prime}\leq\frac{\sum_{i}|C_{i}|}{\sum_{i}|C_{i}|/\phi_{i}}$.

###### Proof.

The proof is by a simple induction on the number of cuts in the sequence $k$
and repeated application of Lemma 9.2.

The base case of $k=1$ is trivial and the base case of $k=2$ is immediate from
Lemma 9.2.

Consider the case of $k>3$. By Lemma 9.2 we know that $C:=C_{k-1}\cup C_{k}$
is a cut with sparsity $\phi_{C}$ which is at most
$\frac{|C_{k-1}|+|C_{k}|}{|C_{k-1}|/\phi_{k-1}+|C_{k}|/\phi_{k}}$. Now
consider the cut sequence resulting from taking the union of the last two
cuts, namely $(C_{1},C_{2},\ldots,C_{k-2},C)$. The source component of $C$ is
the same as the source component of $C_{k-1}$ and so the precondition of our
induction holds and, in particular, by induction we know that
$\bigcup_{i}C_{i}$ has sparsity at most

$\displaystyle\frac{\sum_{i}|C_{i}|}{|C|/\phi_{C}+\sum_{i\leq
k-2}|C_{i}|/\phi_{i}}.$ (6)

Further, observe that by our upper bound on $\phi_{C}$ and the fact that
$|C|=|C_{k-1}|+|C_{k}|$ we know that
$\frac{|C|}{\phi_{C}}\geq\frac{|C_{k-1}|}{\phi_{k-1}}+\frac{|C_{k}|}{\phi_{k}}$.
Combining this with Equation 6 gives that $\bigcup_{i}C_{i}$ has sparsity at
most

$\displaystyle\frac{\sum_{i}|C_{i}|}{\sum_{i}|C_{i}|/\phi_{i}},$

as required. ∎

###  9.2 Proving the General Case for (Classic) Cuts

We now conclude this section with our proof that the union of (classic) sparse
cuts is a sparse cut (9.1). Roughly, our proof arranges the sequence of cuts
into a “cut sequence tree” and then decomposes this tree into paths that
satisfy the preconditions of Lemma 9.3 and so can be unioned together to get
cuts of the same sparsity. After contracting such paths in our cut sequence
tree we can argue that the result is a depth $O(\log n)$ tree and so by
averaging over layers of this tree we can argue that some layer induces
sparsity within an $O(\log n)$ of the sparsity for which we are aiming. For
readers familiar with heavy-light decompositions [ST81]: this decomposition
can be understood as a special sort of heavy-light decomposition whose heavy
paths correspond satisfy the preconditions of Lemma 9.3.

Formally, our proof will arrange our cuts into a cut sequence tree which
corresponds to the natural laminar partition gotten by applying a sequence of
sparse cuts. See Figure 2 for an illustration.

(a) Cut sequence on $G$.

(b) Connected components.

(c) Cut sequence tree.

Figure 2: A cut sequence (2(a)), the resulting connected components from
applying all cuts in the sequence (2(b)) and the corresponding cut sequence
tree (2(c)). Cuts colored to correspond to the depth of their nodes in the cut
sequence tree. Internal nodes in cut sequence tree labeled according to their
corresponding cut and leaves labeled according to their connected component.

######  Definition 9.4 (Cut Sequence Tree).

Given graph $G=(V,E)$, let $\mathcal{C}:=(C_{1},C_{2},\ldots,C_{k})$ be a
sequence of (classic) cuts. Then, the cut tree $T_{\mathcal{C}}$ of
$\mathcal{C}$ is recursively defined as follows.

  * •

Suppose $k=1$. Then $T_{\mathcal{C}}$ is a star with one leaf for every
connected component of $G-C_{1}$.

  * •

Suppose $k>1$. Then let $T_{\mathcal{C}^{\prime}}$ be the cut sequence tree
for $\mathcal{C}^{\prime}=(C_{1},C_{2},\ldots,C_{k-1})$ and let $H_{k}$ be the
source component of $C_{k}$. $T_{\mathcal{C}}$ is the result of taking
$T_{\mathcal{C}^{\prime}}$ and adding one child for each connected component
of $H_{k}-C_{k}$ to the leaf of $T_{\mathcal{C}^{\prime}}$ corresponding to
$H_{k}$.

Observe that in the above tree each internal vertex corresponds to a cut of
$\mathcal{C}$ and every vertex corresponds to a connected component in $G$
after applying some prefix of the cuts $\mathcal{C}$.

We proceed to prove the our main theorem for the section. See 9.1

###### Proof.

Let $T_{\mathcal{C}}$ be the cut sequence tree of
$\mathcal{C}=(C_{1},C_{2},\ldots)$ as defined in Definition 9.4.

Call an edge from parent $u$ to child $v$ _heavy_ if:

  1. 1.

$u$ and $v$ are internal in $T_{\mathcal{C}}$ and;

  2. 2.

the component corresponding to $v$ is not a witness component of the cut
corresponding to $u$.

Otherwise, call an edge _light_.

Observe that as each vertex has at most one heavy child the collection of
heavy edges induces vertex-disjoint paths in $T_{\mathcal{C}}$, the union of
which contain all vertices corresponding to a cut in $\mathcal{C}$ (i.e. all
internal vertices of $T_{\mathcal{C}}$). Also, observe that any any root to
leaf path intersects at most $O(\log n)$ light edges since each time a light
edge is traversed the corresponding component’s number of vertices is
decreased by at least $\frac{1}{2}$.

Consider one such path of heavy edges $P=(u_{1},u_{2},\ldots)$ where $u_{1}$
is the vertex closest to the root in $T_{\mathcal{C}}$. Call such a path a
heavy path. Observe that by definition of a heavy edge the cut sequence gotten
by taking the cuts corresponding $(C_{1}^{\prime},C_{2}^{\prime},\ldots)$ to
these vertices satisfies the conditions of Lemma 9.3 and so their union
$\mathcal{C}^{\prime}:=\bigcup_{i}C_{i}^{\prime}$ has sparsity at most

$\displaystyle\frac{\sum_{i}|C_{i}^{\prime}|}{\sum_{i}|C_{i}^{\prime}|/\phi_{i}^{\prime}}.$
(7)

where $\phi_{i}^{\prime}$ is the sparsity of $C_{i}^{\prime}$.

Next, consider the cut sequence from taking the cuts corresponding to all such
heavy paths. More formally order the heavy paths of $T_{\mathcal{C}}$ in a
fixed but arbitrary order $(P_{1},P_{2},\ldots)$ where if $i<j$ then no vertex
of $P_{j}$ is an ancestor of a vertex in $P_{i}$ in $T_{\mathcal{C}}$. Next,
consider the cut sequence
$\tilde{\mathcal{C}}:=(\tilde{C}_{1},\tilde{C}_{2},\ldots)$ where
$\tilde{C}_{i}$ is the result of taking the union of all cuts corresponding to
vertices in path $P_{i}$.

Observe that the cut tree $T_{\tilde{\mathcal{C}}}$ for this sequence
$\tilde{\mathcal{C}}$ is just the result of contracting all heavy edges in
$T_{\mathcal{C}}$. Furthermore, observe that this tree has depth at most
$O(\log n)$ since any root to leaf path in $T_{\mathcal{C}}$ intersects at
most $O(\log n)$ light edges.

Consider a fixed layer of $T_{\tilde{\mathcal{C}}}$, namely a subset of
vertices all of who are equal distance in $T_{\tilde{\mathcal{C}}}$ from the
root of $T_{\tilde{\mathcal{C}}}$. Let $\tilde{L}$ be the cuts of
$\tilde{\mathcal{C}}$ corresponding to these vertices and let $L$ be all cuts
of $\mathcal{C}$ that are a subset of some cut in $\tilde{\mathcal{C}}$.

Further, assume that $\tilde{L}$ is the layer with corresponding $L$
maximizing $\sum_{C_{i}\in L}|C_{i}|/\phi_{i}$. Observe that by averaging we
know that

$\displaystyle\sum_{C_{i}\in L}|C_{i}|/\phi_{i}\geq\Omega(1/\log
n)\cdot\sum_{i}|C_{i}|/\phi_{i}$ (8)

Letting $C=\bigcup_{i}C_{i}$ we know that

$\displaystyle\sum_{S_{C}\in\mathcal{S}_{C}}\mathrm{vol}(S_{C})\geq\sum_{\tilde{C}\in\tilde{L}}\sum_{S_{\tilde{C}}\in\mathcal{S}_{\tilde{C}}}\mathrm{vol}(S_{\tilde{C}})$
(9)

since the witness components of all cuts in $\tilde{L}$ are disjoint and the
one component of $G-C$ that is not a witness component of $C$ can only be
smaller in volume than any of the non-witness components of cuts in
$\tilde{L}$.

Furthermore, observe that by the definitions of sparsity (Definition 5.2), $L$
and $\tilde{L}$ as well as Equation 7 we have

$\displaystyle\sum_{\tilde{C}\in\tilde{L}}\sum_{S_{\tilde{C}}\in\mathcal{S}_{\tilde{C}}}\mathrm{vol}(S_{\tilde{C}})\geq\sum_{C_{i}\in
L}|C_{i}|/\phi_{i}.$ (10)

Combining Equations 8, 9 and 10 we get

$\displaystyle\Omega(1/\log
n)\cdot\sum_{i}|C_{i}|/\phi_{i}\leq\sum_{S_{C}\in\mathcal{S}_{C}}\mathrm{vol}(S_{C}).$

which when combined with the definition of sparsity and fact that
$|C|=\sum_{i}|C_{i}|$ gives our claim. ∎

##  10 Union of Sparse Moving Cut Sequence is Sparse

In the previous section we saw that the union of sequence of classic sparse
cuts is itself a sparse cut. In this section, we prove this fact in the much
more challenging length-constrained setting. In particular, we show that
taking the union of moving cuts preserves sparsity up to an $N^{O(1/s)}$
factor.

Formally, we consider a sequence of moving cuts, defined as follows.

######  Definition 10.1 (Sequence of Moving Cuts).

Given graph $G=(V,E)$ and node-weighting $A$, a sequence of moving cuts is a
sequence of moving cuts $(C_{1},C_{2},\ldots)$. We refer to the $(h,s)$-length
sparsity of $C_{i}$ with respect to $A$ in $G-\sum_{j<i}C_{j}$ as its
$(h,s)$-length sparsity in the sequence. We say the sequence
$(C_{1},C_{2},\ldots)$ is $(h,s)$-length $\phi$-sparse if each $C_{i}$ is
$(h,s)$-length $\phi$-sparse in the sequence.

The following summarizes the main theorem of this section: that the union of
sparse length-constrained moving cuts is sparse. See 1.2 Observe that if every
cut $C_{i}$ above is $(h,s)$-length, then $\sum_{i}C_{i}$ is
$(h^{\prime},s^{\prime})$-length $\phi$-sparse. However, if some of the cuts
are even sparser then this lowers the sparsity of $\sum_{i}C_{i}$.
$\frac{\phi}{\operatorname{spars}_{(h,s)}(C,A)}\cdot|C|$.

To prove the above theorem we must demonstrate the existence of some unit
demand $D$ that witnesses the sparsity of $\sum_{i}C_{i}$. However, if $D_{i}$
is the demand which witnesses the sparsity of $C_{i}$, we cannot just use
$\sum_{i}D_{i}$ as $D$ since the result need not be unit. The main idea is to
argue that $\sum_{i}D_{i}$ can be understood as, more or less, greedily
constructing a spanner in parallel and as such induces a graph with arboricity
about $N^{O(1/s)}$ where $s$ is the length slack (see Section 4 for a
definition of arboricity). We can then decompose $\sum_{i}D_{i}$ into trees
and use each of these trees to “disperse” the load of $\sum_{i}D_{i}$ so that
the resulting demand $D$ is unit (after scaling down by about the arboricity).
The rest of this section formalizes this argument.

###  10.1 Low Arboricity Demand Matching Graph via Parallel Greedy Spanners

We begin by formalizing the graph induced by the witnessing demands of our cut
sequence. We call this graph the demand matching graph. Informally, this graph
simply creates $A(v)$ copies for each vertex $v$ and then matches copies to
one another in accordance with the witnessing demands.

######  Definition 10.2 (Demand Matching Graph).

Given a graph $G=(V,E)$, a node-weighting $A$ and $A$-respecting demands
$\mathcal{D}=(D_{1},D_{2},\ldots)$ we define the demand matching (multi)-graph
$G(\mathcal{D})=(V^{\prime},E^{\prime})$ as follows:

  * •

Vertices: $H$ has vertices $V^{\prime}=\bigsqcup_{v}\text{copies}(v)$ where
$\text{copies}(v)$ is $A(v)$ unique “copies” of $v$.

  * •

Edges: For each demand $D_{i}$, let $E_{i}$ be any matching where the number
of edges between $\text{copies}(u)$ and $\text{copies}(v)$ for each $u,v\in V$
is $D_{i}(u,v)$. Then $E^{\prime}=\bigcup_{i}E_{i}$.

The key property of the demand matching graph that we use is that it induces a
graph with low arboricity. We prove this by observing that it can be
understood as performing a certain parallel greedy spanner construction. The
following summarizes this.

######  Lemma 10.3 (Bounded Arboricity of Demands of Sequence of Cuts).

Let $C_{1},C_{2},\ldots$ be a sequence of $(h,s)$-length cuts with witnessing
demands $\mathcal{D}=(D_{1},D_{2},\ldots)$. Then $G(\mathcal{D})$ has
arboricity at most $s^{3}\cdot\log^{3}N\cdot N^{O(1/s)}$.

###### Proof.

We say that a sequence $(E_{1},\ldots,E_{k})$ of edge sets on $V$ is $s$-pg
(abbreviation for $s$-parallel greedy) for some integer $s\geq 2$, iff for
each $1\leq i\leq k$,

  * •

set $E_{i}$ is a matching on $V$; and

  * •

if we denote by $G_{i-1}$ the graph on $V$ induced by edges in $\bigcup_{1\leq
j\leq i-1}E_{j}$, then for every edge $(u,v)\in E_{i}$, $d_{G_{i-1}}(u,v)>s$.

Equivalently, a sequence $(E_{1},\ldots,E_{k})$ is $s$-pg iff for each $1\leq
i\leq k$, every cycle in $G_{i}$ of length at most $s+1$ contains at least two
edges in $E_{i}$. We say that a graph $G$ is $s$-pg iff its edge set $E(G)$ is
the union of some $s$-pg sequence on $V(G)$. [HHT23] proves that every $s$-pg
graph on $n$ vertices has arboricity $s^{3}\cdot\log^{3}n\cdot n^{O(1/s)}$.

We now show that this fact implies Lemma 10.3 by showing that
$G({\mathcal{D}})$ is a $s$-pg graph. By definition, $G({\mathcal{D}})$ is the
union of a sequence of matchings. Denote $D=(D_{1},\ldots,D_{k})$. For each
$i$, let $G_{i}({\mathcal{D}})$ be the union of all matchings corresponding to
$D_{k},\ldots,D_{i}$. Consider an edge in $E_{i-1}$, the matching
corresponding to demand $D_{i-1}$. By definition, it suffices to show that for
each $(u,v)\in E_{i-1}$, there is no length-at-most-$s$ path in $G_{i}$
containing $u,v$. Assume for contradiction that there exists a path
$P=(u,x_{1},\ldots,x_{s-1},v)$ in $G_{i}$. This means that in graph
$G-\sum_{1\leq j\leq i-1}C_{j}$, every pair in
$(u,x_{1}),(x_{1},x_{2}),\ldots,(x_{s-1},v)$ is at distance at most $h$. By
triangle inequality, this implies that the distance between $u,v$ in
$G-\sum_{1\leq j\leq i-1}C_{j}$ is less than $hs$. However, as the moving cut
$C_{i-1},C_{i-1},\ldots,C_{1}$ separates all pairs in
$D_{i-1},D_{i-1},\ldots,D_{1}$ to distance more than $hs$, as an edge in
$E_{i-1}$ (which is a pair in $\bigcup_{1\leq j\leq i-1}D_{j}$), $u$ and $v$
should be at distance more than $hs$ in $G-\sum_{1\leq j\leq i-1}C_{j}$, a
contradiction. ∎

###  10.2 Matching-Dispersed Demand

In the previous section we formalized the graph induced by the witnessing
demands $(D_{1},D_{2},\ldots)$ of a sequence of sparse moving cuts and argued
that this graph has low arboricity. We now discuss how to use the forest
decomposition of this graph to disperse $(D_{1},D_{2},\ldots)$ so that the
result is a unit demand.

(a) Input tree $T$.

(b) $\mathrm{disperse}_{T}$.

Figure 3: How we disperse demand given a tree $T$ (3(a)). 3(b) gives the
support of $\mathrm{disperse}_{T}$ dashed in blue; notice that each vertex has
degree at most $2$.

The following notion of tree matching demand formalizes how we disperse the
demand in each tree of the forest decomposition of demand matching graph.
Informally, given a tree this demand simply matches siblings in the tree to
one another. If there are an odd number of siblings the leftover child is
matched to its parent. See Figure 3 for an illustration.

######  Definition 10.4 (Tree Matching Demand).

Given tree $T=(V,E)$ we define the tree-matching demand on $T$ as follows.
Root $T$ arbitrarily. For each vertex $v$ with children $C_{v}$ do the
following. If $|C_{v}|$ is odd let $U_{v}=C_{v}\cup\\{v\\}$, otherwise let
$U_{v}=C_{v}$. Let $M_{v}$ be an arbitrary perfect matching on $U_{v}$ and
define the demand associated with $v$ as

$\displaystyle D_{v}(u_{1},u_{2}):=\begin{cases}1&\text{if
$\\{u_{1},u_{2}\\}\in M_{v}$}\\\ 0&\text{otherwise}.\end{cases}$

where each edge in $M_{v}$ has an arbitrary canonical $u_{1}$ and $u_{2}$.
Then, the tree matching demand for $T$ is defined as

$\displaystyle\mathrm{disperse}_{T}:=\sum_{v\text{ internal in }T}D_{v}$

We observe that a tree matching demand has size equal to the input size (up to
constants).

######  Lemma 10.5.

Let $T$ be a tree with $n-1$ vertices. Then
$|\mathrm{disperse}_{T}|\geq\frac{n-1}{2}$.

###### Proof.

For each $v$ that is internal in $T$ let the vertices $U_{v}$ and the perfect
matching $M_{v}$ on $U_{v}$ be as defined in Definition 10.4. Then, observe
that $\sum_{v}|U_{v}|\geq n-1$ since every vertex except for the root appear
in at least one $U_{v}$. On the other hand, for each $v$ since $M_{v}$ is a
perfect matching on $U_{v}$ we have $|M_{v}|=\frac{1}{2}|U_{v}|$ and since
$|\mathrm{disperse}_{T}|=\sum_{v\text{ internal in }T}|M_{v}|$, it follows
that $|\mathrm{disperse}_{T}|\geq\frac{n-1}{2}$ as required. ∎

Having formalized how we disperse a demand on a single tree with the tree
matching demand, we now formalize how we disperse an arbitrary demand by
taking a forest cover, applying the matching-dispersed demand to each tree and
then scaling down by the arboricity.

######  Definition 10.6 (Matching-Dispersed Demand).

Given graph $G$, node-weighting $A$ and demands
$\mathcal{D}=(D_{1},D_{2},\ldots)$, let $G(\mathcal{D})$ be the demand
matching graph (Definition 10.2), let $T_{1},T_{2},\ldots$ be the trees of a
minimum size forest cover with $\alpha$ forests of $G(\mathcal{D})$
(Definition 10.2) and let
$\mathrm{disperse}_{T_{1}},\mathrm{disperse}_{T_{2}},\ldots$ be the
corresponding tree matching demands (Definition 10.4). Then, the matching-
dispersed demand on nodes $u,v\in V$ is

$\displaystyle\mathrm{disperse}_{\mathcal{D},A}(u,v):=\frac{1}{2\alpha}\cdot\sum_{i}\sum_{u^{\prime}\in\text{copies}(u)}\sum_{v^{\prime}\in\text{copies}(v)}\mathrm{disperse}_{T_{i}}(u^{\prime},v^{\prime})$

We begin with a simple helper lemma that observes that the matching-dispersed
demand has size essentially equal to the input demands (up to the arboricity).

######  Lemma 10.7.

Given graph $G$, node-weighting $A$ and and demands
$\mathcal{D}=(D_{1},D_{2},\ldots)$ where $G(\mathcal{D})$ has arboricity
$\alpha$, we have that the matching-dispersed demand
$\mathrm{disperse}_{\mathcal{D},A}$ satisfies
$|\mathrm{disperse}_{\mathcal{D},A}|\geq\frac{1}{4\alpha}\sum_{i}|D_{i}|$

###### Proof.

Observe that the number of edges in $G(\mathcal{D})$ is exactly
$\sum_{i}|D_{i}|$ and so summing over each tree $T_{j}$ in our forest cover
and applying Lemma 10.5 gives

$\displaystyle\sum_{j}|\mathrm{disperse}_{T_{j}}|\geq\frac{1}{2}\cdot\sum_{i}|D_{i}|$

Combining this with the definition of $\mathrm{disperse}_{\mathcal{D},A}$
(Definition 10.6) gives the claim. ∎

We now argue the key properties of the matching-dispersed demand which will
allow us to argue that it can be used as a witnessing demand for
$\sum_{i}D_{i}$.

######  Lemma 10.8 (Properties of Matching-Dispersed Demand).

Given graph $G=(V,E)$ and node-weighting $A$, let $C_{1},C_{2},\ldots$ be a
sequence of moving cuts where $C_{i}$ is $(h,s)$-length $\phi_{i}$-sparse in
$G-\sum_{j<i}C_{i}$ w.r.t. $A$ with witnessing demands
$\mathcal{D}=(D_{1},D_{2},\ldots)$. Then the matching dispersed demand
$\mathrm{disperse}_{\mathcal{D},A}$ is:

  * •

a $2h$-length $A$-respecting demand;

  * •

$h\cdot(s-2)$-separated by $\sum_{i}C_{i}$ and;

  * •

of size
$|\mathrm{disperse}_{\mathcal{D},A}|\geq\frac{1}{s^{3}\cdot\log^{3}N\cdot
N^{O(1/s)}}\sum_{i}\frac{|C_{i}|}{\phi_{i}}$.

###### Proof.

To see that $\mathrm{disperse}_{\mathcal{D},A}$ is $2h$-length observe that a
pair of vertices $u$ and $v$ have $\mathrm{disperse}_{\mathcal{D},A}(u,v)>0$
only if there is a path consisting of at most two edges between a node in
$\text{copies}(u)$ and a node in $\text{copies}(v)$ in the demand matching
graph $G(\mathcal{D})$ (Definition 10.2). Furthermore,
$u^{\prime}\in\text{copies}(u)$ and $v^{\prime}\in\text{copies}(v)$ have an
edge in $G(\mathcal{D})$ only if there is some $i$ such that $D_{i}(u,v)>0$
and since each $D_{i}$ is $h$-length, it follows that in such a case we know
$d_{G}(u,v)\leq h$. Thus, it follows by the triangle inequality that
$\mathrm{disperse}_{\mathcal{D},A}$ is $2h$-length.

To see that $\mathrm{disperse}_{\mathcal{D},A}$ is $A$-respecting we observe
that each vertex in $G(D)$ is incident to at most $2\alpha$ matchings across
all of the tree matching demands we use to construct
$\mathrm{disperse}_{\mathcal{D},A}$ (at most $2$ matchings per forest in our
forest cover). Thus, for any $u\in V$ since $|\text{copies}(u)|=A(u)$ we know

$\displaystyle\sum_{u^{\prime}\in\text{copies}(u)}\sum_{j}\sum_{v}\sum_{v^{\prime}\in\text{copies}(v)}\mathrm{disperse}_{T_{j}}(u^{\prime},v^{\prime})\leq\sum_{u^{\prime}\in\text{copies}(u)}2\alpha\leq
2\alpha\cdot A(u).$

It follows that for any $u\in V$ we have

$\displaystyle\sum_{v}\mathrm{disperse}_{\mathcal{D},A}(u,v)=\sum_{v}\frac{1}{2\alpha}\sum_{j}\sum_{u^{\prime}\in\text{copies}(u)}\sum_{v^{\prime}\in\text{copies}(v)}\mathrm{disperse}_{T_{j}}(u^{\prime},v^{\prime})\leq
A(u)$

A symmetric argument shows that
$\sum_{v}\mathrm{disperse}_{\mathcal{D},A}(v,u)\leq A(u)$ and so we have that
$\mathrm{disperse}_{\mathcal{D},A}$ is $A$-respecting.

We next argue that $\sum_{i}C_{i}$ is a moving cut that $h(s-2)$-separates
$\mathrm{disperse}_{\mathcal{D},A}$. Consider an arbitrary pair of vertices
$u$ and $v$ such that $\mathrm{disperse}_{\mathcal{D},A}(u,v)>0$; it suffices
to argue that $\sum_{i}C_{i}$ $h(s-2)$-separates $u$ and $v$. As noted above,
$\mathrm{disperse}_{\mathcal{D},A}(u,v)>0$ only if there is a path
$(u^{\prime},w^{\prime},v^{\prime})$ in $G(\mathcal{D})$ where
$u^{\prime}\in\text{copies}(u)$, $v^{\prime}\in\text{copies}(v)$ and for some
$w\in V$ we have $w^{\prime}\in\text{copies}(w)$. But,
$\\{u^{\prime},w^{\prime}\\}$ and $\\{w^{\prime},v^{\prime}\\}$ are edges in
$G(\mathcal{D})$ only if there is some $i$ and $j$ such that $D_{i}(u,w)>0$
and $D_{j}(w,v)>0$.

By definition of $G(\mathcal{D})$ (Definition 10.2), each $D_{i}$ corresponds
to a different matching in $G(\mathcal{D})$ and so since
$\\{u^{\prime},w^{\prime}\\}$ and $\\{w^{\prime},v^{\prime}\\}$ share the
vertex $w^{\prime}$, we may assume $i\neq j$ and without loss of generality
that $i<j$. Let $G_{\leq i}$ be $G$ with $\sum_{l\leq i}C_{l}$ applied.

Since $D_{i}$ is $hs$-separated by $C_{\leq i}$ and $D_{i}(u,w)>0$, we know
that

$\displaystyle d_{G_{\leq i}}(u,w)\geq hs.$ (11)

On the other hand, since $D_{j}$ is an $h$-length demand, $j>i$ and
$D_{j}(w,v)>0$, we know that the distance between $w$ and $v$ in $G_{\leq i}$
is

$\displaystyle d_{G_{\leq i}}(w,v)\leq h.$ (12)

Thus, it follows that $C_{\leq i}$ must $h(s-2)$ separate $u$ and $v$ since
otherwise we would know that $d_{G_{\leq i}}(u,w)\leq h(s-2)$ and so combining
this with Equation 12 and the triangle inequality we get $d_{G_{\leq
i}}(u,w)\leq hs-h$, contradicting Equation 11. Thus, $\sum_{i}C_{i}$ must
$h(s-2)$ vertices $u$ and $v$.

Lastly, we argue that
$|\mathrm{disperse}_{\mathcal{D},A}|\geq\frac{1}{s^{3}\cdot\log^{3}N\cdot
N^{O(1/s)}}\sum_{i}\frac{|C_{i}|}{\phi_{i}}$. By Lemma 10.7 we know that

$\displaystyle|\mathrm{disperse}_{\mathcal{D},A}|\geq\frac{1}{4\alpha}\sum_{i}|D_{i}|$

where $\alpha$ is the arboricity of $G(\mathcal{D})$; applying our bound of
$s^{3}\cdot\log^{3}N\cdot N^{O(1/s)}$ on the arboricity of $G(\mathcal{D})$
from Lemma 10.3 and the fact that since each $C_{i}$ is $\phi_{i}$-sparse, we
know that $|D_{i}|\geq\frac{|C_{i}|}{\phi_{i}}$ for each $i$ gives us

$\displaystyle|\mathrm{disperse}_{\mathcal{D},A}|\geq\frac{1}{4\cdot
s^{3}\cdot\log^{3}N\cdot N^{O(1/s)}}\sum_{i}\frac{|C_{i}|}{\phi_{i}},$

as required. ∎

###  10.3 Proving Union of Sparse Moving Cuts is a Sparse Moving Cut

We conclude this section by arguing that the union of sparse moving cuts is
itself sparse. Our argument does so by using the matching-dispersed demand as
the witnessing demand for the union of sparse cuts.

See 1.2

###### Proof.

Recall that to demonstrate that $\sum_{i}C_{i}$ is a $\phi^{\prime}$-sparse
$(h^{\prime},s^{\prime})$-length sparse cut, it suffices to argue that there
exists an $h^{\prime}$-length $A$-respecting demand $D$ that is
$h^{\prime}s^{\prime}$-separated by $\sum_{i}C_{i}$ where
$|D|\geq\frac{\sum_{i}|C_{i}|}{\phi^{\prime}}$.

Lemma 10.8 demonstrates the existence of exactly such a demand—namely the
matching dispersed demand as defined in Definition 10.6—for $h^{\prime}=2h$,
$s^{\prime}=\frac{(s-2)}{2}$ and $\phi^{\prime}=s^{3}\cdot\log^{3}N\cdot
N^{O(1/s)}\cdot\frac{\sum_{i}|C_{i}|}{\sum_{i}|C_{i}|/\phi_{i}}$, giving the
claim. ∎

##  11 Equivalence of Distances to Length-Constrained Expander

We now use the tools we developed in the previous section to argue that
several quantities related to length-constrained expansion are all equal (up
to slacks in sparsity, $h$ and length slack). This equivalence will form the
backbone of the analysis of our algorithm. Before proceeding, it may be useful
for the reader to recall the definition of a sequence of moving cuts
(Definition 10.1) and $\operatorname{spars}$ (Definition 5.13). The

The following series of definitions provides the quantities we will argue are
all equal up to slacks.

######  Definition 11.1.

Fix a graph $G$, node-weighting $A$ and parameters $h$, $s$ and $\phi$. Then,
we define the following quantities:

  1. 1.

Largest Sparse Cut Size: $\text{LC}(\phi,h,s)$ is the size of the largest
$(h,s)$-length $\phi$-sparse cut in $G$ w.r.t. $A$. That is

$\displaystyle\text{LC}(\phi,h,s):=|C_{0}|$

where $C_{0}$ is the moving cut of largest size in the set
$\\{C:\operatorname{spars}_{(h,s)}(C,A)\leq\phi\\}$.

  2. 2.

Largest Sparse Cut Sequence Size: $\text{LSC}(\phi,h,s)$ is the size of the
largest sequence of $\phi$-sparse moving cuts. Then

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

where $(C_{1},C_{2},\ldots)$ is the $(h,s)$-length $\phi$-expanding moving cut
sequence maximizing $\sum_{i}|C_{i}|$.

  3. 3.

Largest Weighted Sparse Cut Sequence Size: $\text{LWSC}(\phi,h,s)$ is the
largest weighted size of a sparse cut sequence, namely

$\displaystyle\text{LWSC}(\phi,h,s):=\sum_{i}\frac{\phi}{\operatorname{spars}_{(h,s)}(C_{i},A)}\cdot|C_{i}|$

where $(C_{1},C_{2},\ldots)$ is the $(h,s)$-length $\phi$-expanding moving cut
sequence maximizing
$\sum_{i}\frac{\phi}{\operatorname{spars}_{(h,s)}(C_{i},A)}\cdot|C_{i}|$ and
each $\operatorname{spars}_{(h,s)}(C_{i},A)$ is computed after applying
$C_{j}$ for $j<i$.

  4. 4.

Largest Expander’s Complement Size: $\text{LEC}(\phi,h,s)$ is $\phi$ times the
size of the complement of the largest $(h,s)$-length $\phi$-expanding subset
of $A$. That is, let $\hat{A}$ be the $(h,s)$-length $\phi$-expanding node-
weighting on $G$ satisfying $\hat{A}\preceq A$ with largest size and let
$\bar{A}=A-\hat{A}$ be its complement. Then

$\displaystyle\text{LEC}(\phi,h,s):=\phi\cdot|\bar{A}|.$

  5. 5.

Smallest Expander Decomposition Size: $\text{SED}(\phi,h,s)$ is the size of
the smallest expander decomposition. That is,

$\displaystyle\text{SED}(\phi,h,s):=|C^{*}|$

where $C^{*}$ is the moving cut of minimum size such that $A$ is
$(h,s)$-length $\phi$-expanding in $G-C^{*}$.

The following formalizes our main claim in this section, the equivalence of
the above quantities.

######  Theorem 11.1.

Fix a graph $G$, parameters $k,k^{\prime}\geq 1$ and $\phi,h,s$ and a node-
weighting $A$.

$\displaystyle\text{LC}(\phi,h,s)\leq\text{LEC}(\phi_{1},h,s)\leq\text{LSC}(\phi_{2},h_{2},s_{2})\leq\text{LC}(\phi_{3},h_{3},s_{3})$

where

$\displaystyle\phi_{1}=3\phi$ $\displaystyle\phi_{2}=\phi_{1}\cdot
2^{O(k)}\cdot N^{O(1/k^{\prime})}\cdot\log^{5}N\cdot s^{3}\cdot N^{O(1/s)},$
$\displaystyle h_{2}=h\cdot 2k^{\prime},$ $\displaystyle s_{2}=s\cdot
O\left(\frac{k}{k^{\prime}}\cdot\log N\right)$
$\displaystyle\phi_{3}=\phi_{2}\cdot s^{3}\cdot\log^{3}N\cdot N^{O(1/s)},$
$\displaystyle h_{3}=h_{2}\cdot 2,$ $\displaystyle
s_{3}=\frac{(s_{2}-2)}{2}~{}.$

Furthermore, if $A$ is $(h_{4},s_{4})$-length $\phi_{G}$-expanding then:

$\displaystyle\frac{\phi_{G}}{\phi_{4}}\cdot\text{LEC}(\phi,h,s)\leq\text{SED}(\phi_{4},h_{4},s_{4})\leq\text{LSC}(\phi_{4},h_{4},s_{4})\leq\text{LC}(\phi_{5},h_{5},s_{5})\leq\text{LEC}(\phi_{5},h_{5},s_{5})$

where

$\displaystyle\phi_{4}=\phi\cdot 2^{O(k)}\cdot
N^{O(1/k^{\prime})}\cdot\log^{2}N,$ $\displaystyle h_{4}=h\cdot k^{\prime},$
$\displaystyle s_{4}=O\left(\frac{k}{k^{\prime}}\cdot\log N\right)$
$\displaystyle\phi_{5}=\phi_{4}\cdot s^{3}\cdot\log^{3}N\cdot N^{O(1/s)},$
$\displaystyle h_{5}=h_{4}\cdot 2,$ $\displaystyle
s_{5}=\frac{(s_{4}-2)}{2}~{}.$

The remainder of this section is dedicated to providing proofs of a series of
inequalities which can be combined to get the inequalities in 11.1.

##### Techniques.

We prove the equivalence of these quantities by a series of inequalities. Four
of these inequalities are non-trivial and rely on the above-established
theory; intuition below.

  * •

$\text{LWSC}\leq\text{LC}$: Let $(C_{1},C_{2},\ldots)$ be the largest weighted
sequence of $(h,s)$-length $\phi$-sparse cuts and let $C_{0}$ be the largest
$(h,s)$-length $\phi$-sparse cut. Showing that the size of
$(C_{1},C_{2},\ldots)$ is at most the size of $C_{0}$ follows from observing
that (as discussed above), one can take the union of cuts in
$(C_{1},C_{2},\ldots)$ to (essentially) get an $(h,s)$-length $\phi$-sparse
cut of equal size. Since $C_{0}$ is the largest such cut, the inequality
follows. Here, we also make use of the idea of “padding out” a sparse cut
which forces said cut to have an exact desired sparsity.

  * •

$\text{LC}\leq\text{LEC}$: Consider the largest $(h,s)$-length $\phi$-sparse
cut $C_{0}$. Intuitively, $C_{0}$ should not cut too much into any part of the
graph that is already $(h,s)$-length $\phi$-expanding, otherwise it would not
sparse. Thus, $C_{0}$ cannot have size much larger than the part of the graph
that is not expanding. Formalizing this intuition relies on the idea of a
“projected down demand.”

  * •

$\text{LEC}\leq\text{LWSC}$ and $\text{LEC}\leq\text{SED}$: Again, let
$(C_{1},C_{2},\ldots)$ be the largest weighted sequence of $(h,s)$-length
$\phi$-sparse cuts. Proving that the amount of the graph that is not expanding
is at most the size of $(C_{1},C_{2},\ldots)$ can be done using the above-
described characterization of $(h,s)$-length expanders in terms of expander
power embeddings. In particular, the union of cuts in $(C_{1},C_{2},\ldots)$
must be an $(h,s)$-length $\phi$-expander decomposition, otherwise we could
append another cut to it and contradict its maximum size. Thus, after applying
this sequence, the resulting graph can embed expander powers into _most_
neighborhoods using short paths. It follows that in the original graph these
parts must have been $(h,s)$-length expanding, which, in turn, upper bounds
how much of the original graph is not $(h,s)$-length expanding. Arguing
$\text{LEC}\leq\text{SED}$ is similar.

The remainder of the inequalities to be proven are mostly immediate from the
relevant definitions. We conclude the section with the proof of this theorem
by appropriately stringing together these inequalities.

Figure 4: An overview of the inequalities we show. An arrow from $a$ to $b$
indicates $a\leq b$. Each non-trivial inequality opaque and labeled with the
key idea of its proof.

###  11.1 Weighted Sparse Cut Sequence (3) at Most Largest Cut (1)

We show $\text{LWSC}\leq\text{LC}$ using the idea of padding out sparse cuts
and the fact that the union of sparse moving cuts is sparse. In particular,
padding out cuts allows us to increase the size of our cuts while forcing them
to still have bounded sparsity. This allows us to pad out the cuts in our
sequence and then take the union of this padded out sequence to observe that
it results in a sparse cut which, by definition, can be no larger than the
sparsest cut.

######  Theorem 11.2.

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

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

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

The following formalizes our notion of padding out sparse cuts.

######  Lemma 11.2 (Padding Out Sparse Cut).

Given graph $G$, let $C$ be a $(h,s)$-length $\phi$-sparse moving cut w.r.t.
node-weighting $A$. Then there exists an $(h,s)$-length $\phi$-sparse moving
cut $C^{\prime}$ such that

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

###### Proof.

The basic idea is to simply arbitrarily add length increases to $C$ which
increases its size while increasing its sparsity; doing so until its sparsity
reaches $\phi$ allows us to make $C^{\prime}$ of the appropriate size. We must
take some slight care to make sure that there are enough length increases we
can add to $C$ to make it appropriately large.

For each edge $e$ let $\bar{C}(e)=1-C(e)$ be the complement of $C$. It follows
that

$\displaystyle|\bar{C}|\geq|A|-|C|.$

Furthermore, since there is some $A$-respecting demand $D$ witnessing the
$(h,s)$-length $\operatorname{spars}_{(h,s)}(C,A)$-sparsity of $C$ where