strengthen the expander decomposition we compute to deal with the slacks from
13.4. In particular, recall that by 13.4 if the graph is already $(\leq
h\cdot\frac{1}{\epsilon}\cdot s^{O(1/\epsilon)},s)$-length $\phi$-expanding
then when we apply 13.4 we get a $(\leq h,s_{w})$-length $\phi_{w}$-expansion
witness where $s_{w}=\frac{1}{\epsilon^{2}}\cdot s^{O(1/\epsilon)}$ and
$\phi_{w}=\tilde{O}(\phi\epsilon/N^{O(\epsilon)})$.

Fix an $\epsilon$ and let $\epsilon_{0}=\operatorname{poly}(\epsilon)$ so that
if $s_{0}=\exp(\operatorname{poly}(1/\epsilon_{0}))$ we have that

$\displaystyle\frac{1}{\epsilon_{0}^{2}}\cdot
s_{0}^{O(1/\epsilon_{0})}\leq\exp(\operatorname{poly}(1/\epsilon))$

and we let
$\phi_{0}=\phi\cdot\tilde{O}\left(N^{O(\epsilon_{0})}\right)/\epsilon_{0}$ so
that

$\displaystyle\phi\geq\phi_{0}\cdot\epsilon/\tilde{O}(N^{O(\epsilon)})$

Thus, if our graph is $(\leq h_{0},s_{0})$-length $\phi_{0}$-expanding and we
apply 13.4 with these parameters then we get back a $(\leq h,s)$-length
$\phi$-expansion witness.

Next, apply our algorithm for computing length-constrained expander
decompositions using $\epsilon_{0}$ to compute a $(\leq h_{0},s_{0})$-length
$\phi_{0}$-expander decomposition. Since $h_{0}\geq h$ and
$\epsilon_{0}=\operatorname{poly}(\epsilon)$, such a decomposition is a $(\leq
h,\exp(\operatorname{poly}(\epsilon)))$-length $\phi$-expander decomposition
but with a multiplicative cut slack increase of
$\phi_{0}/\phi=N^{O(\epsilon_{0})}/\epsilon_{0}$ for a total cut slack of
(assuming $\epsilon_{0}\geq\log\log N/\log N$)

$\displaystyle N^{\epsilon_{0}}\cdot
N^{O(\epsilon_{0})}/\epsilon_{0}=N^{O(\epsilon_{0})\log(\epsilon_{0})}/\epsilon_{0}\leq
N^{O(\epsilon_{0})}$

Lastly, letting $\epsilon_{0}$ be smaller by an appropriate polynomial gives a
length slack of $\exp(\operatorname{poly}(\epsilon))$ and cut slack of
$n^{\epsilon}$. Furthermore, the time to compute this expander decomposition
is as described above since our parameters have only changed by a polynomial.
Furthermore, if we apply 13.4 after applying the above decomposition we get
back the desired witness. Finally, the work to invoke 13.4 with
$L=N^{\epsilon}_{0}$ is

$\displaystyle m\cdot\tilde{O}\left(\frac{1}{\epsilon_{0}}\cdot
s_{0}^{O(1/\epsilon_{0})}\cdot N^{O(\epsilon_{0})}+\frac{1}{\epsilon_{0}}\cdot
N^{\epsilon_{0}}\cdot
N^{O(\epsilon_{0})}\cdot\operatorname{poly}(h)\right)+\frac{\tilde{O}(1)}{\operatorname{poly}(\epsilon_{0})}\sum_{i}\textnormal{{W}}_{\textnormal{ED}}(A_{i},m_{i})$
$\displaystyle\leq m\cdot\tilde{O}\left(\frac{1}{\epsilon_{0}}\cdot
s_{0}^{O(1/\epsilon_{0})}\cdot N^{O(\epsilon_{0})}+\frac{1}{\epsilon}\cdot
N^{O(\epsilon_{0})}\cdot\operatorname{poly}(h)\right)$
$\displaystyle\qquad+\frac{\tilde{O}(1)}{\operatorname{poly}(\epsilon_{0})}\sum_{i}m_{i}\cdot\tilde{O}\left(N^{O(\operatorname{poly}(\epsilon_{0}))}\cdot\operatorname{poly}(h)\right)$
$\displaystyle\leq m\cdot\tilde{O}\left(\frac{1}{\epsilon_{0}}\cdot
s_{0}^{O(1/\epsilon_{0})}\cdot N^{O(\epsilon_{0})}+\frac{1}{\epsilon}\cdot
N^{O(\epsilon_{0})}\cdot\operatorname{poly}(h)\right)$
$\displaystyle\qquad+\frac{\tilde{O}(1)}{\operatorname{poly}(\epsilon_{0})}\frac{1}{\epsilon_{0}}\cdot\tilde{O}(m+n^{1+O(\epsilon_{0})}+N^{O(\epsilon_{0})})\cdot\tilde{O}\left(N^{O(\operatorname{poly}(\epsilon_{0}))}\cdot\operatorname{poly}(h)\right)$
$\displaystyle\leq
m\cdot\tilde{O}\left(N^{O(\operatorname{poly}(\epsilon))}\cdot\operatorname{poly}(h)\right)$

where above we applied the previously described algorithm for expander
decompositions and in the last line we again assumed $\epsilon\geq
1/\log^{1/c}N$ for a suitable large constant $c$. Note that the above is
asymptotically the same as the time to compute our expander decompositions.
The depth calculation is analogous. ∎

In Section 16 we show how to achieve the above algorithm with the linkedness
property. Likewise, we note that the above algorithm immediately gives
“witnessed” expander decompositions. Specifically, if we run the above
algorithm after already applying our expander decomposition, then we find no
sparse cuts and the output of our algorithm (and, in particular, 13.4) is a
collection of routers, one for each cluster of our neighborhood cover, along
with an embedding of a router into each cluster of the neighborhood cover. We
also note that plugging the above result into 13.4 gives efficient
approximation algorithms for the demand-size-largest cut problem.

##  16 Maintaining Extra Properties (1.1 with Linkedness)

In the previous sections we showed how repeatedly cutting large length-
constrained sparse cuts gives length-constrained expander decompositions. In
this section, we discuss how to incorporate additional graph properties—in
particular, the linkedness property—into these decompositions.

##### Techniques.

The basic idea for achieving said properties is to use the robustness of
length-constrained expanders. In particular, start with a length-constrained
expander decomposition. The resulting graph is a length-constrained expander
but may not have our desired properties. We then force our graph to have our
properties, possibly at the expense of length-constrained expansion. By the
robustness properties of length-constrained expanders, we can easily restore
length-constrained expansion, now possibly at the cost of our properties.
Going back and forth between restoring our properties and length-constrained
expansion eventually gives us a length-constrained expander with our desired
properties.

We call a ${\mathcal{P}}$ set of (possibly infinitely many) graphs a
_property_. We say that a graph $G$ has property ${\mathcal{P}}$ iff
$G\in{\mathcal{P}}$. We say that an algorithm $\mathcal{A}$ _maintains
property ${\mathcal{P}}$_ with initial rate
$I:\mathbb{R}^{+}\to\mathbb{R}^{+}$ and maintenance rate
$M:\mathbb{R}^{+}\to\mathbb{R}^{+}$, iff for every graph $G$ on $n$ vertices,

  * •

the algorithm $\mathcal{A}$ can first find a subset $E^{\prime}\subseteq E(G)$
of at most $I(n)\cdot|E(G)|$ edges such that the graph $G^{\prime}=G\setminus
E^{\prime}$ has property ${\mathcal{P}}$; and

  * •

upon any online sequence of $k$ edge deletions from $G^{\prime}$, the
algorithm $\mathcal{A}$ maintains a pruned set of at most $M(n)\cdot k$ edges
of $G^{\prime}$, such that when the edges in the pruned set are removed from
$G^{\prime}$, the remaining graph has property ${\mathcal{P}}$.

In this case, we also say that the property ${\mathcal{P}}$ has (or can be
maintained with) rate $(I(\cdot),M(\cdot))$.

The main result in this section is the following theorem. We will first prove
this theorem, and then use it to achieve an additional linkedness property in
1.1.

######  Theorem 16.1.

Let ${\mathcal{P}}_{1},\ldots,{\mathcal{P}}_{k}$ be graph properties with
rates $(I_{1},M_{1}),\ldots,(I_{k},M_{k})$ respectively where
$M_{1}\geq\cdots\geq M_{k}$. Assume further that

  * •

$M_{1}\cdot\sum_{2\leq i\leq k}M_{i}<1/4$; and

  * •

$\sum_{2\leq i\leq k}M_{i}<1/2$.

Then property ${\mathcal{P}}=\bigcap_{1\leq i\leq k}{\mathcal{P}}_{i}$ can be
maintained with rates $(O\big{(}\sum_{1\leq i\leq k}I_{i}),O(\sum_{1\leq i\leq
k}M_{i}))$.

###  16.1 Proof of Theorem 16.1

The remainder of this section is dedicated to the proof of Theorem 16.1. We
first prove the following lemma, which is the special case of Theorem 16.1
where $k=2$.

######  Lemma 16.2.

Let ${\mathcal{P}}_{1},{\mathcal{P}}_{2}$ be graph properties with rates
$(I_{1},M_{1})$ and $(I_{2},M_{2})$. If $M_{1}\cdot M_{2}<1/2$, then the
property ${\mathcal{P}}_{1}\cap{\mathcal{P}}_{2}$ can be maintained with rate
$(I_{1}+(2+2M_{1})\cdot I_{2},M_{1}+2(1+M_{1})^{2}\cdot M_{2})$.

###### Proof.

Denote by $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ the algorithms for
maintaining ${\mathcal{P}}_{1}$ and ${\mathcal{P}}_{2}$ with rates
$(I_{1},M_{1})$ and $(I_{2},M_{2})$, respectively. We now describe an
algorithm that maintains property ${\mathcal{P}}_{1}\cap{\mathcal{P}}_{2}$. We
first apply $\mathcal{A}_{1}$ to $G$ and compute a set $E^{1}_{0}\subseteq
E(G)$ of edges such that $|E^{1}_{0}|\leq I_{1}\cdot|E(G)|$ and $G\setminus
E^{1}_{0}$ has property ${\mathcal{P}}_{1}$. We then apply $\mathcal{A}_{2}$
to $G\setminus E^{1}_{0}$ and compute a set $E^{2}_{0}\subseteq E(G\setminus
E^{1}_{0})$ of edges such that $|E^{2}_{0}|\leq
I_{1}\cdot|E(G\setminus(E^{1}_{0}\cup E^{2}_{0}))|$ and
$G\setminus(E^{1}_{0}\cup E^{2}_{0})$ has property ${\mathcal{P}}_{2}$. We
then perform iterations. In the $i$th iteration, we iteratively maintain
properties ${\mathcal{P}}_{1}$ and ${\mathcal{P}}_{2}$, starting with a graph
$G_{i-1}$ (where $G_{0}=G\setminus(E^{1}_{0}\cup E^{2}_{0})$). We apply
$\mathcal{A}_{1}$ to compute a set $E^{1}_{i}\subseteq E(G_{i-1})$ such that
$|E^{1}_{i}|\leq M_{1}\cdot|E^{2}_{i-1}|$ $G_{i-1}\setminus E^{1}_{i}$ has
property ${\mathcal{P}}_{1}$, and then apply $\mathcal{A}_{2}$ to compute a
set $E^{2}_{i}\subseteq E(G_{i-1}\setminus E^{1}_{i})$ such that
$G_{i-1}\setminus(E^{1}_{i}\cup E^{2}_{i})$ has property ${\mathcal{P}}_{1}$.
Define $G_{i}=G_{i-1}\setminus(E^{1}_{i}\cup E^{2}_{i})$ and continue to the
next iteration. Whenever in some iteration $i^{*}$ we have
$E^{1}_{i^{*}}=E^{2}_{i^{*}}=\emptyset$, we terminate the algorithm and return
the graph $G_{i}$. In other words, the set of edges that we have removed from
$G$ is $E^{\prime}=\bigcup_{0\leq i\leq i^{*}}(E^{1}_{i}\cup E^{2}_{i})$.

We now describe an ball-moving abstract process and use it to estimate the
size of set $E^{\prime}$. We have two boxes denoted by $B_{1}$ and $B_{2}$,
respectively. Initially, $B_{1}$ contains $I_{1}\cdot|E(G)|$ _inactive_ balls
and $B_{2}$ contains $I_{2}\cdot|E(G)|$ _active_ balls. In each iteration, we
either deactivate $t$ balls in $B_{1}$ (if $B_{1}$ contains at least $t$
active balls at the moment) and add $t\cdot M_{2}$ new active balls to
$B_{2}$, or deactivate $t$ balls from $B_{2}$ (if $B_{2}$ contains at least
$t$ active balls at the moment) and add $t\cdot M_{1}$ new active balls to
$B_{1}$, for an arbitrary $t$. The process can continue for arbitrarily many
iterations and may terminate at any point.

On the one hand, we show our algorithm can be modelled a realization of the
process, such that the size of $E^{\prime}$ is bounded by the number of balls
in $B_{1}\cup B_{2}$ at the terminating point. Recall that our algorithm
starts by computing a set $E_{0}^{1}$ and then a set $E_{0}^{2}$ to initiate
properties ${\mathcal{P}}_{1}$ and ${\mathcal{P}}_{2}$, where $|E_{0}^{1}|\leq
I_{1}\cdot|E(G)|$ and $|E_{0}^{2}|\leq I_{2}\cdot|E(G)|$. The reason that the
initial balls in $B_{1}$ are inactive while the initial balls in $B_{2}$ are
active is because the set $E_{0}^{2}$ is computed in graph $G\setminus
E^{0}_{1}$, which means that the edges in $E^{0}_{1}$ are not viewed as the
online updates for property ${\mathcal{P}}_{2}$. In the first iteration after
the initialization, we compute a new prune set $|E^{1}_{1}|\leq
M_{1}\cdot|E_{0}^{2}|$ to maintain ${\mathcal{P}}_{1}$. This can be viewed as
deactivating $|E_{1}^{1}|/M_{1}\leq|E_{0}^{2}|$ balls in $B_{2}$ and add
$|E_{1}^{1}|$ new active balls in $B_{1}$. Similarly, in the algorithm we then
compute a new prune set $E^{2}_{1}$ to maintain ${\mathcal{P}}_{1}$, and this
can be viewed as deactivating $|E_{1}^{2}|/M_{1}$ balls in $B_{2}$ and add
$|E_{1}^{2}|$ new active balls in $B_{2}$. Later iterations can be simulated
in a similar way. The algorithm ends whenever
$E^{1}_{i^{*}}=E^{2}_{i^{*}}=\emptyset$ for some $i^{*}$, and we let the
process end at the same time.

From the definition of maintenance rate, upon $k$ online updates, property
${\mathcal{P}}_{i}$ can be maintained by a pruned set of at most $M_{i}\cdot
k$ edges. This is exactly modelled by our process. In particular, every time
we compute a set $E_{i}^{1}$, in our process we deactivate $|E_{i}^{1}|/M_{2}$
balls from $B_{2}$, so we are guaranteed that $r$ active balls in one $B_{2}$
can give birth to at most $M_{2}\cdot r$ new balls in $B_{1}$. Therefore, at
any time, we are never required to deactivate more balls than the current
active balls in a box. As every edge in the pruned set $E^{\prime}$
corresponds to a distinct ball in $B_{1}$ or $B_{2}$, the size of $E^{\prime}$
is bounded by the number of balls in $B_{1}\cup B_{2}$ at the end of the
process.

On the other hand, we show that, no matter how the process proceeds, the
number of balls in $B_{1}\cup B_{2}$ at any time is at most
$(I_{1}+(2+2M_{1})\cdot I_{2})$. In fact, for each initial active ball in
$B_{2}$, it will eventually gives birth to at most
$1+M_{1}+M_{2}M_{1}+M_{1}M_{2}M_{1}+\cdots$ balls in the final set. Therefore,
the number of balls in $B_{1}\cup B_{2}$ at any time is bounded by

$\begin{split}&|E(G)|\cdot\bigg{(}I_{1}+I_{2}+M_{1}I_{2}+M_{2}(M_{1}I_{2})+M_{1}(M_{2}M_{1}I_{2})+\cdots\bigg{)}\\\
&\leq|E(G)|\cdot\bigg{(}I_{1}+I_{2}\cdot(1+M_{1})\cdot\frac{1}{1-M_{1}M_{2}}\bigg{)}\\\
&\leq|E(G)|\cdot(I_{1}+(2+2M_{1})\cdot I_{2}),\end{split}$

as $M_{1}M_{2}\leq 1/2$. Therefore, our algorithm initializes property
${\mathcal{P}}_{1}\cap{\mathcal{P}}_{2}$ with rate $I\leq
I_{1}+(2+2M_{1})\cdot I_{2}$.

Now upon an update, we perform iterations as exactly described before to
maintain properties ${\mathcal{P}}_{1}$ and ${\mathcal{P}}_{2}$. Via a similar
ball-moving process, we can show that the pruned set upon every update has
size at most

$\begin{split}M&\leq
M_{1}+(1+M_{1})M_{2}+M_{1}(1+M_{1})M_{2}+M_{2}(M_{1}(1+M_{1})M_{2})+\cdots\\\
&\leq M_{1}+M_{2}\cdot(1+M_{1})^{2}\cdot\frac{1}{1-M_{1}M_{2}}\\\ &\leq
M_{1}+2(1+M_{1})^{2}\cdot M_{2}.\end{split}$

∎

We now prove Theorem 16.1 using Lemma 16.2. Denote $I=\sum_{1\leq i\leq
k}I_{i}$ and $M=\sum_{1\leq i\leq k}M_{i}$.

We first show that property ${\mathcal{P}}^{\prime}=\bigcap_{2\leq i\leq
k}{\mathcal{P}}_{i}$ can be maintained with initial rate
$I^{\prime}=O(\sum_{2\leq i\leq k}I_{i})$ and maintenance rate
$M^{\prime}=O(\sum_{2\leq i\leq k}M_{i})$. We describe an algorithm similar to
(but simpler than) the one in the proof of Lemma 16.2 that maintains property
${\mathcal{P}}$. Denote by $\mathcal{A}_{i}$ the algorithm for maintaining
property ${\mathcal{P}}_{i}$. We perform iterations. In the first iteration,
we start with a graph $G_{0}=G$, and apply $\mathcal{A}_{i}$ to compute a set
$E^{1}_{i}\subseteq E(G)$ such that $G\setminus E^{1}_{i}$ has property
${\mathcal{P}}_{i}$. Define $E^{1}=\bigcup_{1\leq i\leq k}E^{1}_{i}$, so
$|E^{1}|\leq\big{(}\sum_{2\leq i\leq k}I_{i}\big{)}\cdot|E(G)|$. We remove
edges in $E^{1}$ from graph $G_{0}$ and denote by $G_{1}$ the remaining graph
as the outcome of iteration $1$. We now describe the second iteration. Observe
that, for each $1\leq i\leq k$, the graph $G_{1}$ produced by iteration $1$
can be seen as obtained from $G\setminus E^{1}_{i}$ by removing edges in
$E^{1}\setminus E^{1}_{i}$. Note that $G\setminus E^{1}_{i}$ has property
${\mathcal{P}}_{i}$. From the definition of maintenance rate, we can apply
$\mathcal{A}_{i}$ to compute another set $E^{2}_{i}\subseteq E(G_{1})$ with
$|E^{2}_{i}|\leq M_{i}\cdot|E^{1}\setminus E^{1}_{i}|\leq M_{i}\cdot|E^{1}|$,
such that $G_{1}\setminus E^{2}_{i}$ has property ${\mathcal{P}}_{i}$. Define
$E^{2}=\bigcup_{1\leq i\leq k}E^{2}_{i}$, so $|E^{2}|\leq\big{(}\sum_{2\leq
i\leq k}M_{i}\big{)}\cdot|E^{1}|$. We sequentially perform iteration $j$ for
$j=3,4,\ldots$ similarly and compute sets $E^{3},E^{4},\ldots$. Whenever for
some iteration the set $E^{i^{*}}$ is empty, we terminate the algorithm and
return $E^{\prime}$ as the union of all sets $E^{1},E^{2},\ldots,E^{i^{*}}$
computed in these iterations. Via a similar ball-moving process as in the
proof of Lemma 16.2, we can show that

$\begin{split}|E^{\prime}|\leq&\sum_{2\leq i\leq
k}I_{i}\cdot|E(G)|+\sum_{j\geq 1}\bigg{(}\sum_{2\leq i\leq
k}M_{i}\bigg{)}^{j}\cdot\sum_{2\leq i\leq k}I_{i}\cdot|E(G)|\\\
\leq&\frac{\sum_{2\leq i\leq k}I_{i}}{1-\sum_{2\leq i\leq
k}M_{i}}\cdot|E(G)|\leq 2\cdot\sum_{2\leq i\leq
k}I_{i}\cdot|E(G)|.\end{split}$

In other words, the initial rate of property ${\mathcal{P}}^{\prime}$ is at
most $I^{\prime}\leq 2\cdot\sum_{2\leq i\leq k}I_{i}$. The same algorithm can
also be used to deal with online update sequence. Via similar arguments, we
can show that the maintenance rate is at most

$M^{\prime}=\bigg{(}\sum_{2\leq i\leq k}M_{i}\bigg{)}+\bigg{(}\sum_{2\leq
i\leq k}M_{i}\bigg{)}^{2}+\bigg{(}\sum_{2\leq i\leq
k}M_{i}\bigg{)}^{3}+\cdots\leq\frac{\sum_{2\leq i\leq k}M_{i}}{1-\sum_{2\leq
i\leq k}M_{i}}\leq 2\cdot\sum_{2\leq i\leq k}M_{i}.$

We then show that property ${\mathcal{P}}_{1}\cap{\mathcal{P}}^{\prime}$ can
be maintained with rate $(O(I),O(M))$. Note that $M_{1}\cdot M^{\prime}\leq
M_{1}\cdot 2\cdot\sum_{2\leq i\leq k}M_{i}\leq 1/2$. Applying Lemma 16.2 to
properties ${\mathcal{P}}^{\prime}$ and ${\mathcal{P}}_{1}$, we get that
property ${\mathcal{P}}$ can be maintained with initial rate

$I^{\prime}+(2+2M^{\prime})\cdot I_{1}\leq I^{\prime}+(2+2\cdot 2\cdot
1/2)I_{1}\leq 5\cdot\sum_{1\leq i\leq k}I_{i},$

and maintenance rate

$M^{\prime}+2(1+M^{\prime})^{2}\cdot M_{1}\leq M^{\prime}+2(1+2\cdot
1/2)^{2}M_{1}\leq 9\cdot\sum_{1\leq i\leq k}M_{i}.$

###  16.2 Achieving Linkedness in 1.1

Let $G$ be the input graph. We define the property ${\mathcal{P}}(G,\beta)$ as
all graphs $G^{\prime}$ with $G^{\prime}=G-C+L_{C}^{\beta}$ for some moving
cut $C$. Clearly, for graph $G$, its initial rate is $0$, and its maintenance
rate is $\beta$ (as removing an edge will cause $\beta$ self-loops to be
added).

Set $s=\exp(\operatorname{poly}(1/\epsilon))$ as in 1.1. Let
${\mathcal{P}}(h,s,\phi)$ be the set of all $(h,s)$-length $\phi$-expanders.

The algorithm for preserving both properties ${\mathcal{P}}(G,\beta)$ and
${\mathcal{P}}(h,s,\phi)$ works as follows. Let

$k=\frac{\operatorname{poly}(\epsilon)}{\epsilon},\quad
k^{\prime}=1/\operatorname{poly}(\epsilon).$

We first apply a $(hk^{\prime},s/\operatorname{poly}(\epsilon))$-length
$\big{(}\phi\cdot 2^{O(k)}\cdot
N^{O(1/k^{\prime})}\cdot\log^{2}N\big{)}$-expander decomposition. This has
initial rate $\phi\cdot 2^{O(k)}\cdot N^{O(1/k^{\prime})}\cdot\log^{2}N\cdot
N^{\epsilon}$. From 8.1 and 11.1, its maintenance rate is
$\phi\cdot\big{(}N^{\epsilon}\cdot 2^{O(k)}\cdot
N^{O(1/k^{\prime})}\big{)}\log N=\phi\cdot N^{\operatorname{poly}(\epsilon)}$.
Therefore, as long as $\beta\leq\frac{1}{2\phi}\cdot
N^{\operatorname{poly}(\epsilon)}$, from Lemma 16.2, properties
${\mathcal{P}}(G,\beta)$ and ${\mathcal{P}}(h,s,\phi)$ can be achieved by
alternately applying the algorithms for maintaining ${\mathcal{P}}(G,\beta)$
and ${\mathcal{P}}(h,s,\phi)$, with the running time dominated by the
initialization running time.

## References

  * [ABS15] Sanjeev Arora, Boaz Barak, and David Steurer.  Subexponential algorithms for unique games and related problems.  Journal of the ACM (JACM), 62(5):1–25, 2015.
  * [ASS08] Noga Alon, Oded Schwartz, and Asaf Shapira.  An elementary construction of constant-degree expanders.  Combinatorics, Probability and Computing, 17(3):319–327, 2008.
  * [BFU92] Andrei Z Broder, Alan M Frieze, and Eli Upfal.  Existence and construction of edge disjoint paths on expander graphs.  In Annual ACM Symposium on Theory of Computing (STOC), pages 140–149, 1992.
  * [Ble96] Guy E Blelloch.  Programming parallel algorithms.  Communications of the ACM, 39(3):85–97, 1996.
  * [CGL+20] Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak.  A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond.  In Symposium on Foundations of Computer Science (FOCS), pages 1158–1167. IEEE, 2020.
  * [Chu23] Julia Chuzhoy.  A distanced matching game, decremental apsp in expanders, and faster deterministic algorithms for graph cut problems.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2023.
  * [CZ23] Julia Chuzhoy and Ruimin Zhang.  A new deterministic algorithm for fully dynamic all-pairs shortest paths.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1159–1172, 2023.
  * [DSHK+11] Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer.  Distributed verification and hardness of distributed approximation.  In Annual ACM Symposium on Theory of Computing (STOC), pages 363–372, 2011.
  * [Fri01] Alan M Frieze.  Edge-disjoint paths in expander graphs.  SIAM Journal on Computing, 30(6):1790–1801, 2001.
  * [GHZ21] Mohsen Ghaffari, Bernhard Haeupler, and Goran Zuzic.  Hop-constrained oblivious routing.  In Annual ACM Symposium on Theory of Computing (STOC), pages 1208–1220, 2021.
  * [GK07] Naveen Garg and Jochen Könemann.  Faster and simpler algorithms for multicommodity flow and other fractional packing problems.  SIAM Journal on Computing, 37(2):630–652, 2007.
  * [GKS17] Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su.  Distributed mst and routing in almost mixing time.  In ACM Symposium on Principles of Distributed Computing (PODC), pages 131–140, 2017.
  * [GL18] Mohsen Ghaffari and Jason Li.  New distributed algorithms in almost mixing time via transformations from parallel algorithms.  In International Symposium on Distributed Computing (DISC), 2018.
  * [GRST21] Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, and Zihan Tan.  The expander hierarchy and its applications to dynamic graph algorithms.  In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2212–2228. SIAM, 2021.
  * [HHG22] Bernhard Haeupler, Jonas Huebotter, and Mohsen Ghaffari.  A cut-matching game for constant-hop expanders.  arXiv preprint arXiv:2211.11726, 2022.
  * [HHL+24] Bernhard Haeupler, D Ellis Hershkowitz, Jason Li, Antti Röyskö, and Thatchaphol Saranurak.  Low-step multi-commodity flow emulators.  In Annual ACM Symposium on Theory of Computing (STOC), 2024.
  * [HHS23] Bernhard Haeupler, D Ellis Hershkowitz, and Thatchaphol Saranurak.  Maximum length-constrained flows and disjoint paths: Distributed, deterministic and fast.  In Annual ACM Symposium on Theory of Computing (STOC), 2023.
  * [HHT23] Bernhard Haeupler, D Ellis Hershkowitz, and Zihan Tan.  Parallel greedy spanners.  arXiv preprint arXiv:2304.08892, 2023.
  * [HLS24] Bernhard Haeupler, Yaowei Long, and Thatchaphol Saranurak.  Dynamic deterministic constant-approximate distance oracles with n to the epsilon worst-case update time.  arXiv preprint arXiv:2402.18541, 2024.
  * [HRG22] Bernhard Haeupler, Harald Räcke, and Mohsen Ghaffari.  Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality.  In Annual ACM Symposium on Theory of Computing (STOC), pages 1325–1338, 2022.
  * [HWZ20] Bernhard Haeupler, David Wajc, and Goran Zuzic.  Network coding gaps for completion times of multiple unicasts.  In Symposium on Foundations of Computer Science (FOCS), pages 494–505. IEEE, 2020.
  * [KKOV07] Rohit Khandekar, Subhash Khot, Lorenzo Orecchia, and Nisheeth K Vishnoi.  On a cut-matching game for the sparsest cut problem.  Univ. California, Berkeley, CA, USA, Tech. Rep. UCB/EECS-2007-177, 6(7):12, 2007.
  * [KR96] Jon Kleinberg and Ronitt Rubinfeld.  Short paths in expander graphs.  In Symposium on Foundations of Computer Science (FOCS), pages 86–95. IEEE, 1996.
  * [KRV09] Rohit Khandekar, Satish Rao, and Umesh Vazirani.  Graph partitioning using single commodity flows.  Journal of the ACM (JACM), 56(4):1–15, 2009.
  * [KT18] Ken-ichi Kawarabayashi and Mikkel Thorup.  Deterministic edge connectivity in near-linear time.  Journal of the ACM (JACM), 66(1):1–50, 2018.
  * [Li21] Jason Li.  Deterministic mincut in almost-linear time.  In Annual ACM Symposium on Theory of Computing (STOC), pages 384–395, 2021.
  * [LMR94] Frank Thomson Leighton, Bruce M Maggs, and Satish B Rao.  Packet routing and job-shop scheduling in o (congestion+ dilation) steps.  Combinatorica, 14(2):167–186, 1994.
  * [LR99] Tom Leighton and Satish Rao.  Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.  Journal of the ACM (JACM), 46(6):787–832, 1999.
  * [Lub85] Michael Luby.  A simple parallel algorithm for the maximal independent set problem.  In Annual ACM Symposium on Theory of Computing (STOC), pages 1–10, 1985.
  * [NSWN17] Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen.  Dynamic minimum spanning forest with subpolynomial worst-case update time.  In Symposium on Foundations of Computer Science (FOCS), pages 950–961. IEEE, 2017.
  * [PR00] David Peleg and Vitaly Rubinovich.  A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction.  SIAM Journal on Computing, 30(5):1427–1442, 2000.
  * [PU87] David Peleg and Eli Upfal.  Constructing disjoint paths on expander graphs.  In Annual ACM Symposium on Theory of Computing (STOC), pages 264–273, 1987.
  * [Rac02] Harald Racke.  Minimizing congestion in general networks.  In Symposium on Foundations of Computer Science (FOCS), pages 43–52. IEEE, 2002.
  * [RS10] Prasad Raghavendra and David Steurer.  Graph expansion and the unique games conjecture.  In Annual ACM Symposium on Theory of Computing (STOC), pages 755–764, 2010.
  * [ST81] Daniel D Sleator and Robert Endre Tarjan.  A data structure for dynamic trees.  In Annual ACM Symposium on Theory of Computing (STOC), pages 114–122, 1981.
  * [ST04] Daniel A Spielman and Shang-Hua Teng.  Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems.  In Annual ACM Symposium on Theory of Computing (STOC), pages 81–90, 2004.
  * [SW19] Thatchaphol Saranurak and Di Wang.  Expander decomposition and pruning: Faster, stronger, and simpler.  In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2616–2635. SIAM, 2019.
  * [Tre05] Luca Trevisan.  Approximation algorithms for unique games.  In Symposium on Foundations of Computer Science (FOCS), pages 197–205. IEEE, 2005.
  * [Val90] Leslie G Valiant.  General purpose parallel architectures.  In Algorithms and Complexity, pages 943–971. Elsevier, 1990.
  * [vdBLN+20] Jan van den Brand, Yin-Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang.  Bipartite matching in nearly-linear time on moderately dense graphs.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 919–930. IEEE, 2020.
  * [W+01] Douglas Brent West et al.  Introduction to graph theory, volume 2.  Prentice hall Upper Saddle River, 2001.