# Deterministic Near-Linear Time Minimum Cut in Weighted Graphs

Monika Henzinger  Institute of Science and Technology Austria (ISTA),
Klosterneuburg, Austria. See funding information in the acknowledgement
section. email<EMAIL_ADDRESS>Jason Li Simons Institute, UC
Berkeley. email<EMAIL_ADDRESS>Satish Rao UC Berkeley. email:
<EMAIL_ADDRESS>Di Wang Google Research. email<EMAIL_ADDRESS>
###### Abstract

In 1996, Karger [Kar96] gave a startling randomized algorithm that finds a
minimum-cut in a (weighted) graph in time $O(m\log^{3}n)$ which he termed
near-linear time meaning linear (in the size of the input) times a
polylogarthmic factor. In this paper, we give the first deterministic
algorithm which runs in near-linear time for weighted graphs.

Previously, the breakthrough results of Kawarabayashi and Thorup [KT19] gave a
near-linear time algorithm for simple graphs (which was improved to have
running time $O(m\log^{2}n\log\log n)$ in [HRW20].) The main technique here is
a clustering procedure that perfectly preserves minimum cuts. Recently, Li
[Li21] gave an $m^{1+o(1)}$ deterministic minimum-cut algorithm for weighted
graphs; this form of running time has been termed “almost-linear”. Li uses
almost-linear time deterministic expander decompositions which do not
perfectly preserve minimum cuts, but he can use these clusterings to, in a
sense, “derandomize” the methods of Karger.

In terms of techniques, we provide a structural theorem that says there exists
a sparse clustering that preserves minimum cuts in a weighted graph with
$o(1)$ error. In addition, we construct it deterministically in near linear
time. This was done exactly for simple graphs in [KT19, HRW20] and with
polylogarithmic error for weighted graphs in [Li21]. Extending the techniques
in [KT19, HRW20] to weighted graphs presents significant challenges, and
moreover, the algorithm can only polylogarithmically approximately preserve
minimum cuts. A remaining challenge is to reduce the polylogarithmic-
approximate clusterings to $1+o(1/\log n)$-approximate so that they can be
applied recursively as in [Li21] over $O(\log n)$ many levels. This is an
additional challenge that requires building on properties of tree-packings in
the presence of a wide range of edge weights to, for example, find sources for
local flow computations which identify minimum cuts that cross clusters.

##  1 Introduction

The minimum cut problem of finding the partition in a graph with $n$ nodes and
$m$ edges which minimizes the number (or weight) of edges between the parts
has a long history and many applications. Algorithms were initially derived
from algorithms for the minimum $s-t$ cut problem, which finds a partition
that separates $s$ and $t$ and minimizes the edge number or weight between the
pieces; here one can simply use $n-1$ instances of the minimum $s-t$ cut to
find a minimum cut. It is interesting to remind the reader that the minimum
$s-t$ cut problem has as a dual, the maximum $s-t$ flow problem, whose flow
value equals the minimum cut value, and algorithms are inextricably linked for
both.

For minimum cut itself, a directed version of a dual was developed in 1962 by
Nash-Williams [NW61], who showed that a packing of arborescences could be
found in a directed graph whose size is equal to the size of a related cut.
This packing figures in modern algorithms. In particular, the packing
algorithm of Gabow [Gab95] makes this duality algorithmically effective. We
also use it in our algorithm. Approximate versions using the multiplicative
weights methods [PST95] of these ideas are directly useful in our work.

A linear-time deterministic method for producing a “sparse” graph with
$O(\lambda n)$ edges that preserves all minimum cuts for a graph with minimum
cut size $\lambda$ was given by Nagamochi and Ibaraki [NI92]. Another
structural breakthrough was given by Karger [KAR93] who showed that the
remarkably simple randomized algorithm of repeatedly choosing a random edge to
collapse, returns a minimum cut with probability $1/n^{2}$. This yields a
proof that the number of minimum cuts is at most $O(n^{2})$ which is matched
by the number of minimum cuts on a simple cycle. The method can also be used
to bound the number of near-minimum cuts. This led to a sequence of randomized
algorithms [KS96, BK96, Kar00] with improved running times over the
deterministic maximum-flow based approaches.

Furthermore, Karger [Kar00] gave a randomized algorithm that ran in time
$O(m\log^{3}n)$, which yielded a minimum cut with high probability. The
algorithm makes use of the structural insights on the number of cuts in a
graph, on tree packings, and on analyzing sampling methods to yield a weighted
graph with few edges that almost preserved all minimum cuts. This, along with
a packing of trees and a clever dynamic program yielded Karger’s bounds.

For deterministic algorithms, the state of the art remained largely tied to
maximum flow based methods until the breakthrough work of Kawarabayashi and
Thorup [KT19] who developed graph decomposition techniques to give a
$\tilde{O}(m)$ deterministic algorithm for simple graphs, which was improved
by Henzinger, Rao, and Wang [HRW20] to $O(m\log^{2}n\log\log n)$111While the
running time is better than Karger’s randomized algorithm, subsequent work has
provided an $O(m\log^{2}n)$ time randomized algorithm for minimum cut in
simple graphs [GMW20].. Interestingly, the decomposition method’s closest
progenitor was perhaps the work of Spielman and Teng [ST04] who gave
randomized near-linear time algorithms for solving linear systems. Moreover,
these graph decomposition methods are a central ingredient in the recent
randomized almost-linear time algorithms for maximum flow [CKL+22]. We note
that a central tool in [KT19] was the page-rank algorithm which was replaced
by local flow algorithms in [HRW20]. The usefulness of decompositions in both
randomized and deterministic settings is notable.

The main weakness of the method of [KT19, HRW20] is that it is limited to
simple graphs due to several issues, one of which is the fact that any minimum
cut of size $\lambda$ must consist of either a single vertex or must have at
least $\lambda$ vertices. When $\lambda$ is large222When $\lambda$ is small,
the minimum cut can be found using [Gab95]., this allows the decomposition
procedure of [KT19, HRW20] to find clusterings which are “perfect” in the
sense that they don’t “cross” any cut whose size is close to a minimum cuts.
This is one of several obstacles that we must overcome.

Li [Li21] produced an $m^{1+o(1)}$ deterministic algorithm for weighted graphs
using deterministic constructions of expander decompositions [LS21, CGL+20]
to, in a sense, derandomize Karger’s [Kar00] approach to minimum cut. His
approach is limited by both the time for constructing hierarchical expander
decompositions and the “inefficiency” (relative to [KT19]) of the resulting
decompositions, in the sense that the minimum cut in the corresponding
collapsed graph might be a factor of $\Omega(\log n)$ larger per level in the
hierarchical decomposition than the minimum cut. This leads to a super-
polylogarithmic multiplicative factor in the size of the minimum cut over all
levels. Fortunately, through the framework of Karger’s randomized algorithm,
this multiplicative approximation can be paid for in the running time to
compute a so-called _skeleton graph_ , from which an exact minimum cut can be
computed.

In this paper, we give an $\tilde{O}(m)$ deterministic algorithm for minimum
cut. While we combine the approaches in [Li21] and those in [KT19, HRW20], we
have to address a number of issues in each by devising more efficient
algorithms for weighted graphs as well as deal with the more complicated
structure of minimum cuts in weighted graphs as compared to simple graphs.

Of independent interest, we provide a structural theorem that there exists a
sparse clustering, i.e., a partition of the vertices into set such that there
are few edges between the sets, that preserves minimum cuts in weighted graphs
with $1/\operatorname{polylog}(n)$ multiplicative error. This extends the
theorem of [KT19] which gives a perfect clustering for simple graphs and the
theorem of [Li21] which gives a clustering with a logarithmic error.

###  1.1 Our techniques and related work

We discuss in more detail some of the techniques that we build upon along with
a description of our contributions.

A classical result of Nash and Williams [NW61] showed that any graph $G$ with
minimum cut $\lambda$ contains a packing of $\lambda$ arborescences (directed
trees) in the directed graph where each edge in $G$ is replaced by an edge in
each direction. Gabow [Gab95] provided an efficient $\tilde{O}(\lambda m)$
algorithm that produced the packing. There are randomized approximation
algorithms that produce fractional and approximate packings as well [PST95].

As noted previously, in 1996, Karger’s famous paper [Kar96] gave an
$O(m\log^{3}n)$ randomized min-cut algorithm that takes a graph $G$ and
produces a weighted graph with $O(n\log n)$ edges where the minimum cuts are
preserved to within a $(1+\epsilon)$ factor.333This work is inspired by a
sequence of previous papers on randomized approaches that remained far from
near linear time. [KS96, BK96, BK15]. Then Karger builds a tree packing using
[Gab95] in that weighted graph that consists of $O(\log n)$ trees. In such a
tree packing, there must be a tree which intersects the minimum-cut at most
twice, and Karger provides an efficient dynamic programming algorithm that
given that tree produces a minimum cut.

Karger produces the sparse graph by sampling edges inversely to their
“strength”, a measure of the connectivity of the endpoints, in a manner that
preserves all small cuts and yields a sparse graph. Specifically, the sampling
introduces an edge of weight $1/p$ if an edge is sampled with probability $p$,
which preserves the edge on expectation, and sampling by strength preserves
all cuts with high probability, which can be argued using the bounds on the
number of minimum-cuts and near minimum-cuts as follows from [KS96]. This
sampling procedure was very much randomized and an efficient deterministic
construction has remained elusive. We note that Karger’s algorithm works
naturally for weighted graphs.

The deterministic algorithms for simple graphs in [KT19, HRW20] instead
generate a sparse graph that preserves all non-trivial minimum cuts 444A
trivial cut consists of just one vertex. by producing a hierarchical
clustering. At each level, a set of clusters is produced such that no non-
trivial minimum-cut separates any cluster and has few intercluster edges.
Thus, collapsing the graph and recursing ensures that all non-trivial minimum
cuts are preserved. The collapsing can be repeated until the graph has
$m^{\prime}=\tilde{O}(m/\delta)$ edges, where $\delta$ is the minimum degree,
and then simply run Gabow’s algorithm [Gab95] to find a minimum cut in
$\tilde{O}(\lambda\cdot m/\delta)=\tilde{O}(m)$ time.

An example is useful here. First, note that a simple cycle is “easy” in the
sense that it is sparse and one can simply run Gabow [Gab95] in linear time.
Replacing each vertex with a clique on $\delta$ vertices and connecting
adjacent cliques along the cycle with matchings produces a “dense” graph with
minimum degree $\delta+1$ and minimum cut size $\delta$. Note that the cliques
are not split by any non-trivial minimum cut. The algorithms in [KT19, HRW20]
produce a final graph such that each node is created by collapsing a clique.
The number of edges, including parallel edges, in the collapsed graph is
$O(m/\delta)$ and this graph contains all non-trivial minimum cuts in the
original graph. Note that each collapsed graph induces a vertex clustering or
partition, where each node in the collapsed graph induces a _piece_ in the
partition. Inspired by this example, we say a vertex clustering is _non-
crossing_ if there exists a minimum cut that does not cut any of the pieces.
Thus, the algorithms in [KT19, HRW20] produce a non-crossing vertex
clustering.

To proceed it is useful to provide a little more detail. The algorithms of
[KT19, HRW20] produce the non-crossing clusterings _incrementally_. That is,
their algorithm begins with a partition where any minimum cut only overlaps
(i.e., crosses) any piece by some volume $s$, which is initially $m/2$, and
then proceeds to iteratively refine that clustering, in each iteration
decreasing $s$ by a factor of $2$. Once $s$ is smaller than $\Theta(\delta)$,
where $\delta$ is the minimum vertex degree, they clean up the resulting
partition to obtain the property that a non-trivial minimum cut does not cross
any of the resulting clusters at all. This last step of obtaining a non-
crossing clustering relies crucially on a local expansion property of simple
graphs: that any minimum cut in a simple graph consists of either a single
vertex or at least $\delta$ vertices and, thus, any non-trivial minimum-cut is
extremely sparse for simple graphs. However, this does not hold for weighted
graphs: In a weighted graph a non-trivial minimum cut can contain just two
vertices for arbitrary values of $\delta$.

Moreover, the recursive techniques face substantial issues for weighted graphs
in terms of complexity. The refinement process in [HRW20] performs local flow
computations where the progress is proportional to the total weight of the
edges that are touched. In simple graphs, the weight and the number of edges
are the same and, thus, the total work is near-linear in the number of edges.
For weighted graphs, the number of edges and the total weight differ and we,
thus, need to devise new algorithms for the refinement process. Another issue
in the refinement process is the allocation of sources for the local flows,
which also is more complex as weighted graphs do not “expand” with respect to
weights as fast as simple graphs expand with respect to degrees. E.g., a
degree $\delta$ simple graph has $\delta$-neighbors, where a vertex of
weighted degree of $\delta$ may have only a single neighbor. This is
problematic for the local flow computation.

This expansion issue creates an even bigger obstruction for going from
“almost” non-crossing as defined by $s$ to completely non-crossing. This
barrier remains and we do not produce a clustering such that every cluster is
non-crossing in this work.

Fortunately, Li [Li21] provides an ingenious approach for utilizing
“approximately non-crossing” clusterings to derandomize the sampling approach
of Karger [KS96]. He first shows how to use expander decompositions to produce
approximately non-crossing clusterings555The technical definitions of
approximately non-crossing are a bit different than those in [KT19, HRW20] and
here, but are similar in consequence., the deterministic constructions of
which take $m^{1+o(1)}$ time. He introduced another measure of non-crossing of
cuts for the partition in addition to the volume $s$ of overlap. In
particular, his clusterings ensuring that making a cut consistent with a
clustering would only increase the size of the cut by a multiplicative
$n^{o(1)}$ factor. The idea is to “shift” the cut by adding or removing a
small set of vertices across the cut. This is what he calls _uncrossing_ a
cut. This is how he produces a hierarchical clustering where every minimum cut
is well approximated by an arithmetic expression using a small linear number
of the clusters in the hierarchy.

He argued further that sampling a subset of edges that approximately preserves
the boundary size of the near-linear number of clusters would then preserve
approximately the minimum cuts as well. This contrasts with Karger’s sampling
which argued about an exponential number of cuts. The linear number of cuts
allows one to derandomize the sampling as one can explicitly track whether all
the cuts are properly represented as one chooses edges to include in the
sample. One method to sample edges is to satisfy a weighted sum of the near-
linear number of cuts using a multiplicative weights method to ensure that all
cuts are properly represented. This method was introduced in [Rag88].

The obstruction for Li [Li21] to obtaining a $\tilde{O}(m)$ running time is
both in the use of the expander decomposition and the fact that even a
constant multiplicative factor increase in boundary size, much less a
polylogarithmic, induced by uncrossing cuts limits the number of recursive
levels to a constant. Indeed, a recursion of depth $k=O(\log n)$ would give a
disastrous $\log n^{O(\log n)}$ multiplicative increase in the size of the
minimum cut, while fewer recursive levels are insufficient to sufficiently
sparsify the graph. We note that the use of expander decompositions requires
at least a $\Omega(\log n)$ multiplicative increase of the cut size per level
of the recursion without a fundamental new understanding of finding sparsest
cuts.

We address these problems by using a modified version of the techniques from
[KT19, HRW20] which runs faster and is better in that the uncrossing of
minimum cuts only introduces an error of $(1+\epsilon)$ at each level where
$\epsilon=1/\operatorname{polylog}(n)$. Thus, a subset of the edges (sampled
deterministically as sketched above) that approximates the cuts in the
resulting decomposition yields an accurate representation of all minimum cuts.

As before, we produce these clusterings by first recursively reducing the
overlap, $s$, of any minimum cut to have weighted volume $\tilde{O}(\lambda)$.
Producing clustering with overlap of $s$ needs modification, as does
understanding the cost of uncrossing at the detail level. The recursion needs
significant changes due to the running time analysis having to depend on the
number of edges rather than their weight as mentioned above. At this point,
cuts that do not cross any of the clusters can increase the size of the
minimum cut by a polylogarithmic factor.

We then need to refine these clusters so that the size of the minimum cut
increases only by a $(1+\epsilon)$ factor. To do so, we appeal to several
structural properties of minimum cuts to deal with a spectrum of edge weights.
For “small” clusters (with a polylogarithmic number of vertices), we can use
bounds on the number of minimum cuts along with our flow procedures to produce
a better clustering and charging arguments like those in [KT19, HRW20]. For
large clusters, we have the property that minimum cuts do not overlap them
very much which implies that overlapping minimum cuts contains edges which
have large weights. This allows us to pack few forests into these large weight
edges which, in turn, allows us to appropriately select small sets of sources
for the local flow procedures that find problematic overlapping minimum cuts.
In the end, we prune off overlapping small cuts from a large cluster until the
large cluster is certified to have no bad overlapping mininum cuts. We note
that the localized flow methods are similar to those used in randomized
constructions of expander decompositions [SW19] in addition to those in
[HRW20].

##  2 Preliminaries

We are given an undirected, weighted graph $G=(V,E,w)$. Let $\lambda$ be the
minimum cut in $G$ and let $W$ be the sum of the weights of all edges. We
assume that $W$ is polynomial in $n$. If this is not the case, the stated
running time increases by a factor of $O(\log W)$. We use _component_ to
denote a connected component of $G\setminus E^{\prime}$ for some
$E^{\prime}\subseteq E$. Given a component $C$ we use $\partial C$ to denote
the set of edges called _boundary edges_ with exactly one endpoint in $C$.

##### Weights.

Given two non-overlapping vertex sets $A,B$, we use $w_{G}(A,B)$ (or $w(A,B)$
if the graph we refer to clear from the text) to denote the sum of the weight
of the edges between $A$ and $B$ and we use $w_{G}(A)$ (or $w(A)$) to denote
the sum of the weighted edge degrees of all vertices in $A$. Furthermore, we
adapt the notations to weighted graphs by explicitly using superscript $W$ to
denote the weighted quantities, e.g. $d(v)$ is the number of edges incident to
$v$, $d^{W}(v)$ is the total weight of edges incident to $v$, while
${\hbox{\bf vol}}(V)=\sum_{v\in V}d(v)$, ${\hbox{\bf vol}}^{W}(V)=\sum_{v\in
V}d^{W}(v)$ for any vertex set $V$.

##### Subgraphs.

We use $G[A]$ to denote the subgraph of $G$ induced by the vertices in $A$,
while $G\\{A\\}$ denotes the graph $G[A]$ together with, for every node $u\in
A$ with $w_{G}(u,G\setminus A)>0$, an added self-loop of $u$ with weight
$w_{G}(u,G\setminus A)$. We will use the subgraph $G\\{A\\}$ by default when
we work on a component $A$, and the self-loops make $d^{W}(v)$ the same in
$G\\{A\\}$ as in $G$ for all $v\in A$, so there is no ambiguity when we talk
about the weighted degree or volume in a subgraph.

######  Definition 2.1 (Strength).

Let $s,\tilde{\delta}\geq 0$. A component $C$ in a graph $G$ is _$s$ -strong
for $\tilde{\delta}$_ if every cut $S$ with cut-size $w(S,G\setminus S)\leq
1.1\tilde{\delta}$ satisfies $\min\left({\hbox{\bf vol}}^{W}_{G\\{C\\}}(S\cap
C),{\hbox{\bf vol}}^{W}_{G\\{C\\}}(C\setminus S)\right)\leq s$. We call $s$
the _strength_ of a $s$-strong component. Note that $s$-strong is always
defined with respect to some parameter $\tilde{\delta}$ even though we
frequently drop $\tilde{\delta}$ and just use $s$-strong when it is clear from
the context.

######  Fact 2.2.

Let $s,\tilde{\delta}\geq 0$. Any component that is a subset of an $s$-strong
component is $s$-strong, where both use the same $\tilde{\delta}$ in the
definition of $s$-strong.

######  Definition 2.3.

For a component $A\subset V$ and parameter $\beta\leq 1$, a set $U\subseteq A$
is $\beta$-boundary-sparse in $A$ iff

$w(U,A\setminus U)<\beta\min\\{w(U,V\setminus A),w(A\setminus U,V\setminus
A)\\}.$

Otherwise it is non-$\beta$-boundary-sparse in $A$.

Note that if $U$ is $\beta$-boundary-sparse in $A$, then $A\setminus U$ is
also $\beta$-boundary-sparse in $A$, and that both $\emptyset$ and $A$ are
non-$\beta$-boundary-sparse in $A$.

##### Crossing.

Given two vertex sets $A,B$, we say that $A$ and $B$ _cross_ if the sets
$A\cap B$, $A\cap(V\setminus B)$, $(V\setminus A)\cap B$, and $(V\setminus
A)\cap(V\setminus B)$ are all non-empty. Informally, when we say we wish to
_uncross_ a set $A$ with a set $B$, we mean replacing $A$ with another set
$A^{\prime}$ that does not cross $B$.

##  3 Overview of the algorithm

At a high level, we follow the approach of the $O(|E|^{1+o(1)})$ deterministic
minimum cut algorithm by Li [Li21], which first performs a hierarchical
expander decomposition of the input graph $G$, and uses the structure
uncovered by the decomposition to derandomize the sampling procedure from
Karger’s classical randomized near-linear time minimum cut algorithm [Kar00]
to construct a skeleton graph. Informally speaking, the skeleton graph
approximately preserves the minimum cut from the original graph while being
much sparser. Finally, one can use the (deterministic) tree packing and
dynamic programming techniques from Karger’s result to find the minimum cut.
While all other steps take time $\tilde{O}(|E|)$, the bottleneck of Li’s
algorithm is the deterministic expander decomposition and we replace it with a
customized graph decomposition inspired by ideas from minimum cut algorithms
for unweighted graphs [KT19, HRW20]. Although our decomposition doesn’t
provide all the guarantees of an expander decomposition, it takes time
$\tilde{O}(|E|)$ and we show that it captures all the essential properties
required by the subsequent steps in Li’s algorithm. This improves the time
complexity of the whole algorithm to be nearly linear. Concretely, the goal of
the decomposition is to partition the vertices into subsets, such that there
exists a cut of size $(1+\epsilon)\lambda$ that does not cross any of the
subsets, where $\epsilon=1/\operatorname{polylog}|V|$. In the rest of this
section, we discuss our graph decomposition routines and outline the main
steps of our algorithm. The remaining sections then fill in the details for
these steps.

First we get a close approximation of $\tilde{\lambda}$ of $\lambda$ (i.e.
$\lambda\leq\tilde{\lambda}\leq 1.01\lambda$) by guessing the value of
$\lambda$ and then start decomposing the graph using three different
procedures. The first decomposition routine is similar to [KT19, HRW20] and
decomposes the graph $G^{\prime}$ into _$s_{0}$ -strong_ components for
parameters $\tilde{\delta}=\tilde{\lambda}/1.01$ and
$s_{0}=O(\tilde{\delta}\tau^{2})$ with $\tau=\operatorname{polylog}|V|$. We
intuitively think of $s_{0}$-strong components as having similar guarantees
for near-minimum cuts as expanders in the expander decomposition. Our
decomposition is summarized in the following lemma, whose running time is
near-linear in the unweighted number of edges in the graph.

[$s_{0}$-strong partition]lemmaStrongPartition Given a weighted graph
$G=(V,E,w)$, a parameter $\tilde{\delta}$ such that
$\tilde{\delta}\leq\min_{v\in V}d^{W}(v)$ and a parameter
$s_{0}=\Theta(\tilde{\delta}\log^{c}|V|)$ for some $c\geq 2$, there is an
algorithm that runs in $\tilde{O}(|E|)$ time and partitions the vertex set $V$
into $s_{0}$-strong components for $\tilde{\delta}$ such that the total weight
of the edges between distinct components is at most
$O(\frac{\sqrt{\tilde{\delta}}\log|V|}{\sqrt{s_{0}}})\cdot{\hbox{\bf
vol}}^{W}(V)$. To prove this lemma we need to extend the techniques from
[HRW20] to weighted graphs, which poses the challenges discussed in Subsection
1.1. Sections 4 and 5 shows how we overcome them.

In the algorithm we choose $\tilde{\delta}=\tilde{\lambda}/1.01$. In the
following we always use

$s_{0}=10^{11}\tilde{\delta}\tau^{2}=10^{11}\tilde{\lambda}\tau^{2}/1.01$

and we use $\tau$ to denote $\Theta(\log^{c/2}|V|)$ for some $c\geq 2$. We
will call an $s_{0}$-strong component a _cluster_. To emphasize that a cluster
is $s_{0}$-strong, we will often write $s_{0}$-strong cluster, even though
this is redundant. We then decompose these clusters further. By Fact 2.2 every
refinement of a cluster is a cluster so that the two subsequent decompositions
are only applied to clusters. These decompositions are novel and constitute
our main technical contributions. They are presented in Section 6. The first
decomposes each cluster into at most one large-volume cluster and a collection
of small-volume clusters. It is summarized in the following lemma, which is
proven in Subsection 6.2.

[Large cluster decomposition]lemmaFinalCuts Let $A\subseteq V$ be a cluster,
let $0<\epsilon\leq 0.1$ be a parameter and let $\tilde{\lambda}\leq
1.01\lambda$ be an approximate lower bound to the minimum cut known to the
algorithm. There is an algorithm that partitions $A$ into a (potentially
“large”) set $A_{0}$ and “small” sets $A_{1},\ldots,A_{r}$ such that

  1. 1.

For each $i\in\\{1,2,\ldots,r\\}$, we have
$\textbf{{vol}}^{W}_{G}(A_{i})\leq(\frac{10s_{0}}{\epsilon\tilde{\lambda}})\cdot
s_{0}$.

  2. 2.

The total weight $w(A_{0},A_{1},\ldots,A_{r})$ of inter-cluster edges is at
most $O(\epsilon^{-1})\cdot\partial A$.

  3. 3.

For any set $U\subseteq A$ with $\partial_{G[A]}U\leq 1.01\tilde{\lambda}$ and
$\textbf{{vol}}^{W}_{G}(U)\leq s_{0}$, there exists $U^{*}\subseteq U$ with
$U^{*}\cap A_{0}=\emptyset$ and $w(U\setminus U^{*},V\setminus
A)+\partial_{G[A]}U^{*}\leq(1+\epsilon)\partial_{G[A]}U$.

The algorithm runs in time
$\tilde{O}((\frac{s_{0}}{\epsilon\tilde{\lambda}})^{O(1)}|E(G[A])|)$. By our
choice of $s_{0}$ the running time is $\tilde{O}(|E(G[A])|)$.

By Fact 2.2 every set $A_{i}$ is $s_{0}$-strong. We now call a cluster _small_
if it has volume $(\frac{10s_{0}}{\epsilon\tilde{\lambda}})\cdot s_{0}$ and
_large_ otherwise. As we will choose $\epsilon=O(1/\log^{1.1}|V|)$, a small
cluster has volume
$O(\tilde{\delta}\tau^{4}\log^{1.1}|V|)=\tilde{O}(\lambda)$. Since every
vertex has degree at least $\lambda$, it follows that small clusters contain
only $\tilde{O}(1)$ many vertices. Note that the lemma states that the
potentially large cluster $A_{0}$ has been uncrossed, i.e., every cut $U$ of
size at most $1.01\tilde{\lambda}$ can be shifted to a cut $U^{*}$ such that
$U^{*}$ does not cross $A_{0}$ and such that the size of $U^{*}$ is only a
factor of $(1+\epsilon)$ larger than the size of $U$.

Thus we are left with potentially further decomposing the small clusters, for
which we use the second decomposition. It runs in time polynomial in the
number of vertices of the cluster, which is why we need the clusters to have
only $\operatorname{polylog}|V|$ vertices. We will not define the concept of
_$(1+\epsilon)$ -uncrossable_ in property (1) in this section, but informally,
for two sets $S$ and $A$, we say that $S\cap A$ is $(1+\epsilon)$-uncrossable
with $A$ if either $\partial(S\setminus A)\approx\partial S$ or
$\partial(S\cup A)\approx\partial S$. In other words, we can “uncross” $S$
with $A$ at little additional cost to the size of the boundary. [Small cluster
decomposition]lemmaSmallCuts Let $A\subseteq V$ be a cluster, let
$0<\epsilon\leq 0.01$ be a parameter, and let $\tilde{\lambda}\leq
1.01\lambda$ be an approximate lower bound to the minimum cut known to the
algorithm. There is an algorithm that partitions $A$ into a disjoint union of
clusters $A_{1}\cup A_{2}\cup\cdots\cup A_{k}=A$ such that

  1. 1.

For any set $S\subseteq A$ of $G$ with $\partial_{G[A]}S\leq
1.01\tilde{\lambda}$, there is a partition $\mathcal{P}$ of the set
$\\{A_{1},A_{2},\ldots,A_{k}\\}$ such that for each part
$P=\\{A_{i_{1}},\ldots,A_{i_{\ell}}\\}\in\mathcal{P}$, the set
$S\cap\bigcup_{A^{\prime}\in P}A^{\prime}$ is non-$(1-\epsilon)$-boundary-
sparse in $\bigcup_{A^{\prime}\in P}A^{\prime}$.

  2. 2.

The sum of boundaries $\sum_{i}\partial A_{i}$ is at most
$O(\epsilon^{-3}(\log|A|)^{O(1)}\partial A)$.

The running time of the algorithm is $O(|A|^{9}\operatorname{polylog}|A|)$.
Note that if $A$ is a small cluster, the running time is $\tilde{O}(1)$.

With these decomposition routines, we now outline the algorithm for a weighted
graph $G=(V,E)$. The goal of Step $1$ and the outer loop of Step 2 is to find
a good enough estimation $\tilde{\lambda}$ of the minimum cut value $\lambda$.
Step 1 find a value $\lambda_{0}$ with $\lambda\leq\lambda_{0}\leq 3\lambda$.
As Step 2 iterates over all powers of 1.01 between $\lambda_{0}/3$ and
$1.01\lambda_{0}$, the iteration is executed $O(1)$ times and
$\tilde{\lambda}$ can be seen as a “guess” of $\lambda$ that will at least
once assume a value in $[\lambda,1.01\lambda]$. If $\tilde{\lambda}$ does not
belong to $[\lambda,1.01\lambda]$, an arbitrary cut will be returned, but as
the algorithm returns at the end the smallest over all cuts found for all
guesses, it suffices that the algorithm finds a correct minimum cut in the
iteration when $\tilde{\lambda}\in[\lambda,1.01\lambda]$. Our graph
decomposition procedures are featured in Step 2b, and the subsequent Steps 2c
and 2d are mostly the same as the original $O(|E|^{1+o(1)})$ algorithm by Li
[Li21] and a presented in Section 7.

  1. 1.

We first run Matula’s $(2+\epsilon)$-approximation algorithm [Mat93] (which
can be easily extended to the weighted setting) to get a value $\lambda_{0}$
such that $\lambda\leq\lambda_{0}\leq 3\lambda$.

  2. 2.

For all powers $\tilde{\lambda}$ of $1.01$ between $\lambda_{0}/3$ and
$1.01\lambda_{0}$

    1. (a)

Initialize $j\leftarrow 0$ and $G_{0}\leftarrow G$ with vertex set $V_{0}$ and
edge set $E_{0}$

    2. (b)

While there are at least 2 nodes in $G_{j}=(V_{j},E_{j})$:

      1. i.

Partition $V_{j}$ into subsets called clusters that are $s_{0}$-strong using
the algorithm of Section 3, for parameters
$\tilde{\delta}=\tilde{\lambda}/1.01$ and
$s_{0}=10^{11}\tilde{\delta}\tau^{2}$. Let $\mathcal{C}^{s_{0}}_{j}$ be the
set of $s_{0}$-strong clusters.

      2. ii.

Let $\epsilon=1/\log^{1.1}|V|$.

      3. iii.

For each resulting cluster $C$, we further decompose $C$ according to Section
3 with values $\tilde{\lambda}$ and $\epsilon$. Note that all clusters except
possibly $A_{0}$ (if it exists) is a small cluster.

      4. iv.

For each small cluster, we further decompose it according to Section 3 with
values $\tilde{\lambda}$ and $\epsilon$.

      5. v.

Let ${\cal C}_{j}=\\{C_{j,1},C_{j,2},\dots\\}$ be the resulting set of
clusters. Collapse every cluster $C\in{\cal C}_{j}$ with $|C|>1$ into one node
and call the resulting graph $G_{j+1}=(V_{j+1},E_{j+1})$.

      6. vi.

$j\leftarrow j+1$

    3. (c)

Build a skeleton graph $H$ using the clusters $\\{{\cal C}_{j}\\}_{j}$ using
the algorithm from Section 7.

    4. (d)

Run Karger’s tree packing and dynamic programming algorithm on the skeleton
$H$ to find a cut $S$.

  3. 3.

Output the cut $S$ with the minimum value found over all guesses of
$\tilde{\lambda}$.

Note that every iteration of Step 2b takes time $\tilde{O}(m)$. We will show
in Lemma 3.1 that the clustering ${\cal C}_{j}$ guarantees that ${\hbox{\bf
vol}}^{W}_{G_{j+1}}(V_{j+1})\leq{\hbox{\bf vol}}^{W}_{G_{j}}(V_{j})/2$ for
every $j\geq 0$, so there are $O(\log{\hbox{\bf vol}}^{W}_{G}(V))$ loop
iterations of total time $\tilde{O}(m)$.

For correctness let us first assume that $\tilde{\lambda}$ is between
$\lambda$ and $1.01\lambda$. In that case we will show, for each $j$, that
after Step 2(b)iv, every approximately minimum cut can be “shifted” (or
“uncrossed”) into another cut that does not intersect any cluster and whose
cut value grows at most by factor $(1+o(1/\log|V|))$. In particular,
collapsing such a cluster increases the size of the minimum cut by at most a
factor of $(1+o(1/\log|V|))$, which implies that the minimum cut of $G_{j+1}$
is at most a factor of $(1+o(1/\log|V|))$ larger than the minimum cut of
$G_{j}$. Thus, throughout all $O(\log|V|)$ iterations of Step 2b the minimum
cut in $G_{j}$ is at most $1.01\tilde{\lambda}$, which is a property needed
for the decomposition algorithms in steps2(b)iii and 2(b)iv to correctly
compute the clustering ${\cal C}_{j}$. Using the guarantees of the clusters
${\cal C}_{j}$, the algorithm then constructs a skeleton graph $H$ following
the pessimistic estimator approach of [Li21]. Finally, the algorithm runs (the
remainder of) Karger’s near-linear time minimum cut algorithm on the skeleton
$H$, which is deterministic and returns a minimum cut of $G$.

The lemmata below summarize the two key measures of progress. First, the total
volume halves on each iteration $j$. Second, any near-minimum cut $S$ can be
shifted by $O(\tau^{2})=\operatorname{polylog}(n)$ vertices into a near-
minimum cut $\widetilde{S}$ that does not cross any cluster in the partition,
and, hence, survives the contraction on step 2(b)v.

######  Lemma 3.1 (Progress per iteration).

For each iteration $j$, the total volume drops by a factor of at least $2$ in
each iteration: ${\hbox{\bf vol}}^{W}_{G_{j+1}}(V_{j+1})\leq{\hbox{\bf
vol}}^{W}_{G_{j}}(V_{j})/2$.

###### Proof.

The value of $\tilde{\delta}$ used in Step 2(b)i fulfills the condition of by
Section 3, and, thus, with $c=6$ the lemma implies that the total weight of
edges between clusters is at most
$O(\frac{\sqrt{\tilde{\delta}}\log|V|}{\sqrt{s_{0}}})\cdot\textbf{{vol}}^{W}_{G^{\prime}_{j}}(V_{j})$
for $s_{0}=\Theta(\tilde{\delta}\tau^{2})$ with $\tau=\Theta(\log^{3}|V|)$. In
particular, the sum of the boundaries $\sum_{A}\partial A$ is at most
$O(\frac{\sqrt{\tilde{\delta}}\log|V|}{\sqrt{s_{0}}})\cdot\textbf{{vol}}^{W}_{G^{\prime}_{j}}(V_{j})$.

For each such cluster $A$, by Section 3, Step 2(b)iii produces a partition
into sub-clusters $A_{0},A_{1},\ldots,A_{r}$ such that $\sum_{i}\partial
A_{i}\leq O(\epsilon^{-1})\cdot\partial A$. Therefore, after Step 2(b)iii, the
new sum of boundaries of all clusters is
$O(\frac{\sqrt{\tilde{\delta}}\log|V|}{\epsilon\sqrt{s_{0}}})\cdot\textbf{{vol}}^{W}_{G^{\prime}_{j}}(V_{j})$.
Finally on Step 2(b)iv, by Section 3, each small cluster $A$ is divided one
last time into clusters whose sum of boundaries is at most
$O(\epsilon^{-3}(\log|A|)^{O(1)}\partial A)$, bringing the new total sum of
boundaries to
$O(\frac{\sqrt{\tilde{\delta}}\log|V|(\log\log|V|)^{O(1)}}{\epsilon^{4}\sqrt{s_{0}}})\cdot\textbf{{vol}}^{W}_{G^{\prime}_{j}}(V_{j})$.
Putting everything together, we conclude that the total weight of inter-
cluster edges is at most

$O\left(\frac{\sqrt{\tilde{\delta}}\log|V|(\log\log|V|)^{O(1)}}{\epsilon^{4}\sqrt{s_{0}}}\right)\cdot{\hbox{\bf
vol}}^{W}_{G_{j}}(V_{j}).$

Recall that $s_{0}=10^{11}\tilde{\delta}\tau^{2}$, $\tau=O(\log^{3}|V|)$.
Using a sufficiently large constant factor for $\tau$, this bound is at most
${\hbox{\bf vol}}^{W}_{G_{j}}(V_{j})/2$, as promised. ∎

######  Lemma 3.2 (Structure lemma).

Suppose that Step 2 is run with $\tilde{\lambda}\in[\lambda,1.01\lambda]$, and
fix an iteration $j$. For any cut $S\subseteq V_{j}$ with
$\partial_{G_{j}}S\leq 1.01\lambda$, there exists a set $S^{\prime}\subseteq
V_{j}$ such that

  1. 1.

$S^{\prime}$ does not cross any cluster in $\mathcal{C}_{j}$,

  2. 2.

$\partial_{G_{j}}S^{\prime}\leq(1+3\epsilon)\partial_{G_{j}}S$, and

  3. 3.

$\textbf{{vol}}^{W}_{G_{j}}(S\triangle S^{\prime})\leq
O(s_{0}^{2}/(\epsilon\lambda))$.

For the remainder of this section, we prove Lemma 3.2.

Since $\partial_{G_{j}}S\leq 1.01\lambda\leq 1.01\tilde{\lambda}\leq
1.1\tilde{\delta}$ and each cluster $A\in\mathcal{C}^{s_{0}}_{j}$ is
$s_{0}$-strong for $\tilde{\delta}$, we have
$\min\\{\textbf{{vol}}^{W}_{G_{j}}(S\cap
A),\textbf{{vol}}^{W}_{G_{j}}(A\setminus S)\\}\leq s_{0}$ for all clusters
$A\in\mathcal{C}^{s_{0}}_{j}$. For each such cluster $A$ that crosses $S$,
apply property (3) of Section 3 on either $U=S\cap A$ or $U=A\setminus S$,
whichever has smaller volume. By assumption, $\partial_{G_{j}[A]}U\leq
1.01\lambda\leq 1.01\tilde{\lambda}$ and $\textbf{{vol}}^{W}_{G_{j}}(U)\leq
s_{0}$, so property (3) of Section 3 guarantees a set $U^{*}$ with $U^{*}\cap
A_{0}=\emptyset$ and $w_{G_{j}}(U\setminus U^{*},V_{j}\setminus
A)+\partial_{G_{j}[A]}U^{*}\leq(1+\epsilon)\partial_{G_{j}[A]}U$. To
distinguish the sets among different $A$, we add a subscript $A$ to $U,U^{*}$.

We now shift $S$ into a new set $S^{*}$ by, intuitively, replacing each of the
above $U_{A}$ with $U^{*}_{A}$. Some care is needed to distinguish the cases
$U_{A}=S\cap A$ and $U_{A}=A\setminus S$. If $U_{A}=S\cap A$, then we remove
the vertices of $U_{A}\setminus U^{*}_{A}$ from $S$. If $U_{A}=A\setminus S$,
then we add the vertices of $U_{A}\setminus U^{*}_{A}$ to $S$. By
construction, we only add or remove vertices in $U_{A}$ of total volume at
most $\textbf{{vol}}_{G_{j}}^{W}(U_{A})\leq s_{0}$.

######  Claim 3.3.

$\partial_{G_{j}}S^{*}\leq(1+\epsilon)\partial_{G_{j}}S$.

###### Proof.

Consider a cluster $A\in\mathcal{C}^{s_{0}}_{j}$ with $U_{A}=S\cap A$. If
$U_{A}\neq U^{*}_{A}$, then removing vertices of $U_{A}\setminus U^{*}_{A}$
results in a subset of edges of $E_{G_{j}}(U\setminus U^{*},V_{j}\setminus A)$
being added to $\partial_{G_{j}}S^{*}$, and within cluster $A$, the net
difference of edges is exactly
$\partial_{G_{j}[A]}S^{*}-\partial_{G_{j}[A]}S$. The total net difference of
edges from processing cluster $A$ is at most $w_{G_{j}}(U\setminus
U^{*},V_{j}\setminus A)+\partial_{G_{j}[A]}S^{*}-\partial_{G_{j}[A]}S$, which
is at most $\epsilon\partial_{G_{j}[A]}S$ by property (3) of Section 3. A
symmetric argument holds for the case $U_{A}=A\setminus S$. Finally, over all
clusters $A$, the net differences sum to at most $\epsilon\partial_{G_{j}}S$.
∎

######  Claim 3.4.

There are $O(1)$ many clusters for which $U^{*}_{A}\neq U_{A}$.

###### Proof.

Consider the value of the cut $\partial_{G_{j}}(U_{A}\setminus
U_{A}^{*})\geq\lambda_{G_{j}}\geq\lambda$. We can upper bound
$\partial_{G_{j}}(U_{A}\setminus U_{A}^{*})$ as

$\displaystyle\partial_{G_{j}}(U_{A}\setminus U_{A}^{*})$
$\displaystyle=w_{G_{j}}(U_{A}\setminus U_{A}^{*},V_{j}\setminus
A)+\partial_{G_{j}[A]}(U_{A}\setminus U_{A}^{*})$ $\displaystyle\leq
w_{G_{j}}(U_{A}\setminus U_{A}^{*},V_{j}\setminus
A)+\partial_{G_{j}[A]}U_{A}+\partial_{G_{j}[A]}U_{A}^{*}$
$\displaystyle\leq(2+\epsilon)\partial_{G_{j}[A]}U_{A},$

where the last inequality is by property (3) of Section 3. It follows that
$\partial_{G_{j}[A]}U_{A}\geq\frac{1}{2+\epsilon}\partial_{G_{j}}(U_{A}\setminus
U_{A}^{*})\geq\frac{1}{2+\epsilon}\lambda$. Finally, the edges
$\partial_{G_{j}[A]}U_{A}$ are disjoint among different clusters $A$, so there
are at most $\partial_{G_{j}}S/(\frac{1}{2+\epsilon}\lambda)=O(1)$ many
clusters for which $U^{*}_{A}\neq U_{A}$. ∎

######  Claim 3.5.

$\textbf{{vol}}_{G_{j}}^{W}(S\triangle S^{*})\leq O(s_{0})$.

###### Proof.

For each cluster $A$, we add or remove a subset of $U_{A}$, which has volume
at most $\textbf{{vol}}_{G_{j}}^{W}(U_{A})\leq s_{0}$. By 3.4, there are at
most $O(1)$ many clusters for which $U^{*}_{A}\neq U_{A}$. In each such
cluster, we add/remove vertices with total volume at most $s_{0}$. For the
clusters $A$ with $U^{*}_{A}=U_{A}$, no action is needed. Altogether, we
obtain $\textbf{{vol}}_{G_{j}}^{W}(S\triangle S^{*})\leq O(1)\cdot s_{0}$. ∎

After step (2(b)iii), by construction of $S^{*}$ and Section 3, the set
$S^{*}$ only crosses small clusters, which have volume
$\textbf{{vol}}_{G_{j}}^{W}(A)\leq O(s_{0}^{2}/(\epsilon\lambda))$. Each of
these clusters is then processed according to Section 3 in Step 2(b)iv as
follows. We shift $S^{*}$ into a new set $S^{\prime}$ by, intuitively,
uncrossing with each cluster according to Section 3. For each cluster $A$ that
crosses $S^{*}$, let $\mathcal{P}$ be the partition guaranteed by property (1)
of Section 3. Recall from Definition 2.3 that a set $U$ is $\beta$-boundary-
sparse in $A$ if $w(U,A\setminus U)<\beta\min\\{w(U,V_{j}\setminus
A),w(A\setminus U,V_{j}\setminus A)\\}$. For each $P\in\mathcal{P}$, define
$A_{P}=\bigcup_{A^{\prime}\in P}A^{\prime}$ to avoid clutter. If $S^{*}$
crosses $A_{P}$, then the set $U_{P}=S^{*}\cap A_{P}$ is not
$(1-\epsilon)$-boundary-sparse in $A_{P}$, so either $w(U_{P},A_{P}\setminus
U_{P})\geq(1-\epsilon)w(U_{P},V_{j}\setminus A_{P})$ or
$w(U_{P},A_{P}\setminus U_{P})\geq(1-\epsilon)w(A_{P}\setminus
U,V_{j}\setminus A_{P})$. If $w(U_{P},A_{P}\setminus
U_{P})\geq(1-\epsilon)w(U_{P},V_{j}\setminus A_{P})$, then update
$S^{*}\leftarrow S^{*}\triangle U_{P}$, i.e., we remove the vertices of
$U_{P}$ from $S^{*}$. If $w(U_{P},A_{P}\setminus
U_{P})\geq(1-\epsilon)w(A_{P}\setminus U_{P},V_{j}\setminus A_{P})$, then
update $S^{*}\leftarrow S^{*}\triangle(A_{P}\setminus U_{P})$, i.e., we add
the vertices of $A_{P}\setminus U_{P}$ to $S^{*}$.

By construction, we only add or remove vertices in $A$ of total volume at most
$\textbf{{vol}}_{G_{j}}^{W}(A)\leq
O(\frac{s_{0}}{\epsilon\tilde{\lambda}})\cdot s_{0}$.

######  Claim 3.6.

$\partial_{G_{j}}S^{\prime}\leq\frac{1}{1-\epsilon}\partial_{G_{j}}S^{*}$.

###### Proof.

Consider a cluster $A$ and its partition $\mathcal{P}$ guaranteed by Section
3. If $w(U_{P},A_{P}\setminus U_{P})\geq(1-\epsilon)w(U_{P},V_{j}\setminus
A_{P})$, then the update $S^{*}\leftarrow S^{*}\triangle U_{P}$ results in a
subset of edges of $E_{G_{j}}(U_{P},V_{j}\setminus A)$ being added to
$\partial_{G_{j}}S^{*}$, and within $A_{P}$, all edges of
$E_{G_{j}}(U_{P},A_{P}\setminus U_{P})$ are no longer in
$\partial_{G_{j}}S^{*}$. So the net increase of $\partial_{G_{j}}S^{*}$ is at
most $w(U_{P},V_{j}\setminus A_{P})-w(U_{P},A_{P}\setminus
U_{P})\leq\frac{1}{1-\epsilon}w(U_{P},A_{P}\setminus
U_{P})-w(U_{P},A_{P}\setminus
U_{P})\leq(\frac{1}{1-\epsilon}-1)w(U_{P},A_{P}\setminus U_{P})$. The argument
for the update $S^{*}\leftarrow S^{*}\triangle(A_{p}\setminus U_{P})$ is
symmetric and has the same upper bound of
$(\frac{1}{1-\epsilon}-1)w(U_{P},A_{P}\setminus U_{P})$ for the net increase
of $\partial_{G_{j}}S^{*}$.

Summed over all clusters $A$ and parts $P\in\mathcal{P}$, the total net
increase of $\partial_{G_{j}}S^{*}$ is at most
$(\frac{1}{1-\epsilon}-1)\sum_{A,P}w(U_{P},A_{P}\setminus U_{P})$, which is at
most $(\frac{1}{1-\epsilon}-1)\partial_{G_{j}}S^{*}$ since the edges in
$E_{G_{j}}(U_{P},A_{P}\setminus U_{P})$ are disjoint over all $A,P$. It
follows that
$\partial_{G_{j}}S^{\prime}\leq\frac{1}{1-\epsilon}\partial_{G_{j}}S^{*}$. ∎

######  Claim 3.7.

$\textbf{{vol}}_{G_{j}}^{W}(S^{\prime}\triangle S^{*})\leq
O(s_{0}^{2}/(\epsilon\lambda))$.

###### Proof.

Suppose that $S^{*}$ crosses some $A_{P}$ for a small cluster $A$ and a
partition $\mathcal{P}$ returned by Step 2(b)iv. Recall that $U_{P}=S^{*}\cap
A_{P}$ and that Lemma 3 guarantees that either $w(U_{P},A_{P}\setminus
U_{P})\geq(1-\epsilon)w(U_{P},V_{j}\setminus A_{P})$ or
$w(U_{P},A_{P}\setminus U_{P})\geq(1-\epsilon)w(A_{P}\setminus
U,V_{j}\setminus A_{P})$. In the first case, consider the value of the cut
$\partial_{G_{j}}U_{P}\geq\lambda_{G_{j}}$. We can upper bound
$\partial_{G_{j}}U_{P}$ as

$\partial_{G_{j}}U_{P}=w(U_{P},V_{j}\setminus A_{P})+w(U_{P},A_{P}\setminus
U_{P})\leq\frac{1}{1-\epsilon}w(U_{P},A_{P}\setminus
U_{P})+w(U_{P},A_{P}\setminus
U_{P})=\frac{2-\epsilon}{1-\epsilon}w(U_{P},A_{P}\setminus U_{P}).$

It follows that $w(U_{P},A_{P}\setminus
U_{P})\geq\frac{1-\epsilon}{2-\epsilon}\partial_{G_{j}}U_{P}\geq\frac{1-\epsilon}{2-\epsilon}\lambda_{G_{j}}\geq\frac{1-\epsilon}{2-\epsilon}\lambda$.

The edges $E(U_{P},A_{P}\setminus U_{P})$ are disjoint among pairs $(A,P)$, so
there are at most
$\partial_{G_{j}}S^{*}/(\frac{1-\epsilon}{2-\epsilon}\lambda)\leq(1+\epsilon)\partial_{G_{j}}S/(\frac{1-\epsilon}{2-\epsilon}\lambda)=O(1)$
many pairs $(A,P)$ for which any action is needed. For each, we add or remove
vertices of total volume at most
$\textbf{{vol}}_{G_{j}}^{W}(A)=O(s_{0}^{2}/(\epsilon\tilde{\lambda}))O(s_{0}^{2}/(\epsilon\lambda))$,
and the claim follows. ∎

We now verify the requirements of Lemma 3.2:

  1. 1.

By construction, $S^{\prime}$ does not cross any cluster in $\mathcal{C}_{j}$.

  2. 2.

$\partial_{G_{j}}S^{\prime}\leq\frac{1}{1-\epsilon}\partial_{G_{j}}S^{*}\leq\frac{1}{1-\epsilon}\cdot(1+\epsilon)\partial_{G_{j}}S\leq(1+3\epsilon)\partial_{G_{j}}S$.

  3. 3.

$\textbf{{vol}}^{W}_{G_{j}}(S\triangle
S^{\prime})\leq\textbf{{vol}}^{W}_{G_{j}}(S\triangle
S^{*})+\textbf{{vol}}^{W}_{G_{j}}(S^{*}\triangle S^{\prime})\leq
O(s_{0})+O(s_{0}^{2}/(\epsilon\lambda))\leq O(s_{0}^{2}/(\epsilon\lambda))$.

This concludes the proof of Lemma 3.2

##  4 Unit-Flow Algorithm

We will consider flow problems extensively in our graph decomposition
procedure, and we start with some notations. Formally, a flow problem is
defined with a source function, $\Delta:V\rightarrow\mathbb{R}_{\geq 0}$, a
sink function, $T:V\rightarrow\mathbb{R}_{\geq 0}$, and edge capacities
$c(\cdot)$. We say that $v$ is a sink of capacity $x$ if $T(v)=x$. To avoid
confusion with the way flow is used, we use supply to refer to the substance
being routed in flow problems.

For the sake of efficiency, we will not typically obtain a full solution to a
flow problem. We will compute a _pre-flow_ , which is a function $f:V\times
V\rightarrow\mathbb{R}$, where $f(u,v)=-f(v,u)$. A pre-flow $f$ is source-
feasible with respect to source function $\Delta$ if $\forall
v:\sum_{u}f(v,u)\leq\Delta(v)$. A pre-flow $f$ is capacity-feasible with
respect to $c(\cdot)$ if $|f(u,v)|\leq c(e)$ for $e=\\{u,v\\}\in E$ and
$f(u,v)=0$ otherwise. We say that $f$ is a feasible pre-flow for flow problem
$\Pi$, or simply a pre-flow for $\Pi$, if $f$ is both source-feasible and
capacity-feasible with respect to $\Pi$.

For a pre-flow $f$ and a source function $\Delta(\cdot)$, we extend the
notation to denote $f(v)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\Delta(v)+\sum_{u}f(u,v)$ as the amount of supply ending at $v$
after $f$. Note that $f(v)$ is non-negative for all $v$ if $f$ is source-
feasible. When we use a pre-flow as a function on vertices, we refer to the
function $f(\cdot)$, and it will be clear from the context what
$\Delta(\cdot)$ we are using. If in addition, $\forall v:f(v)\leq T(v)$, the
pre-flow $f$ will be a feasible flow (solution) to the flow problem $\Pi$.

We denote $\operatorname{ex}(v)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\max(f(v)-T(v),0)$ as the excess supply at $v$, and we call the part
of the supply below $T(v)$ as the supply routed to the sink at $v$, or
absorbed by $v$. We call the sum of all the supply absorbed by vertices,
$\sum_{v}\min(f(v),T(v))$, the total supply routed to sinks. Finally, given a
source function $\Delta(\cdot)$, we define
$|\Delta(\cdot)|\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\sum_{v}\Delta(v)$ as the total amount of supply in the flow
problem. Note the total amount of supply is preserved by any pre-flow routing,
so $\sum_{v}f(v)=|\Delta(\cdot)|$ for any source-feasible pre-flow $f$.

In this section, we consider a particular family of flow problems that is
useful in our graph decomposition, and discuss the algorithm we use to compute
pre-flows. The flow problem we consider comes with a source function
$\Delta(\cdot)$, a weighed undirected graph $G$ with edge weights $w_{e}$’s,
an edge capacity parameter $U$ such that $c_{e}=w_{e}\cdot U$ for all edges,
and $T(v)=d^{W}(v)$ for all vertices. As a side note, for the actual flow
problems we solve in our graph decomposition procedure, all the quantities
(i.e. source supply, edge and sink capacities) are in the same unit whose
value can vary across different flow problems, but the flow algorithm should
be completely oblivious to the value of the unit. Nonetheless, in the discuss
of our flow computation we may refer to supply of amount $x$ as $x$ units of
supply.

To solve our flow problems, we use the Unit-Flow algorithm, which was designed
in [HRW20] for unweighted graphs, and we adapt it to weighted graphs. The
algorithm follows the classic Push-belabel framework by Goldberg and Tarjan
[GT88], which at a high level works as follows. The algorithm maintains an
integer label (or height) $l(v)$ for each node $v$ starting at $0$. If there
is excess on any node, the algorithm picks one such node and tries to send its
excess to any neighbour of smaller label while obeying the edge’s residual
capacity (a.k.a Push), and if there is no possible Push for a node with
excess, the algorithm raises the label of the node by $1$ (a.k.a Relabel). The
standard Push-relabel algorithm for max flow keeps carrying out Push or
Relabel until it finds a flow (i.e. no excess supply on any node).

The Unit-Flow algorithm works exactly the same except one difference. In
particular, Unit-Flow takes as input a cap $h$ on the height, and when Push-
relabel needs to raise a node’s label from $h$ to $h+1$, Unit-Flow will
instead leave the node at height $h$ without working further on the node’s
excess supply. Note this is also the only case that Unit-Flow leaves excess on
nodes, so when the algorithm stops, if there is any node with excess, the node
must have label $h$. Since the algorithm description and the running time
analysis follow quite mechanically from the Push-relabel algorithm in [GT88]
using the dynamic-tree data structuer [ST81], in this section we only
summarize the result of Unit-Flow that we will use in our later graph
decomposition. The proof of the main theorem also follows largely from the
original analysis of unweighted Unit-Flow in [HRW20], so we defer most of the
implementation details and analysis of our weighted Unit-Flow to the Appendix
A.

Upon termination of the algorithm, it returns $(1)$ a pre-flow $f$, $(2)$
labels $l(\cdot)$ (i.e. height) on vertices, and (3) a possibly empty cut $A$.
More specifically, Unit-Flow will either successfully route a large amount of
supply to sinks and return an empty cut, or it returns a low conductance cut
using the labels. Formally, we have the following theorem.

######  Theorem 4.1.

Given $G,\Delta,h,U,\beta\geq 2$ such that $\Delta(v)\leq\beta d^{W}(v)$ for
all $v$, Unit-Flow terminates with a pre-flow $f$, where we must have one of
the following three cases

  1. (1)

$f$ is a feasible flow, i.e. $\forall v:\operatorname{ex}(v)=0$. All units of
supply are absorbed by sinks.

  2. (2)

$f$ is not a feasible flow, but $\forall v:f(v)\geq d^{W}(v)$, i.e., at least
${\hbox{\bf vol}}^{W}(G)$ units of supply are absorbed by sinks.

  3. (3)

If $f$ satisfies neither of the two cases above, denote $T$ as the set of
nodes whose labels are $h$ (i.e. largest possible label), and assume
$h\geq\ln{\hbox{\bf vol}}^{W}(G)$, then we can find a cut $(A,\bar{A})$ such
that

    1. (a)

$T\subseteq A$, and $(\beta+U)d^{W}(v)\geq f(v)\geq d^{W}(v)$ for all $v\in
T$, and $f(v)=d^{W}(v)$ for all $v\in A\setminus T$, and $f(v)\leq d^{W}(v)$
for all $v\notin A$.

    2. (b)

The cut’s conductance $\Phi(A)=\frac{W(A,V\setminus A)}{\min\left({\hbox{\bf
vol}}^{W}(A),{\hbox{\bf vol}}^{W}(G)-{\hbox{\bf
vol}}^{W}(A)\right)}\leq\frac{20\ln{\hbox{\bf
vol}}^{W}(G)}{h}+\frac{\beta}{U}$.

    3. (c)

Let $\operatorname{ex}(T)$ be the total amount of excess supply (which can
only be on nodes in $T$), i.e.
$\operatorname{ex}(T)=\sum_{v}\max\left(0,f(v)-d^{W}(v)\right)$, we have
${\hbox{\bf
vol}}^{W}(A)\geq\frac{\operatorname{ex}(T)}{(\beta-1)+10U\ln\left({\hbox{\bf
vol}}^{W}(G)\right)/h}$

Let $C=\left\\{v:f(v)\geq d^{W}(v)\right\\}$ be the set of saturated nodes
when Unit-Flow finishes, the running time for Unit-Flow is $O({\hbox{\bf
vol}}(C)\cdot h\cdot\log{\hbox{\bf vol}}(C))$. Moreover, the above guarantees
hold in the case when $\Delta$ is incremental, i.e., after Unit-Flow finishes
working with the supply from the current $\Delta(\cdot)$, new source supply
can be added on nodes to increase $\Delta(\cdot)$, and the theorem holds when
Unit-Flow finishes with any interim $\Delta(\cdot)$.

Note that the running time only depends on the _unweighted_ volume ${\hbox{\bf
vol}}(C)$ and _not_ on the weighted volume ${\hbox{\bf vol}}^{W}(C)$.

##  5 Guaranteeing $s_{0}$-strength

Our procedure will make progress on the graph by breaking it into
$s_{0}$-strong components, i.e., components such that if we consider any
nearly min cut in the graph, any component will be mostly on one side of the
cut up to some small error. We prove in this section the following result.
Throughout this section, when we talk about $s$-strong components for any
$s\geq s_{0}$, the definition of strength is with respect to the parameter
$\tilde{\delta}$, so we only worry about any cut $S$ with $w(S,G\setminus
S)\leq 1.1\tilde{\delta}$. We denote
$\tau=\Theta(\sqrt{s_{0}/\tilde{\delta}})=\Theta(\ln^{c/2}|V|)$ as the
parameter, such that in the section we always break components along cuts of
conductance at most $O(1/\tau)$. Moreover, we need the following definitions.

######  Definition 5.1.

Given a component $C$ in a graph $G$ we say that a cut $(A,C\setminus A)$ is
_relatively balanced_ if $\min\left({\hbox{\bf vol}}^{W}(A),{\hbox{\bf
vol}}^{W}(C\setminus A)\right)\geq\Omega\left(\frac{{\hbox{\bf
vol}}^{W}(C)}{\tau^{2}\ln m_{G}}\right)$ where all volumes refer to the graph
$G\\{C\\}$ (which are the same as in $G$ due to the added self-loops).

We start with some input graph $G$ with $m_{G}$ edges and minimum weighted
node degree at least $\tilde{\delta}$. By definition $G$ is ${\hbox{\bf
vol}}^{W}(G)/2$-strong. For a component $C$ that is already certified to be
$s$-strong for some $s\geq s_{0}$, our algorithm will try to certify $C$ is
$s/2$-strong, but during the process it may find a low conductance cut in $C$
and break up $C$. When we break a $s$-strong component $C$ into
$(C^{\prime},C\setminus C^{\prime})$, by definition we already certify
$C^{\prime}$ is $\min(s,{\hbox{\bf vol}}^{W}(C^{\prime})/2)$-strong (and
similarly for $C\setminus C^{\prime}$). The running time to certify that $C$
is $s/2$-strong or to find a low conductance cut will be $\tilde{O}(m_{C})$,
where $m_{C}$ is the number of edges in $C$. We will iteratively work on the
graph (by cutting or certifying) and stop when all connected components are
certified to be $s_{0}$-strong where for concreteness we use the explicit
value of $s_{0}=10^{11}\tilde{\delta}\tau^{2}$.

Moreover, for the low conductance cut we use to divide a component $C$, either
the cut is relatively balanced (i.e., the weighted volume of both $C^{\prime}$
and $C\setminus C^{\prime}$ is at most $(1-\frac{1}{\tau^{2}\ln
m_{G}}){\hbox{\bf vol}}^{W}(C)$), or we can certify that the larger side of
the cut is $s/2$-strong. This guarantees that the total running time to
decompose the graph $G$ into $s_{0}$-strong components is near-linear in the
number of edges of the graph (i.e. $m_{G}$).

For now, we will work with the graph $G\\{C\\}$ of one connected component $C$
that is certified to be $s$-strong for some $s>s_{0}$. We use $m_{C}$, $W_{C}$
to denote the number of edges and weighted volume of $G\\{C\\}$ respectively.

###  5.1 Flow Problems and Excess Scaling

We will construct a sequence of flow problems, and have a total of (up to)
$L=O(\ln m_{C})$ stages for each flow problem. The basic structure is that
each flow problem will start at stage $0$ and be associated with a source node
at stage $0$.

Technically for each flow problem, we need its associated source node to
reserve a distinct $\tilde{\delta}$ adjacent edge weight for that flow
problem, and thus we can (and may have to) use the same node $v$ as the source
node of multiple flow problems if $d^{W}(v)\gg\tilde{\delta}$ to accommodate a
large enough number of flow problems in total. However, for the sake of
notation simplicity, it is easier if we can associate each flow problem with a
distinct source node (and thus refer to it by its source node), and to make
sure the graph can still support enough flow problems, we assume each node $v$
has $\tilde{\delta}\leq d^{W}(v)\leq 2\tilde{\delta}$. The lower bound
automatically holds, and for any node $v$ with $d^{W}(v)>2\tilde{\delta}$, we
can view it as several virtual nodes such that they (virtually) partition the
total weight of $v$’s adjacent edges in a way that the weighted degree of each
is between $\tilde{\delta}$ and $2\tilde{\delta}$. This guarantees that we
have at least $\frac{W_{C}}{2\tilde{\delta}}$ distinct (virtual) nodes to use
as source nodes. Consequently, we WLOG make the following assumption.

######  Assumption 5.2.

We can pick up to $\frac{W_{C}}{2\tilde{\delta}}$ distinct nodes in the graph
as source nodes of our flow problems in stage $0$, and all source nodes have
weighted degree at least $\tilde{\delta}$.

##### Stages.

For the flow problem associated with a node $v$, we will inject a certain
amount of source supply at $v$ in stage $0$ and try to spread it to sinks
iteratively in stages. In each stage we use Unit-Flow, which may terminate
with some excess supply. If the total excess supply is at most a $O(1/\ln
m_{C})$ fraction of the total amount of source supply, we will call the flow
problem _successful for that stage_ (otherwise _unsuccessful for that stage_)
and advance the flow problem into the next stage. We keep working on a flow
problem until it is unsuccessful at some stage or we finish successfully
through all $L$ stages. We then pick a new source node and work on the flow
problem starting with the new node at stage $0$, and keep doing this until
enough flow problems are successful at any particular stage. The flow problems
happen sequentially, i.e. we work on a flow problem through stages
$0,1,\ldots$ until it is unsuccessful at some stage, and then start a new flow
problem. Moreover, every flow problem is associated with a distinct
(stage-$0$) source node.

##### Batches.

We will group the sequence of flow problems into batches, where we keep adding
flow problems into the current batch until (a) we find enough flow problems
successfully finishing at stage L in the current batch or (b) the total number
of flow problems in the current batch reaches a limit. In case (a) we start a
new batch, and in Case (b) we will show that we can find a relatively balanced
low conductance cut.

##### Capacity sharing.

We will run multiple flow problems of the same stage on the same copy of the
graph, which means the pre-flows share the edge and sink capacities in the
same graph. More specifically,

  * •

All the flow problems (over all batches) in stage $0$ will share a single copy
of the graph (i.e., the edge and sink capacities). That is, the edge
capacities and sink capacities are constraints over the total flow routed by
_all_ the flow problems in stage $0$.

  * •

For any later stage $i\in\\{1,\ldots,L\\}$, all the flow problems _of the same
batch in stage $i$_ will run on a single copy of the graph, while flow
problems of different batches or of different stages have separate copies of
the graph (i.e. , do not share their edge and sink capacities).

##### Flow problems.

We now fill in more details. For a flow problem associated with source node
$v$ in batch $i$, we denote its source supply function at stage $j$ as
$\Delta_{i,j}^{v}(\cdot)$. At stage $0$, we have
$\Delta_{i,0}^{v}(v^{\prime})=10^{7}\tilde{\delta}\tau$ if $v^{\prime}=v$ and
$0$ otherwise (i.e. start in stage $0$ with source supply only at node $v$).
As in the excess scaling algorithm in [HRW20], _all the quantities for a flow
problem (i.e. source supply, sink capacity, and edge capacity) in a stage are
specified in some unit_. For stage $i$, the unit is

$\mu_{i}=\lceil\frac{2s}{2^{i}10^{7}\tilde{\delta}\tau}\rceil,$

and in particular the total number of stages $L$ equals the smallest value of
$i$ by which the unit becomes at most $1$. Since $s$ is at most $W_{C}/2$, we
know $L\leq\ln W_{C}=O(\ln m_{C})$ if edge weights are bounded by polynomials
of $m$. For stage $j$, the edge capacity (i.e. total net supply routed over
the edge by all flow problems sharing the same copy of the graph) of $e$ is
$U_{j}\cdot w_{e}$ units, where $w_{e}$ is the edge weight of $e$. We use
$U_{0}=10^{8}\tau^{2}$ and $U_{j}=100\tau$ for $j\geq 1$. The total sink
capacity (shared across all flow problems using the same copy of the graph) of
a node $v$ is always its weighted degree $d^{W}(v)$ units.

We consider all the flow problems sharing the same copy of the graph in
aggregate as one flow problem, and denote the (aggregate) source supply
function as $\Delta_{i,j}(\cdot)$ for the aggregated problem corresponding to
batch $i$ and stage $j$; for stage $0$ since there is one copy of the graph
over all batches, the function $\Delta_{i,0}(\cdot)$ is only for convenience
in the analysis, and we denote the actual aggregate source supply function as
$\Delta_{0}(\cdot)$. For $i,j$, the source function $\Delta_{i,j}(\cdot)$ is
considered as incremental as we add more flow problems to the aggregate
problem, i.e. we add $\Delta_{i,j}^{v}(\cdot)$ to $\Delta_{i,j}(\cdot)$ when a
flow problem in batch $i$ associated with node $v$ reaches stage $j$, and we
solve each aggregate flow problem with one run of the Unit-Flow algorithm with
incremental source supply. Because of how Unit-Flow works, if some supply
introduced by $\Delta_{i,j}^{v}(\cdot)$ is absorbed in a sink during the
execution of Unit-Flow, it will remain absorbed throughout the execution even
with additional source supply introduced later. Similarly, if some supply is
left as excess supply after Unit-Flow terminates with some interim
$\Delta_{i,j}(\cdot)$, the excess must be at a node already at height $h$, and
it will remain as excess even with additional source supply added later. In
particular, this means whenever Unit-Flow finishes with the interim aggregate
flow problem after we add some $\Delta_{i,j}^{v}(\cdot)$ to it, we can tell at
that point whether the flow problem of $v$ is successful for stage $j$ or not,
and we know which of the supply introduced in $\Delta_{i,j}^{v}(\cdot)$ will
be absorbed or be excess (without even knowing the complete aggregate flow
problem in future).

The source supply function $\Delta_{i,j+1}^{v}(\cdot)$ is defined to be double
the amount of absorbed supply on each node, more specifically it is defined as
follows: Let $f_{i,j}^{v}(v^{\prime})$ be the total amount of supply
introduced by $\Delta_{i,j}^{v}(\cdot)$ that gets routed to any node
$v^{\prime}$ by Unit-Flow, and let $\operatorname{ex}_{i,j}^{v}(v^{\prime})$
be the amount of excess (from that flow) routed to $v^{\prime}$, then formally
we set

$\Delta_{i,j+1}^{v}(v^{\prime})=2\left(f_{i,j}^{v}(v^{\prime})-\operatorname{ex}_{i,j}^{v}(v^{\prime})\right)\qquad\forall
v^{\prime}.$

Note that the excess also depends on the earlier flow problems using this copy
of the graph since the sink capacities are shared. Recall that each flow
problem starts with supply $10^{7}\tilde{\delta}\tau$ (in unit $\mu_{0}$) at
stage $0$, and if all supply has been carried over into the next stage (i.e.
no excess) since stage $0$, the amount of supply at stage $j$ would increase
to $2^{j}10^{7}\tilde{\delta}\tau$ (in unit $\mu_{j}$ since
$\mu_{0}=2^{j}\mu_{j}$). We call a flow problem _successful at stage $j$_ if
at the end of stage $j$, the amount of supply for the flow problem being
absorbed by sinks, i.e. $\sum_{v^{\prime}}f_{i,j}^{v}(v^{\prime})$, is at
least $(1-\frac{j+1}{10(L+1)})2^{j}10^{7}\tilde{\delta}\tau$. Equivalently, a
flow problem reaching stage $j\geq 1$ loses at most a
$\frac{j}{10(L+1)}=O(j/\ln m_{C})$ fraction of the initial source supply as
excess over all previous stages. The absorbed supply on nodes after removing
excess after stage $j$ would serve as the source supply if we proceed the flow
problem to the next stage $j+1$, and the amount would double (i.e. the factor
of $2$ in the formula above for $\Delta_{i,j+1}^{v}(\cdot)$) as we switch to
the unit $\mu_{j+1}=\mu_{j}/2$.

In our Unit Flow computation, we will use $h=\Theta(\tau^{2}\ln m_{G})$ for
stage $0$, and we put $10^{7}\tilde{\delta}\tau$ units of source supply on the
source node for every flow problem. As the source nodes are distinct for
different flow problems and all nodes have weighted degree at least
$\tilde{\delta}$, we know the ratio $\Delta_{0}(v)/d^{W}(v)$ (i.e. $\beta$ in
Theorem 4.1) is at most $O(\tau)$. For all stages $j\geq 1$, we will use
$h=\Theta(\tau\ln m_{G})$ and since we only carry absorbed supply into the
next stage, we have $\beta\leq 2$ in later stages. Note the $2$ comes from the
scaling of unit value from stage $j$ to $j+1$.

##### Termination of the Certification Procedure: Cut or Certification.

Whenever we finish the (incremental) Unit-Flow computation of a flow problem
in a stage, we perform two checks as described below. If none of the checks
passes, we proceed the flow problem to the next stage $j+1$ if it’s successful
for the current stage $j<L$, or start a new flow problem with a new sourve
vertex at stage $0$ if the current flow problem is not successful or it
finishes stage $j=L$.

_Check $1$:_ Recall that if a flow problem is successful after $L$ stages, it
has lost at most a $\frac{L}{10(L+1)}\leq\frac{1}{10}$ fraction of its initial
source supply. Thus, it routes at least $0.9\cdot
10^{7}\tilde{\delta}\tau\cdot\mu_{0}=1.8s$ source supply to sinks. When we
stop with a particular flow problem successfully at stage $L$, we check if
there are already $\frac{W_{C}}{10s}$ successful flow problems at stage $L$ in
the current batch.

If so, we call the current batch _successful_ and start a new batch of flow
problems unless we already have $5000\tau$ successful batches. If we succeed
in constructing $5000\tau$ successful batches, we can certify that $C$ (or a
constant fraction of it) is $s^{\prime}$-strong with $s^{\prime}=s/2$ (see the
proof in Section 5.3).

_Check $2$:_ If Check 1 fails, we check if the result of Unit-Flow for the
(aggregate) flow problem of any stage $j\geq 0$ in the current batch has more
than $\frac{W_{C}}{10^{6}\tau(L+1)}$ excess supply in total. As soon as this
happens, we call this batch _unsuccessful_ and we will show in Section 5.2
that we can find a _relatively balanced_ low conductance cut in component $C$,
i.e., both sides have weighted volume $\Omega(\frac{W_{c}}{\tau^{2}\ln
m_{G}})$. Thus, we stop the certification procedure, divide $C$ along the cut,
leave the cut edges as inter-cluster edges, and continue the certification
procedure on each of the two components, which are both $s$-strong by
definition since $C$ is $s$-strong.

We show that the second stopping condition guarantees that the flow problems
are well-defined. We start with the following lemma bounding the maximum
number of flow problems we may run in a batch and stage (whether the flow
problem is successful or not in the stage).

######  Lemma 5.3.

For any batch $i$ we will work on at most
$\frac{W_{C}}{10^{11}\tilde{\delta}\tau^{2}}$ flow problems in stage $0$, and
at most $\frac{W_{C}}{2\cdot 2^{j}10^{7}\tilde{\delta}\tau}$ flow problems in
any stage $j\geq 1$.

###### Proof.

We start with proving the claim for stage $0$. Assume by contradiction that we
have worked on $\frac{W_{C}}{10^{11}\tilde{\delta}\tau^{2}}$ flow problems in
any batch $i$, but neither of the two stopping conditions are satisfied. In
particular, this means that for every stage $j\geq 0$ the total excess in the
Unit-Flow result of stage $j$ is less than $\frac{W_{C}}{10^{6}\tau(L+1)}$. We
know that in order for a flow problem to reach stage $j$ but not stage $j+1$,
the flow problem must lose at least
$\frac{2^{j}10^{6}\tilde{\delta}\tau}{L+1}$ units (in unit $\mu_{j}$) of
supply in stage $j$ alone (i.e. as excess supply). Thus, dividing the upper-
bound of the total excess in stage $j$ shows that, in any stage $j$, the
number of unsuccessful flow problems is at most
$\frac{W_{C}}{2^{j}10^{12}\tilde{\delta}\tau^{2}}$. Hence, the total number of
flow problems that are unsuccessful over all stages $j\geq 0$ is at most
$\frac{2W_{C}}{10^{12}\tilde{\delta}\tau^{2}}$. As we have started
$\frac{W_{C}}{10^{11}\tilde{\delta}\tau^{2}}$ flow problems in stage $0$, we
must have at least
$\frac{W_{C}}{10^{12}\tilde{\delta}\tau^{2}}=\frac{W_{C}}{10s_{0}}\geq\frac{W_{C}}{10s}$
successful flow problems in stage $L$, which contradicts the assumption that
we haven’t finished this batch.

The claim for any $j\geq 1$ follows the similar argument. In particular, our
analysis above says that the number of flow problems that can be unsuccessful
over all stages $j^{\prime}\geq j$ is at most
$\frac{2W_{C}}{2^{j}10^{12}\tilde{\delta}\tau^{2}}$, and if we already have
$\frac{W_{C}}{2\cdot 2^{j}10^{7}\tilde{\delta}\tau}$ flow problems reaching
stage $j$, we must have at least $\frac{W_{C}}{4\cdot
2^{j}10^{7}\tilde{\delta}\tau}$ of them being successful in stage $L$. Since
$2^{j}\leq 2^{L}=\frac{2s}{10^{7}\tilde{\delta}\tau}$, we have
$\frac{W_{C}}{4\cdot 2^{j}10^{7}\tilde{\delta}\tau}\geq\frac{W_{C}}{4\cdot
2^{L}10^{7}\tilde{\delta}\tau}=\frac{W_{C}}{8s}\geq\frac{W_{C}}{10s},$ which
again is a contradiction.

∎

With the above result, we can show below that there will be enough distinct
nodes in $C$ that we can use as the source node for flow problems in stage
$0$. Furthermore, we show the aggregate flow problem for any batch and stage
has at most $W_{C}/2$ units of supply. This ensures we must get case $(1)$ or
$(3)$ in Theorem 4.1, and if we get case $(3)$ then $A$ (i.e. the side with
excess) must be the smaller side of the cut.

######  Lemma 5.4.

There are enough distinct nodes to serve as source nodes in stage $0$, and in
every stage the total source supply is at most $W_{C}/2$ in any aggregated
flow problem.

###### Proof.

We show first that there are enough source nodes in stage 0 to support all the
(successful or not) flow problems. By Lemma 5.3 we have at most
$\frac{W_{C}}{10^{11}\tilde{\delta}\tau^{2}}$ flow problems in a batch in
stage $0$, so we need at most $\frac{5000\tau
W_{C}}{10^{11}\tilde{\delta}\tau^{2}}=\frac{5W_{C}}{10^{8}\tilde{\delta}\tau}$
nodes to serve as the source node in stage $0$ over all the $5000\tau$
batches. Recall we have WLOG 5.2, so we have up to
$\frac{W_{C}}{2\tilde{\delta}}>\frac{5W_{C}}{10^{8}\tilde{\delta}\tau}$ nodes
to use, which is enough in this case.

Recall that quantities of supply are in the unit $\mu_{j}$ when we discuss
flow in stage $j$. We know the total sink capacity in the graph of stage $0$
(which is shared across all batches) is more than twice the total source
supply as follows. We calculated above that we have at most
$\frac{5W_{C}}{10^{8}\tilde{\delta}\tau}$ flow problems in stage $0$, and we
add $10^{7}\tilde{\delta}\tau$ source supply in each flow problem, so the
total supply is at most $W_{C}/2$. Note the total sink capacity is $W_{C}$ in
the shared graph.

Now we show the total sink capacity in the graph of stage $j\geq 1$ for any
batch $i$ is more than twice of the total supply. Since we work on at most
$\frac{W_{C}}{2\cdot 2^{j}10^{7}\tilde{\delta}\tau}$ flow problems in stage
$j$ by Lemma 5.3, and each flow problem can have at most
$2^{j}10^{7}\tilde{\delta}\tau$ units (in unit $\mu_{j}$) of source supply in
stage $j$ since we start with $10^{7}\tilde{\delta}\tau$ units (in unit
$\mu_{0}$) in stage $0$, and only the absorbed supply goes into the next stage
while the value of one unit being halved. Thus the total supply
$|\Delta_{i,j}(\cdot)|\leq W_{C}/2$ through the procedure for any $i,j$. ∎

###  5.2 The Cut Case

In this section we show that if in any batch $i$ and stage $j$, after Unit-
Flow finishes with a flow problem, if the second stopping condition (i.e.
Check $2$) is satisfied, then we can find a relatively balanced low
conductance cut. Recall in this case we have at least
$\frac{W_{C}}{10^{6}\tau(L+1)}=\Omega(\frac{W_{C}}{\tau\ln m_{G}})$ excess in
the Unit Flow result for the aggregated flow problem of batch $i$ stage $j$.

######  Lemma 5.5.

After (incrementally) running Unit-Flow on a flow problem, if we have at least
$\Omega(\frac{W_{C}}{\tau\ln m_{G}})$ excess in the flow for some stage $j\geq
0$, then we can find a cut $(A,C\setminus A)$ of conductance
$O(\frac{1}{\tau})$ such that

$\min\left({\hbox{\bf vol}}^{W}(A),{\hbox{\bf vol}}^{W}(C\setminus
A)\right)\geq\Omega\left(\frac{W_{C}}{\tau^{2}\ln m_{G}}\right).$

###### Proof.

We will apply Theorem 4.1 to it to show the result. Note that the flow problem
cannot fulfill Case $(1)$ of the theorem since there is excess remaining in
the current pre-flow solution, and we also cannot get case $(2)$ as there is
not enough supply to saturate all sinks since $|\Delta_{i,j}(\cdot)|\leq
W_{C}/2$ for all $i$ and $j$ by Lemma 5.4. Thus, we must get a cut as in case
$(3)$. We look at the parameters of our flow problems show that the
conductance and volume properties in the lemma follow from Theorem
4.1$(3)(b,c)$.

In stage $0$, the source supply we put on any node $v$ is
$10^{7}\tilde{\delta}\tau$, and since $d^{W}(v)\geq\tilde{\delta}$ we know the
$\beta$ in Theorem 4.1 is $O(\tau)$, and $U$ is $10^{8}\tau^{2}$. Recall that
we use $h=\Theta(\tau^{2}\ln m_{G})$ in stage $0$, so Theorem 4.1$(3)(b)$
guarantees the conductance of the cut is $O(\frac{1}{\tau})$. By Lemma 5.4, we
have at most $W_{C}/2$ supply in the aggregate flow problem in each Unit-Flow
computation, so the side $A$ in the returned cut must be the smaller side in
terms of weighted volume. Since
$\operatorname{ex}(T)\geq\Omega(\frac{W_{C}}{\tau\ln m_{G}})$, by Theorem
4.1$(3)(c)$ we know ${\hbox{\bf
vol}}^{W}(A)\geq\Omega\left(\frac{W_{C}}{\tau^{2}\ln m_{G}}\right)$ from our
choice of $U,h,\beta$.

It is straightforward to do the same calculation for stages $j\geq 1$ to show
the conductance and volume guarantees, where we have
$\beta=2,U=100\tau,h=\Theta(\tau\ln m_{G})$ in these stages. ∎

##### Edges on the cut.

When we find a relatively balanced low conductance cut as above, we will break
the $C$ along the cut into $A$ and $C\setminus A$. The edges crossing the cut
are duplicated to exist in both $G\\{A\\}$ and $G\\{C\setminus A\\}$ (as self-
loops) by our definition of these sub-graphs. Note that if $C$ is $s$-strong,
$G\\{A\\}$ and $G\\{C\setminus A\\}$ must also be $s$-strong, even though we
add a copy of each cut edge to both sides. Also since the conductance of the
cut is $O(1/\tau)$, the total weight of the inter-cluster edges is at most a
$O(1/\tau)$ fraction of the weighted volume of the smaller side, so even with
two copies of each cut edge on both side of a cut, we can charge $O(1/\tau)$
to each unit of weight on the smaller side of the cut. Since a unit of weight
can be on the smaller side of a cut at most $O(\ln m_{G})$ times before we get
to a trivial cluster, the total additional weight from adding the cut boundary
edges over all recursive calls starting from the whole graph is at most
$O(\frac{{\hbox{\bf vol}}^{W}(G)\ln m_{G}}{\tau})\leq 0.001{\hbox{\bf
vol}}^{W}(G)$ as we have a large enough $\tau=\Omega(\ln m_{G})$, so for
simplicity we can safely ignore the impact of the additional edges to the
total asymptotic running time.

###  5.3 The Certification Case

In the previous section we showed that if the algorithm terminated in the
second stopping condition (Check $2$), then the algorithm finds a relatively
balanced low conductance cut. Next, we look at the case when the algorithm
terminated in Check $1$. In this section on we will explicitly multiply values
in stage $j$ by the unit $\mu_{j}$ so all quantities are in unit $1$.

We now consider only the flow problems that successfully finishes all $L$
stages. For such a flow problem associated with source node $v$, we call $v$
together with the edges on which its supply was transported an _edge-bundle_
with _center_ $v$. As the algorithm terminated in Check 1, we find $5000\tau$
batches, each with $\frac{W}{10s}$ edge-bundles. That is, each edge-bundle
routes at least $1.8s$ (i.e. $0.9\cdot 10^{7}\tilde{\delta}\tau\cdot\mu_{0}$)
supply to sinks in stage $L$. We start with the following definition.

######  Definition 5.6.

For an edge-bundle with source node $v$ in a $s$-strong component $C$, we call
the edge-bundle _$s$ -captured_ if in stage $0$, the flow problem from $v$ is
successful and at most $0.5s$ of its supply is routed to nodes in $C\setminus
S$ for any cut $S$ in $G$ with ${\hbox{\bf vol}}^{W}(S\cap C)\leq{\hbox{\bf
vol}}^{W}(C\setminus S)$ and cut-size $w(S,G\setminus S)\leq
1.1\tilde{\delta}$. We call an edge-bundle $s$-free if it’s not $s$-captured.

Note in the above definition, since $C$ is $s$-strong w.r.t the same
$\tilde{\delta}$ (Definition 2.1), we know all the cut $S$ being considered
must have ${\hbox{\bf vol}}^{W}(S\cap C)\leq s$. We start with the following
result, which implies that in the case where we successfully get $5000\tau$
bathes each with $\frac{W}{10s}$ edge-bundles, all these edge-bundles are
$s$-free since at least $1.8s>1.6s$ supply is routed to sinks in stage $L$ for
each edge-bundle.

######  Lemma 5.7.

The flow problem corresponding to any $s$-captured edge-bundle cannot have a
total of more than $1.6$s supply routed to sinks in stage $L$.

###### Proof.

Consider any $s$-captured edge-bundle and a corresponding cut $S$. By
definition at most $0.5s$ supply is routed to $C\setminus S$ in stage $0$. The
remaining at least $1.5s$ supply is inside $C\cap S$ after stage $0$, and we
can look at how much can be routed into $C\setminus S$ in later stages.

By our choice of edge capacity for edge $e$ being
$U_{j}\mu_{j}w_{e}=100\tau\frac{2s}{2^{j}10^{7}\tilde{\delta}\tau}w_{e}$ in
stage $j\geq 1$, we know that over all later stages, the total edge capacity
is at most $\frac{2sw_{e}}{10^{5}\tilde{\delta}}$ for edge $e$. If we sum over
all edges across the cut $C\cap S$ and $C\setminus S$, the total capacity is
at most $\frac{2s\cdot 1.1\tilde{\delta}}{10^{5}\tilde{\delta}}$, so we can
route at most $0.1s$ supply into $C\setminus S$.

In total this means at most $0.6s$ supply can be routed to nodes (and thus
absorbed by sinks) in $C\setminus S$ over all $L$ stages. The nodes in $C\cap
S$ can absorb at most $s$ supply since ${\hbox{\bf vol}}^{W}(C\cap S)\leq s$,
so in total at most $1.6s$ supply can be absorbed by sinks. ∎

######  Lemma 5.8.

There are at most $50\tau$ edge-bundles that are $s$-free but with centers
inside a cut $S$ such that ${\hbox{\bf vol}}^{W}(S\cap C)\leq{\hbox{\bf
vol}}^{W}(C\setminus S)$ and $w(S\cap C,C\setminus S)\leq 1.1\tilde{\delta}$.

###### Proof.

For an edge-bundle with center inside $C\cap S$ to be $s$-free, the flow
problem must send at least $0.5s$ supply from $v\in C\cap S$ to nodes in
$C\setminus S$ in stage $0$. The total edge capacity across $C\cap S$ to
$C\setminus S$ in stage $0$ is at most $U_{0}\mu_{0}\cdot
1.1\tilde{\delta}=10^{8}\tau^{2}\frac{2s}{10^{7}\tilde{\delta}\tau}1.1\tilde{\delta}\leq
22s\tau$, so we can have at most $\frac{22s\tau}{0.5s}\leq 50\tau$ such edge-
bundles. ∎

We construct a new flow problem $\Pi_{F}$ based on all the successful stage
$L$ flows we get as follows. There are in total
$5000\tau\cdot\frac{W_{C}}{10s}$ such flow problems, and in the stage-$L$ pre-
flow result for each of them, we have at least $1.8s$ supply absorbed in
sinks. We aggregate the absorbed supply over all the
$5000\tau\cdot\frac{W_{C}}{10s}$ pre-flows, and scale the amount down by
$500\tau$, and we will use the result amount of supply on each node as the
source supply function $\tilde{\Delta}$ for our new flow problem $\Pi_{F}$.
The sink capacity of any node $v$ in our new flow problem will again be
$d^{W}(v)$.

######  Observation 5.9.

The total amount of source supply in $\Pi_{F}$ is more than the total sink
capacity (i.e. $W_{C}$), since
$|\tilde{\Delta}(\cdot)|\geq\frac{1.8s}{500\tau}\frac{5000\tau
W_{C}}{10s}=1.8W_{C}>W_{C}$. Moreover,
$\tilde{\Delta}(v)\leq\frac{5000\tau\cdot d^{W}(v)}{500\tau}=10d^{W}(v)$,
since pre-flows in the same batch share the sink capacity $d^{W}(v)$.

Note that any source supply in $\tilde{\Delta}$ on some node $v$ is a result
of our previous flow problems, that is, the supply on $v$ must be from either
the initial source supply we put on $v$ in stage $0$, or being routed to $v$
by the pre-flows over the stages $0,\ldots L$. Consider any cut $S$ being
considered in the definition of $s$-captured, we first bound the amount of
source flow in $\tilde{\Delta}$ on nodes in $S\cap C$.

######  Lemma 5.10.

For any cut $S$ such that $w(S,G\setminus S)\leq 1.1\tilde{\delta}$ and
${\hbox{\bf vol}}^{W}(S\cap C)\leq{\hbox{\bf vol}}^{W}(C\setminus S)$, we have
$\tilde{\Delta}(C\cap S)\leq s/4$

###### Proof.

We first bound the amount of supply inside $S$ from the initial source supply
we put on nodes in $S$ in stage $0$. By Lemma 5.7 and Lemma 5.8, at most
$50\tau$ nodes in $S$ are centers of the edge-bundles we include, so the total
amount of supply is at most $50\tau\cdot 2s=100\tau s$.

Now we bound the amount of supply that can be routed in to $S$ by the pre-
flows. For stage $0$, since all flow problems share a single copy of the
graph, the total supply can be routed into $S$ over all of them is at most the
total capacity into $S$, which is

$U_{0}\cdot w(S\cap C,C\setminus S)\cdot\mu_{0}\leq 10^{8}\tau^{2}\cdot
1.1\tilde{\delta}\cdot\frac{2s}{10^{7}\tilde{\delta}\tau}\leq 22\tau s.$

For stages $1,\ldots,L$, the different batches don’t share edge capacities, so
the total capacity into $S$ is

$\displaystyle 5000\tau\cdot w(S\cap C,C\setminus
S)\cdot\sum_{j=1}^{L}U_{j}\mu_{j}\leq$ $\displaystyle 5000\tau\cdot
1.1\tilde{\delta}\cdot 2U_{1}\mu_{1}$ $\displaystyle=$ $\displaystyle
5000\tau\cdot 1.1\tilde{\delta}\cdot
100\tau\cdot\frac{2s}{10^{7}\tilde{\delta}\tau}\leq\tau s.$

Since we scale the supply down by $500\tau$ to get $\tilde{\Delta}$, we know

$\tilde{\Delta}(S\cap C)\leq\frac{100\tau s+22\tau s+\tau
s}{500\tau}\leq\frac{s}{4}.$

∎

For the flow problem $\Pi_{F}$, we will again use $U=100\tau$ and call Unit-
Flow with $h=\Theta(\tau\ln m_{G})$, and we have the following result.

######  Lemma 5.11.

We can either certify $C$ is $s/2$-strong, or find a cut $A\subsetneq C$ such
that $\Phi_{C}(A)=\frac{w(A,C\setminus A)}{\min({\hbox{\bf
vol}}^{W}(A),{\hbox{\bf vol}}^{W}(C\setminus A))}\leq\tau$, ${\hbox{\bf
vol}}^{W}(A)=\Theta(W_{C})$ and $A$ is $s/2$-strong.

###### Proof.

Consider any cut $S$ as in Lemma 5.10, we first show that the set $\tilde{C}$
of nodes whose sinks are saturated in the Unit-Flow result of $\Pi_{F}$ must
have ${\hbox{\bf vol}}^{W}(\tilde{C}\cap S)\leq s/2$. This is because at most
$s/4$ supply starts in $S$ by Lemma 5.10, and in the pre-flow for $\Pi_{F}$,
the additional supply that can be routed into $S$ is bounded by the total edge
capacity into $S$, which by our choice of $U$ is at most $100\tau\cdot
1.1\tilde{\delta}\leq s_{0}/\tau<s/\tau$, and thus the total supply in $S$
when Unit-Flow finishes is at most $s/2$, and thus ${\hbox{\bf
vol}}^{W}(\tilde{C}\cap S)\leq s/2$. Note this certified that $\tilde{C}$ (and
thus any subset of it) is $s/2$-strong.

By 5.9, we know there must be excess in the pre-flow from Unit-Flow, so we
cannot get case $(1)$ in Theorem 4.1. If we get case $(2)$, then we know
$C=\tilde{C}$ and by the above argument ${\hbox{\bf vol}}^{W}(C\cap S)\leq
s/2$ for all such $S$, which certifies $C$ is $s/2$-strong. If we get case
$(3)$, let $(A,C\setminus A)$ be the returned cut. We know all nodes in $A$
are saturated, i.e. $A\subset\tilde{C}$, so $A$ is $s/2$-strong. The claim on
conductance $\Phi(A)$ and volume ${\hbox{\bf vol}}^{W}(A)$ follow $(3)(b)$ and
$(3)(c)$ in Theorem 4.1 respectively by our choice of
$U=100\tau,h=\Theta(\tau\ln W_{C})$, and note by 5.9 $\beta\leq
10,\operatorname{ex}(T)\geq 0.8W_{C}$. ∎

We conclude this section with the proof of the main lemma of $s_{0}$-strong
partition. *

###### Proof.

Our procedure starts with the graph $G$, and recursively running the
certification procedure until all components are certified to be
$s_{0}$-strong. Note a component with weighted volume at most $s_{0}$ is by
definition $s_{0}$-strong. Thus, if for any component $C$ we always divide it
along a relatively balanced low conductance cut whose smaller side has
weighted volume at least $\Omega({\hbox{\bf
vol}}^{W}(C)/\operatorname{polylog}{\hbox{\bf vol}}^{W}(G))$, then the depth
of our recursion is at most $O(\operatorname{polylog}{\hbox{\bf vol}}^{W}(G))$
until all components have weighted volume at most $s_{0}$.

In our certification procedure, the only case when we don’t divide $C$ along a
relatively balanced cut is in the case of Section 5.3 where we get a cut
$(A,C\setminus A)$ as in Lemma 5.11. Since ${\hbox{\bf
vol}}^{W}(A)=\Theta({\hbox{\bf vol}}^{W}(C))$, if it is not relatively
balanced, we know $A$ must be the larger side, and we certify it’s
$s/2$-strong. Thus, when we cannot find a relatively balanced cut, we make
progress by certifying a smaller strength on the larger side of the cut (or
possibly the entire component $C$). This can happen at most
$\ln\frac{{\hbox{\bf vol}}^{W}(G)}{s_{0}}$ times before we are done with the
component. Consequently, when we look at both cases (i.e. cut or certify), the
depth of the recursion is at most $O(\operatorname{polylog}{\hbox{\bf
vol}}^{W}(G))$ since in each level we either decrease the weighted volume by a
factor of $1-\Omega(1/\operatorname{polylog}{\hbox{\bf vol}}^{W}(G))$ or
certify a strength of $1/2$ the current certified strength for the larger side
of the unbalanced cut.

The running time of our certification procedure for a component $C$ is
$\tilde{O}(m_{C})$ if $C$ has $m_{C}$ edges. This is because we run one Unit-
Flow computation for the aggregate flow problem in each stage and each batch,
so $L\cdot 5000\tau=O(\tau\ln m_{C})$ of them in total (plus the last flow
problem $\Pi_{F}$ if needed). Each of the Unit-Flow computation takes time
$\tilde{O}(m_{C}\cdot h)$ by Theorem 4.1, which is at most
$\tilde{O}(m_{C}\tau^{2})$ by our choice of $h$, i.e. $h=\tau^{2}\ln m_{G}$
for stage $0$, and $h=\tau\ln m_{G}$ for all later stages and $\Pi_{F}$. In
total, the running time of all the Unit-Flow calls take
$\tilde{O}(m_{C}\tau^{3})$ in the certification procedure of $C$. By our
earlier discussion, the recursion depth of the partition procedure is at most
$O(\operatorname{polylog}{\hbox{\bf vol}}^{W}(G))$, the total running time for
all the Unit-Flow calls over all components is $\tilde{O}(m_{G}\tau^{3})$.

As to the total weight of edges between distinct components, since we only
divide a component along cut of conductance at most $O(1/\tau)$, so we can
charge the weight of cut edges to the weighted volume of the smaller side of
the cut. Since one unit of volume can be on the smaller side of a cut at most
$O(\ln{\hbox{\bf vol}}^{W}(G))$ times before we stop, each unit of weight is
charged at most $O(\frac{\ln m_{G}}{\tau})$, so the total weight of edges
between components is $O(\frac{{\hbox{\bf vol}}^{W}(V)\ln|V|}{\tau})$
(assuming polynomially bounded edge weights). Given our choice of
$\tau=\Theta(\sqrt{s_{0}/\tilde{\delta}})=\Theta(\ln^{c/2}|V|)$, the running
time is $\tilde{O}(m_{G}\tau^{3})=\tilde{O}(m_{G})$ as in the lemma statement.
The weight of edges between components is
$O(\frac{\ln|V|}{\tau})\cdot{\hbox{\bf vol}}^{W}(G)$, which is
$O(\frac{\sqrt{\tilde{\delta}}\ln|V|}{\sqrt{s_{0}}})\cdot{\hbox{\bf
vol}}^{W}(G)$ as claimed in the lemma. ∎

##  6 From $s_{0}$-strength to efficient uncrossing.

Recall that an $s_{0}$-strong decomposition, ${\cal D}$, of a graph $G$ is a
decomposition of $V$ in which any min-cut, $S$, has at most volume $s_{0}$ in
common with any cluster $A\in{\cal D}$ in the decomposition, i.e., the volume
of $A\cap S$ is at most $s_{0}$.

In this section, we convert such a decomposition into a decomposition, ${\cal
D^{\prime}}$ such that for any min-cut $S$ and cluster $A\in{\cal D^{\prime}}$
an uncrossing of the cut $S$ with $A$ does not locally increase the cut-size
“too much”. Recall the definition of boundary-sparsity given in Definition
2.3.

Intuitively, for a cut $S$ that crosses $A$, if $S\cap A$ is not
$\beta$-boundary-sparse in $A$, then uncrossing $S$ with respect to $A$ only
increases the cut size by a small amount proportional to $1/\beta$. In other
words, we want to find $\beta$-boundary-sparse cuts in $A$ since these are the
cuts that do not allow for cheap uncrossing. Ideally, in our final
decomposition, no cluster would contain any $\beta$-boundary-sparse sets. In
reality, we will only be able to achieve a slightly relaxed version of this
statement; see Section 3 below.

We will proceed by considering each cluster in the original decomposition and
further decomposing it as necessary. In Section 6.1, we give a procedure that
works for clusters that have volume $\tilde{O}(s_{0})$ and, thus, consist of
$\tilde{O}(1)$ vertices. We call such clusters _small_ clusters. In Section
6.2 we give a procedure for _large_ clusters, i.e. clusters that are not
small.

###  6.1 Efficient uncrossing for small clusters.

Recall that a small cluster contains $\tilde{O}(1)$ vertices. Thus a running
time that is polynomial in the number of vertices of $A$ is sufficient for our
purpose. Throughout this section we assume that $\tilde{\lambda}\leq
1.01\lambda$ is an approximate lower bound of the minimum cut value that is
available to our algorithm.

To prove Section 3, we will need the following helper lemma, whose proof is
standard.

######  Theorem 6.1.

Given a weighted graph $H$ and a parameter $\alpha\geq 1$, there is a
deterministic algorithm that enumerates all $\alpha$-approximate minimum cuts
of $H$, of which there are $O(n^{\lfloor 2\alpha\rfloor})$. The algorithm runs
in time $\tilde{O}(m^{2}n^{\lfloor 2\alpha\rfloor})\leq\tilde{O}(n^{\lfloor
2\alpha\rfloor+4})$.

###### Proof.

First, compute a maximum (spanning) tree packing of $H$, which can be done in
$\tilde{O}(mn)$ time [Bar95] to produce a packing of $\tilde{O}(m)$ trees. It
was shown in [Kar00]) that for any $\alpha$-approximate minimum cut $S$, there
is a tree $T$ in a maximum tree packing for which $\partial_{T}S\leq 2\alpha$,
i.e., at most $2\alpha$ many edges of $T$ cross the cut $S$. The algorithm
iterates over all $\tilde{O}(m)$ trees in the packing, and for each tree $T$,
considers all ways to remove at most $2\alpha$ edges, group the components
together into two sides of a cut, and determine the size of the cut. For
constant $\alpha$, this takes $O(mn^{\lfloor 2\alpha\rfloor})$ time per tree,
for a total of $\tilde{O}(m^{2}n^{\lfloor 2\alpha\rfloor})$ time. The
algorithm then computes the minimum cut $\lambda$ over this collection, which
is the minimum cut of $G$, and outputs the subcollection of cuts of value at
most $\alpha\lambda$. The bound of $O(n^{\lfloor 2\alpha\rfloor})$ for the
number of such cuts was shown in [Kar00]. ∎

We now prove Section 3. The algorithm for Section 3 has two stages. The first
stage, described in the next lemma, decomposes $A$ into clusters such that (a)
each has boundary size $O(\tilde{\lambda})$ and minimum cut in the induced
graph of at least $0.49\tilde{\lambda}$ and (b) the size of the sum of their
boundaries is small, namely $O(\epsilon^{-1}\partial A)$. These clusters are
further broken down in the next stage given in Lemma 6.3. To shorten the
notation given a cluster $A$ and a set $U\subseteq A$, we use $\partial U$ to
denote $w(U,\bar{U})$ and $\partial_{G[A]}U$ to denote $w(U,A\setminus U)$.

######  Lemma 6.2.

Let $A\subseteq V$ be a cluster. Suppose an algorithm is given a mincut
estimate $\tilde{\lambda}\in[\lambda,1.01\lambda]$. Then, the algorithm can
decompose $A$ into a disjoint union of clusters $A_{1}\cup A_{2}\cup\cdots\cup
A_{k}=A$ such that

  1. 1.

For each cluster $A_{i}$, either $\partial A_{i}\leq 3\tilde{\lambda}$ or
there is no $(1-\epsilon)$-boundary-sparse set $U$ in $A_{i}$ with
$\partial_{G[A_{i}]}U\leq 1.01\tilde{\lambda}$.

  2. 2.

The sum of boundaries $\sum_{i}\partial A_{i}$ is $O(\epsilon^{-1}\partial
A)$.

  3. 3.

For each cluster $A_{i}$, the induced graph $G[A_{i}]$ has minimum cut at
least $0.49\tilde{\lambda}$.

The algorithm takes time $\tilde{O}(|A|^{9})$.

###### Proof.

We first describe an algorithm that fulfills the first two properties. At the
end, we augment it to satisfy property (3).

_Property 1._ Given a cluster $A$ the algorithm maintains a current
decomposition $\mathcal{D}$, initialized to the singleton set $\\{A\\}$. The
algorithm iteratively considers sets in $\mathcal{D}$ that have not been
processed yet until all have been processed, starting with $A$. For a given
set $A^{\prime}$, the algorithm does the following.

First, if $\partial A^{\prime}\leq 3\tilde{\lambda}$, then the algorithm keeps
$A^{\prime}$ as is, declares $A^{\prime}$ as processed, and proceeds to the
next set in $\mathcal{D}$. Otherwise, it applies the algorithm of Theorem 6.1
to the induced graph $G[A^{\prime}]$ for $\alpha=2.1$, which takes
$\tilde{O}(|A^{\prime}|^{8})$ time, and let $\mathcal{C}$ be the set of
returned cuts. Compute the cut $U^{*}\in\mathcal{C}$ such that
$\partial_{G[A^{\prime}]}U^{*}$ is the smallest cut over all cuts in
$\mathcal{C}$. By the choice of $\mathcal{C}$, $U^{*}$ is the minimum cut in
$G[A^{\prime}]$. We now have a few cases.

  1. (a)

If $\partial_{G[A^{\prime}]}U^{*}\leq 0.49\tilde{\lambda}$, then the algorithm
decomposes $A^{\prime}$ into $U^{*}$ and $A^{\prime}\setminus U^{*}$, i.e., it
removes $A^{\prime}$ from $\mathcal{D}$ and adds the unprocessed sets $U^{*}$
and $A^{\prime}\setminus U^{*}$ to $\mathcal{D}$. (The sets $U^{*}$ and
$A^{\prime}\setminus U^{*}$ are processed at a later iteration.)

  2. (b)

If $\partial_{G[A^{\prime}]}U^{*}>0.49\tilde{\lambda}$, then it follows from
our choice of $\alpha=2.1$ that the collection $\mathcal{C}$ contains all sets
$U\subseteq A^{\prime}$ with $\partial_{G[A^{\prime}]}U\leq
1.01\tilde{\lambda}$. The algorithm iterates over all sets in $\mathcal{C}$
and looks for one that is $(1-\epsilon)$-boundary-sparse and has boundary size
$\leq 1.01\tilde{\lambda}$. If a $(1-\epsilon)$-boundary-sparse set with
boundary size $\leq 1.01\tilde{\lambda}$ does not exist, then the algorithm
keeps $A^{\prime}$ as is, declares $A^{\prime}$ as processed, and proceeds to
the next set in $\mathcal{D}$. Otherwise, let $U$ be an arbitrary
$(1-\epsilon)$-boundary-sparse set with boundary size $\leq
1.01\tilde{\lambda}$. The algorithm decomposes $A^{\prime}$ into $U$ and
$A^{\prime}\setminus U$, i.e., removes $A^{\prime}$ from $\mathcal{D}$ and
adds the unprocessed sets $U$ and $A^{\prime}\setminus U$ into $\mathcal{D}$.
(The sets $U$ and $A^{\prime}\setminus U$ are processed at a later iteration.)

All sets in the final decomposition satisfy property (1) by construction. As
each iteration of the algorithm processes one set, each set is processed only
once, and the collection of processed sets forms a laminar family, there are
at most $|A|$ many iterations. As each iteration takes time
$\tilde{O}(|A|^{8})$, the total running time is $\tilde{O}(|A|^{9})$.

_Property 2._ Let $\mathcal{D}_{1}$ be the decomposition of $A$ at the end of
the algorithm. If $\partial A\leq 3\tilde{\lambda}$ then the algorithm does
nothing and property (2) is trivially true. Otherwise, assume that the
algorithm decomposes $A$. Throughout the algorithm, we maintain a potential
function

$\Phi(\mathcal{D})=\sum_{A^{\prime}\in\mathcal{D}}\max\\{0,\partial
A^{\prime}-2.1\tilde{\lambda}\\}.$

The initial value of $\Phi(\mathcal{D})=\Phi(\\{A\\})=O(\partial A).$ We will
show (1) that $\Phi(\mathcal{D})$ does not increase throughout the
decomposition, which implies that $\Phi(\mathcal{D}_{1})\leq\Phi(\\{A\\})$.
Moreover, we show that (2) each time a set $A^{\prime}$ with $\partial
A^{\prime}\leq 2.2\tilde{\lambda}$ is added to $\mathcal{D}$, the potential
$\Phi(\mathcal{D})$ drops by at least $\Omega(\epsilon\tilde{\lambda})$. These
two claims together imply property (2) because

$\displaystyle\sum_{A^{\prime}\in\mathcal{D}_{1}}\partial A^{\prime}$
$\displaystyle=\sum_{A^{\prime}\in\mathcal{D}_{1}:\partial A^{\prime}\leq
2.2\tilde{\lambda}}\partial
A^{\prime}+\sum_{A^{\prime}\in\mathcal{D}_{1}:\partial
A^{\prime}>2.2\tilde{\lambda}}\partial A^{\prime}$
$\displaystyle\leq\frac{\Phi(\\{A\\})}{\Omega(\epsilon\tilde{\lambda})}\cdot
0.1\tilde{\lambda}+O(\Phi(\mathcal{D}_{1}))\leq O(\Phi(\\{A\\})/\epsilon)\leq
O(\partial A/\epsilon).$

To show the two claims, suppose a set $A^{\prime}$ is decomposed into $U$ and
$A^{\prime}\setminus U$ for some $U\subseteq A^{\prime}$. By construction, we
always have $\partial_{G[A^{\prime}]}U\leq 1.01\tilde{\lambda}$. If $\partial
U$ and $\partial(A^{\prime}\setminus U)$ are both at least
$2.1\tilde{\lambda}$, then the net increase in $\Phi(\mathcal{D})$ is

$\displaystyle\max\\{0,\partial
U-2.1\tilde{\lambda}\\}+\max\\{0,\partial(A^{\prime}\setminus
U)-2.1\tilde{\lambda}\\}-\max\\{0,\partial A^{\prime}-2.1\tilde{\lambda}\\}$
$\displaystyle=(\partial U-2.1\tilde{\lambda})+(\partial(A^{\prime}\setminus
U)-2.1\tilde{\lambda})-(\partial A^{\prime}-2.1\tilde{\lambda})$
$\displaystyle=2w(U,A^{\prime}\setminus U)-2.1\tilde{\lambda}\leq 2\cdot
1.01\tilde{\lambda}-2.1\tilde{\lambda}<-0.08\tilde{\lambda}.$

If $\partial U$ and $\partial(A^{\prime}\setminus U)$ are both at most
$2.1\tilde{\lambda}$, then the net increase in $\Phi(\mathcal{D})$ is

$\displaystyle\max\\{0,\partial
U-2.1\tilde{\lambda}\\}+\max\\{0,\partial(A^{\prime}\setminus
U)-2.1\tilde{\lambda}\\}-\max\\{0,\partial A^{\prime}-2.1\tilde{\lambda}\\}$
$\displaystyle\leq 0+0-(\partial A^{\prime}-2.1\tilde{\lambda})\leq
0+0-(3\tilde{\lambda}-2.1\tilde{\lambda})\leq-0.9\tilde{\lambda}.$

Else, suppose without loss of generality that $\partial U\leq
2.1\tilde{\lambda}\leq\partial(A^{\prime}\setminus U)$. The net increase in
$\Phi(\mathcal{D})$ is

$\displaystyle\max\\{0,\partial
U-2.1\tilde{\lambda}\\}+\max\\{0,\partial(A^{\prime}\setminus
U)-2.1\tilde{\lambda}\\}-\max\\{0,\partial A^{\prime}-2.1\tilde{\lambda}\\}$
$\displaystyle=0+(\partial(A^{\prime}\setminus
U)-2.1\tilde{\lambda})-(\partial A^{\prime}-2.1\tilde{\lambda})$
$\displaystyle=\partial(A^{\prime}\setminus U)-\partial A^{\prime}$
$\displaystyle=w(U,A^{\prime}\setminus U)-w(U,\overline{A^{\prime}}).$

If $\partial_{G[A^{\prime}]}U\leq 0.49\tilde{\lambda}$, i.e., the algorithm
went through case (a), then

$w(U,\overline{A^{\prime}})=\partial U-w(U,A^{\prime}\setminus
U)\geq\lambda-0.49\tilde{\lambda}\geq
0.99\tilde{\lambda}-0.49\tilde{\lambda}=0.5\tilde{\lambda},$

and the net increase in $\Phi(\mathcal{D})$ is

$w(U,A^{\prime}\setminus U)-w(U,\overline{A^{\prime}})\leq
0.49\tilde{\lambda}-0.5\tilde{\lambda}<-0.01\tilde{\lambda}.$

If $\partial_{G[A^{\prime}]}U>0.49\tilde{\lambda}$, i.e., case (b), then $U$
is $(1-\epsilon)$-boundary-sparse in $A^{\prime}$ by construction, so the net
increase in $\Phi(\mathcal{D})$ is

$w(U,A^{\prime}\setminus U)-w(U,\overline{A^{\prime}})\leq
w(U,A^{\prime}\setminus U)-\frac{w(U,A^{\prime}\setminus
U)}{1-\epsilon}\leq-\Omega(\epsilon w(U,A^{\prime}\setminus
U))\leq-\Omega(\epsilon\tilde{\lambda}).$

This concludes the proof that the algorithm that fulfills the properties (1)
and (2).

_Property 3._ To satisfy property (3), we take the decomposition
$\mathcal{D}_{1}$ after termination of the algorithm above and, while there
exists a cluster $A^{\prime}$ in the current decomposition whose induced graph
$G[A^{\prime}]$ has minimum cut $0.49\tilde{\lambda}$ or less, we find the
minimum cut $U^{*}\subseteq A^{\prime}$ and decompose $A^{\prime}$ into
$U^{*}$ and $A^{\prime}\setminus U^{*}$. Computing the minimum cut can be done
by applying Theorem 6.1 for $\alpha=1$, which takes
$\tilde{O}(|A^{\prime}|^{6})$ time.

We claim that this additional step increases
$\sum_{A^{\prime}\in\mathcal{D}_{1}}\partial A^{\prime}$ by only a constant
factor. Let $\mathcal{D}$ be the decomposition during this process and let
$\mathcal{D}_{2}$ be the decomposition at the end of this process. Consider
the potential function

$\Phi^{\prime}(\mathcal{D})=\sum_{A^{\prime}\in\mathcal{D}}(\partial
A^{\prime}-0.98\tilde{\lambda}).$

Note that
$\Phi^{\prime}(\mathcal{D}_{1})\leq\sum_{A^{\prime}\in\mathcal{D}_{1}}\partial
A^{\prime}$. Since $\partial
A^{\prime}\geq\lambda\geq\frac{1}{1.01}\tilde{\lambda}\geq
0.99\tilde{\lambda}$, we have $\partial A^{\prime}\leq 99(\partial
A^{\prime}-0.98\tilde{\lambda})$ and $\sum_{A^{\prime}\in\mathcal{D}}\partial
A^{\prime}\leq O(\Phi^{\prime}(\mathcal{D}))$. In particular,
$\sum_{A^{\prime}\in\mathcal{D}_{2}}\partial A^{\prime}\leq
O(\Phi^{\prime}(\mathcal{D}_{2}))$. We will show that
$\Phi^{\prime}(\mathcal{D})$ does not increase over time. This shows the claim
as it implies that $\sum_{A^{\prime}\in\mathcal{D}_{2}}\partial A^{\prime}\leq
O(\Phi^{\prime}(\mathcal{D}_{2}))\leq
O(\Phi^{\prime}(\mathcal{D}_{1}))=O(\sum_{A^{\prime}\in\mathcal{D}_{1}}\partial
A^{\prime})$. To show that $\Phi^{\prime}$ does not increase upon decomposing
some $A^{\prime}\in\mathcal{D}$ into $U$ and $A^{\prime}\setminus U$, the net
increase of $\Phi^{\prime}(\mathcal{D})$ is

$(\partial U-0.98\tilde{\lambda})+(\partial(A^{\prime}\setminus
U)-0.98\tilde{\lambda})-(\partial
A^{\prime}-0.98\tilde{\lambda})=2w(U,A^{\prime}\setminus
U)-0.98\tilde{\lambda}\leq 2\cdot 0.49\tilde{\lambda}-0.98\tilde{\lambda}\leq
0,$

proving the claim. This concludes the proof. ∎

Using Lemma 6.2 as a first step, we now apply the following lemma to each
cluster with boundary at most $3\tilde{\lambda}$ output by Lemma 6.2.

######  Lemma 6.3.

Let $A\subseteq V$ be a cluster satisfying the following two guarantees:

  * •

$\partial A\leq 3\tilde{\lambda}$, and

  * •

the minimum cut of $G[A]$ is at least $0.49\tilde{\lambda}$.

Let $0<\epsilon\leq 0.01$ be a parameter. Suppose an algorithm is given a
mincut estimate $\tilde{\lambda}\in[\lambda,1.01\lambda]$. Then, the algorithm
can decompose $A$ into a disjoint union of clusters $A_{1}\cup
A_{2}\cup\cdots\cup A_{k}=A$ such that

  1. 1.

For any set $S\subseteq A$ with $\partial_{G[A]}S\leq 1.01\tilde{\lambda}$,
there is a partition $\mathcal{P}$ of $\\{A_{1},A_{2},\ldots,A_{k}\\}$ such
that for each part $P\in\mathcal{P}$, the set $S\cap\bigcup_{A^{\prime}\in
P}A^{\prime}$ is non-$(1-\epsilon)$-boundary-sparse in $\bigcup_{A^{\prime}\in
P}A^{\prime}$.

  2. 2.

There are at most $O(\epsilon^{-2}(\log|A|)^{O(1)})$ many clusters, and each
cluster $A_{i}$ satisfies $\partial A_{i}\leq\partial A$.

The algorithm runs in time $\tilde{O}(|A|^{8})$.

###### Proof.

Apply Theorem 6.1 for $\alpha=2.1$ to obtain, in time $\tilde{O}(|A|^{8})$, a
collection $\mathcal{C}_{0}$ of $\tilde{O}(|A|^{4})$ sets that contains all
$\emptyset\subsetneq U\subsetneq A$ with $\partial_{G[A]}U\leq
1.01\tilde{\lambda}$. Take the subcollection
$\mathcal{C}\subseteq\mathcal{C}_{0}$ of all $U\in\mathcal{C}$ with
$\partial_{G[A]}U\leq 1.01\tilde{\lambda}$. The rest of the algorithm
recursively decomposes an input cluster $A^{\prime}$ (starting with
$A^{\prime}=A$) while keeping a set $\mathcal{C}^{\prime}\subseteq\mathcal{C}$
that starts as $\mathcal{C}^{\prime}=\mathcal{C}$ and may lose elements over
time.

Initially, the algorithm removes from $\mathcal{C}^{\prime}$ all cuts
$C\in\mathcal{C}^{\prime}$ such that $C\cap A^{\prime}$ is not
$(1-\epsilon)$-boundary sparse in $A^{\prime}$. We call this the initial
_pruning_ step. The recursive algorithm then considers the following cases in
order:

  1. (a)

If there is $C\in\mathcal{C}^{\prime}$ that crosses $A^{\prime}$ such that
$\partial_{G[A^{\prime}]}(C\cap A^{\prime})\leq 0.4\tilde{\lambda}$, decompose
$A^{\prime}$ into $C\cap A^{\prime}$ and $A^{\prime}\setminus C$ and
recursively call $C\cap A^{\prime}$ and $A^{\prime}\setminus C$ with the
updated $\mathcal{C}^{\prime}$.

  2. (b)

Otherwise, if there exists $C\in\mathcal{C}^{\prime}$ that crosses
$A^{\prime}$ , take a set $C\in\mathcal{C}^{\prime}$ with minimum $|C\cap
A^{\prime}|$ crossing $A^{\prime}$. Decompose $A^{\prime}$ into $C\cap
A^{\prime}$ and $A^{\prime}\setminus C$ and recursively call $C\cap
A^{\prime}$ and $A^{\prime}\setminus C$ with the updated
$\mathcal{C}^{\prime}$.

  3. (c)

Otherwise, return the trivial decomposition $A^{\prime}$.

_Running time analysis._ In the initial pruning step, the algorithm can check
each of the $\tilde{O}(|A|^{4})$ sets in $\mathcal{C}^{\prime}$ in
$O(|A|^{2})$ time. As the set of processed sets forms a laminar family, there
are $O(|A|)$ many recursive instances, so the recursive algorithm takes time
$\tilde{O}(|A|^{7})$. Together with the initial $\tilde{O}(|A|^{8})$ time to
compute $\mathcal{C}^{\prime}$, this establishes the running time.

_Correctness: Property ( 1)._ We first show that the resulting decomposition
satisfies property (1) of the lemma. Consider a set $S\subseteq A$ with
$\partial_{G[A]}S\leq 1.01\tilde{\lambda}$. If $S=\emptyset$ or $S=A$, then
property (1) is trivial because $\emptyset$ and $A$ are always
non-$(1-\epsilon)$-boundary sparse in $A$.

Thus we are left with proving property (1) if $S$ is a cut in $A$. Since
$\partial_{G[A]}S\leq 1.01\tilde{\lambda}$, we have $S\cap A\in\mathcal{C}$,
so initially $S\cap A\in\mathcal{C}^{\prime}$ on the root instance $A$. We now
prove property (1) by induction on the recursion tree of the algorithm. As
base cases, we consider instances $A^{\prime}$ where $S$ is removed from
$\mathcal{C}^{\prime}$ in the initial pruning step. Since $S$ is removed from
$\mathcal{C}^{\prime}$, it is non-$(1-\epsilon)$-boundary sparse in
$A^{\prime}$, i.e., property (1) holds for the trivial partition with the
entire decomposition of $A^{\prime}$ as a single part. For instances
$A^{\prime}$ where $S\in\mathcal{C}^{\prime}$ survives the initial pruning
step, we apply induction on the two recursive instances $C\cap A^{\prime}$ and
$A^{\prime}\setminus C$ and take the union of the two partitions, which is a
partition of the decomposition returned by instance $A^{\prime}$. It follows
that property (1) holds.

_Correctness: Property ( 2)._ To show property (2), we first make two
observations.

######  Observation 6.4.

If the algorithm decomposes by case (a) into $U=C\cap A^{\prime}$ and
$A^{\prime}\setminus C=A^{\prime}\setminus U$, then $\partial U\leq\partial
A^{\prime}-0.19\tilde{\lambda}$ and $\partial(A^{\prime}\setminus
U)\leq\partial A^{\prime}-0.19\tilde{\lambda}$.

###### Proof.

Suppose the algorithm decomposes into $U=C\cap A^{\prime}$ and
$A^{\prime}\setminus C=A^{\prime}\setminus U$. First observe that if the
algorithm decomposes by case (a), then

$\displaystyle w(U,\overline{A^{\prime}})=\partial U-w(U,A^{\prime}\setminus
U)\geq\lambda-0.4\tilde{\lambda}\geq
0.99\tilde{\lambda}-0.4\tilde{\lambda}=0.59\tilde{\lambda}$
$\displaystyle\implies$ $\displaystyle\partial(A^{\prime}\setminus U)=\partial
A^{\prime}-w(U,\overline{A^{\prime}})+w(U,A^{\prime}\setminus U)\leq\partial
A^{\prime}-0.59\tilde{\lambda}+0.4\tilde{\lambda}=\partial
A^{\prime}-0.19\tilde{\lambda}$

and by symmetry, we also obtain $\partial U\leq\partial
A^{\prime}-0.19\tilde{\lambda}$. In other words, boundary size decreases by at
least $0.19\lambda$ on both recursive instances. ∎

######  Observation 6.5.

If the algorithm decomposes by case (b) into $U=C\cap A^{\prime}$ and
$A^{\prime}\setminus C=A^{\prime}\setminus U$, then $\partial U\leq\partial
A^{\prime}-0.4\epsilon\tilde{\lambda}$ and $\partial(A^{\prime}\setminus
U)\leq\partial A^{\prime}-0.4\epsilon\tilde{\lambda}$.

###### Proof.

If the algorithm decomposes by case (b), then since $U$ is
$(1-\epsilon)$-boundary-sparse in $A^{\prime}$,

$\displaystyle\partial(A^{\prime}\setminus U)$ $\displaystyle=\partial
A^{\prime}-w(U,\overline{A^{\prime}})+w(U,A^{\prime}\setminus U)$
$\displaystyle\leq\partial
A^{\prime}-\frac{1}{1-\epsilon}w(U,A^{\prime}\setminus
U)+w(U,A^{\prime}\setminus U)\leq\partial A^{\prime}-\epsilon
w(U,A^{\prime}\setminus U)\leq\partial A^{\prime}-0.4\epsilon\tilde{\lambda}$

and by symmetry, $\partial U\leq\partial
A^{\prime}-0.4\epsilon\tilde{\lambda}$. ∎

The two observations together show that boundary size decreases by at least
$\min\\{0.19\tilde{\lambda},0.4\epsilon\tilde{\lambda}\\}$ on both recursive
instances.

We now upper bound the number of clusters by tracking the following three
parameters of a cluster $A^{\prime}$:

  1. 1.

The boundary size $\partial A^{\prime}$, and

  2. 2.

The maximum cut size within $A^{\prime}$ of a cut in $\mathcal{C}^{\prime}$
after the pruning step, defined by

$c(A^{\prime})=\max_{\begin{subarray}{c}C\in\mathcal{C}^{\prime}\\\
\text{after}\\\ \text{pruning}\end{subarray}}\partial_{G[A^{\prime}]}(C\cap
A^{\prime}),$

which we define as $0$ if $\mathcal{C}^{\prime}=\emptyset$, and

  3. 3.

The cluster size $|A^{\prime}|$.

We claim that the first two parameters are at most $3\tilde{\lambda}$ and
$1.01\tilde{\lambda}$, respectively. The first parameter is always at most
$3\tilde{\lambda}$ since originally $\partial A\leq 3\tilde{\lambda}$ by
assumption, and we have shown that boundary size never increases upon
recursion. The second parameter is at most $1.01\tilde{\lambda}$ originally,
and it never increases upon recursion since the value
$\partial_{G[A^{\prime}]}(C\cap A^{\prime})$ decreases as $A^{\prime}$ gets
smaller upon recursion and $\mathcal{C}^{\prime}$ can only lose elements over
time.

Let $f(b,c,d)$ be the maximum number of clusters in the final decomposition
starting from a cluster $A^{\prime}$ with $\partial A^{\prime}\leq b$,
$c(A^{\prime})\leq c$, and $|A^{\prime}|\leq d$. Our goal is to show that

$f(b,c,d)\leq O\left(\big{(}\frac{b}{\epsilon\tilde{\lambda}}\big{)}^{2}(\log
d)^{O(b/\tilde{\lambda})}\right).$

We recursively bound $f(b,c,d)$ by stepping through each case of the
algorithm. To do so we first make two observations.

######  Observation 6.6.

If the algorithm decomposes by case (a) into $U=C\cap A^{\prime}$ and
$A^{\prime}\setminus C=A^{\prime}\setminus U$, then the maximum number of
clusters in the final decomposition of each recursive instance
$U,A^{\prime}\setminus U$ is upper bounded by $f(b-0.19\tilde{\lambda},c,d)$,
i.e., we have $f(b,c,d)=2f(b-0.19\tilde{\lambda},c,d).$

###### Proof.

This observation follows directly from Observation 6.4 as it shows that
$\partial U,\partial(A^{\prime}\setminus U)\leq\partial
A^{\prime}-0.19\tilde{\lambda}\leq b-0.19\tilde{\lambda}$. ∎

######  Observation 6.7.

If the algorithm decomposes by case (b), we must have $|C\cap
A^{\prime}|\leq|A^{\prime}|/2$. Moreover, all sets
$C^{\prime}\in\mathcal{C}^{\prime}$ that cross $C\cap A^{\prime}$ must also
cross $A^{\prime}\setminus C$.

###### Proof.

For the first statement, if $C\cap A^{\prime}$ is $(1-\epsilon)$-boundary-
sparse, then so is $A^{\prime}\setminus C$, and since the algorithm minimizes
for $|C\cap A^{\prime}|$, we must have $|C\cap
A^{\prime}|\leq|A^{\prime}\setminus C|$, which means that $|C\cap
A^{\prime}|\leq|A^{\prime}|/2$.

For the second statement, suppose for contradiction that there exists
$C^{\prime}\in\mathcal{C}^{\prime}$ that crosses $C\cap A^{\prime}$ but not
$A^{\prime}\setminus C$. Without loss of generality, by replacing $C^{\prime}$
with $\overline{C^{\prime}}$ if needed, we can assume that $C^{\prime}$ is
disjoint from $A^{\prime}\setminus C$. But then $|C^{\prime}\cap
A^{\prime}|<|C\cap A^{\prime}|$, and by minimality, $C^{\prime}$ should have
been selected over $C$, a contradiction. ∎

######  Observation 6.8.

If the algorithm decomposes by case (b) we obtain the recursive bound

$\displaystyle f(b,c,d)\leq\max\\{1,\
2f(b-0.19\tilde{\lambda},c,d)+f(b,c,d/2),\
f(b,0.6c,d)+f(b-0.4\epsilon\tilde{\lambda},c,d)\\}$

###### Proof.

Suppose that the algorithm decomposes by case (b) into $U=C\cap A^{\prime}$
and $A^{\prime}\setminus C=A^{\prime}\setminus U$. By 6.7, we have
$|U|\leq|A^{\prime}|/2$ and moreover, all sets
$C^{\prime}\in\mathcal{C}^{\prime}$ that cross $U$ must also cross
$A^{\prime}\setminus U$. We case on whether $c(U)\geq 0.6c(A^{\prime})$, i.e.,
whether there exists $C^{\prime}\in\mathcal{C}^{\prime}$ that crosses $U$ with
$\partial_{G[U]}C^{\prime}\geq 0.6c(A^{\prime})$.

  1. 1.

If such a set $C^{\prime}$ exists, then from
$\partial_{G[U]}C^{\prime}+\partial_{G[A^{\prime}\setminus
U]}C^{\prime}\leq\partial_{G[A^{\prime}]}C^{\prime}$ we obtain
$\partial_{G[A^{\prime}\setminus
U]}C^{\prime}\leq\partial_{G[A^{\prime}]}C^{\prime}-\partial_{G[U]}C^{\prime}\leq
c(A^{\prime})-0.6c(A^{\prime})=0.4c(A^{\prime})$. Since $C^{\prime}$ also
crosses $A^{\prime}\setminus U$, the recursive instance $A^{\prime}\setminus
U$ must go through case (a); let $A_{1},A_{2}$ be the decomposition of
$A^{\prime}\setminus U$. Then by 6.4, $\partial A_{1},\partial
A_{2}\leq\partial(A^{\prime}\setminus U)-0.19\tilde{\lambda}\leq\partial
A^{\prime}-0.19\tilde{\lambda}$. By induction on clusters $U,A_{1},A_{2}$, the
total number of clusters at the end is at most

$2f(b-0.19\tilde{\lambda},c,d)+f(b,c,d/2).$

  2. 2.

Otherwise, we have $c(U)<0.6c(A^{\prime})$. By 6.5, we have
$\partial(A^{\prime}\setminus U)\leq\partial
A^{\prime}-0.4\epsilon\tilde{\lambda}$. By induction, the total number of
clusters at the end is at most

$f(b,0.6c,d)+f(b-0.4\epsilon\tilde{\lambda},c,d).$

Overall, if the algorithm decomposes by case (b) we obtain the recursive bound

$\displaystyle f(b,c,d)\leq\max\\{$ $\displaystyle 1,$ $\displaystyle
2f(b-0.19\tilde{\lambda},c,d)+f(b,c,d/2),$ $\displaystyle
f(b,0.6c,d)+f(b-0.4\epsilon\tilde{\lambda},c,d)\\}.$

∎

Next we state the base cases for our induction that bounds $f(b,c,d)$.

  1. 1.

Since we always have $\partial A^{\prime}\geq\lambda>0.99\tilde{\lambda}$, we
have the vacuous bound $f(b,c,d)=0$ for $b\leq 0.99\tilde{\lambda}$.

  2. 2.

If $\mathcal{C}^{\prime}=\emptyset$, no further recursion is necessary. Thus,
$f(b,0,d)=1$.

  3. 3.

If $|A^{\prime}|=1$, the cluster cannot be cut any further. Thus,
$f(b,c,1)=1$.

We now bound $f(b,c,d)$ using a case analysis depending on the value of the
second parameter. As shown by Observation 6.6 and 6.8, the value of the second
parameter never increases. Furthermore, if it drops to at most
$0.4\tilde{\lambda}$ on a set $A^{\prime}$ then the algorithm always executes
case (a) for all subsequent recursive calls on subsets of $A^{\prime}$. Thus,
we bound this setting first.

_Case 1:_ If $c(A^{\prime})\leq 0.4\tilde{\lambda}$, then the algorithm either
takes case (a) or does nothing (in the case $c(A^{\prime})=0$), so

$f(b,c,d)\leq\max\\{1,2f(b-0.19\tilde{\lambda},c,d)\\}\text{ for }c\leq
0.4\tilde{\lambda}.$

Every recursive case still has $c(A^{\prime})\leq 0.4\tilde{\lambda}$, so the
algorithm only makes recursive calls through case (a). The number of recursive
branches doubles for at most
$\lceil\frac{b-0.99\tilde{\lambda}}{0.19\tilde{\lambda}}\rceil\leq\frac{b-0.99\tilde{\lambda}}{0.19\tilde{\lambda}}+1\leq\frac{b}{0.19\tilde{\lambda}}\leq\frac{6b}{\tilde{\lambda}}$
levels of recursion and $2^{x}\geq 1$ for all positive $x$, so it holds that
$f(b,c,d)\leq 2^{6b/\tilde{\lambda}}$.

_Case 2:_ For $c\in(0.4\tilde{\lambda},0.61\tilde{\lambda}]$, the algorithm
either takes case (b) or case (c). We claim the bound

$f(b,c,d)\leq\frac{b}{0.4\epsilon\tilde{\lambda}}(2+2\log_{2}d)^{6b/\tilde{\lambda}}.$

It is trivially true for $b\leq 0.99\tilde{\lambda}$ and $d=1$. Note that
$0.6c\leq 0.6\cdot 0.61\tilde{\lambda}\leq 0.4\tilde{\lambda}$ so that a call
on a set with second parameter $0.6c$ guarantees that case (a) is executed on
this call and we can apply the bound from Case 1. Now by induction on $b\geq
0.99\tilde{\lambda}$ and $d>1$ it holds that

$\displaystyle f(b,c,d)$ $\displaystyle\leq\max\\{$ $\displaystyle 1,$
$\displaystyle 2f(b-0.19\tilde{\lambda},c,d)+f(b,c,d/2),$ $\displaystyle
f(b,0.6c,d)+f(b-0.4\epsilon\tilde{\lambda},c,d)\\}$ $\displaystyle\leq\max\\{$
$\displaystyle 1,$ $\displaystyle
2\cdot\frac{b}{0.4\epsilon\tilde{\lambda}}(2+2\log_{2}d)^{6(b-0.19\tilde{\lambda})/\tilde{\lambda}}+\frac{b}{0.4\epsilon\tilde{\lambda}}(2+2\log_{2}(d/2))^{6b/\tilde{\lambda}},$
$\displaystyle
2^{6b/\tilde{\lambda}}+\frac{b-0.4\epsilon\tilde{\lambda}}{0.4\epsilon\tilde{\lambda}}(2+2\log_{2}d)^{6b/\tilde{\lambda}}\\}$
$\displaystyle\leq\max\\{$ $\displaystyle 1,$ $\displaystyle
2\cdot\frac{b}{0.4\epsilon\tilde{\lambda}}(2+2\log_{2}d)^{6b/\tilde{\lambda}-1}+\frac{b}{0.4\epsilon\tilde{\lambda}}(2+2\log_{2}d)^{6b/\tilde{\lambda}-1}\cdot(2+2\log_{2}d-2),$
$\displaystyle(2+2\log_{2}d)^{6b/\tilde{\lambda}}+\frac{b-0.4\epsilon\tilde{\lambda}}{0.4\epsilon\tilde{\lambda}}(2+2\log_{2}d)^{6b/\tilde{\lambda}}\\}$
$\displaystyle=$
$\displaystyle\frac{b}{0.4\epsilon\tilde{\lambda}}(2+2\log_{2}d)^{6b/\tilde{\lambda}}.$

_Case 3:_ For $c\in[0.61\tilde{\lambda},1.01\tilde{\lambda}]$, we claim the
bound

$f(b,c,d)\leq\left(\frac{b}{0.4\epsilon\tilde{\lambda}}\right)^{2}(2+2\log_{2}d)^{6b/\tilde{\lambda}}.$

It is trivially true for $b\leq 0.99\tilde{\lambda}$ and $d=1$. Note that
$0.6c\leq 0.6\cdot 1.01\tilde{\lambda}\leq 0.61\tilde{\lambda}$, which implies
that a call on a set with second parameter $0.6c$ guarantees that the bound
from Case 2 can be applied to this call. Now by induction on $b\geq
0.99\tilde{\lambda}$ and $d>1$, it holds that

$\displaystyle f(b,c,d)$ $\displaystyle\leq\max\\{$ $\displaystyle 1,$
$\displaystyle 2f(b-0.19\tilde{\lambda},c,d)+f(b,c,d/2),$ $\displaystyle
f(b,0.6c,d)+f(b-0.4\epsilon\tilde{\lambda},c,d)\\}$ $\displaystyle\leq\max\\{$
$\displaystyle 1,$ $\displaystyle
2\cdot\left(\frac{b}{0.4\epsilon\tilde{\lambda}}\right)^{2}(2+2\log_{2}d)^{6(b-0.19\tilde{\lambda})/\tilde{\lambda}}+\left(\frac{b}{0.4\epsilon\tilde{\lambda}}\right)^{2}(2+2\log_{2}(d/2))^{6b/\tilde{\lambda}},$
$\displaystyle\frac{b}{0.4\epsilon\tilde{\lambda}}(2+2\log_{2}d)^{6b/\tilde{\lambda}}+\bigg{(}\frac{b-0.4\epsilon\tilde{\lambda}}{0.4\epsilon\tilde{\lambda}}\bigg{)}^{2}(2+2\log_{2}d)^{6b/\tilde{\lambda}}\\}$
$\displaystyle\leq\max\\{$ $\displaystyle 1,$ $\displaystyle
2\cdot\left(\frac{b}{0.4\epsilon\tilde{\lambda}}\right)^{2}(2+2\log_{2}d)^{6b/\tilde{\lambda}-1}+\left(\frac{b}{0.4\epsilon\tilde{\lambda}}\right)^{2}(2+2\log_{2}d)^{6b/\tilde{\lambda}-1}\cdot(2+2\log_{2}d-2),$
$\displaystyle\frac{b}{0.4\epsilon\tilde{\lambda}}(2+2\log_{2}d)^{6b/\tilde{\lambda}}+\bigg{(}\frac{b-0.4\epsilon\tilde{\lambda}}{0.4\epsilon\tilde{\lambda}}\bigg{)}\left(\frac{b}{0.4\epsilon\tilde{\lambda}}\right)(2+2\log_{2}d)^{6b/\tilde{\lambda}}\\}$
$\displaystyle=$
$\displaystyle\left(\frac{b}{0.4\epsilon\tilde{\lambda}}\right)^{2}(2+2\log_{2}d)^{6b/\tilde{\lambda}}.$

Since $b\leq 3\tilde{\lambda}$, $c\leq 1.01\tilde{\lambda}$, and $d\leq|A|$,
we obtain the desired bound $O(\epsilon^{-2}(\log|A|)^{O(1)})$. ∎

Finally, we claim that Lemmas 6.2 and 6.3 together imply Section 3. Applying
Lemma 6.2 to the initial cluster $A$ produces clusters $A^{\prime}$ whose
total boundary size is $O(\epsilon^{-1}\partial A)$. Each cluster $A^{\prime}$
with $\partial A^{\prime}>3\tilde{\lambda}$ has no $(1-\epsilon)$-boundary-
sparse set $U\subseteq A$ with $\partial_{G[A]}A\leq 1.01\tilde{\lambda}$, so
in particular, for every $1.01$-approximate minimum cut $S\subseteq V$ of $G$,
the set $S\cap A^{\prime}$ is non-$(1-\epsilon)$-boundary-sparse in
$A^{\prime}$.

For each cluster $A^{\prime}$ with $\partial A^{\prime}\leq 3\tilde{\lambda}$,
Lemma 6.3 produces $O(\epsilon^{-2}(\log|A^{\prime}|)^{O(1)})$ many clusters,
each of boundary size at most $\partial A^{\prime}$, such that for every
$1.01$-approximate minimum cut $S\subseteq V$ of $G$, there is a partition
$\mathcal{P}$ of the decomposition such that for each part $P\in\mathcal{P}$,
the set $S\cap\bigcup_{A^{\prime}\in P}A^{\prime}$ is
non-$(1-\epsilon)$-boundary-sparse in $\bigcup_{A^{\prime}\in P}A^{\prime}$.
Recall that the total boundary size of the output of Lemma 6.2 is
$O(\epsilon^{-1}\partial A)$. It follows that the total boundary size of the
outputs of Lemma 6.3 over all $A^{\prime}$ is $O(\epsilon^{-1}\partial A)\cdot
O(\epsilon^{-2}(\log|A|)^{O(1)})=O(\epsilon^{-3}(\log|A|)^{O(1)}\partial A)$.

Given a $1.01$-approximate minimum cut $S\subseteq V$ of $G$, we define the
partition $\mathcal{P}$ so that every cluster $A^{\prime}$ with $\partial
A^{\prime}>3\tilde{\lambda}$ produced by Lemma 6.2 is a singleton part in
$\mathcal{P}$, and for each cluster $A^{\prime}$ that is further decomposed by
Lemma 6.3, we add to $\mathcal{P}$ the partition guaranteed property (1) of
Lemma 6.3.

By construction, for each part $P$ in the final partition $\mathcal{P}$, the
set $S\cap\bigcup_{A^{\prime}\in P}A^{\prime}$ is non-$(1-\epsilon)$-boundary
sparse in $\bigcup_{A^{\prime}\in P}A^{\prime}$. For the running time, the
algorithm calls Lemma 6.2 once and Lemma 6.3 up to $|A|$ times, for a total
running time of $\tilde{O}(|A|^{9})$. This concludes the proof of Section 3.

###  6.2 Large clusters

In this section, we present a fast algorithm to break down a large cluster
$A$, i.e., a cluster with $\Omega(s_{0})$ total volume, into a (potentially
large) cluster $A_{0}$ and a (potentially empty) collection of small clusters
$A_{1},\dots,A_{r}$. The key property of cluster $A_{0}$ is that any near-
minimum cut $U$ with small volume can be transformed, or “uncrossed”, into a
small enough cut $U^{*}$ with $U^{*}\cap A_{0}=\emptyset$. More formally, the
main result of this section is the following.

We begin with a high-level description of the algorithm. In the rest of the
section let $A$ be a large cluster.

##### Setting up the sources.

To find cuts that are not uncrossable with $A$, the algorithm sets up a
collection of flow problems. Let $U\subset A$ is a set with ${\hbox{\bf
vol}}_{G}(U)\leq s_{0}$ that is not uncrossable with $A$. More precisely,
suppose that $w(U,V\setminus A)\geq(1+\epsilon)w(U,A\setminus U)$; we will use
this definition of “uncrossable” for intuition in this section. Consider a
flow problem in $G[A]$ where each vertex $v\in U$ has source $w(v,V\setminus
A)$, each edge has flow capacity equal to its weight, and each vertex has sink
capacity equal to $\eta d^{W}_{G}(v)$ for small enough $\eta>0$. Within $U$,
there is $w(U,V\setminus A)$ source originating from $U$, at most
$w(U,A\setminus U)$ flow leaves through the edges $\partial_{G[A]}U$, and at
most $\eta{\hbox{\bf vol}}^{W}_{G}(U)\leq\eta s_{0}$ flow that is absorbed in
$U$. Since $w(U,V\setminus A)\geq(1+\epsilon)w(U,A\setminus U)$, the flow
cannot be feasible as long as $\eta>0$ is small enough. It turns out that to
make this argument work, we must set $\eta>0$ small enough that there is not
enough sink to absorb all the source. Therefore, we split the source up into
many sub-sources, each of them small enough to be fully absorbed. More
formally, we construct a collection of subsets $S\subseteq A$ that are
small—$O(s_{0})$ volume each—such that for each $U$ with (i)
$\partial_{G[A]}U\lesssim\tilde{\lambda}$ and (ii) ${\hbox{\bf
vol}}^{W}(U)\leq s_{0}$ that is (iii) not uncrossable, there exists a set $S$
containing $U$. For each set $S$, we construct a flow where only vertices
$v\in S$ receive their $w(v,V\setminus A)$ of source (with edge capacities and
sinks unchanged). This is not quite achievable for technical purposes, but we
show that it is possible _if the induced graph $G[U]$ has minimum cut
$\Omega(\lambda)$_. In this case, if we run a variant of tree packing on
$G[A]$, then there is a lot of “room” in $G[U]$ to pack trees, and the
vertices in $U$ will be contained in the union of $O(1)$ many trees, even
after a post-processing step where each tree is broken down into pieces of
volume $O(s_{0})$. We then stitch the trees together by connecting pieces
together in a bounded fashion so that one of the resulting sets $S$ contains
$U$.

##### Executing the flows.

Consider a set $U$ with $\partial_{G[A]}U\lesssim\tilde{\lambda}$ and
${\hbox{\bf vol}}^{W}(U)\leq s_{0}$ that is not uncrossable. In the previous
step we have constructed a “source set” $S\subseteq A$ with ${\hbox{\bf
vol}}^{W}(S)\leq O(s_{0})$ and $U\subseteq S$. We cannot afford to run a
separate flow where each vertex of $S$ is a source, for each “source set” $S$,
since each flow computation may take linear time. (Note that if the graph
$G[A]$ were unweighted, then we can resort to local flow algorithms, but these
do not have local guarantees in weighted graphs.)

Instead, we set up instances of _approximate isolating cuts_ which allow us to
execute the flows of many sources at once. We partition the collection of
sources into $\textup{polylog}(n)$ subcollections that are vertex-disjoint
(which is a requirement for approximate isolating cuts) and solve an instance
of the approximate isolating cuts problem for each subcollection, obtaining a
cut $C_{i}\subseteq A$ for each source $S_{i}$ such that if $U\subseteq S_{i}$
then either $U\subseteq C_{i}$ or $U\setminus C_{i}$ is now uncrossable in
$G[A\setminus C_{i}]$. We then remove all cuts $C_{i}$ from $A$, and continue
to the instance of the next subcollection where we restrict to the remaining
sources $S\cap A$ on the remaining induced graph $G[A]$.

##### Removing the connected assumption.

In general, $G[U]$ may not be well-connected. (It may even be disconnected, or
very loosely connected.) The algorithm simply handles this issue by cycling
through the approximate isolating cut problem instances some
$\textup{polylog}(n)$ times. The analysis is a lot more complicated and
technical, and we have to break down a general set $U$ into well-connected
sets and analyze the progress the algorithm makes in each cycle.

####  6.2.1 Setting up the sources

Let $W=\tilde{\lambda}^{3}/(50s_{0}^{2})$. Let $A\subseteq V$. The algorithm
first constructs the following unweighted multi-graph $H$ supported on the
same vertices and edges as $G[A]$: for each edge $e$ in $G[A]$, let
$w_{H}(e)=\lfloor w_{G}(e)/W\rfloor$, i.e., there are $\lfloor
w_{G}(e)/W\rfloor$ parallel edges between the endpoints of $e$ in $H$.

##### Well-connected case.