# A Simple Framework for Finding Balanced Sparse Cuts via APSP

Li Chen
Georgia Tech
<EMAIL_ADDRESS>Li Chen was supported by NSF Grant CCF-2106444. Rasmus Kyng
ETH Zurich
<EMAIL_ADDRESS>The research leading to these results has received funding
from the grant “Algorithms and complexity for high-accuracy flows and convex
optimization” (no. 200021 204787) of the Swiss National Science Foundation.
Maximilian Probst Gutenberg22footnotemark: 2
ETH Zurich
<EMAIL_ADDRESS>Sushant Sachdeva
University of Toronto
<EMAIL_ADDRESS>Sushant Sachdeva’s research is supported by an NSERC
(Natural Sciences and Engineering Research Council of Canada) Discovery Grant.

###### Abstract

We present a very simple and intuitive algorithm to find balanced sparse cuts
in a graph via shortest-paths. Our algorithm combines a new multiplicative-
weights framework for solving unit-weight multi-commodity flows with standard
ball growing arguments. Using Dijkstra’s algorithm for computing the shortest
paths afresh every time gives a very simple algorithm that runs in time
$\widetilde{O}(m^{2}/\phi)$ and finds an $\widetilde{O}(\phi)$-sparse balanced
cut, when the given graph has a $\phi$-sparse balanced cut. Combining our
algorithm with known deterministic data-structures for answering approximate
All Pairs Shortest Paths (APSP) queries under increasing edge weights
(decremental setting), we obtain a simple deterministic algorithm that finds
$m^{o(1)}\phi$-sparse balanced cuts in $m^{1+o(1)}/\phi$ time. Our
deterministic almost-linear time algorithm matches the state-of-the-art in
randomized and deterministic settings up to subpolynomial factors, while being
significantly simpler to understand and analyze, especially compared to the
only almost-linear time deterministic algorithm, a recent breakthrough by
Chuzhoy-Gao-Li-Nanongkai-Peng-Saranurak (FOCS 2020).

##  1 Introduction

Graph partitioning is a fundamental algorithmic primitive that has been
studied extensively. There are several ways to formalize the question. We
focus on the question of finding balanced separators in a graph. More
precisely, given an $m$-edge graph $G=(V,E)$, the conductance of a cut is
defined by
$\Phi_{G}(S)=\frac{|E_{G}(S,\overline{S})|}{\min\\{{{\textsf{vol}}}(S),{{\textsf{vol}}}{({V\setminus
S})}\\}}$ where $E_{G}(S,\overline{S})$ is the set of edges with exactly one
endpoint in $S,$ and the volume of $S,$ denoted ${{\textsf{vol}}}(S)$ is the
sum of the degrees of vertices in $S.$ We say that a cut $(S,V\setminus S)$ is
$b$-balanced if ${{\textsf{vol}}}(S),{{\textsf{vol}}}(V\setminus S)\geq
b\cdot{{\textsf{vol}}}(V).$ The objective in the Balanced Separator problem is

> Given parameters $b,\phi\leq 1,$ either find a cut $(S,V\setminus S)$ that
> is $b$-balanced and has conductance $\Phi_{G}(S)\leq\phi,$ or certify that
> every $\Omega(b)$-balanced111Note that we allow the algorithm to return an
> $\Omega(b)$-balanced sparse cut when the graph has a $b$-balanced sparse
> cut. Such an algorithm is known as a pseudo-approximation algorithm. All
> known efficient algorithms for balanced cut find pseudo-approximations. cut
> has conductance at least $\alpha\phi.$

The Balanced Separator problem is a classic NP-hard problem and under the
Small-Set-Expansion hypothesis, even NP-hard to approximate to within an
arbitrary constant [RST12]. Thus, the above formulation allows for
$\alpha$-approximation for some $\alpha<1.$ This problem has been studied
extensively due to its application to divide-and-conquer on graphs, and
theoretical connections to random walks, spectral graph theory, and metric
embeddings.

#### Our Results.

In this paper, we present a very simple and intuitive algorithm for Balanced
Separator. Our algorithm gives a simple framework based on (scalar)
multiplicative weights that reduces the problem to computing approximate
shortest paths in a graph under increasing lengths for the edges (decremental
setting). Our framework either finds a balanced cut with small conductance, or
certifies that every balanced cut has large conductance (Theorem 4.1).

If one simply uses Dijkstra’s algorithm to compute the necessary shortest
paths afresh each time, our algorithm gives an $\widetilde{O}(m^{2}/\phi)$
time algorithm that achieves approximation $\alpha=\Omega(1/\log^{2}n)$ for
cuts of constant balance, and $\alpha=\Omega(1/\log n\cdot\log\log n)$ for
cuts of constant balance and conductance (Theorem 2.4). If we instead use
known $n^{o(1)}$-approximate deterministic dynamic algorithms for decremental
All-Pairs-Shortest-Paths (APSP), we obtain an algorithm that runs in
$m^{1+o(1)}/\phi$ and achieves an approximation of $\alpha=n^{o(1)}$ (Theorem
2.3).

Our algorithm can be described very simply. We attempt to embed an explicit
expander $H$ as a multi-commodity flow using paths of length
$\widetilde{O}(\phi^{-1})$ in $G,$ while ensuring that the congestion on the
edges in $G$ is at most $\widetilde{O}(\phi^{-1}).$ If the ends of points of
an edge $e\in H$ are connected in $G$ using a short path, we use the path in
$G$ to route $e.$ Further, we increase the length of each edge on this path by
a multiplicative factor. This increased length makes it less likely that this
path will be used in the future. A simple multiplicative-weights argument here
now allows us to bound the congestion over the course of entire algorithm. If
our algorithm succeeds in embedding most edges of $H$ in $G,$ this provides us
a certificate that all balanced cuts in $G$ have expansion
$\widetilde{\Omega}(\phi).$ If our algorithm fails, we find several edges of
$H$ such that the ends points of these edges are at distance
$\widetilde{\Omega}(\phi^{-1})$ as measured by the lengths of the edges
computed by the algorithm. Now, we can apply a simple ball-growing argument to
recover a balanced cut of conductance $\phi.$

#### Applications.

While finding the Balanced Sparsest Cut is a crucial ingredient in Divide-And-
Conquer frameworks for many algorithms (see [Shm97] for an introduction), and
has various applications ranging from VLSI Design, Image Segmentation [SM00]
to PRAM emulation, we want to point out in particular that our algorithm can
be used to replace the use of the Cut-Matching framework [KRV09] in the work
of Saranurak-Wang [SW19] (see Remark 4.6 in Section 4.1). Together, this gives
an elegant framework for computing expander decompositions which in turn have
been pivotal in various recent breakthroughs in algorithmic graph theory with
applications to computing Electric Flows [ST04], Maximum Flows and Min-Cost
Flows [CKLPGS22], Gomory-Hu Trees [AKT21, AKLPST22] for finding Global Min-
Cuts deterministically [KT18, LP20, LS21], and many, many more.

#### Comparison to Previous Works.

There has been a lot of work on algorithms for Balanced Separator. The
celebrated work of Leighton and Rao [LR99] showed that one could achieve an
$O(\log n)$ approximation to Balanced Separator by repeatedly solving a linear
program that computes a fractional multi-commodity flow. Several works give a
faster implementation of this approach via a multiplicative-weights algorithms
for multi-commodity flow [PST95, You95, GK07, Fle00], and by using the
Leighton-Rao result as a black-box to deduce that they compute an $O(\log n)$
approximation. However, the running time they achieved for Balanced Separator
was $\Omega(nm^{2})$ since they repeatedly find and remove low-conductance
cuts, each of which might be highly unbalanced, possibly introducing a factor
of $n.$ In contrast, our algorithm works directly with balanced cuts, rather
than multi-commodity flows. Our algorithm is in the same spirit as the Garg-
Könemann, Fleischer framework from [GK07, Fle00], but directly incorporates
the Leighton-Rao algorithm for finding low conductance cuts.

The groundbreaking work of Spielman and Teng on solving Laplacian linear
systems [ST04] introduced the notion of local algorithms for finding low-
conductance cuts, where the running time of the algorithm scales almost-
linearly with the smaller size of the output cut. Thus the algorithm can be
applied repeatedly to find balanced cuts in almost-linear time. Inspired by
this work, multiple local algorithms were proposed [ACL07, AP09]. While all
these algorithms are fast, and almost-linear in running time, they are
inherently randomized, and the balanced cut found has conductance
$\widetilde{\Omega}(\sqrt{\phi})$.In contrast, our algorithm is deterministic,
and finds a cut of conductance at most $\phi\cdot m^{o(1)}.$

Another line of work develops fast SDP algorithms based on matrix-
multiplicative weights. The most popular of these is the Cut-Matching
framework of Khandekar-Rao-Vazirani [KRV09]. Inspired by [KRV09], several
works [AK07, OSVV08, OV11, OSV12] obtained almost-linear time algorithms for
Balanced Separator building on the matrix-multiplicative weights framework.
While the cut-matching framework and the resulting algorithms are elegant,
they rely on rather involved techniques that are non-intuitive. The celebrated
work of Arora-Rao-Vazirani [ARV09] obtained an $O(\sqrt{\log n})$
approximation for Balanced Separator via an SDP based algorithm. Faster
algorithms built on their ideas [AHK10, She09] achieved almost-linear running
time with $O(\sqrt{\log n})$ approximation. However, these algorithms are very
involved, based on matrix-multiplicative weights, randomized, and rely on
near-linear time (approximate) max-flow. Our algorithm and analysis work with
scalar multiplicative weights and are very simple to understand. Further, our
algorithm only need to invoke approximate shortest-path oracles under
increasing edge weights.

The only previous deterministic, almost-linear time approximation algorithm
for Balanced Separator was given recently by Chuzhoy-Gao-Li-Nanongkai-Peng-
Saranurak [CGLNPS20]. Their algorithm relies on a rather intricate recursive
scheme that implicitly uses at each recursion level a reduction to decremental
APSP. But even the analysis on a single level relies on the rather involved
expander pruning framework. In contrast to their work, the simplicity of our
algorithm and analysis stands out.

We also point out that a generalization of [CGLNPS20] to weighted graphs was
given by Li and Saranurak [LS21]. This algorithm implicitly uses [CGLNPS20],
and is therefore even more involved.

##  2 Main Result

We formally state our results in this section. Our main result is the
following theorem.

######  Theorem 2.1.

Given an $n$-vertex, $m$-edge graph $G$, an $\alpha_{\texttt{APSP}}$-approx
decremental APSP algorithm and conductance parameter $\phi$ and balance
parameter $b\in[1/n,1/4]$, the algorithm
$\textsc{LowConductanceCutOrCertify}(G,\phi,b)$ either

  1. 1.

Returns a cut $(S,\overline{S})$ with
${{\textsf{vol}}}_{G}(S),{{\textsf{vol}}}_{G}(\overline{S})\geq
b\cdot{{\textsf{vol}}}(G)$ with conductance $\Phi_{G}(S)\leq\phi$, or

  2. 2.

Certifies that every cut $(X,\overline{X})$ with
${{\textsf{vol}}}_{G}(X),{{\textsf{vol}}}_{G}(\overline{X})=\Omega(b\cdot{{\textsf{vol}}}_{G}(G))$
has conductance at least
$\phi\cdot\Omega\left(\frac{1}{\alpha_{\texttt{APSP}}\log
n\cdot\log(1/b)\cdot\log(\log(n)\alpha_{\texttt{APSP}}/(b\phi))}\right)=\phi\cdot\Omega\left(\frac{1}{\alpha_{\texttt{APSP}}\log^{3}(n)}\right).$

The algorithm is deterministic and requires the APSP data structure to undergo
$O(\alpha_{\texttt{APSP}}\cdot m\phi^{-1}\log^{3}n)$ updates, queries it
$O(m)$ times and spends an additional $O(\alpha_{\texttt{APSP}}\cdot
m\phi^{-1}\log^{3}n)$ time.

######  Remark 2.2.

APSP data structures often answer queries in time proportional to the number
of edges on the approximate shortest path that they return. Our algorithm
ensures that the number of such edges on all paths is bound by
$O(\alpha_{\texttt{APSP}}\cdot m\phi^{-1}\log^{3}n)$.

We note that for computing balanced cuts (i.e. cuts where $b$ is constant)
which is arguably the most interesting case, our approximation guarantee
becomes $\Omega(1/\alpha_{\texttt{APSP}}\log
n\cdot\log(\alpha_{\texttt{APSP}}\phi^{-1}\cdot\log n))$. For a decremental
APSP data structure with constant-approximation and
$\phi\geq\Omega(1/\log^{O(1)}n)$, this further simplifies to $\Omega(1/\log
n\log\log n)$.

Using the efficient $n^{o(1)}$-approximate decremental APSP data structure
from [BGS21] or [Chu21], we obtain the following result222We remark that both
data structures [BGS21, Chu21] implicitly rely on the framework of Chuzhoy-
Gao-Li-Nanongkai-Peng-Saranurak [CGLNPS20], thus, our reduction in combination
with these data structures does not yield a simpler algorithm in itself. We
are however optimistic that simpler data structures for the decremental APSP
problem are available in the future that do not necessarily rely on expander
techniques.:

######  Theorem 2.3.

Given an $n$-vertex, $m$-edge graph $G$, a conductance parameter $\phi$ and
balance parameter $b\in[1/n,1/4]$, there is an algorithm
$\textsc{LowConductanceCutOrCertify}(G,\phi,b)$ that can either

  1. 1.

Find a cut $(S,\overline{S})$ with
${{\textsf{vol}}}_{G}(S),{{\textsf{vol}}}_{G}(\overline{S})\geq
b\cdot{{\textsf{vol}}}(G)$ with conductance $\Phi_{G}(S)\leq\phi$, or

  2. 2.

Certify that every cut $(X,\overline{X})$ with
${{\textsf{vol}}}_{G}(X),{{\textsf{vol}}}_{G}(\overline{X})=\Omega(b\cdot{{\textsf{vol}}}_{G}(G))$
has conductance $\phi/n^{o(1)}.$

The algorithm is deterministic and runs in $m^{1+o(1)}/\phi$ time.

On the other hand, one can run Dijkstra’s shortest path algorithm for every
query and obtain the following:

######  Theorem 2.4.

Given an $n$-vertex, $m$-edge graph $G$, a conductance parameter $\phi$ and
balance parameter $b\in[1/n,1/4]$, there is a deterministic algorithm
$\textsc{LowConductanceCutOrCertify}(G,\phi,b)$ that can either

  1. 1.

Find a cut $(S,\overline{S})$ with
${{\textsf{vol}}}_{G}(S),{{\textsf{vol}}}_{G}(\overline{S})\geq
b\cdot{{\textsf{vol}}}(G)$ with conductance $\Phi_{G}(S)\leq\phi$, or

  2. 2.

Certify that every cut $(X,\overline{X})$ with
${{\textsf{vol}}}_{G}(X),{{\textsf{vol}}}_{G}(\overline{X})=\Omega(b\cdot{{\textsf{vol}}}_{G}(G))$
has conductance $\phi\cdot\Omega\left(\frac{1}{\log
n\cdot\log(1/b)\cdot\log(\log(n)/(\phi b))}\right).$

The algorithm is deterministic and runs in $\widetilde{O}(m^{2}/\phi)$ time.

##  3 Preliminaries

#### Sparsity and Expanders.

In this article, we consider an undirected $n$-vertex graph $G=(V,E)$. For
such a graph, we define the sparsity of a cut $\emptyset\subsetneq S\subsetneq
V$ by
$\Psi_{G}(S)=\frac{|E_{G}(S,\overline{S})|}{\min\\{|S|,|\overline{S}|\\}}$
where $E_{G}(S,\overline{S})$ is the set of edges with exactly one endpoint in
$S$. The sparsity of a graph $G$ is defined $\Psi(G)=\min_{\emptyset\subsetneq
S\subsetneq V}\Psi(S)$. If $G$ contains no $\psi$-sparse cut, we say that $G$
is a $\psi$-expander.

#### Conductance vs. Sparsity.

Via a simple reduction replacing each vertex of degree $d$ with an explicit
expander graph on $d$ vertices (see Appendix A), we can reduce to the case
where every vertex has degree at most 10. In such a graph, for any set
$S\subseteq V,$ $|S|\leq{{\textsf{vol}}}(S)\leq 10|S|,$ and thus, instead of
conductance
$\Phi_{G}(S)=\frac{|E_{G}(S,\overline{S})|}{\min\\{{{\textsf{vol}}}(S),{{\textsf{vol}}}{({V\setminus
S})}\\}},$ we can work with sparsity
$\Psi_{G}(S)=\frac{|E_{G}(S,\overline{S})|}{\min\\{|S|,|V\setminus S|\\}}.$
Throughout the rest of the article, we will therefore work with sparsity
instead of conductance.

#### Expander Constructions.

Given any $n$, there is a deterministic construction of a $\Omega(1)$-expander
on $n$ vertices of bounded degree. This will be an essential tool used in our
proof and we use $\psi_{0}$ to denote the universal lower bound on the
sparsity of such family of expanders.

######  Theorem 3.1 (See Thm. 2.4 of [CGLNPS20] based on Thm 2 of [GG81].).

There is an universal constant $\psi_{0}\in(0,1)$ and an algorithm
$\textsc{ConstDegExpander}(n)$ that returns a $\psi_{0}$-expander $H$ on a
vertex set of size $n$ with maximum degree $9$. The algorithm runs in time
$O(n)$.

######  Remark 3.2.

While deterministic algorithms to construct a constant-degree, constant
sparsity expander require rather involved proof techniques, we prove in
Appendix C a simple randomized algorithm to construct a $O(\log n)$-degree
$\Omega(\log n)$-expander $H$ in $O(n\log n)$ time. Using this randomized
algorithm in place of the above theorem only affects guarantees of our overall
algorithm by polylogarithmic factors.

#### Graph Embeddings.

Given graphs $H$ and $G$ that are defined over the same vertex set, then we
say that a function $\Pi_{H\mapsto G}$ is an _embedding_ if it maps each edge
$(u,v)\in H$ to a $u$-to-$v$ path $P_{u,v}=\Pi_{H\mapsto G}(u,v)$ in $G$. We
say that the _congestion_ of $\Pi_{H\mapsto G}$ is the maximum number of times
that any edge $e\in E(G)$ appears on any embedding path:

$\mathit{cong}(\Pi_{H\mapsto G})=\max_{e\in E(G)}|\\{e^{\prime}\in
E(H)\;|\;e\in\Pi_{H\mapsto G}(e^{\prime})\\}|.$

#### Certifying Expander Graphs via Embeddings.

Graph embeddings are useful since they allow us to argue that if we can embed
a graph $H$ that is known to be an expander into a graph $G$, then we can
reason about the sparsity of $G$, as shown below.

######  Lemma 3.3.

Given a $\psi$-expander graph $H$ and an embedding of $H$ into $G$ with
congestion $C$, then $G$ must be an
$\Omega\left(\frac{\psi}{C}\right)$-expander.

###### Proof.

Consider any cut $(S,V\setminus S)$ with $|S|\leq|V\setminus S|$. Since $H$ is
a $\psi$-expander, we have that $|E_{H}(S,V\setminus S)|\geq\psi|S|$. We also
know by the embedding of $H$ into $G$, that for each edge $(u,v)\in
E_{H}(S,V\setminus S)$, we can find path a $P_{u,v}$ in $G$ that also has to
cross the cut $(S,V\setminus S)$ at least once. But since each edge in $G$ is
on at most $C$ such paths, we can conclude that at least $|E_{H}(S,V\setminus
S)|/C\geq\psi|S|/C$ edges in $G$ cross the cut $(S,V\setminus S)$. ∎

We use the following generalization of this Folklore result to balanced sparse
cuts.

######  Lemma 3.4.

Given a $\psi$-expander graph $H$, a subgraph $H^{\prime}\subseteq H$ with
$|E(H\setminus H^{\prime})|\leq\frac{\psi}{2}bn$ for some $b\in[0,1]$ and an
embedding $\Pi_{H^{\prime}\mapsto G}$ of $H^{\prime}$ into $G$ with congestion
$C$, then for all cuts $(S,\overline{S})$ where $bn\leq|S|\leq n/2$, we have
$\Psi_{G}(S)=\Omega\left(\frac{\psi}{C}\right)$.

###### Proof.

Observe that for each such $(S,\overline{S})$, we have
$|E_{H^{\prime}}(S,\overline{S})|\geq|E_{H}(S,\overline{S})|-|E(H\setminus
H^{\prime})|\geq\psi|S|-\frac{\psi}{2}bn\geq\frac{\psi}{2}|S|$. Using the same
argument as above, the cut size of $S$ in $G$ is at least
$\left|E_{G}(S,\overline{S})\right|\geq\left|E_{H^{\prime}}(S,\overline{S})\right|/C\geq\psi|S|/2C.$
∎

#### Decremental All-Pairs Shortest-Paths (APSP).

A decremental $\alpha_{\texttt{APSP}}$-approximate All-Pairs Shortest-Paths
(APSP) data structure (abbreviated $\alpha_{\texttt{APSP}}$-APSP) is a data
structure that is initialized to an $m$-edge $n$-vertex graph $G$ and supports
the following operations:

  * •

$\textsc{IncreaseEdgeWeight}(u,v,\Delta)$: increases the edge weight of
$(u,v)$ by $\Delta$.

  * •

$\textsc{QueryDistance}(u,v)$: for any $u,v\in V$ returns a distance estimate
$\tilde{d}(u,v)$ that $\alpha_{\texttt{APSP}}$-approximates the distance from
$u$ to $v$ in the current graph $G$ denoted $d_{G}(u,v)$, i.e.
$\tilde{d}(u,v)\in[d_{G}(u,v),\alpha_{\texttt{APSP}}\cdot d_{G}(u,v)]$.

  * •

$\textsc{QueryPath}(u,v)$: returns a path $\pi$ from $u$ to $v$ in the current
graph $G$ of total weight $\tilde{d}(u,v)$ (that is the value of the distance
estimate if queried).

We denote the total time required by the data structure to execute a series of
$q$ queries and $u$ update operations on an $n$-vertex constant-degree graph
by $T_{APSP}(q,u)$.

Recently, deterministic $n^{o(1)}$-approximate APSP data structures have been
developed (see [Chu21, BGS21]) that process any sequence of $\tilde{O}(m)$
edge weight increases in total time $m^{1+o(1)}$ while answering distance
queries in time $n^{o(1)}$ time and for a path query, returns paths in time
near-linear in the number of edges on the path (i.e. if it returns a path $P$,
it takes at most time $|P|n^{o(1)}$. We conjecture that in the near-future,
$O(\log n)$-APSP data structures are found that implement edge weight
increases in time $\tilde{O}(m)$ and answers distance queries in time
$\tilde{O}(1)$ and path queries in time $\tilde{O}(|P|)$.

##  4 Our Algorithm

In this section, we present an algorithm to find sparse cuts with respect to
sparsity or embed an expander into a constant-degree graph $G$. By standard
reductions (given in Appendix A and Appendix B), one can translate between
sparsity and conductance and remove the bounded-degree assumption, both with
only a constant loss in quality. Thus, by proving the theorem below, we
directly establish our main result, Theorem 2.1.

######  Theorem 4.1.

Given a graph $G$ of degree at most 10, an $\alpha_{\texttt{APSP}}$-approx
decremental APSP algorithm and sparsity parameter $\psi$ and balance parameter
$b\in[1/n,1/4]$, there is an algorithm
$\textsc{SparseCutOrCertify}(G,\psi,b)$ (Algorithm 2) that can either

  1. 1.

Find a cut $(S,\overline{S})$ with $|S|,|\overline{S}|\geq bn$ of sparsity
$\leq\psi$, or

  2. 2.

Certify that every cut $(X,\overline{X})$ with $|X|,|\overline{X}|=\Omega(bn)$
has sparsity
$\psi\cdot\Omega\left(\frac{1}{\alpha_{\texttt{APSP}}\log
n\cdot\log(1/b)\cdot\log(\log(n)\alpha_{\texttt{APSP}}/(b\psi))}\right).$

The algorithm is deterministic and requires the APSP data structure to undergo
$O(\alpha_{\texttt{APSP}}\cdot n/\psi\log^{3}n)$ updates, queries it $O(n)$
times and spends an additional $O(\alpha_{\texttt{APSP}}\cdot
n/\psi\log^{3}n)$ time.

######  Remark 4.2.

Our algorithm ensures that the total number of edges summed across all queried
paths is bound by $O(\alpha_{\texttt{APSP}}\cdot n/\psi\log^{3}n)$.

The algorithm contains two phases. The first phase tries to embed an
$\Omega(1)$-expander into the input graph $G$ with congestion
$\widetilde{O}(1/\psi).$ Let $F$ be the subset of expander-edges the algorithm
cannot embed. If $|F|=O(bn)$, i.e. the algorithm embed all but $O(bn)$ edges,
Lemma 3.4 ensures that every $b$-balanced cut has sparsity
$\widetilde{\Omega}(\psi).$ Otherwise, $|F|=\Omega(bn)$ and the algorithm
outputs an edge weight $\boldsymbol{\mathit{w}}$ such that every $(u,v)\in F$
are far apart w.r.t. $\boldsymbol{\mathit{w}}.$ In this case, the second phase
is initiated to extract a sparse $\Omega(b)$-balanced cut from these far-apart
pairs of vertices.

###  4.1 An Algorithm to Separate Or Certify

First, we present the algorithm for the first phase that either embeds a large
portion of an expander or finds a large set of far-apart vertex-pairs w.r.t.
some edge weights $\boldsymbol{\mathit{w}}.$

######  Lemma 4.3.

Given an $\alpha_{\texttt{APSP}}$-APSP data structure, two graphs $G$ and $H$
over the same vertex set $V$, a congestion parameter $C\in[1,n]$, and a
balance parameter $b\in[1/n,1/2]$. The algorithm
$\textsc{SeparateOrCertify}(G,H,C,b)$ (Algorithm 1) outputs either

  1. 1.

A set of weights $\boldsymbol{{\mathit{w}}}\in\mathbb{R}_{\geq 1}^{E(G)}$ with
$\|\boldsymbol{{\mathit{w}}}\|_{1}\leq 20n$, a number $b^{\prime}\in[b,1/2]$,
and a subset of edges $F\subseteq E(H)$ with $|F|>10b^{\prime}n$ such that

$\forall(u,v)\in
F,\quad\operatorname{\mathtt{dist}}_{\boldsymbol{{\mathit{w}}}}(u,v)>\frac{C}{b^{\prime}},\text{
or }$

  2. 2.

A graph $H^{\prime}\subseteq H$ with $|E(H)\setminus E(H^{\prime})|\leq 10bn$
and an embedding $\Pi_{H^{\prime}\mapsto G}$ that maps each edge $(u,v)$ in
$H^{\prime}$ to a $uv$-path in $G$ with congestion
$O(C\cdot\alpha_{\texttt{APSP}}\cdot\log(1/b)\cdot\log(C\cdot\alpha_{\texttt{APSP}}/b))$.

The algorithm is deterministic and requires the APSP data structure to undergo
$O(C\alpha_{\texttt{APSP}}n\log^{2}n)$ edge updates and $O(n)$ distance
queries along with additional $O(C\alpha_{\texttt{APSP}}n\log^{2}n)$ time.

1$H^{\prime}=(V,\emptyset)$; $\Pi_{H^{\prime}\mapsto G}\leftarrow\emptyset$;
$\boldsymbol{\mathit{w}}\leftarrow\mathbf{1}^{|E(G)|}$;
$\eta\leftarrow\frac{1}{4C\alpha_{\texttt{APSP}}\log_{2}(10/b)}$.

2 Maintain an $\alpha_{\texttt{APSP}}$-approximate APSP data structure on $G$
weighted by $\boldsymbol{\mathit{w}}$.

3 for  _$i=0,1,\ldots,\lfloor\log_{2}(1/b)\rfloor$_ do

4 foreach  _$e=(u,v)\in E(H)\setminus E(H^{\prime})$_ do

5 if  _$\textsc{APSP}.\textsc{QueryDist}(u,v)\leq 2^{i}\cdot
C\alpha_{\texttt{APSP}}$_ then

6 Add $e$ to $H^{\prime}$; $\Pi_{H^{\prime}\mapsto
G}(e)\leftarrow\textsc{APSP}.\textsc{QueryPath}(u,v)$.

7 foreach  _$f\in\Pi_{H^{\prime}\mapsto G}(e)$_ do

8 $\textsc{APSP}.\textsc{IncreaseWeight}(e,\eta\boldsymbol{\mathit{w}}_{e})$;
$\boldsymbol{\mathit{w}}_{e}\leftarrow(1+\eta)\boldsymbol{\mathit{w}}_{e}$.

9

10

11 if  _$|E(H)\setminus E(H^{\prime})| >10n/2^{i}$_ then return
$(\boldsymbol{\mathit{w}},2^{-i},E(H)\setminus E(H^{\prime}))$.

12

return $(H^{\prime},\Pi_{H^{\prime}\mapsto G})$.

fAlgorithm 1 $\textsc{SeparateOrCertify}(G,H,C,b)$

#### The Algorithm.

Algorithm 1 implements $\textsc{SeparateOrCertify}(G,H,C,b)$. Here, the task
of finding an embedding of $H$ into $G$ is interpreted as a multicommodity
flow problem, that is each edge $(u,v)\in H$ gives rise to the demand to route
one unit of flow from $u$ to $v$. Later, we use a $\psi_{0}$-expander in place
of $H$.

The goal of the algorithm is to find such an embedding/ multicommodity flow
with small congestion which combined with our choice of $H$ certifies that $G$
is a good (almost) expander (i.e. contains no balanced sparse cut). Here, we
guess the congestion to be roughly $C$ and want to enforce
$\operatorname{\mathtt{cong}}(\Pi_{H\mapsto G})\leq C$. In fact, we even
provide a slightly tighter analysis.

To achieve this goal, we use a technique which is an instance of the
_Multiplicative Weight Update (MWU)_ framework. Initially, we define a uniform
weight function $\boldsymbol{\mathit{w}}$ with weights over $G$. We try to
embed each edge $(u,v)\in E(H)$ using a short $uv$-path $P_{uv}$ in $G$ with
respect to $\boldsymbol{\mathit{w}}$. Whenever we embed an edge $(u,v)$ in
such a way and the path $P_{uv}$ contains an edge $e\in E(G)$, we increase the
weight $\boldsymbol{\mathit{w}}_{e}$ by a multiplicative factor $(1+\eta)$.
Naturally, after $t$ edges have been embedded by using the edge $e$, we have
scaled up the weight of $e$ by a factor of $(1+\eta)^{t}$. Using
$e^{x}\leq(1+2x),x\in[0,1]$, and setting $\eta\approx C$ ensures that the
weight $\boldsymbol{\mathit{w}}_{e}$ approaches a large polynomial in $n$ for
$t\gg 2\eta\log n$ (which again is $\approx C$).

At the same time, the algorithm only embeds edges $(u,v)\in E(H)$ if the
distance between the endpoints in $G$ w.r.t. $\boldsymbol{\mathit{w}}$ is
small. This ensures that $\|\boldsymbol{\mathit{w}}\|_{1}=O(n\log(1/b))$ and
that we never use an edge $e$ into which many embedding paths are already
routed.

More precisely, we proceed in rounds to embed edges in $H$. At later rounds
(i.e. when $i$ large), we have already embed a large number of edges in $H$.
Since the number of remaining edges is small, we allow for them to be embed
with slightly longer paths which still lets us argue that
$\|\boldsymbol{\mathit{w}}\|_{1}$ is increased by at most $O(n)$ in the
current round. If in any round, it is not possible to embed many of the
remaining edges with paths of weight at most the current threshold, we can
simply return these edges and end up in the first scenario.

#### Correctness (Returning in Algorithm 1).

We start by proving the following claim which then immediately establishes
correctness if Algorithm 1 terminates at Algorithm 1 (i.e. in the second
scenario).

######  Invariant 4.4.

After the $i$-th iteration of the for-loop in Algorithm 1, we have
$\|\boldsymbol{\mathit{w}}\|_{1}\leq 10n(1+2\eta
C\alpha_{\texttt{APSP}}\cdot(i+1))\leq 20n$.

###### Proof.

Initially, $\|\boldsymbol{\mathit{w}}\|_{1}=\|\mathbf{1}^{|E(G)|}\|_{1}\leq
10n$.

To gauge the increase in $\|\boldsymbol{\mathit{w}}\|_{1}$ during the $i$-th
iteration of the for-loop, consider the effect of embedding a new edge $e$ in
the foreach-loop starting in Algorithm 1 (we only consider such iterations if
the if-statement in Algorithm 1 evaluates true as otherwise
$\boldsymbol{\mathit{w}}$ does not change). Letting
$\boldsymbol{\mathit{w}}^{OLD}$ denote $\boldsymbol{\mathit{w}}$ just before
the foreach-loop iteration and $\boldsymbol{\mathit{w}}^{NEW}$ right after. We
clearly have that
$\|\boldsymbol{\mathit{w}}^{NEW}\|_{1}=\|\boldsymbol{\mathit{w}}^{OLD}\|+\eta\cdot\boldsymbol{\mathit{w}}^{OLD}(\Pi_{H^{\prime}\mapsto
G}(e))$ from Algorithm 1. But since the if-statement was true, we have that
$\boldsymbol{\mathit{w}}^{OLD}(\Pi_{H^{\prime}\mapsto G}(e))\leq 2^{i}\cdot
C\alpha_{\texttt{APSP}}$. We conclude that each edge that is newly embed
increases $\|\boldsymbol{\mathit{w}}\|_{1}$ by at most $\eta\cdot 2^{i}\cdot
C\alpha_{\texttt{APSP}}$.

At the beginning of the $i$-th iteration of the for-loop, there are at most
$10n/2^{i}$ edges in in $E(H)\setminus E(H^{\prime})$. At the very first
iteration $i=0$, $|E(H)|\leq 20n$ as the max degree of $H$ is at most $10.$
Later, $|E(H)\setminus E(H^{\prime})|\leq 10n/2^{i-1}$ holds or otherwise the
algorithm would terminate after the $(i-1)$-th iteration in Algorithm 1. Thus,
during the $i$-th iteration, the foreach-loop in Algorithm 1 iterates over at
most $10n/2^{i-1}$ edges as well. We can bound the total increase of
$\|\boldsymbol{\mathit{w}}\|_{1}$ during the $i$-th iteration by

$\frac{10n}{2^{i-1}}\cdot\eta\cdot 2^{i}\cdot
C\alpha_{\texttt{APSP}}=20n\cdot\eta C\alpha_{\texttt{APSP}}.$

The total number of iterations is at most $\lfloor\log_{2}(1/b)\rfloor+1.$
This establish the second inequality using the definition of $\eta$.

∎

Note that for every edge $(u,v)$ that is in $E(H)\setminus E(H^{\prime})$ when
the algorithm returns in Algorithm 1, the preceding foreach-loop iterated over
$(u,v)$ and found that $\textsc{APSP}.\textsc{QueryDist}(u,v)>2^{i}\cdot
C\alpha_{\texttt{APSP}}$ (as otherwise $(u,v)$ would have been added to
$E(H^{\prime})$). But this implies that
$\operatorname{\mathtt{dist}}_{\boldsymbol{\mathit{w}}}(u,v)>2^{i}\cdot
C=C/b^{\prime}$ by our choice of $b^{\prime}$. To establish correctness, it
only remains to use the if-condition preceding Algorithm 1 and observe that
the condition does not hold when $i=0$.

#### Correctness (Returning in Algorithm 1).

It is straight-forward to see from Algorithm 1 that $\Pi_{H^{\prime}\mapsto
G}$ is a correct embedding from $H^{\prime}$ to $G$ and that $|E(H)\setminus
E(H^{\prime})|\leq 10bn$. It thus only remains to bound the congestion of
$\Pi_{H^{\prime}\mapsto G}$.

######  Lemma 4.5.

The congestion of $\Pi_{H^{\prime}\mapsto G}$ is at most
$\frac{2\log(2C\alpha_{\texttt{APSP}}/b)}{\eta}$.

###### Proof.

Let us fix any edge $e\in E(G)$. Note that each time we add an embedding path
in the foreach-loop starting in Algorithm 1 that contains $e$, we increase the
weight $\boldsymbol{\mathit{w}}_{e}$ to $(1+\eta)\boldsymbol{\mathit{w}}_{e}$.
Since initially, $\boldsymbol{\mathit{w}}_{e}=1$, we have that after $t$ times
that the edge $e$ was used to embed an edge in the foreach-loop, we have that
$\boldsymbol{\mathit{w}}_{e}=(1+\eta)^{t}\geq e^{t\eta/2}$ since $e^{x}\leq
1+2x$ for $x\in[0,1]$. In particular, if the algorithm embeds $t$ times into
$e$ for $t>\frac{2\log(2C\alpha_{\texttt{APSP}}/b)}{\eta}$, then at the end of
the algorithm, we would have
$\boldsymbol{\mathit{w}}_{e}>\frac{2C\alpha_{\texttt{APSP}}}{b}$.

However, note that by the if-condition in Algorithm 1, we never embed into an
edge $e$ that has weight more than $2^{\log_{2}(1/b)}\cdot
C\alpha_{\texttt{APSP}}=\frac{C\alpha_{\texttt{APSP}}}{b}$ since otherwise the
path using this edge has higher weight. We can thus conclude that at the end
of the algorithm,
$\boldsymbol{\mathit{w}}_{e}\leq(1+\eta)\frac{C\alpha_{\texttt{APSP}}}{b}\leq\frac{2C\alpha_{\texttt{APSP}}}{b}$,
which leads to a contradiction. ∎

#### Run time Analysis.

The for-loop of the algorithm runs at most $O(\log(1/b))$ iterations and in
the $i^{th}$ iteration at most $O(n/2^{i})$ edges are iterated over in the
foreach-loop starting in Algorithm 1. Thus, the total number of queries to the
APSP data structure can be bound by $O(\sum_{i}n/2^{i})=O(n)$.

The time the algorithm spends updating the weights in Algorithm 1 can be bound
by observing that each edge $e$ has its weight increased only after an
additional embedding path was added through $e$; but the congestion is bound
by $O(\log n/\eta)$ by Lemma 4.5, thus the foreach-loop is executed at most
$O(n\log n/\eta)$ times over the entire course of the algorithm. This
concludes our analysis of the number of updates to the APSP data structure.
The runtime analysis of the algorithm follows along the same line of
reasoning.

######  Remark 4.6.

Our algorithm can be extended to compute expander decompositions, following
the approach of [SW19]. We refer the reader to this paper for additional
background and the necessary definitions. For readers familiar with [SW19], we
briefly describe the key step we need to implement: When
$\textsc{SeparateOrCertify}(G,H,C,b)$ certifies that most edges in the
expander $H$ can be embedded into $G$ (and hence by Lemma 3.4 there are no
sparse balanced cuts in $G$) then we need to be able to extract a large
expander from $G$ so that we only need to recurse on a small (potentially)
non-expanding part To find an induced subgraph with large expansion, we first
produce a new graph $G^{\prime}$ by adding the edges $E(H)\setminus
E(H^{\prime})$ to $G$. This ensures that $G^{\prime}$ is a good expander. We
then use the expander pruning of [SW19] to delete the same edges
$E(H)\setminus E(H^{\prime})$ from $G^{\prime}$, resulting in a large leftover
expander $G^{\prime\prime}$ with vertex set $V^{\prime\prime}$. By
construction $G[V^{\prime\prime}]$ is now a large expander.

###  4.2 Extracting the Sparsest Cut

In order to prove Theorem 4.1, we now have to show how to extract a sparsest
cut from the weight function that is returned in case no embedding is found.
We point out that in order to do so it is significantly more convenient to
work with an integral weight function $\boldsymbol{\mathit{w}}$. We therefore
round the weight function that we obtain Lemma 4.3 up which might result in
$\|\boldsymbol{\mathit{w}}\|_{1}$ being at most twice as large as stated.

We use the following auxiliary algorithm that finds a cut with few edges
crossing given any two vertices at large distance.

######  Claim 4.7.

The procedure $\textsc{FindThinLayer}(G,\boldsymbol{{\mathit{w}}},u,v,D)$
takes a graph $G$ weighted by $\boldsymbol{{\mathit{w}}}\in\mathbb{N}_{\geq
1}^{E(G)}$ and two vertices $u,v$ such that
$\operatorname{\mathtt{dist}}_{\boldsymbol{{\mathit{w}}}}(u,v)>D$ for some
integer $D>4\log_{2}\|\boldsymbol{{\mathit{w}}}\|_{1}$. It returns a set of
vertices $S\neq\emptyset$ such that $|S|\leq|V|/2$ and $|E_{G}(S,V\setminus
S)|\leq\frac{4\boldsymbol{{\mathit{w}}}(S)\log_{2}\|\boldsymbol{{\mathit{w}}}\|_{1}}{D}$.
The algorithm runs in time $O(|E_{G}(S)|\log|E_{G}(S)|)$.

Given this auxiliary algorithm, we can state the final algorithm and prove our
main result, Theorem 4.1. As described before, we use the algorithm
$\textsc{SeparateOrCertify}(G,H,C,\hat{b})$ with a constant degree, constant
sparsity expander $H$. It is straight-forward to conclude that $G$ contains no
balanced sparse cuts, if the procedure can embed $H$.

Otherwise, we take the weight function and repeatedly find a separator between
the endpoints of edges in $F$ that are far from each other (using the
auxiliary algorithm). Note that if there are roughly $b^{\prime}n$ edges in
$F$ at distance roughly $C/b^{\prime}$, then using the auxiliary algorithm
repeatedly with $D\approx C/b^{\prime}$, produces a cut where the smaller side
has $\Omega(|F|)=\Omega(b^{\prime}n)$ vertices. Using the guarantees from the
auxiliary procedure, we further have that the number of edges in the induced
cut are at most $\tilde{O}(b^{\prime}n/C)$. Thus, the sparsity of the cut must
be $\tilde{O}(1/C)$ where $C\approx 1/\psi$ by our choice of parameters.

1$H\leftarrow\textsc{ConstDegExpander}(|V(G)|)$; $C\leftarrow 320\log n/\psi$;

2 if  _$\textsc{SeparateOrCertify}(G,H,C,2b)$ returns
$(H^{\prime},\Pi_{H^{\prime}\mapsto G})$_ then

3 return $(H^{\prime},\Pi_{H^{\prime}\mapsto G})$.

4else // i.e. if it returns $(\boldsymbol{{\mathit{w}}},b^{\prime},F)$

5
$\widehat{\boldsymbol{\mathit{w}}}\leftarrow\lceil\boldsymbol{{\mathit{w}}}\rceil$.

6 $X\leftarrow V(G)$.

7 $D\leftarrow 2C/b^{\prime}$.

8 while  _$\exists(u,v)\in H[X]\cap F$ and $|V\setminus X|\leq n/4$_ do

9 // $\operatorname{\mathtt{dist}}_{\widehat{\boldsymbol{\mathit{w}}}}(u,v)>D$

10
$S\leftarrow\textsc{FindThinLayer}(G[X],\widehat{\boldsymbol{\mathit{w}}},u,v,D)$.

11 $X\leftarrow X\setminus S$.

12 return $V\setminus X$.

fAlgorithm 2 $\textsc{SparseCutOrCertify}(G,\psi,b)$

See 4.1

###### Proof.

The case where Algorithm 2 returns in Algorithm 2 follows directly from Lemma
4.3, Theorem 3.1 and Lemma 3.4. Let us therefore analyze the remaining case
where the algorithm returns in Algorithm 2 (the while-loop can be seen to
terminate since each iteration shrinks the set $X$ by 4.7 and $X=\emptyset$
trivially has no two vertices at far distance).

We first prove that the final set $V\setminus X$ has size
$b^{\prime}n\leq|V\setminus X|\leq\frac{3}{4}n$:

  * •

$b^{\prime}n\leq|V\setminus X|$: Initially, $H[X]=H$ and $F\subseteq H$
contains more than $10b^{\prime}n$ edges by Lemma 4.3. Every edge $(u,v)\in F$
has
$\operatorname{\mathtt{dist}}_{\widehat{\boldsymbol{\mathit{w}}}}(u,v)\geq\operatorname{\mathtt{dist}}_{\boldsymbol{{\mathit{w}}}}(u,v)>C/b^{\prime}.$
Since the maximum degree of $H$ is $10$, as long as $|V\setminus
X|<b^{\prime}n$, $H[X]$ contains all but $10b^{\prime}n$ edges from $H.$ Thus,
$H[X]\cap F$ is not empty and the while-loop continues. We conclude that
$b^{\prime}n\leq|V\setminus X|$ holds.

  * •

$|V\setminus X|\leq\frac{3}{4}n$: Since the while-loop condition allows only
invocations of FindThinLayer if $|V\setminus X|\leq n/4$, and since this
procedure returns the smaller side of the cut it produces by 4.7 (which is
found on $G[X]$), we can conclude that at the end of the algorithm
$|V\setminus X|\leq n/4+n/2\leq\frac{3}{4}n$.

This indicates that $|X|\geq n/4\geq b^{\prime}n/2\geq bn$ since $2b\leq
b^{\prime}\leq\frac{1}{2}.$

Next, we bound the sparsity of the cut $V\setminus X.$ Let
$S_{1},S_{2},\ldots,S_{k}$ be the sets returned by procedure FindThinLayer one
after another over the course of the while-loop, such that $V\setminus X=\cup
S_{i}$. We first observe that these sets are vertex-disjoint since after the
$i$-th iteration, the procedure FindThinLayer is invoked on the graph
$G_{i}=G[V\setminus(S_{1}\cup\ldots\cup S_{i})]$ to find $S_{i+1}$. Further,
the final cut $(X,V\setminus X)$ contains only edges that were previously in a
thin layer, i.e.

$E_{G}(X,V\setminus
X)\subseteq\bigcup_{i}E_{G_{i}}(V\setminus(S_{1}\cup\ldots\cup S_{i}),S_{i}).$

It remains to use the guarantee of 4.7 that for each $S_{i}$, we have
$|E_{G_{i}}(S_{i},V\setminus(S_{1}\cup\ldots\cup
S_{i}))|\leq\frac{4\widehat{\boldsymbol{\mathit{w}}}(S_{i})\log_{2}\|\boldsymbol{{\mathit{w}}}\|_{1}}{D}$
and by the vertex-disjointness of $S_{1},S_{2},\ldots,S_{k}$, we thus have
that

$\displaystyle|E_{G}(X,V\setminus X)|$
$\displaystyle\leq|\bigcup_{i}E_{G_{i}}(S_{i},V\setminus(S_{1}\cup\ldots\cup
S_{i}))|\leq\sum_{i}\frac{4\widehat{\boldsymbol{\mathit{w}}}(S_{i})\log\|\widehat{\boldsymbol{\mathit{w}}}\|_{1}}{D}$
$\displaystyle\leq\frac{4\|\widehat{\boldsymbol{\mathit{w}}}\|_{1}\log\|\widehat{\boldsymbol{\mathit{w}}}\|_{1}}{D}=\frac{8n\cdot
b^{\prime}\log n}{C}$

where we use $\|\boldsymbol{{\mathit{w}}}\|\leq 20n$ from Theorem 4.1 and
$\widehat{\boldsymbol{\mathit{w}}}$ is obtained from rounding up
$\boldsymbol{{\mathit{w}}}$, and our choice of $D$. Since we have shown that
$|X|,|V\setminus X|\geq b^{\prime}n/2\geq bn$, choosing $C=320\log n/\psi$, we
have $\Psi(V\setminus X)=\Psi(X)\leq\psi$, as desired.

We use the disjointness of $S_{1},S_{2},\ldots,S_{k}$ to argue that the total
time spend in procedure FindThinLayer can be bound by $O(n\log n)$. The
remainder of the runtime analysis is trivial given Lemma 4.3. ∎

It remains to provide an implementation of
$\textsc{FindThinLayer}(G,\boldsymbol{{\mathit{w}}},u,v,D)$ and prove 4.7. The
algorithm follows a simple ball-growing procedure. It grows balls from both
endpoints $u$ and $v.$ Because the distance between $u$ and $v$ are guaranteed
to be large, the procedure takes longer time. However, these two balls cannot
be larger than the entire graph. There must be a moment that one of the ball
grows only by a thin layer.

See 4.7

###### Proof.

Since $\operatorname{\mathtt{dist}}_{\boldsymbol{{\mathit{w}}}}(u,v)>D$ by
assumption, we have that at least one of $u$ and $v$ have their ball to radius
$D/2$ contain at most half the vertices in $G$. More formally, for some
$z\in\\{u,v\\}$, $|B_{G,\boldsymbol{{\mathit{w}}}}(z,D/2)|\leq|V|/2$. We claim
that there is a radius $0<r\leq D/2$, such that taking $S=B(z,r)$ satisfies
the above guarantees. For this proof, it is convenient to define the following
auxiliary function $\Phi(z,r)=\sum_{e\in E}\Phi(z,r,e)$ where the latter
functions are defined for all edges $e=(x,y)\in E$ by

$\Phi(z,r,e)=\begin{cases}|\operatorname{\mathtt{dist}}_{\boldsymbol{{\mathit{w}}}}(z,x)-\operatorname{\mathtt{dist}}_{\boldsymbol{{\mathit{w}}}}(z,y)|&\text{if
}\operatorname{\mathtt{dist}}_{\boldsymbol{{\mathit{w}}}}(z,x)\leq r\text{ and
}\operatorname{\mathtt{dist}}_{\boldsymbol{{\mathit{w}}}}(z,y)\leq r\\\
r-\operatorname{\mathtt{dist}}_{\boldsymbol{{\mathit{w}}}}(z,x)&\text{if
}\operatorname{\mathtt{dist}}_{\boldsymbol{{\mathit{w}}}}(z,x)\leq
r<\operatorname{\mathtt{dist}}_{\boldsymbol{{\mathit{w}}}}(z,y)\\\
r-\operatorname{\mathtt{dist}}_{\boldsymbol{{\mathit{w}}}}(z,y)&\text{if
}\operatorname{\mathtt{dist}}_{\boldsymbol{{\mathit{w}}}}(z,y)\leq
r<\operatorname{\mathtt{dist}}_{\boldsymbol{{\mathit{w}}}}(z,x)\\\
0&\text{otherwise}\end{cases}$

Here, an edge $e=(x,y)\in E(G)$ contributes the distance between its two
endpoints $x$ and $y$ (which is at most $\boldsymbol{\mathit{w}}_{e}$) to
$\Phi(z,r,e)$ if both endpoints are fully contained in the ball $B(z,r)$. If
neither of the endpoints are contained it contributes $0$. Otherwise,
$e=(x,y)$ contributes the distance of the endpoint closer to $z$ to the
boundary of the ball. In both cases,
$0\leq\Phi(z,r,e)\leq\boldsymbol{{\mathit{w}}}_{e}$. This means in particular
that the weight of edges incident to $B(z,r)$ denoted by
$\boldsymbol{{\mathit{w}}}(E(B(z,r)))$ is always greater-equal to $\Phi(z,r)$,
i.e. $\boldsymbol{{\mathit{w}}}(E(B(z,r)))\geq\Phi(z,r)$ for all $r$.

Note further that $\Phi(z,r+1)-\Phi(z,r)$ is exactly $|E_{G}(B(z,r),V\setminus
B(z,r))|$, the number of edges that leave $B(z,r)$. To see this, observe that
an edge $e=(x,y)$ contributes $1$ to the difference if
$\operatorname{\mathtt{dist}}_{\boldsymbol{{\mathit{w}}}}(x,z)\leq
r<r+1\leq\operatorname{\mathtt{dist}}_{\boldsymbol{{\mathit{w}}}}(y,z)$ holds,
i.e. $e$ leaves $B(z,r)$. Otherwise, the contribution of $e$ are identical in
both $\Phi(z,r)$ and $\Phi(z,r+1).$ Here we use that
$\boldsymbol{{\mathit{w}}}$ is integral and so are distances in $G$.

Given this set-up, assume for contradiction that for all $0<r<D/2$, we have

$\Phi(z,r+1)>\left(1+\frac{4\log_{2}\|\boldsymbol{{\mathit{w}}}\|_{1}}{D}\right)\Phi(z,r).$

By induction we have that

$\Phi(z,D/2)\geq\left(1+\frac{4\log_{2}\|\boldsymbol{{\mathit{w}}}\|_{1}}{D}\right)^{D/2-1}\Phi(z,1)>\|\boldsymbol{{\mathit{w}}}\|_{1}$

where we use that $1+x\geq 2^{x}$ for $x\in[0,1]$. This would give a
contradiction since
$\|\boldsymbol{{\mathit{w}}}\|_{1}\geq\boldsymbol{{\mathit{w}}}(E(B(z,D/2)))\geq\Phi(z,D/2)>\|\boldsymbol{{\mathit{w}}}\|_{1}$.

Therefore, there must be some radius $0<r<D/2$ such that

$\displaystyle\Phi(z,r+1)\leq\left(1+\frac{4\log_{2}\|\boldsymbol{{\mathit{w}}}\|_{1}}{D}\right)\Phi(z,r).$

Combining with our previous discussion yields that

$\displaystyle|E(B(z,r),V\setminus B(z,r))|$
$\displaystyle=\Phi(z,r+1)-\Phi(z,r)$
$\displaystyle\leq\frac{4\log_{2}\|\boldsymbol{{\mathit{w}}}\|_{1}}{D}\Phi(z,r)$
$\displaystyle\leq\frac{4\boldsymbol{{\mathit{w}}}(E(B(z,r)))\log_{2}\|\boldsymbol{{\mathit{w}}}\|_{1}}{D}.$

We can therefore take $S=B(z,r)$, as desired.

Finally, to compute this cut, we run Dijkstra’s algorithm from $u$ and $v$ in
parallel and check for the earliest radius $r$ for either of them such that
the inequality holds. Thus, the algorithm runs in time
$O(|E_{G}(S)|\log|E_{G}(S)|)$. ∎

## References

  * [ACL07] Reid Andersen, Fan R.. Chung and Kevin J. Lang  “Using PageRank to Locally Partition a Graph”  In _Internet Mathematics_ 4.1, 2007, pp. 35–64
  * [AHK10] Sanjeev Arora, Elad Hazan and Satyen Kale  “O(sqrt(log(n)) Approximation to SPARSEST CUT in Õ(n${}^{\mbox{2}}$) Time”  In _SIAM J. Comput._ 39.5, 2010, pp. 1748–1771  DOI: 10.1137/080731049
  * [AK07] Sanjeev Arora and Satyen Kale  “A combinatorial, primal-dual approach to semidefinite programs”  In _Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007_ ACM, 2007, pp. 227–236  DOI: 10.1145/1250790.1250823
  * [AKLPST22] Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak and Ohad Trabelsi  “Breaking the cubic barrier for all-pairs max-flow: Gomory-Hu tree in nearly quadratic time”, 2022  FOCS
  * [AKT21] Amir Abboud, Robert Krauthgamer and Ohad Trabelsi  “Subcubic algorithms for Gomory–Hu tree in unweighted graphs”  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , 2021, pp. 1725–1737
  * [AP09] Reid Andersen and Yuval Peres  “Finding Sparse Cuts Locally Using Evolving Sets”  In _Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing_ , STOC ’09  Bethesda, MD, USA: ACM, 2009, pp. 235–244  DOI: 10.1145/1536414.1536449
  * [ARV09] Sanjeev Arora, Satish Rao and Umesh V. Vazirani  “Expander flows, geometric embeddings and graph partitioning” Announced at STOC’04  In _J. ACM_ 56.2, 2009, pp. 5:1–5:37
  * [BGS21] Aaron Bernstein, Maximilian Probst Gutenberg and Thatchaphol Saranurak  “Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time”  In _arXiv preprint arXiv:2101.07149_ , 2021
  * [CGLNPS20] 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 _2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)_ , 2020, pp. 1158–1167  IEEE
  * [Chu21] Julia Chuzhoy  “Decremental all-pairs shortest paths in deterministic near-linear time”  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , 2021, pp. 626–639
  * [CKLPGS22] Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg and Sushant Sachdeva  “Maximum flow and minimum-cost flow in almost-linear time”  In _Accepted to FOCS’2022_ , 2022
  * [Fle00] Lisa K Fleischer  “Approximating fractional multicommodity flow independent of the number of commodities”  In _SIAM Journal on Discrete Mathematics_ 13.4 SIAM, 2000, pp. 505–520
  * [GG81] Ofer Gabber and Zvi Galil  “Explicit constructions of linear-sized superconcentrators”  In _Journal of Computer and System Sciences_ 22.3 Academic Press, 1981, pp. 407–420
  * [GK07] Naveen Garg and Jochen Könemann  “Faster and simpler algorithms for multicommodity flow and other fractional packing problems”  In _SIAM Journal on Computing_ 37.2 SIAM, 2007, pp. 630–652
  * [KRV09] Rohit Khandekar, Satish Rao and Umesh V. Vazirani  “Graph partitioning using single commodity flows”  In _J. ACM_ 56.4, 2009, pp. 19:1–19:15
  * [KT18] Ken-ichi Kawarabayashi and Mikkel Thorup  “Deterministic edge connectivity in near-linear time”  In _Journal of the ACM (JACM)_ 66.1 ACM New York, NY, USA, 2018, pp. 1–50
  * [LP20] Jason Li and Debmalya Panigrahi  “Deterministic min-cut in poly-logarithmic max-flows”  In _2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)_ , 2020, pp. 85–92  IEEE
  * [LR99] Tom Leighton and Satish Rao  “Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms”  In _J. ACM_ 46.6 New York, NY, USA: Association for Computing Machinery, 1999, pp. 787–832  DOI: 10.1145/331524.331526
  * [LS21] Jason Li and Thatchaphol Saranurak  “Deterministic weighted expander decomposition in almost-linear time”  In _arXiv preprint arXiv:2106.01567_ , 2021
  * [OSV12] L. Orecchia, S. Sachdeva and N.. Vishnoi  “Approximating the exponential, the lanczos method and an $\tilde{O}(m)$-time spectral algorithm for balanced separator.”  In _STOC_ , 2012
  * [OSVV08] Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani and Nisheeth K. Vishnoi  “On partitioning graphs via single commodity flows”  In _Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008_ ACM, 2008, pp. 461–470  DOI: 10.1145/1374376.1374442
  * [OV11] Lorenzo Orecchia and Nisheeth K. Vishnoi  “Towards an SDP-based approach to spectral methods: a nearly-linear-time algorithm for graph partitioning and decomposition”  In _Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms_ San Francisco, California: SIAM, 2011, pp. 532–545  URL: http://dl.acm.org/citation.cfm?id=2133036.2133078
  * [PST95] Serge A Plotkin, David B Shmoys and Éva Tardos  “Fast approximation algorithms for fractional packing and covering problems”  In _Mathematics of Operations Research_ 20.2 INFORMS, 1995, pp. 257–301
  * [RST12] Prasad Raghavendra, David Steurer and Madhur Tulsiani  “Reductions between Expansion Problems”  In _2012 IEEE 27th Conference on Computational Complexity_ , 2012, pp. 64–73  DOI: 10.1109/CCC.2012.43
  * [She09] Jonah Sherman  “Breaking the Multicommodity Flow Barrier for O(vlog n)-Approximations to Sparsest Cut”  In _FOCS_ IEEE Computer Society, 2009, pp. 363–372
  * [Shm97] David B Shmoys  “Cut problems and their application to divide-and-conquer”  In _Approximation algorithms for NP-hard problems_ , 1997, pp. 192–235
  * [SM00] Jianbo Shi and Jitendra Malik  “Normalized cuts and image segmentation”  In _IEEE Transactions on pattern analysis and machine intelligence_ 22.8 Ieee, 2000, pp. 888–905
  * [ST04] Daniel A Spielman and Shang-Hua Teng  “Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems”  In _Proceedings of the thirty-sixth annual ACM symposium on Theory of computing_ , 2004, pp. 81–90
  * [SW19] Thatchaphol Saranurak and Di Wang  “Expander Decomposition and Pruning: Faster, Stronger, and Simpler”  In _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019,_ , SODA ’19, 2019
  * [You95] Neal E. Young  “Randomized Rounding without Solving the Linear Program”  In _Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’95  San Francisco, California, USA: Society for IndustrialApplied Mathematics, 1995, pp. 170–178

##  Appendix A Reducing Conductance to Sparsity

Here, we prove Theorem 2.1. The proof is an adaption of Lemma 5.4 and Theorem
5.5 of [CGLNPS20].

#### The Transformation Algorithm.

Our algorithm is essentially a wrapper function around our main result Theorem
4.1. That is, we first construct a bounded degree graph $\widehat{G}$ from
$G$, then run the algorithm from Theorem 4.1 on $\widehat{G}$. If the
algorithm certifies that $\widehat{G}$ has no balanced sparse cuts, we prove
that $G$ has no balanced low-conductance cuts. Otherwise, if the algorithm
returns a sparse cut in $\widehat{G},$ we recover a balanced low-conductance
cut in $G.$

We first describe the construction of $\widehat{G}$ given $G=(V,E)$. Let us
assume an arbitrary ordering of the edges incident to each vertex $v\in V$.
$\widehat{G}=(\widehat{V},\widehat{E})$ is constructed as follows:

  1. 1.

For each vertex $v\in V$, create a set of vertices
$X_{v}=\\{v_{1},v_{2},\ldots,v_{\deg(v)}\\}$, and an $\psi_{0}$-expander
$H_{v}$ on $X_{v}$ using Theorem 3.1. Add $H_{v}$ to $\widehat{G}.$

  2. 2.

For each edge $e=(u,v)\in E$, we add $(u_{i},v_{j})$ to $\widehat{E}$ if $e$
is the $i^{th}$ (and $j^{th}$) edge incident to $u$ (and $v$, respectively).

Clearly, $\widehat{G}$ has ${{\textsf{vol}}}(G)=2m$ vertices and each vertex
has at most $10$ incident edges, $9$ from the expander and $1$ from the
corresponding edge in $G$.

We now run the algorithm from our main result, Theorem 4.1, on the graph
$\widehat{G}$. If the algorithm certifies that no $b$-balanced $\psi$-sparse
cut exists in $\widehat{G},$ we return the same result for $G$. Otherwise, we
run Algorithm 3 on the returned cut $(A,\overline{A})$ in $\widehat{G}$ to
obtain a $\Omega(b)$-balanced $\Omega(\psi)$-sparse cut $(S,\overline{S})$ in
$G$. It is straight-forward to check that Algorithm 3 is deterministic and
runs in time linear in the number of edges of $G$ and thus the runtimes stated
in Theorem 4.1 are asymptotically not affected.

return $S=\left\\{u\in V~{}\middle|~{}\left|X_{u}\cap
A\right|\geq\left|X_{u}\setminus A\right|\right\\}$.

fAlgorithm 3 $\textsc{Transform}(G,\widehat{G},A\subseteq V(\widehat{G}))$

#### Certifying $G$.

We start by showing that if no $\Omega(b)$-balanced $O(\psi)$-sparse cut is
found on $\widehat{G}$, then no such cut exists in $G$ either.

######  Lemma A.1.

Given a balance parameter $b\in(0,1/4)$, if every cut $(X,\overline{X})$ in
$\widehat{G}$ with $\left|X\right|,\left|\overline{X}\right|\geq
b\cdot|V(\widehat{G})|$ has $\Psi_{\widehat{G}}(S)\geq\psi$, then every cut
$(S,\overline{S})$ in $G$ with
${{\textsf{vol}}}_{G}(S),{{\textsf{vol}}}_{G}(\overline{S})\geq
b\cdot{{\textsf{vol}}}(G)$ has $\Phi_{G}(X)\geq\psi$.

###### Proof.

Let $(S,\overline{S})$ be any cut in $G$ with
${{\textsf{vol}}}_{G}(S),{{\textsf{vol}}}_{G}(\overline{S})\geq
b\cdot{{\textsf{vol}}}(G)$. Define $X_{S}=\cup_{u\in S}X_{u}$ and
$\overline{X_{S}}=\cup_{u\not\in S}X_{u}=X_{\overline{S}}.$ Observe that
$|E_{G}(S,\overline{S})|=|E_{\widehat{G}}(X_{S},\overline{X_{S}})|$ because
the $\psi_{0}$-expander edges in $\widehat{G}$ do not appear in the cut and
every cut edge $(u_{i},v_{j})$ in $\widehat{G}$ corresponds to the cut edge
$(u,v)\in G.$

By construction of $\widehat{G}$, we have that
$|X_{S}|={{\textsf{vol}}}_{G}(S)$ and
$|\overline{X_{S}}|={{\textsf{vol}}}_{G}(\overline{S})$ and therefore
$|X_{S}|,|\overline{X_{S}}|\geq b\cdot{{\textsf{vol}}}(G)=b|V(\widehat{G})|$
by assumption on $(S,\overline{S})$. Thus $(X_{S},\overline{X_{S}})$ is
balanced in $\widehat{G}$ and we can use the guarantee that
$\Phi_{\widehat{G}}(X_{S})\geq\psi$. This yields

$\displaystyle|E_{G}(S,\overline{S})|=|E_{\widehat{G}}(X_{S},\overline{X_{S}})|\geq\psi\cdot\min\\{\left|X_{S}\right|,\left|\overline{X_{S}}\right|\\}=\psi\cdot\min\\{{{\textsf{vol}}}(S),{{\textsf{vol}}}(\overline{S})\\}.$

∎

#### Returning a Sparse Cut.

It remains to prove that the above algorithm transforms any balanced sparse
cut in $\widehat{G}$ to a balanced low conductance cut in $G.$ We prove this
claim in two steps. We first show that the number of edges in the cut
$(S,\overline{S})$ in $G$ is comparable to the number of edges in
$(A,\overline{A})$ in $\widehat{G}$.

######  Claim A.2.

$|E_{G}(S,\overline{S})|=O\left(\left|E_{\widehat{G}}(A,\overline{A})\right|\right)$.

###### Proof.

Define $X_{S}=\cup_{u\in S}X_{u}$. Consider any vertex $u\in V$, we have that
the graph $H_{u}$ contributes at least $\psi_{0}\cdot\min\\{|X_{u}\cap
A|,|X_{u}\setminus A|\\}$ edges to the cut
$\left|E_{\widehat{G}}(A,\overline{A})\right|$. But in $\widehat{G}$, the
number of edges incident to $X_{u}$ that are in the cut $(S,\overline{S})$ but
where previously not in the cut $(A,\overline{A})$ can be at most
$\min\\{|X_{u}\cap A|,|X_{u}\setminus A|\\}$ since $H_{u}$ is contained
entirely in $S$ or $\overline{S}$ and only one additional edge is incident to
each vertex in $X_{u}$.

Thus, we can charge each edge in $E_{H_{u}}(A,\overline{A})$ with at most
$1/\psi_{0}$ edges from $E_{\widehat{G}}(S,\overline{S})\setminus
E_{\widehat{G}}(A,\overline{A})$ incident on $u$ and cover all such edges. We
conclude that
$|E_{\widehat{G}}(S,\overline{S})|\leq|E_{\widehat{G}}(A,\overline{A})|+|E_{\widehat{G}}(A,\overline{A})|/\psi_{0}$,
and finally use that
$|E_{G}(S,\overline{S})|=|E_{\widehat{G}}(X_{S},\overline{X_{S}})|$ as
observed in Lemma A.1. ∎

Next, we prove that $(S,\overline{S})$ is a balanced cut.

######  Claim A.3.

If $\Psi_{G}(A)\leq\psi_{0}/2$, we have
${{\textsf{vol}}}_{G}(S)\geq\frac{1}{2}|A|$ and
${{\textsf{vol}}}_{G}(\overline{S})\geq\frac{1}{2}|\overline{A}|$.

###### Proof.

We prove ${{\textsf{vol}}}_{G}(S)\geq\frac{1}{2}|A|$ (the proof of
${{\textsf{vol}}}_{G}(\overline{S})\geq\frac{1}{2}|\overline{A}|$ is
symmetric). Let us assume for the sake of contradiction that
${{\textsf{vol}}}_{G}(S)<\frac{1}{2}|A|$. We argued before that for every
$u\in V$, we have $|E_{H_{u}}(A,\overline{A})|\geq\psi_{0}\cdot\min\\{|A\cap
X_{u}|,|A\setminus X_{u}|\\}$. We again define $X_{S}=\cup_{u\in S}X_{u}$ and
observe that the fact that $\sum_{u\in S}|A\cap
X_{u}|\leq|X_{S}|={{\textsf{vol}}}_{G}(S)<\frac{1}{2}|A|$ implies that
$\sum_{u\in S}|A\setminus X_{u}|\geq|A|-|X_{S}|>\frac{1}{2}|A|$. Definition of
$S$ also yields that $|A\setminus X_{u}|\leq|A\cap X_{u}|.$

Combining insights, we conclude

$|E_{\widehat{G}}(A,\overline{A})|\geq\sum_{u}|E_{H_{u}}(A,\overline{A})|\geq\sum_{u}\psi_{0}\cdot\min\\{|A\cap
X_{u}|,|A\setminus X_{u}|\\}\geq\sum_{u\in S}\psi_{0}\cdot|A\setminus
X_{u}|>\frac{\psi_{0}}{2}|A|$

which implies that $\Psi_{G}(A)>\psi_{0}/2$ which contradicts our assumption,
as desired. ∎

Finally, we combine our insights to prove Theorem 2.1.

###### Proof of Theorem 2.1..

We have from the algorithm that $|A|,|\overline{A}|\geq
b\cdot|V(\widehat{G})|=2bm$. Therefore, by A.3, we produce a cut
$(S,\overline{S})$ in $G$ with
${{\textsf{vol}}}_{G}(S),{{\textsf{vol}}}_{G}(\overline{S})\geq
b/2\cdot{{\textsf{vol}}}(G)$. By A.2, we further have that
$|E_{G}(S,\overline{S})|\leq O(\left|E_{\widehat{G}}(A,\overline{A})\right|)$
and therefore
$\Phi_{G}(S)=\frac{|E_{G}(S,\overline{S})|}{{{\textsf{vol}}}_{G}(S),{{\textsf{vol}}}_{G}(\overline{S})}=O\left(\frac{\left|E_{\widehat{G}}(A,\overline{A})\right|}{\min\\{|A|,|\overline{A}|\\}}\right)=O(\phi)$
where the last equality stems from the fact that $(A,\overline{A})$ had
$\Psi_{\widehat{G}}(A)\leq\phi$ by Theorem 4.1. ∎

##  Appendix B The Constant-Degree Assumption

In this section, we prove that the following assumptions are without loss of
generality.

######  Assumption B.1.

When computing a sparse cut with respect to sparsity, we may assume at a cost
of a constant factor in the output quality that the input graph $G$ has
maximum degree 10.

###### Proof.

Consider obtaining the graph $\widehat{G}$ from $G$ by adding $\lceil
m/n\rceil$ self-loops to each vertex in $G$. We then invoke Theorem 2.1 on
$\widehat{G}$ with $\psi$ and parameter $b$.

Note first that in a connected graph $G$, we have that $\widehat{G}\leq 4m$.
Further, note that since self-loops do not appear in cuts, we have
$E_{G}(S,\overline{S})=E_{\widehat{G}}(S,\overline{S})$ for all $S$.

Now, if the algorithm certifies low conductance of $\widehat{G}$, we have for
each $(S,\overline{S})$ in $G$ where $|S|,|\overline{S}|\geq 4b\cdot n$ that
${{\textsf{vol}}}_{\widehat{G}}(S)\geq|S|\lceil m/n\rceil\geq 4bm\geq
b\cdot{{\textsf{vol}}}(\widehat{G})$. Since
$|E_{G}(S,\overline{S})|=|E_{\widehat{G}}(S,\overline{S})|\geq\psi\min\\{{{\textsf{vol}}}_{\widehat{G}}(S),{{\textsf{vol}}}_{\widehat{G}}(\overline{S})\\}\geq\frac{1}{3}\psi\min\\{|S|,|\overline{S}|\\}$.
Thus every $4b$-balanced sparse cut has sparsity at least $\frac{1}{3}\psi$.
Otherwise, the algorithm returns a cut $(S,\overline{S})$ of conductance at
most $\phi$ in $\widehat{G}$. But, we have
$\Phi_{\widehat{G}}(S)\geq\Psi_{\widehat{G}}(S)=\Psi_{G}(S)$ for all $S$. ∎

##  Appendix C A Simple Randomized Algorithm to Construct Low-Degree Expanders

1Construct an empty graph $H$ on $n$ vertices.

2 foreach  _$v\in V(H)$_ do

3 for  _$i=1,2,\ldots,k=80\log n$_ do

4 Sample a vertex $u$ from $V(H)$ uniformely and i.i.d. at random.

5 Add edge $(u,v)$ to $H$.

6

return $H$

fAlgorithm 4 $\textsc{RandConstDegExpander}(n)$

#### The Algorithm.

Here, we provide Algorithm 4 which implements the algorithm mentioned in
Remark 3.2.

#### Analysis.

Before we start our analysis, we recall the following Chernoff bound.

######  Theorem C.1.

Given i.i.d. $\\{0,1\\}$-random variables $X_{1},X_{2},\ldots,X_{k}$,
$X=\sum_{i}X_{i}$ and any $\delta\geq 0$, we have
$P[X\geq(1+\delta)\mathbb{E}[X]]\leq
e^{-\frac{\delta^{2}\mathbb{E}[X]}{(2+\delta)}}$ and
$P[X\leq(1-\delta)\mathbb{E}[X]]\leq e^{-\frac{\delta^{2}\mathbb{E}[X]}{2}}$.

Let us first prove that $H$ has bounded degree.

######  Claim C.2.

Algorithm 4 returns $H$ such that w.h.p., the maximum degree is $O(\log n)$.

###### Proof.

Each vertex $u$ is selected as the second endpoint of an edge added to $H$ in
the inner for-loop with probability $1/n$ per iteration. As there are $nk$
iterations of this for-loop, and each iteration is independent, we have by the
Chernoff bound that each vertex $u$ is at most $k$ times selected with
probability at least $1-e^{-\frac{4k}{4}}=1-e^{-k}=1-n^{-32}$.

Since each vertex $u$ has degree equal to $k$ plus the number of times it is
sampled, we have that its degree is at most $2k$ with probability at most
$1-n^{-32}$. We obtain our result over all vertices in $H$ by applying a union
bound. ∎

######  Claim C.3.

Algorithm 4 returns a $\Omega(\log n)$-expander $H$ w.h.p.

###### Proof.

Consider any set $S$ with $|S|\leq n/2$. Then, we have that
$\mathbb{E}[E_{H}(S,\overline{S})]\geq\frac{1}{2}|S|k$ since each edge $(u,v)$
sampled when the foreach-loop iterates over a vertex $v\in S$ has $u\not\in S$
with probability at least $\frac{1}{2}$ and there are $|S|k$ such sampling
events. Since they are independent, we further have from the Chernoff bound
that $P[|E_{H}(S,\overline{S})|\leq\frac{1}{4}|S|k]\leq
e^{-\frac{|S|k}{16}}=n^{-5|S|}$. It is clear that if
$|E_{H}(S,\overline{S})|>\frac{1}{4}|S|k$ then
$\Psi_{H}(S)\geq\frac{k}{4}=\Omega(\log n)$.

The remaining difficulty is that there are an exponential number of cuts so a
union bound seems at first hard to apply. However, we observe that there are
at most ${\alpha\choose n}\leq\left(\frac{ne}{\alpha}\right)^{\alpha}\leq
n^{3\alpha}$ for $\alpha\geq 1$ cuts where the smaller half contains $\alpha$
vertices. As we have proven that a cut is $\psi$-sparse with probability at
most $n^{-5\alpha}$, we can thus conclude by a simple union bound argument
that $H$ is not $\Omega(\log n)$-expander with probability at most
$\sum_{\alpha\geq 1}{\alpha\choose n}\cdot n^{-5\alpha}\leq 1/n$. ∎