to be $N_{i^{\prime}}\cap B_{j}$, and a newly created node denoted by $z$. We
iteratively do this, setting the two children of $z$ in the same way as for
the root node, such that we construct a caterpillar tree on the nodes
$N_{i^{\prime}}\cap B_{j}$ for $N_{i^{\prime}}\in X_{j}$. Finally, after this
construction, we replace the child node $N_{i}\cap B_{j}$ of
$\mathrm{parent}(N_{i}\cap B_{j})$ with the root node $R_{B_{j}}$ of our newly
constructed caterpillar tree.

Note that every $\mathrm{parent}(N_{i^{\prime}}\cap B_{j})$ for
$N_{i^{\prime}}\in X_{j}\setminus N_{i}$ no longer has a corresponding
$N_{i^{\prime}}\cap B_{j}$ as a child node, since it has been placed in the
new caterpillar tree. Therefore, as a final step, we remove
$\mathrm{parent}(N_{i^{\prime}}\cap B_{j})$ from the tree
$\mathcal{T}_{\mathsf{MS}}^{\prime}$, and appropriately update the child and
parent node directly below and above $\mathrm{parent}(N_{i^{\prime}}\cap
B_{j})$ to ensure that the tree stays connected.

After travelling up the entire tree, this transformation ensures that all the
vertices in $B_{j}$ are placed in the same subtree, since
$\bigcup_{N_{i^{\prime}}\in X_{j}}N_{i^{\prime}}\cap B_{j}=B_{j}$. Crucially,
because $N_{i}$ is an anchor node, we know by the construction of the tree
$\mathcal{T}_{\mathsf{MS}}$ that every $N_{i^{\prime}}\in X_{j}\setminus
N_{i}$ is placed lower in the tree $\mathcal{T}_{\mathsf{MS}}^{\prime}$, and
hence we do not have to consider the induced cost of moving any critical node
higher up in the tree down to $N_{i}$. To illustrate, We visualise (part of)
the transformation in Figure 4. We call the resulting tree
$\mathcal{T}_{\mathsf{MS}}^{\prime\prime}$, and we bound its cost with the
following lemma.

######  Lemma B.6.

It holds that

$\mathsf{COST}_{G}\left(\mathcal{T}_{\mathsf{MS}}^{\prime\prime}\right)\leqslant\mathsf{COST}_{G}\left(\mathcal{T}_{\mathsf{MS}}^{\prime}\right)+O(\beta\cdot
k^{3}/\phi_{\mathrm{in}}^{10})\cdot\mathsf{OPT}_{G}.$

###### Proof.

We bound the cost of the transformation by looking at the total induced cost
incurred at every $N_{i}\in\mathcal{S}$ that is an anchor node. First of all,
notice that for all nodes $N_{i}\cap B_{j}$ in
$\mathcal{T}_{\mathsf{MS}}^{\prime}$ we have that

$|\mathrm{parent}_{\mathcal{T}_{\mathsf{MS}}^{\prime}}(N_{i}\cap
B_{j})|\leqslant|\mathrm{parent}_{\mathcal{T}_{\mathsf{MS}}}(N_{i})|\leqslant
6k\cdot|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})|,$ (B.12)

where the first inequality holds because of the construction of
$\mathcal{T}_{\mathsf{MS}}^{\prime}$ and the second inequality follows by
Lemma B.2. Recall that $\mathbb{T}_{\mathrm{deg}}(N_{i})$ is the tree
$\mathbb{T}_{\mathrm{deg}}$ that $N_{i}$ originally corresponds to.

Now let us fix some $N_{i}$ that is also an anchor node, and let
$\mathcal{X}_{i}$ be the set such that $X_{j}\in\mathcal{X}_{i}$ shares
$N_{i}$ as their anchor node, i.e.,
$N_{i}=\operatorname{argmax}_{N_{i^{\prime}}\in X_{j}}|N_{i^{\prime}}|$ for
$X_{j}\in\mathcal{X}_{i}$. The only edges whose cost can increase when moving
up $N_{i^{\prime}}\cap B_{j}$ for some $N_{i^{\prime}}\in X_{j}$ will be the
edges with one endpoint in $N_{i^{\prime}}\cap B_{j}$, since moving them up
potentially increases their lowest common ancestor to be
$|\mathrm{parent}_{\mathcal{T}_{\mathsf{MS}}^{\prime}}(N_{i}\cap B_{j})|$.
Note that because we carefully choose to perform the transformations at the
_anchor_ node, we don’t introduce any new vertices from higher up in the tree
which could potentially change the size of the lowest common ancestor.

Therefore, we can bound the cost of moving up all $N_{i^{\prime}}\cap B_{j}$
for $N_{i^{\prime}}\in X_{j}$ and $X_{j}\in\mathcal{X}_{i}$ as

$\displaystyle\sum_{X_{j}\in\mathcal{X}_{i}}\left(|\mathrm{parent}_{\mathcal{T}_{\mathsf{MS}}^{\prime}}(N_{i}\cap
B_{j})|\sum_{N_{i^{\prime}}\in
X_{j}}\mathrm{vol}\\!\left(\\!\,N_{i^{\prime}}\cap B_{j}\,\\!\right)\right)$
$\displaystyle\leqslant$ $\displaystyle
6k\cdot|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})|\cdot\sum_{X_{j}\in\mathcal{X}_{i}}\sum_{N_{i^{\prime}}\in
X_{j}}\mathrm{vol}\\!\left(\\!\,N_{i^{\prime}}\cap B_{j}\,\\!\right)$ (B.13)
$\displaystyle\leqslant$ $\displaystyle
6k\cdot|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})|\cdot\sum_{X_{j}\in\mathcal{X}_{i}}\sum_{N_{i^{\prime}}\in
X_{j}}|N_{i^{\prime}}\cap B_{j}|\cdot\Delta_{G}(N_{i^{\prime}}\cap B_{j})$
$\displaystyle\leqslant$ $\displaystyle
6k\cdot|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})|\sum_{X_{j}\in\mathcal{X}_{i}}\sum_{N_{i^{\prime}}\in
X_{j}}|N_{i^{\prime}}\cap B_{j}|\cdot\beta\cdot\Delta_{G}(N_{i}\cap B_{j})$
(B.14) $\displaystyle\leqslant$ $\displaystyle
6k\cdot|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})|\cdot\sum_{X_{j}\in\mathcal{X}_{i}}\sum_{N_{i^{\prime}}\in
X_{j}}|N_{i^{\prime}}\cap B_{j}|\cdot\beta\cdot\Delta_{G}(N_{i})$
$\displaystyle\leqslant$ $\displaystyle
6k\cdot\beta\cdot|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})|\cdot
14k\cdot\Delta_{G[C(N_{i})]}(N_{i})\cdot\sum_{X_{j}\in\mathcal{X}_{i}}\sum_{N_{i^{\prime}}\in
X_{j}}|N_{i^{\prime}}|$ (B.15) $\displaystyle\leqslant$ $\displaystyle
O(k^{3}\cdot\beta)\cdot|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})|\cdot\Delta_{G[C(N_{i})]}(N_{i})\cdot|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})|$
(B.16) $\displaystyle\leqslant$ $\displaystyle
O(k^{3}\cdot\beta)\cdot|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})|\cdot\delta_{G[C(N_{i})]}(\mathrm{sib}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i}))\cdot|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})|$
(B.17) $\displaystyle\leqslant$ $\displaystyle
O(k^{3}\cdot\beta)\cdot|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(\mathrm{sib}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i}))|\cdot\mathrm{vol}_{G[C(N_{i})]}\left(\mathrm{sib}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})\right).$
(B.18)

Here, (B.13) follows by (B.12), (B.14) follows by the fact that all degrees
$d_{u}$ of $u\in N_{i^{\prime}}\cap B_{j}$ for $N_{i^{\prime}}\in X_{j}$ lie
within a factor of $\beta$ of each other. Since we denote by $C(N_{i})$ the
cluster to which $N_{i}$ originally corresponds, (B.15) holds because of
Property (A3) of Lemma A.10, (B.16) holds because we only move the critical
nodes $N_{i^{\prime}}$ that are below $N_{i}$ in the caterpillar construction,
so the sum of their sizes is at most
$|\mathrm{parent}_{\mathcal{T}_{\mathsf{MS}}}(N_{i})|$, which we upper bound
with (B.12). Moreover, (B.17) follows by the fact that the minimum degree in
$G[C(N_{i})]$ of a sibling node of $N_{i}$ (Definition A.7) is at least the
maximum degree of $N_{i}$ in $G[C(N_{i})]$, (B.18) holds because

$|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})|\leqslant
2\cdot|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(\mathrm{sib}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i}))|$

and

$\delta_{G[C(N_{i})]}(\mathrm{sib}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i}))\cdot|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})|\leqslant
4\cdot\mathrm{vol}_{G[C(N_{i})]}\left(\mathrm{sib}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})\right).$

The bound above holds as long as $N_{i}$ has a sibling node, and it remains to
examine the case in which $N_{i}$ doesn’t have a sibling node. Recall that the
set of extended critical nodes of a cluster $C_{s}$ returned by Lemma B.1 is
$\mathcal{S}_{s}\triangleq\\{B_{1},\ldots,B_{s_{\max}},A_{s_{\max}}\\}$. The
only critical node _without_ a sibling node is $A_{s_{\max}}$, and we know by
construction that $|A_{s_{\max}}|\leqslant 2$. Because
$\mathcal{T}_{\mathsf{MS}}$ is a caterpillar tree based on the sizes of the
nodes, $A_{s_{\max}}$ is placed as one of the critical nodes furthest down the
tree. Given that there are at most three critical nodes of size at most two in
every $C_{s}$, $A_{s_{\max}}$ must be one of the last $3\ell$ extended
critical nodes in the caterpillar tree.

Suppose one of these $A_{s_{\max}}$ from some $\mathcal{S}_{s}$ is an anchor
node. The only nodes in the tree $\mathcal{T}_{\mathsf{MS}}^{\prime}$ that can
be moved up to this node are other nodes of size at most two, of which there
are at most $3\ell$ (three for every partition $C_{s}$). Let
$N_{q}\triangleq\operatorname{argmax}_{\begin{subarray}{c}N_{i^{\prime}}\in\mathcal{S}\\\
|N_{i^{\prime}}|\leqslant
2\end{subarray}}\mathrm{vol}\\!\left(\\!\,N_{i^{\prime}}\,\\!\right)$ be the
critical node of size at most two with the largest volume. Then, all the
transformations (at most $3k$) occurring in the lower part of the tree
$\mathcal{T}_{\mathsf{MS}}$ can be upper bounded by

$\displaystyle 3k\left(3k\cdot 2\cdot\sum_{\begin{subarray}{c}i^{\prime}\\\
|N_{i^{\prime}}|\leqslant
2\end{subarray}}\mathrm{vol}_{G}(N_{i^{\prime}})\right)$ $\displaystyle=$
$\displaystyle O(k^{3})\cdot\mathrm{vol}_{G}(N_{q})$ $\displaystyle=$
$\displaystyle O(k^{4})\cdot\mathrm{vol}_{G[C(N_{q})]}\left(N_{q}\right)$
$\displaystyle=$ $\displaystyle O(\beta\cdot
k^{3})\cdot|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{q})}(N_{q})|\cdot\mathrm{vol}_{G[C(N_{q})]}\left(N_{q}\right),$
(B.19)

where the first equality holds as $N_{q}$ is the largest volume extended
critical node of size at most two, the second one holds by Property (A3) of
Lemma A.10, and the last one holds because
$|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{q})}(N_{q})|\leqslant 4$ and
the fact that $k\leqslant 2^{k(\gamma+1)}=\beta$ for $k\geqslant 1$ and
$\gamma>0$.

Finally, to upper bound the total cost of the transformation, we assume for
the upper bound that every extended critical node is an anchor node, and we
split the sum over the induced cost of all the anchor nodes that have critical
siblings (B.18), and the transformation in the bottom of the tree
corresponding to critical nodes of size at most 2, which don’t have critical
siblings (B.19). Hence, the total cost of the transformation is at most

$\displaystyle O(\beta\cdot k^{3})\cdot\sum_{\begin{subarray}{c}i=1\\\
|N_{i}|>2\end{subarray}}^{k_{1}}|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(\mathrm{sib}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i}))|\cdot\mathrm{vol}_{G[C(N_{i})]}\left(\mathrm{sib}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})\right)+$
$\displaystyle\qquad O(\beta\cdot
k^{3})\cdot|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{q})}(N_{q})|\cdot\mathrm{vol}_{G[C(N_{q})]}\left(N_{q}\right)$
$\displaystyle\leqslant$ $\displaystyle O(\beta\cdot
k^{3})\cdot\sum_{i=1}^{k_{1}}\left|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})\right|\cdot\mathrm{vol}_{G[C(N_{i})]}(N_{i})$
(B.20) $\displaystyle\leqslant$ $\displaystyle O(\beta\cdot
k^{3})\cdot\sum_{s=1}^{\ell}\frac{4}{\Phi_{G[C_{s}]}}\cdot\mathsf{COST}_{G[C_{s}]}(\mathbb{T}_{s})$
(B.21) $\displaystyle=$ $\displaystyle O(\beta\cdot
k^{3})\cdot\sum_{s=1}^{\ell}\frac{1}{\Phi_{G[C_{s}]}^{5}}\cdot\mathsf{OPT}_{G[C_{s}]}$
(B.22) $\displaystyle=$ $\displaystyle O(\beta\cdot
k^{3}/\phi_{\mathrm{in}}^{10})\cdot\mathsf{OPT}_{G}.$

Here, (B.20) holds because the first sum of (B.20) is over
$|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})|\cdot\mathrm{vol}_{G[C(N_{i})]}(N_{i})$
for all $1\leqslant i\leqslant k_{1}$ _except_ for the extended critical nodes
that are not the sibling node of any critical node. Hence, we upper bound the
sum by including these terms, and relabeling the indices. Moreover, (B.21)
follows by Lemma A.3, and (B.22) follows by Theorem A.4 applied to every
induced subgraph $G[C_{s}]$. This proves the statement. ∎

###### Proof of Lemma 5.3.

Since the tree $\mathcal{T}_{\mathsf{MS}}^{\prime\prime}$ separates all the
individual buckets $B\in\mathcal{B}$ by construction, we can upper bound the
cost of $\mathsf{WOPT}_{G/\mathcal{B}}$ with respect to the cost of
$\mathcal{T}_{\mathsf{MS}}^{\prime\prime}$ and have that

$\mathsf{WOPT}_{G/B}\leqslant\mathsf{COST}_{G}\left(\mathcal{T}_{\mathsf{MS}}\right)+O(k/\phi_{\mathrm{in}}^{10})\cdot\mathsf{OPT}_{G}+O(\beta\cdot
k^{3}/\phi_{\mathrm{in}}^{10})\cdot\mathsf{OPT}_{G}=O\left(\beta\cdot
k^{23}/\lambda_{k+1}^{10}\right)\cdot\mathsf{OPT}_{G},$

where the first inequality holds by Lemmas B.5 and B.6, and the second one
holds by Lemma B.1 and the fact
$\phi_{\mathrm{in}}=\Theta(\lambda_{k+1}/k^{2})$. ∎

###### Proof of Lemma 5.2.

We bound the cost of the internal edges in $G[B_{j}]$ for $1\leqslant
j\leqslant\kappa$ using the trivial upper bound for every $B_{j}$, and have
that

$\displaystyle\sum_{i=1}^{k}\sum_{B\in\mathcal{B}_{i}}\mathsf{COST}_{G[B]}\left(\mathcal{T}_{B}\right)$
$\displaystyle\leqslant\sum_{j=1}^{\kappa}|B_{j}|\cdot\mathrm{vol}\\!\left(\\!\,B_{j}\,\\!\right)=\sum_{i^{\prime}=1}^{k_{1}}\sum_{X_{j}\in\mathcal{X}_{i^{\prime}}}|B_{j}|\cdot\sum_{N_{i^{\prime\prime}}\in
X_{j}}\mathrm{vol}\\!\left(\\!\,N_{i^{\prime\prime}}\cap B_{j}\,\\!\right)$
$\displaystyle\leqslant$
$\displaystyle\sum_{i^{\prime}=1}^{k_{1}}\sum_{X_{j}\in\mathcal{X}_{i^{\prime}}}|\mathrm{parent}_{\mathcal{T}_{\mathsf{MS}}^{\prime}}(N_{i^{\prime}}\cap
B_{j})|\cdot\sum_{N_{i^{\prime\prime}}\in
X_{j}}\mathrm{vol}\\!\left(\\!\,N_{i^{\prime\prime}}\cap B_{j}\,\\!\right)$

where the last inequality holds by construction of the tree
$\mathcal{T}_{\mathsf{MS}}^{\prime}$ and the property of anchor nodes. By
repeating the same calculation as the one in proving Lemma 5.3, we have that

$\displaystyle\sum_{i=1}^{k}\sum_{B\in\mathcal{B}_{i}}\mathsf{COST}_{G[B]}\left(\mathcal{T}_{B}\right)\leqslant$
$\displaystyle\sum_{i^{\prime}=1}^{k_{1}}\sum_{X_{j}\in\mathcal{X}_{i^{\prime}}}|\mathrm{parent}_{\mathcal{T}_{\mathsf{MS}}^{\prime}}(N_{i^{\prime}}\cap
B_{j})|\cdot\sum_{N_{i^{\prime\prime}}\in
X_{j}}\mathrm{vol}\\!\left(\\!\,N_{i^{\prime\prime}}\cap B_{j}\,\\!\right)$
$\displaystyle=$ $\displaystyle O\left(\beta\cdot
k^{23}/\lambda_{k+1}^{10}\right)\cdot\mathsf{OPT}_{G},$

which proves the statement. ∎

###  B.3 Proof of Theorem 5.1

Now we prove the approximation and running time guarantee of Algorithm 1. In
the following Lemma we analyse the approximation and running time guarantee of
WRSC.

######  Lemma B.7.

Let $w_{\mathrm{max}}/w_{\mathrm{min}}=O(n^{\gamma})$ for a constant
$\gamma>1$, and $\mathcal{B}$ the set of all buckets constructed inside every
$P_{1},\ldots P_{k}$. Then, given a contracted graph $H=G/\mathcal{B}$ as
input the WRSC algorithm runs in $\widetilde{O}(n)$ time and returns an HC
tree $\mathcal{T}$, such that

$\mathsf{WCOST}(\mathcal{T})=O\left(1\right)\cdot\mathsf{WOPT}_{G/\mathcal{B}}.$

###### Proof.

We denote by $\mathcal{B}$ the set containing all the buckets obtained
throughout all sets $P_{i}$, i.e.,

$\mathcal{B}\triangleq\bigcup_{i=1}^{k}\mathcal{B}_{i},$

and it holds that $|\mathcal{B}|=\kappa\leqslant
k\cdot\log_{\beta}\left(\Delta_{G}/\delta_{G}\right)$. Recall that our choice
of $\gamma$ and $\beta$ satisfies

$\frac{w_{\max}}{w_{\min}}=O(n^{\gamma})$

and $\beta=2^{k(\gamma+1)}$. Hence, it holds that

$\frac{\Delta_{G}}{\delta_{G}}=O\left(n^{\gamma+1}\right),$

and the total number of buckets in $\mathcal{B}$ is upper bounded by

$k\cdot\max\\{1,\log_{\beta}n^{\gamma+1}\\}\leqslant
k+\frac{k\cdot(\gamma+1)}{\log\beta}\cdot\log n=k+\log n.$

Hence, there are at most $k+\log n$ vertices in $G/\mathcal{B}$. To compute
the optimal weighted sparsest cut in $H=G/\mathcal{B}$, we compute
$\mathsf{sparsity}_{H}(S)$ for every subset $S\subset V(H)$, the total number
of which is upper bounded by $2^{k+\log n}=O\left(2^{k}\cdot n\right)$. Since
both $w(S,V(H)\setminus S)$ and $\mathrm{vol}_{H}(S)$ can be computed in
$\widetilde{O}(1)$ time, the sparsest cut of $G/\mathcal{B}$ can be computed
in $\widetilde{O}(n)$ time given that $k$ is a constant. Combining this with
the master theorem proves the time complexity of the WRSC algorithm.

The approximation guarantee for the algorithm follows from Lemma 3.2 and the
fact that we compute the optimal weighted sparsest cut; as such we have
$\alpha=1$ ∎

Next, we study the time complexity of Algorithm 1. We first show that the cost
$\mathsf{COST}_{G}\left(\mathcal{T}\right)$ can be computed in nearly-linear
time, assuming that the internal nodes of our constructed tree $\mathcal{T}$
have several useful attributes.

######  Lemma B.8.

Let $\mathcal{T}_{G}$ be an HC tree of a graph $G=(V,E,w)$, with depth $D$.
Assume that every internal node $N$ of $\mathcal{T}_{G}$ has (i) a pointer
$\mathsf{parent}$ that points to its parent node, (ii) an attribute
$\mathsf{size}$, which specifies the number of leaves in the subtree
$\mathcal{T}_{G}\left(G[N]\right)$, and (iii) an attribute $\mathsf{depth}$
that specifies the depth of $\mathcal{T}_{G}\left(G[N]\right)$. Then,
$\mathsf{COST}_{G}(\mathcal{T}_{G})$ can be computed in $O(m\cdot D)$ time.

###### Proof.

Since $G$ has $m$ edges, it suffices to show that we can compute the value
$\mathsf{cost}_{G}(e)$ for every edge $e=\\{u,v\\}\in E$ in $O(D)$ time. Let
us fix an arbitrary edge $e=\\{u,v\\}$, and let $N_{u}$ and $N_{v}$ be the
leaf nodes of $\mathcal{T}_{G}$ corresponding to $u$ and $v$ respectively.
Without loss of generality, we assume that $N_{u}(\mathsf{depth})\geqslant
N_{v}(\mathsf{depth})$. We successively travel from $N_{u}$ up the tree via
the $\mathsf{parent}$ pointers until we reach a node $N^{\prime}_{u}$, such
that $N^{\prime}_{u}(\mathsf{depth})=N_{v}(\mathsf{depth})$. After that, we
find the lowest common ancestor of $u$ and $v$ by simultaneously travelling up
one node at a time, starting from both $N^{\prime}_{u}$ and $N_{v}$, until we
reach the same internal node $N_{r}$. Once this condition is satisfied, we can
readily compute $\mathsf{cost}_{G}(\\{u,v\\})=w_{e}\cdot
N_{r}(\mathsf{size})$. The overall running time for computing
$\mathsf{cost}_{G}(\\{u,v\\})$ is $O(D)$, and therefore the statement holds. ∎

By Lemma B.8 we know that the time complexity of constructing $\mathcal{T}$ is
linear in the depth of $\mathcal{T}$. The following lemma shows that the depth
of $\mathcal{T}$ is $O(\log n)$, and the entire $\mathcal{T}$ can be
constructed in nearly-linear time.

######  Lemma B.9.

Algorithm 1 runs in $\widetilde{O}\left(m\right)$ time, and constructs the
tree $\mathcal{T}$ of depth $O\left(\log n\right)$. Moreover, every internal
node $N\in\mathcal{T}$ has a pointer $\mathsf{parent}$, and every node
$T\in\mathcal{T}$ has attributes $\mathsf{size}$ and $\mathsf{depth}$.

###### Proof.

We follow the execution of Algorithm 1 to analyse its time complexity, and the
depth of its constructed $\mathcal{T}$. Line 1 of Algorithm 1 applies spectral
clustering to obtain the clusters $\\{P_{i}\\}_{i=1}^{k}$, and the running
time of this step is $\widetilde{O}(m)$ [PSZ17]. Since ordering the vertices
of every $P_{i}$ with respect to their degrees takes
$O\left(|P_{i}|\log|P_{i}|\right)$ time, the total time complexity of sorting
the vertices for $\\{P_{i}\\}$, finding $\\{u^{(i)}\\}$, as well as
constructing $\\{\mathcal{B}_{i}\\}$ (Lines 1–1) is
$O\left(\sum_{i=1}^{k}|P_{i}|\log|P_{i}|\right)=O(n\log n)$.

Now let $B_{j}\in\mathcal{B}$ be an arbitrary bucket, and we study the
construction of $\mathcal{T}_{B_{j}}$. We assume that $B_{j}$ has vertices
$u_{1},\dots,u_{n_{j}}$ sorted in increasing order of their degrees, where
$n_{j}=|B_{j}|$. We construct the balanced tree $\mathcal{T}_{B_{j}}$
recursively as follows:

  1. 1.

Initialise a root node $N_{0}$, such that $N_{0}(\mathsf{size})=n_{j}$, and
$N_{0}(\mathsf{parent})=\emptyset$;

  2. 2.

Create nodes $N_{1}$ and $N_{2}$ corresponding to the vertices
$u_{1},\dots,u_{\lceil n_{j}/2\rceil}$ an $u_{\lceil n_{j}/2\rceil+1},\dots
u_{n_{j}}$ respectively. Set $N_{1}(\mathsf{parent})=N_{0}$ and
$N_{2}(\mathsf{parent})=N_{0}$;

  3. 3.

Recursively construct the subtrees rooted at $N_{1}$ and $N_{2}$ on the
corresponding sets of vertices, until we reach the leaves.

By construction, $\mathcal{T}_{B_{j}}$ is a balanced tree and has $O(n_{j})$
internal nodes. Hence, the depth of $\mathcal{T}_{B_{j}}$ is $O(\log
n_{j})=O(\log n)$. Moreover, it’s straightforward to see that this step (Lines
1–1) takes $O(n\log n)$ time for constructing each $\mathcal{T}_{B_{j}}$.

For constructing the contracted graph $H$ from $\mathcal{B}$, notice that
every edge of $G$ only contributes to exactly one of the edge weights in $H$;
as such constructing $H$ (Line 1) takes $O(m)$ time. Finally, to complete the
construction of $\mathcal{T}$, we run the WRSC algorithm on $H$ (Line 1), and
assume that we know how the vertices are split at each iteration of the
recursive weighted sparsest cut algorithm. We construct the tree $\mathcal{T}$
recursively as follows:

  1. 1.

Initialise a root node $R_{0}$, such that $R_{0}(\mathsf{size})=n$, and
$R_{0}(\mathsf{parent})=\emptyset$;

  2. 2.

Create two nodes $R_{1}$ and $R_{2}$ corresponding to the sets $A$ and $B$,
where $(A,B)$ is the first split of the WRSC algorithm. Set
$R_{1}(\mathsf{parent})=R_{0}$ and $R_{2}(\mathsf{parent})=R_{0}$;

  3. 3.

Recursively construct the subtrees rooted at $R_{1}$ and $R_{2}$ on the
corresponding sets of vertices and split $(A,B)$ returned by the WRSC
algorithm, until we reach the leaves corresponding to $B_{1},\ldots
B_{\kappa}$.

  4. 4.

For each $\mathcal{T}_{B_{j}}\in\mathbb{T}$, we update the parent of the root
node $N_{0}(\mathsf{parent})$ with
$N_{0}(\mathsf{parent})=R_{B_{j}}(\mathsf{parent})$, where $R_{B_{j}}$ is the
leaf node corresponding to $B_{j}$ in the tree construction returned above by
the WRSC algorithm. We also delete the leaf node $R_{B_{j}}$, thereby
effectively replacing $R_{B_{j}}$ by $\mathcal{T}_{B_{j}}$.

By Lemma B.7 we know that the WRSC algorithm (Line 1) runs in nearly-linear
$\widetilde{O}(m)$ time. Taking everything together, this proves the time
complexity of Algorithm 1. The $O(\log n)$ depth of $\mathcal{T}$ follows by
the fact that (i) the depth of every tree $\mathcal{T}_{B_{j}}$ is $O(\log
n)$, and (ii) the distance between the root of $\mathcal{T}$ and the root of
any such tree $\mathbb{T}_{B_{j}}$ in $\mathcal{T}$ is also $O(\log{n})$.

Finally, to set the $\mathsf{depth}$ attribute of every internal node, we
perform a top-down traversal from the root of $\mathcal{T}$ to the leaves, and
update the $\mathsf{depth}$ for every internal node as one more than the depth
of their parent. ∎

We are now ready to prove the main result, which we will state here in full.

######  Theorem B.10 (Formal statement of Theorem 5.1).

Let $G=(V,E,w)$ be a graph with
$w_{\mathrm{max}}/w_{\mathrm{min}}=O(n^{\gamma})$ for a constant $\gamma>1$,
and $k>1$ such that $\lambda_{k+1}>0$ and $\lambda_{k}<\left(\frac{1}{270\cdot
c_{0}\cdot(k+1)^{6}}\right)^{2}$, where $c_{0}$ is the constant in Lemma A.12.
Algorithm 1 runs in time $\widetilde{O}(m)$ and both constructs an HC tree
$\mathcal{T}$ of $G$ and computes $\mathsf{COST}_{G}(\mathcal{T})$ satisfying
$\mathsf{COST}_{G}(\mathcal{T})=O\left(2^{k(\gamma+1)}\cdot
k^{23}/\lambda_{k+1}^{10}\right)\cdot\mathsf{OPT}_{G}$. In particular, when
$\lambda_{k+1}=\Omega(1)$ and $k=O(1)$, the algorithm’s constructed tree
$\mathcal{T}$ satisfies that
$\mathsf{COST}_{G}(\mathcal{T})=O(1)\cdot\mathsf{OPT}_{G}$.

###### Proof of Theorem B.10.

Let $\mathcal{T}$ be the tree returned by Algorithm 1. By combining (5.2),
(5.5), Lemma 5.2, and the approximation guarantee in Lemma B.7 we have that

$\mathsf{COST}_{G}(\mathcal{T})=O\left(2^{k(\gamma+1)}\cdot
k^{23}/\lambda_{k+1}^{10}\right)\cdot\mathsf{OPT}_{G}.$

The time complexity of Algorithm 1 follows by Lemma B.9. Moreover, as the
depth of $\mathcal{T}$ is $O(\log n)$, and every internal node
$N\in\mathcal{T}$ has a pointer $\mathsf{parent}$ and attributes
$\mathsf{size}$ and $\mathsf{depth}$, by Lemma B.8 we can compute
$\mathsf{COST}_{G}(\mathcal{T})$ in nearly-linear time $\widetilde{O}(m)$.

We complete the proof by dealing with our assumption that the algorithm knows
the number of clusters $k$. If the number of clusters $k$ is unknown, we
perform a standard technique from the literature [CAKMT17, MS21] and run
independent copies of Algorithm 1 with all possible values $k^{\prime}$
ranging from $1$ to $k$. By adding an extra $O(k)=O(1)$ factor in the overall
time complexity, we ensure that one of the runs has the correct number of
clusters $k^{\prime}=k$. ∎

##  Appendix C Omitted Details of Proof of Theorem 5.4

This section presents omitted details of the proof of Theorem 5.4, and is
structured as follows: we present a technical overview of our result in
Section C.1; we describe our designed algorithm in Section C.2, and prove
Theorem 5.4 in Section C.3. We introduce the parameter $\eta_{S}$ such that

$\eta_{S}\geqslant\max_{1\leqslant i\leqslant
k}\frac{\Delta(S_{i})}{\delta(S_{i})};$

this will be used in our later discussion.

###  C.1 Overview of Main Techniques

We give an overview of our main techniques and discuss why spectral clustering
suffices to construct HC trees with good approximation guarantees for well-
clustered graphs. One general challenge for analysing the approximation ratio
of any HC tree $\mathcal{T}$ of $G$ is due to the limited understanding of the
“structure” of an optimal HC tree. There are two main approaches to address
this: (1) the first approach is to ensure that most “cuts” induced at the top
of the tree $\mathcal{T}$ are sparse; as such, a recursive application of the
sparsest cut algorithm is employed; (2) the second approach is to reason about
the structure of an optimal HC tree assuming that the underlying graphs have a
highly symmetric hierarchical structure of clusters [CAKMT17], or a clear
cluster structure [MS21]. In particular, the algorithm in [MS21] requires that
every returned vertex set has high inner conductance. Therefore, taking these
into account, the starting point of our approach is to consider the role of
high inner-conductance in bounding the cost of an HC tree.

Suppose that the optimal clusters $S_{1},\ldots,S_{k}$ corresponding to
$\rho(k)$ are given, and it holds $\Phi_{G[S_{i}]}\geqslant\Phi_{\mathrm{in}}$
for $1\leqslant i\leqslant k$. These $k$ clusters could have different sizes,
volumes, and degree distributions. We show that one can construct a tree
$\mathcal{T}_{S}$, by first constructing trees $\mathcal{T}_{G[S_{i}]}$ on
every induced subgraph $G[S_{i}]$, and simply concatenating these
$\mathcal{T}_{G[S_{i}]}$ in a “caterpillar” style according to the sizes of
$|S_{i}|~{}(1\leqslant i\leqslant k)$. Moreover, the cost of our constructed
tree $\mathcal{T}_{S}$ can be upper bounded with respect to
$\mathsf{OPT}_{G}$. See Figure 5 for an illustration of a caterpillar tree,
and Lemma C.1 for a formal statement; the proof of Lemma C.1 can be found at
the end of the subsection.

$d_{u}$$d_{u}\beta$$d_{u}\beta^{-1}$$\delta_{G}(P_{i})$$d_{u}$$\Delta_{G}(P_{i})$$B(u)$$\mathcal{T}_{\mathsf{MS}}^{\prime}$$N_{i}\cap
B_{1}$$N_{i}\cap B_{2}$$N_{i}\cap
B_{\kappa}$$\mathcal{T}_{\mathsf{MS}}^{\prime\prime}$$N_{i}\cap
B_{1}$$N_{i}\cap B_{\kappa}$$N_{2}\cap B_{2}$$N_{1}\cap B_{2}$$N_{k_{1}}\cap
B_{2}$$S_{1}$$S_{2}$$S_{k-1}$$S_{k}$$\mathcal{T}_{S}$

Figure 5: An illustration of our constructed “caterpillar” tree from optimal
clusters $S_{1},\ldots,S_{k}$ that satisfy
$|S_{1}|\geqslant\ldots\geqslant|S_{k}|$.

######  Lemma C.1.

Let $G=(V,E,w)$ be an input graph of $n$ vertices, and $G$ has optimal
clusters $S_{1},\ldots,S_{k}$ corresponding to $\rho(k)\leqslant 1/k$ and it
holds that $\Phi_{G[S_{i}]}\geqslant\Phi_{\mathrm{in}}$ for $1\leqslant
i\leqslant k$. Given $S_{1},\ldots,S_{k}$ as part of the input, there is a
nearly-linear time algorithm that constructs an HC tree $\mathcal{T}_{S}$ such
that

$\mathsf{COST}_{G}(\mathcal{T}_{S})\leqslant\frac{36\cdot\eta_{S}}{\Phi_{\mathrm{in}}}\cdot\mathsf{OPT}_{G}.$

Since $\Phi_{\mathrm{in}}=\Omega(1)$ for many well-clustered graphs, Lemma C.1
states that a simple caterpillar construction based on the $k$ optimal
clusters achieves an approximation of $O(\eta_{S})$, which is $O(1)$ if the
degrees of _every_ cluster are almost-balanced. Moreover, thanks to this
caterpillar structure over the $S_{i}$’s and an arbitrary tree construction
for every $G[S_{i}]$, we can construct $\mathcal{T}_{S}$ and compute its cost
in nearly-linear time.

However, the above discussion assumes that the optimal clusters are known,
which are co-$\mathsf{NP}$ hard to find [BKV+81]. As the starting point of our
algorithm, we therefore employ the spectral clustering algorithm, expecting
that the output clusters $P_{1},\ldots,P_{k}$ could directly replace
$S_{1},\ldots,S_{k}$. Unfortunately, it is unclear whether this approach would
work for the following two reasons:

  1. 1.

while the output $P_{1},\ldots,P_{k}$ of spectral clustering can be applied to
approximate the optimal $S_{1},\ldots,S_{k}$, it is unknown whether every
$P_{i}$ approximates their corresponding optimal $S_{i}$ with respect to
$\Phi_{G[S_{i}]}$; moreover, it remains open whether the inner conductance
$\Phi_{G[S_{i}]}$ is approximated by $\Phi_{G[P_{i}]}$. Without the inner
conductance guarantee of $\Phi_{G[P_{i}]}$ for all $1\leqslant i\leqslant k$,
we cannot apply Lemma C.1.

  2. 2.

while Lemma A.9 shows that the symmetric difference between every $P_{i}$ and
their optimal corresponding $S_{i}$ can be bounded, this approximation
guarantee can still increase the ratio between the maximum and minimum degrees
in $P_{i}$. That is, with spectral clustering alone, we cannot upper bound
$\eta_{P}$ (which is an upper bound for
$\max_{i}(\Delta(P_{i})/\delta(P_{i}))$) from $\eta_{S}$. Moreover, Lemma A.9
does not provide any guarantees on the difference in size between $S_{i}$ and
$P_{i}$, which is crucial if we want to construct arbitrary
$\mathcal{T}_{P_{i}}$’s.

We overcome these two bottlenecks through the following high-level ideas:

  1. 1.

we show that bounded inner conductance of every output $P_{i}$ isn’t needed,
and that the approximate $P_{i}$’s returned from spectral clustering suffice
to construct an HC tree with guaranteed approximation. This is a fundamental
difference compared with [MS21], which requires the inner conductance being
constant for every partition set.

  2. 2.

we introduce a novel bucketing procedure that decomposes $P_{i}$’s into
further subsets, by grouping together vertices of similar degree. These
subsets will form the basis of our tree construction.

Thanks to the bucketing step, we are able to construct an HC tree in nearly-
linear line.

###### Proof of Lemma C.1.

Given an input graph $G$ and optimal clusters $S_{1},\ldots,S_{k}$ such that
$|S_{1}|\geqslant\ldots\geqslant|S_{k}|$, we construct the tree
$\mathcal{T}_{S}$ through the following two steps: first of all, we construct
an arbitrary HC tree $\mathcal{T}_{S_{i}}$ for every $G[S_{i}]$, $1\leqslant
i\leqslant k$; secondly, we construct $\mathcal{T}_{S}$ by concatenating the
trees $\mathcal{T}_{S_{1}},\ldots,\mathcal{T}_{S_{k}}$ in a caterpillar style,
i.e., $\mathcal{T}_{S_{1}}$ is at the top of the tree, and
$\mathcal{T}_{S_{2}},\ldots,\mathcal{T}_{S_{k}}$ are appended inductively.
Since we can construct every $\mathcal{T}_{G[S_{i}]}$ in an arbitrary manner
and the tree $\mathcal{T}_{S}$ can be constructed from
$\\{\mathcal{T}_{G[S_{i}]}\\}_{1\leqslant i\leqslant k}$ through sorting the
clusters by their sizes, the overall algorithm runs in nearly-linear time.

Next, we analyse $\mathsf{COST}_{G}(\mathcal{T}_{S})$. By definition, it holds
that

$\mathsf{COST}_{G}(\mathcal{T}_{S})=\sum_{i=1}^{k}\sum_{e\in
E[G[S_{i}]]}\mathsf{cost}_{G}(e)+\sum_{e\in\widetilde{E}}\mathsf{cost}_{G}(e),$
(C.1)

where $\widetilde{E}$ is the set of edges crossing different clusters. For the
first summation of (C.1), we have that

$\sum_{i=1}^{k}\mathsf{COST}_{G[S_{i}]}(\mathcal{T}_{S_{i}})\leqslant\frac{18\cdot\eta_{S}}{\Phi_{\mathrm{in}}}\cdot\sum_{i=1}^{k}\mathsf{OPT}_{G[S_{i}]}\leqslant\frac{18\cdot\eta_{S}}{\Phi_{\mathrm{in}}}\cdot\mathsf{OPT}_{G}.$
(C.2)

Here, the first inequality follows the fact that the cost of any HC tree of
$G=(V,E,w)$ is at most $|V|\cdot\mathrm{vol}(G)$ (Fact A.1) and subsequently
applying Lemma A.8; the second inequality holds because
$\mathsf{OPT}_{G[S_{i}]}$ is at most $\mathsf{OPT}_{G}$ for all $1\leqslant
i\leqslant k$.

For the second summation of (C.1), it holds that

$\sum_{e\in\widetilde{E}}\mathsf{cost}_{G}(e)=\sum_{i=1}^{k-1}\sum_{j=i+1}^{k}\sum_{\begin{subarray}{c}u\in
S_{i},v\in S_{j}\\\ e=\\{u,v\\}\end{subarray}}\mathsf{cost}_{G}(e).$

We look at all the edges adjacent to vertices in $S_{1}$. By construction, it
holds that $|S_{1}|\geqslant n/k$, and
$\lvert\mathsf{leaves}\left(\mathcal{T}_{S}[u\vee v]\right)\rvert=n$ for any
edge $\\{u,v\\}$ satisfying $u\in S_{1},v\in V\setminus S_{1}$. Since
$w(S_{1},V\setminus S_{1})\leqslant\mathrm{vol}(S_{1})\cdot\rho(k)$, it holds
that

$\sum_{\begin{subarray}{c}u\in S_{1},v\not\in S_{1}\\\
e=\\{u,v\\}\end{subarray}}\mathsf{cost}_{G}(e)=n\cdot w(S_{1},V\setminus
S_{1})\leqslant n\cdot\mathrm{vol}(S_{1})\cdot\rho(k)\leqslant
k\cdot|S_{1}|\cdot\rho(k)\cdot\mathrm{vol}(S_{1}).$

We continue with looking at the edges between $S_{2}$ and
$V\setminus(S_{1}\cup S_{2})$. As $S_{2}$ is the largest cluster among
$S_{2},\ldots,S_{k}$, it holds that $|S_{2}|\geqslant\frac{n-|S_{1}|}{k-1}$,
which implies that $n-|S_{1}|<k\cdot|S_{2}|$. Notice that any edge
$e=\\{u,v\\}$ with $u\in S_{2}$ and $v\in V\setminus(S_{1}\cup S_{2})$
satisfies that $\lvert\mathsf{leaves}\left(\mathcal{T}_{S}[u\vee
v]\right)\rvert=n-|S_{1}|$, and as such we have that

$\sum_{\begin{subarray}{c}u\in S_{2},v\not\in S_{1}\cup S_{2}\\\
e=\\{u,v\\}\end{subarray}}\mathsf{cost}_{G}(e)\leqslant(n-|S_{1}|)\cdot
w(S_{2},V\setminus(S_{1}\cup S_{2}))\leqslant
k\cdot|S_{2}|\cdot\rho(k)\cdot\mathrm{vol}(S_{2}).$

Generalising the analysis above, we have that

$\displaystyle\sum_{e\in\widetilde{E}}\mathsf{cost}_{G}(e)$
$\displaystyle=\sum_{i=1}^{k-1}\sum_{j=i+1}^{k}\sum_{\begin{subarray}{c}u\in
S_{i},v\in S_{j}\\\ e=\\{u,v\\}\end{subarray}}\mathsf{cost}_{G}(e)$
$\displaystyle\leqslant
k\cdot\rho(k)\cdot\sum_{i=1}^{k}|S_{i}|\cdot\mathrm{vol}(S_{i})$
$\displaystyle\leqslant\frac{18\cdot\eta_{S}}{\Phi_{\mathrm{in}}}\cdot\sum_{i=1}^{k}\mathsf{OPT}_{G[S_{i}]},$
(C.3)

where the last inequality follows from Lemma A.8. Combining (C.1), (C.2) with
(C.3), we have that

$\mathsf{COST}_{G}(\mathcal{T}_{S})\leqslant\frac{36\cdot\eta_{S}}{\Phi_{\mathrm{in}}}\cdot\mathsf{OPT}_{G},$

which proves the statement. ∎

###  C.2 Algorithm Description

Now informally describe our algorithm and refer the reader to Algorithm 2 for
the formal presentation. The algorithm takes as input a graph $G=(V,E,w)$ with
$k$ optimal clusters $\\{S_{i}\\}_{i=1}^{k}$. For simplicity, we assume that
the algorithm knows the target number of clusters $k$ and an upper bound
$\eta_{S}$ such that

$\eta_{S}\geqslant\max_{1\leqslant i\leqslant
k}\frac{\Delta(S_{i})}{\delta(S_{i})},$

and we carefully deal with this assumption at the end of the section. As the
first step, the algorithm runs the $\mathsf{SpectralClustering}$ subroutine
and obtains the approximate clusters $\\{P_{i}\\}_{i=1}^{k}$. Following our
previous discussion, it is unclear whether the algorithm can or cannot use the
clusters $P_{i}$ directly in order to construct an $O(1)$-approximate tree. To
overcome this difficulty, we further partition every $P_{i}$ into degree-based
buckets, but rather than setting $\beta=2^{k(\gamma+1)}$ as we did for
Algorithm 1, we set $\beta=\eta_{S}$. Recall then for any set $P_{i}$ and
every vertex $u\in P_{i}$, the _bucket_ of $P_{i}$ starting at $u$ is defined

$B\left(u\right)=\left\\{v\in P_{i}:d_{u}\leqslant d_{v}<\eta_{S}\cdot
d_{u}\right\\}.$

Again, it is important to note that the bucket $B(u)$ contains _every_ vertex
$v\in P_{i}$ whose degree satisfies $d_{u}\leqslant d_{v}<\eta_{S}\cdot
d_{u}$. We refer the reader to Figure 6(a) for an illustration of the
bucketing procedure.

$d_{u}$$d_{u}\beta$$d_{u}\beta^{-1}$$\delta_{G}(P_{i})$$d_{u}$$\Delta_{G}(P_{i})$$B(u)$$\mathcal{T}_{\mathsf{MS}}^{\prime}$$N_{i}\cap
B_{1}$$N_{i}\cap B_{2}$$N_{i}\cap
B_{\kappa}$$\mathcal{T}_{\mathsf{MS}}^{\prime\prime}$$N_{i}\cap
B_{1}$$N_{i}\cap B_{\kappa}$$N_{2}\cap B_{2}$$N_{1}\cap B_{2}$$N_{k_{1}}\cap
B_{2}$$S_{1}$$S_{2}$$S_{k-1}$$S_{k}$$\mathcal{T}_{S}$$d_{u}$$d_{u}\eta_{S}$$d_{u}\eta_{S}^{-1}$$\delta(P_{i})$$d_{u}$$\Delta(P_{i})$$B(u)$

(a)

$d_{u}$$d_{u}\beta$$d_{u}\beta^{-1}$$\delta_{G}(P_{i})$$d_{u}$$\Delta_{G}(P_{i})$$B(u)$$\mathcal{T}_{\mathsf{MS}}^{\prime}$$N_{i}\cap
B_{1}$$N_{i}\cap B_{2}$$N_{i}\cap
B_{\kappa}$$\mathcal{T}_{\mathsf{MS}}^{\prime\prime}$$N_{i}\cap
B_{1}$$N_{i}\cap B_{\kappa}$$N_{2}\cap B_{2}$$N_{1}\cap B_{2}$$N_{k_{1}}\cap
B_{2}$$S_{1}$$S_{2}$$S_{k-1}$$S_{k}$$\mathcal{T}_{S}$$d_{u}$$d_{u}\eta_{S}$$d_{u}\eta_{S}^{-1}$$\delta(P_{i})$$d_{u}$$\Delta(P_{i})$$B(u)$$d_{u_{i}^{*}}$$d_{u_{i}^{*}}\eta_{s}$$d_{u_{i}^{*}}\eta^{-1}_{s}$$\delta(P_{i})$$d_{u_{i}^{*}}$$\Delta(P_{i})$$B(u_{i}^{*})$

(b)

Figure 6: This figure illustrates two different bucketings of the vertices
inside some $P_{i}$. Figure (a) is a bucketing induced by some vertex $u$.
Figure (b) is the bucketing induced by $u_{i}^{*}$ with
$\mathrm{vol}\\!\left(\\!\,B(u^{*})\,\\!\right)$ maximised.

Similar to before, vertices $u,v\in P_{i}$ having different degrees $d_{u}\neq
d_{v}$ generally induce different bucketings. In order to determine the
appropriate bucketing, Algorithm 2 chooses as representative a vertex
$u_{i}^{*}\in P_{i}$, whose induced bucket $B\left(u_{i}^{*}\right)$ has the
highest volume (Line 2 of Algorithm 2). To motivate this choice, notice that
every cluster $P_{i}$ has a large overlap with its corresponding optimal
cluster $S_{i}$ and the degrees of the vertices inside $S_{i}$ are within a
factor of $\eta_{S}$ of each other. If an arbitrary vertex $u\in P_{i}$ is
chosen as representative, the bucketing $B\left(u\right)$ of $P_{i}$ might
equally divide the vertices in $P_{i}\cap S_{i}$ into two consecutive buckets,
which is undesirable. However, we will prove that our specific choice of
$u_{i}^{*}$ guarantees that the bucketing $\mathcal{B}_{u_{i}^{*}}$ contains
one bucket $B_{j}\in\mathcal{B}_{u_{i}^{*}}$ largely overlapping with $S_{i}$
(see Figure 6(b) for an illustration).

Once the bucketing procedure of $P_{i}$ is complete the algorithm proceeds and
constructs an arbitrary _balanced_ binary tree $\mathcal{T}_{B_{j}}$, for
every bucket $B_{j}$, and adds the tree $\mathcal{T}_{B_{j}}$ to a global set
of trees $\mathbb{T}$. This process is repeated for every cluster $P_{i}$. As
a final step, the algorithm merges the trees inside $\mathbb{T}$ in a
caterpillar fashion in decreasing order of the sizes, placing the larger sized
trees closer to the root (Lines 2-2 of Algorithm 2). The resulting tree
$\mathcal{T}_{\mathrm{SCB}}$ is the output of the algorithm.

###  C.3 Algorithm Analysis

This subsection analyses the performance of Algorithm 2, and proves Theorem
5.4. It is organised as follows: in the first part we prove several properties
of our carefully constructed bucketing procedure. In the second part, we prove
that the cost of our constructed tree $\mathcal{T}_{\mathrm{SCB}}$ achieves
the claimed approximation guarantee. Thirdly, we give a detailed description
of how we can efficiently construct the tree $\mathcal{T}_{\mathrm{SCB}}$ and
compute its cost in nearly-linear time. The proof of Theorem 5.4 follows by
combining the three main results.

We first prove that our bucketing procedure induces at most $2k$ buckets
inside every cluster $P_{i}$, and the total number of buckets throughout all
clusters $P_{i}$ is at most $2k^{2}$.

######  Lemma C.2.

Let $P_{i}$ be an arbitrary cluster, and
$u^{*}_{i}=\operatorname{argmax}_{u\in
P_{i}}\mathrm{vol}\\!\left(\\!\,B\left(u\right)\,\\!\right)$ be a vertex
inducing the bucketing $\mathcal{B}_{u_{i}^{*}}$. The following statements
hold:

  1. 1.

$B\left(u_{i}^{*}\right)\in\mathcal{B}_{u_{i}^{*}}$;

  2. 2.

For every optimal cluster $S_{j}$, the vertices in $S_{j}\cap P_{i}$ belong to
at most two buckets, i.e.,

$\left\lvert\left\\{B_{t}\in\mathcal{B}_{u_{i}^{*}}:S_{j}\cap
B_{t}\neq\emptyset\right\\}\right\rvert\leqslant 2;$

  3. 3.

The bucketing induced by $u_{i}^{*}$ contains at most $2k$ buckets
$\left\lvert\mathcal{B}_{u_{i}^{*}}\right\rvert\leqslant 2k$.

###### Proof.

The first property follows trivially from the definition. The second property
follows from our assumption that
$\Delta(S_{i})\leqslant\eta_{S}\cdot\delta(S_{i})$ for every optimal cluster
$S_{i}$. Therefore, the vertices inside $S_{i}$ belong to at most $2$ buckets.
The third property follows from the second one and summing over all clusters.
∎

Our second result presents a very important property of our bucketing
procedure. We show that, in every cluster $P_{i}$, exactly one bucket
$B_{j}\in\mathcal{B}_{u_{i}^{*}}$ has large overlap with the optimal cluster
$S_{i}$, and all the other buckets have low volume. We emphasise that this
result is only possible due to our calibration technique of choosing the
bucketing induced by a vertex $u_{i}^{*}\in P_{i}$, whose bucket
$B\left(u_{i}^{*}\right)$ has the highest volume.

######  Lemma C.3.

Let $P_{i}$ be an arbitrary cluster, and
$u^{*}_{i}=\operatorname{argmax}_{u\in
P_{i}}\mathrm{vol}\\!\left(\\!\,B\left(u\right)\,\\!\right)$ be a vertex
inducing the bucketing $\mathcal{B}_{u_{i}^{*}}$. The following two statements
hold:

  1. 1.

There exists a unique _heavy_ bucket $B_{j}\in\mathcal{B}_{u^{*}_{i}}$ such
that $\mathrm{vol}\\!\left(\\!\,B_{j}\cap
S_{i}\,\\!\right)\geqslant\left(1-\frac{2k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\right)\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)$;

  2. 2.

For every other bucket $B_{t}\in\mathcal{B}_{u^{*}_{i}}\setminus\\{B_{j}\\}$
it holds that
$\mathrm{vol}\\!\left(\\!\,B_{t}\,\\!\right)\leqslant\frac{k\cdot
C_{\ref{lem:MS22+}}}{\Upsilon(k)}\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)$.

###### Proof.

For the first statement, we show that the bucket $B(u^{*}_{i})$ satisfies the
claim. Let $u_{\min}$ be a vertex in $P_{i}\cap S_{i}$ of the lowest degree.
Since the degrees of all vertices in $S_{i}$ (and hence in $P_{i}\cap S_{i}$)
are within a factor of $\eta_{S}$ from each other, we know that all vertices
in $P_{i}\cap S_{i}$ must be in the bucket $B\left(u_{\min}\right)$, i.e.,
$P_{i}\cap S_{i}\subseteq B\left(u_{\min}\right)$. Moreover, by the choice of
$u^{*}_{i}$ we have that

$\mathrm{vol}\\!\left(\\!\,B\left(u^{*}_{i}\right)\,\\!\right)\geqslant\mathrm{vol}\\!\left(\\!\,B\left(u_{\min}\right)\,\\!\right)\geqslant\mathrm{vol}\\!\left(\\!\,P_{i}\cap
S_{i}\,\\!\right)\geqslant\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)-\mathrm{vol}\\!\left(\\!\,P_{i}\triangle
S_{i}\,\\!\right)\geqslant\left(1-\frac{k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\right)\cdot\mathrm{vol}(S_{i}),$ (C.4)

where the last inequality follows by Lemma A.9. We now write

$\displaystyle\mathrm{vol}\\!\left(\\!\,B\left(u_{i}^{*}\right)\cap
S_{i}\,\\!\right)$
$\displaystyle=\mathrm{vol}\\!\left(\\!\,B\left(u^{*}_{i}\right)\,\\!\right)-\mathrm{vol}\\!\left(\\!\,B\left(u^{*}_{i}\right)\setminus
S_{i}\,\\!\right)$ $\displaystyle\geqslant\left(1-\frac{k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\right)\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)-\mathrm{vol}\\!\left(\\!\,P_{i}\setminus
S_{i}\,\\!\right)$ $\displaystyle\geqslant\left(1-\frac{2k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\right)\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right),$

where the first inequality uses (C.4). The uniqueness of the heavy bucket
follows by noticing that $\mathrm{vol}\\!\left(\\!\,B(u_{i}^{*})\cap
S_{i}\,\\!\right)>\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)/2$.

The second statement essentially follows from the fact that $S_{i}$ has a
large volume overlap with $B\left(u_{i}^{*}\right)$. Concretely, let
$B_{t}\in\mathcal{B}_{u_{i}^{*}}\setminus\left\\{B\left(u_{i}^{*}\right)\right\\}$
be an arbitrary bucket. We have that

$\displaystyle\mathrm{vol}\\!\left(\\!\,B_{t}\,\\!\right)$
$\displaystyle=\mathrm{vol}\\!\left(\\!\,B_{t}\cap
S_{i}\,\\!\right)+\mathrm{vol}\\!\left(\\!\,B_{t}\setminus S_{i}\,\\!\right)$
$\displaystyle\leqslant\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)-\mathrm{vol}\\!\left(\\!\,S_{i}\setminus
B_{t}\,\\!\right)+\mathrm{vol}\\!\left(\\!\,P_{i}\setminus S_{i}\,\\!\right)$
$\displaystyle\leqslant\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)-\mathrm{vol}\\!\left(\\!\,S_{i}\cap
B\left(u_{i}^{*}\right)\,\\!\right)+\mathrm{vol}\\!\left(\\!\,P_{i}\triangle
S_{i}\,\\!\right)$ $\displaystyle\leqslant\frac{2k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)+\frac{k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)$
$\displaystyle=\frac{k\cdot
C_{\ref{lem:MS22+}}}{\Upsilon(k)}\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right).$

This completes the proof. ∎

In order to analyse the final constructed tree $\mathcal{T}_{\mathrm{SCB}}$,
we analyse the properties of the buckets in the context of the entire graph
$G$, and not just on every set $P_{i}$. We denote by $\mathcal{B}$ the set
containing all the buckets obtained throughout all sets $P_{i}$, i.e.,

$\mathcal{B}\triangleq\bigcup_{i=1}^{k}\mathcal{B}_{u^{*}_{i}},$

where $u^{*}_{i}=\operatorname{argmax}_{u\in
P_{i}}\mathrm{vol}\\!\left(\\!\,B\left(u\right)\,\\!\right)$ is a vertex
inducing the corresponding bucketing in set $P_{i}$. We remark that
$\mathcal{B}$ is a partition of $V$. We use

$\ell\triangleq|\mathcal{B}|$

to denote the total number of buckets, and we know by Lemma C.2 that
$\ell\leqslant 2k^{2}$. For convenience, we label the buckets
$\mathcal{B}=\\{B_{1},\dots,B_{\ell}\\}$ in decreasing order of the sizes
breaking ties arbitrarily, i.e., $|B_{i}|\geqslant|B_{i+1}|$, for all
$i<\ell$.

Based on Lemma C.3, exactly $k$ buckets in $\mathcal{B}$ are heavy, meaning
that they have large overlap with the optimal clusters $S_{i}$. We denote by
$\mathcal{B}_{\mathrm{H}}$ the set of those $k$ buckets; we emphasise once
more that each heavy bucket corresponds to a unique cluster $S_{i}$ and vice-
versa. Additionally, we denote by
$\mathcal{B}_{\mathrm{L}}\triangleq\mathcal{B}\setminus\mathcal{B}_{\mathrm{H}}$
the set of the remaining _light_ buckets.

The next two results summarise the main properties of our constructed buckets.
We first present three properties of the heavy buckets which bound their size,
volume and weight of the crossing edges.

######  Lemma C.4.

For every heavy bucket $B_{j}\in\mathcal{B}_{\mathrm{H}}$ corresponding to
$S_{i}$, the following statements hold:

  1. (B1)

$\mathrm{vol}\\!\left(\\!\,B_{j}\,\\!\right)\leqslant\left(1+\frac{k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\right)\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)$;

  2. (B2)

$|B_{j}|\leqslant\left(1+\eta_{S}\right)\cdot|S_{i}|$.

  3. (B3)

$w(B_{j},\overline{B_{j}})\leqslant\frac{k\cdot
C_{\ref{lem:MS22+}}+\lambda_{k+1}}{\Upsilon(k)}\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)$.

###### Proof.

Let $B_{j}\in\mathcal{B}_{\mathrm{H}}$ be a heavy bucket corresponding to
$S_{i}$. For (B1), we have that

$\mathrm{vol}\\!\left(\\!\,B_{j}\,\\!\right)=\mathrm{vol}\\!\left(\\!\,B_{j}\cap
S_{i}\,\\!\right)+\mathrm{vol}\\!\left(\\!\,B_{j}\setminus
S_{i}\,\\!\right)\leqslant\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)+\mathrm{vol}\\!\left(\\!\,P_{i}\triangle
S_{i}\,\\!\right)\leqslant\left(1+\frac{k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\right)\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right).$

To prove (B2), suppose for contradiction that
$|B_{j}|>\left(1+\eta_{S}\right)\cdot|S_{i}|$, which implies that
$|B_{j}\setminus S_{i}|=|B_{j}|-|B_{j}\cap S_{i}|>\eta_{S}\cdot|B_{j}\cap
S_{i}|$. Based on this, we have that

$\displaystyle\mathrm{vol}\\!\left(\\!\,B_{j}\setminus S_{i}\,\\!\right)$
$\displaystyle\geqslant|B_{j}\setminus S_{i}|\cdot\delta(B_{j}\setminus
S_{i})>\eta_{S}\cdot|B_{j}\cap S_{i}|\cdot\frac{\Delta(B_{j}\cap
S_{i})}{\eta_{S}}$ $\displaystyle\geqslant\mathrm{vol}\\!\left(\\!\,B_{j}\cap
S_{i}\,\\!\right)\geqslant\left(1-\frac{2k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\right)\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right),$

where the second inequality follows from the fact that, inside bucket $B_{j}$
all the degrees are within a factor of $\eta_{S}$ of each other and the last
inequality follows by Lemma C.3. This implies that

$\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)<\frac{1}{1-\frac{2k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}}\cdot\mathrm{vol}\\!\left(\\!\,P_{i}\triangle
S_{i}\,\\!\right)\leqslant\frac{\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)}{\frac{3\Upsilon(k)}{k\cdot
C_{\ref{lem:MS22+}}}-2}\leqslant\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right),$

where the second inequality follows by Lemma A.9, and last inequality by our
assumption on $\Upsilon(k)$.

Finally, we prove (B3). We have that

$\displaystyle w(B_{j},\overline{B_{j}})$ $\displaystyle\leqslant w(B_{j}\cap
S_{i},\overline{B_{j}})+w(B_{j}\setminus S_{i},\overline{B_{j}})$
$\displaystyle\leqslant w(B_{j}\cap S_{i},\overline{B_{j}}\cap
S_{i})+w(B_{j}\cap S_{i},\overline{B_{j}}\setminus
S_{i})+\mathrm{vol}\\!\left(\\!\,B_{j}\setminus S_{i}\,\\!\right)$
$\displaystyle\leqslant\mathrm{vol}\\!\left(\\!\,\overline{B_{j}}\cap
S_{i}\,\\!\right)+w(S_{i},\overline{S_{i}})+\mathrm{vol}\\!\left(\\!\,P_{i}\triangle
S_{i}\,\\!\right)$ $\displaystyle\leqslant\frac{2k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)+\rho(k)\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)+\frac{k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)$
(C.5) $\displaystyle\leqslant\frac{k\cdot
C_{\ref{lem:MS22+}}+\lambda_{k+1}}{\Upsilon(k)}\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right),$
(C.6)

where (C.5) follows from Lemmas C.3 and A.9, and (C.6) uses the fact that
$\rho(k)=\frac{\lambda_{k+1}}{\Upsilon(k)}$. ∎

The final technical result is similar with Lemma C.4, and presents several
useful upper bounds of the volume and size of the light buckets.

######  Lemma C.5.

For every _light_ bucket $B_{t}\in\mathcal{B}_{\mathrm{L}}$, the following
statements hold:

  1. (B4)

$\mathrm{vol}\\!\left(\\!\,B_{t}\cap
S_{j}\,\\!\right)\leqslant\eta_{S}\cdot\mathrm{vol}\\!\left(\\!\,B_{t}\cap
S_{i}\,\\!\right)$, for all clusters $S_{i},S_{j}$ satisfying $|B_{t}\cap
S_{j}|\leqslant|B_{t}\cap S_{i}|$;

  2. (B5)

$\mathrm{vol}\\!\left(\\!\,B_{t}\cap S_{i}\,\\!\right)\leqslant\frac{2k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)$,
for all clusters $S_{i}$;

  3. (B6)

$\sum_{B_{t}\in\mathcal{B}_{\mathrm{L}}}|B_{t}|\cdot\mathrm{vol}\\!\left(\\!\,B_{t}\,\\!\right)\leqslant\frac{4k^{2}\cdot
C_{\ref{lem:MS22+}}\cdot\eta_{S}}{3\Upsilon(k)}\cdot\sum_{i=1}^{k}|S_{i}|\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)$.

###### Proof.

Let $B_{t}\in\mathcal{B}_{\mathrm{L}}$ be a light bucket, and let
$S_{i},S_{j}$ be optimal clusters so that $|B_{t}\cap
S_{j}|\leqslant|B_{t}\cap S_{i}|$. It holds that

$\mathrm{vol}\\!\left(\\!\,B_{t}\cap S_{j}\,\\!\right)\leqslant|B_{t}\cap
S_{j}|\cdot\Delta(B_{t}\cap S_{j})\leqslant|B_{t}\cap
S_{j}|\cdot\eta_{S}\cdot\delta(B_{t}\cap
S_{i})\leqslant\eta_{S}\cdot\mathrm{vol}\\!\left(\\!\,B_{j}\cap
S_{i}\,\\!\right),$

where the second inequality uses the fact that inside bucket $B_{t}$ all the
degrees are within a factor of $\eta_{S}$. This proves (B4).

Next, we prove (B5). Suppose that $B_{t}$ is a bucket from some cluster
$P_{r}$, and let $S_{i}$ be an arbitrary cluster. The proof continues by a
case distinction:

##### Case $1$: $r=i$.

In this case, since $B_{t}$ is a light bucket in $P_{r}$, by Lemma C.3 we have
that

$\mathrm{vol}\\!\left(\\!\,B_{t}\cap
S_{i}\,\\!\right)=\mathrm{vol}\\!\left(\\!\,B_{t}\cap
S_{r}\,\\!\right)\leqslant\frac{2k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\cdot\mathrm{vol}\\!\left(\\!\,S_{r}\,\\!\right).$

##### Case $2$: $r\neq i$.

In this case we simply have that

$\mathrm{vol}\\!\left(\\!\,B_{t}\cap
S_{i}\,\\!\right)\leqslant\mathrm{vol}\\!\left(\\!\,P_{r}\cap
S_{i}\,\\!\right)\leqslant\mathrm{vol}\\!\left(\\!\,P_{i}\triangle
S_{i}\,\\!\right)\leqslant\frac{k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right).$

Combining the two cases proves (B5).

We finally prove (B6). We have that

$\displaystyle\sum_{B_{t}\in\mathcal{B}_{\mathrm{L}}}|B_{t}|\mathrm{vol}\\!\left(\\!\,B_{t}\,\\!\right)$
$\displaystyle=\sum_{B_{t}\in\mathcal{B}_{\mathrm{L}}}\left(\sum_{i=1}^{k}|B_{t}\cap
S_{i}|\right)\left(\sum_{j=1}^{k}\mathrm{vol}\\!\left(\\!\,B_{t}\cap
S_{j}\,\\!\right)\right)$
$\displaystyle=\sum_{B_{t}\in\mathcal{B}_{\mathrm{L}}}\sum_{i,j=1}^{k}|B_{t}\cap
S_{i}|\mathrm{vol}\\!\left(\\!\,B_{t}\cap S_{j}\,\\!\right)$
$\displaystyle=\sum_{B_{t}\in\mathcal{B}_{\mathrm{L}}}\left(\sum_{\begin{subarray}{c}i,j=1:\\\
|B_{t}\cap S_{i}|\leqslant|B_{t}\cap S_{j}|\end{subarray}}^{k}|B_{t}\cap
S_{i}|\mathrm{vol}\\!\left(\\!\,B_{t}\cap
S_{j}\,\\!\right)+\sum_{\begin{subarray}{c}i,j=1:\\\ |B_{t}\cap
S_{i}|>|B_{t}\cap S_{j}|\end{subarray}}^{k}|B_{t}\cap
S_{i}|\mathrm{vol}\\!\left(\\!\,B_{t}\cap S_{j}\,\\!\right)\right)$ (C.7)
$\displaystyle\leqslant\sum_{B_{t}\in\mathcal{B}_{\mathrm{L}}}\left(\sum_{\begin{subarray}{c}i,j=1:\\\
|B_{t}\cap S_{i}|\leqslant|B_{t}\cap S_{j}|\end{subarray}}^{k}|B_{t}\cap
S_{j}|\mathrm{vol}\\!\left(\\!\,B_{t}\cap
S_{j}\,\\!\right)+\sum_{\begin{subarray}{c}i,j=1:\\\ |B_{t}\cap
S_{i}|>|B_{t}\cap S_{j}|\end{subarray}}^{k}|B_{t}\cap
S_{i}|\cdot\eta_{S}\cdot\mathrm{vol}\\!\left(\\!\,B_{t}\cap
S_{i}\,\\!\right)\right)$ (C.8)
$\displaystyle\leqslant\sum_{B_{t}\in\mathcal{B}_{\mathrm{L}}}\left(k\sum_{j=1}^{k}|B_{t}\cap
S_{j}|\mathrm{vol}\\!\left(\\!\,B_{t}\cap
S_{j}\,\\!\right)+k\sum_{i=1}^{k}|B_{t}\cap
S_{i}|\cdot\eta_{S}\cdot\mathrm{vol}\\!\left(\\!\,B_{t}\cap
S_{i}\,\\!\right)\right)$ $\displaystyle\leqslant
2k\cdot\eta_{S}\sum_{i=1}^{k}\sum_{B_{t}\in\mathcal{B}_{\mathrm{L}}}|B_{t}\cap
S_{i}|\mathrm{vol}\\!\left(\\!\,B_{t}\cap S_{i}\,\\!\right)$
$\displaystyle\leqslant 2k\cdot\eta_{S}\cdot\frac{2k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\cdot\sum_{i=1}^{k}\sum_{B_{t}\in\mathcal{B}_{\mathrm{L}}}|B_{t}\cap
S_{i}|\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)$ (C.9)
$\displaystyle\leqslant\frac{4k^{2}\cdot
C_{\ref{lem:MS22+}}\cdot\eta_{S}}{3\Upsilon(k)}\sum_{i=1}^{k}|S_{i}|\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right),$

where (C.7) follows by grouping the terms $|B_{t}\cap
S_{i}|\mathrm{vol}\\!\left(\\!\,B_{t}\cap S_{j}\,\\!\right)$ into two
categories, (C.8) follows by (B4), and (C.9) follows by (B5). ∎

Now we combine the properties shown earlier, and upper bound the cost of our
constructed tree $\mathcal{T}_{\mathrm{SCB}}$ through the following lemma.

######  Lemma C.6.

It holds that

$\mathsf{COST}_{G}\left(\mathcal{T}_{\mathrm{SCB}}\right)\leqslant\left(1+\frac{5k^{4}\cdot
C_{\ref{lem:MS22+}}}{\Upsilon(k)}\right)\cdot\frac{36\cdot\eta_{S}^{2}}{\Phi_{\mathrm{in}}}\cdot\mathsf{OPT}_{G}.$

###### Proof.

By construction, we know that $\mathcal{T}_{\mathrm{SCB}}$ is the caterpillar
tree formed by merging the trees $\mathcal{T}_{B_{j}}$, for all
$B_{j}\in\mathcal{B}$. Therefore, in order to bound the overall cost it
suffices to bound the cost within each induced subtree $\mathcal{T}_{B_{j}}$
as well as the cost of the edges crossing different buckets. Formally, we have
that

$\displaystyle\mathsf{COST}_{G}\left(\mathcal{T}_{\mathrm{SCB}}\right)$
$\displaystyle=\sum_{j=1}^{\ell}\mathsf{COST}_{G[B_{j}]}\left(\mathcal{T}_{B_{j}}\right)+\sum_{j=1}^{\ell-1}\sum_{t=j+1}^{\ell}\sum_{e\in
E(B_{j},B_{t})}\mathsf{cost}_{G}(e)$
$\displaystyle\leqslant\sum_{j=1}^{\ell}|B_{j}|\mathrm{vol}\\!\left(\\!\,B_{j}\,\\!\right)+\sum_{j=1}^{\ell-1}\sum_{t=j+1}^{\ell}\sum_{e\in
E(B_{j},B_{t})}\mathsf{cost}_{G}(e).$ (C.10)

W study the first term of (C.10), and have that

$\displaystyle\sum_{j=1}^{\ell}|B_{j}|\mathrm{vol}\\!\left(\\!\,B_{j}\,\\!\right)$
$\displaystyle\leqslant\sum_{B_{j}\in\mathcal{B}_{\mathrm{H}}}|B_{j}|\mathrm{vol}\\!\left(\\!\,B_{j}\,\\!\right)+\sum_{B_{t}\in\mathcal{B}_{\mathrm{L}}}|B_{t}|\mathrm{vol}\\!\left(\\!\,B_{t}\,\\!\right)$
$\displaystyle\leqslant\left(1+\eta_{S}\right)\left(1+\frac{k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\right)\left(\sum_{i=1}^{k}|S_{i}|\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)\right)+\frac{4k^{2}\cdot
C_{\ref{lem:MS22+}}\cdot\eta_{S}}{3\Upsilon(k)}\cdot\left(\sum_{i=1}^{k}|S_{i}|\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)\right)$
(C.11) $\displaystyle\leqslant\left(2\eta_{S}\cdot\left(1+\frac{k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\right)+\frac{4k^{2}\cdot
C_{\ref{lem:MS22+}}\cdot\eta_{S}}{3\Upsilon(k)}\right)\sum_{i=1}^{k}|S_{i}|\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)$
$\displaystyle\leqslant\left(2\eta_{S}+\frac{2k^{2}\cdot
C_{\ref{lem:MS22+}}\cdot\eta_{S}}{\Upsilon(k)}\right)\cdot\frac{18\cdot\eta_{S}}{\Phi_{\mathrm{in}}}\cdot\mathsf{OPT}_{G}$
(C.12) $\displaystyle=\left(1+\frac{k^{2}\cdot
C_{\ref{lem:MS22+}}}{\Upsilon(k)}\right)\cdot\frac{36\cdot\eta_{S}^{2}}{\Phi_{\mathrm{in}}}\cdot\mathsf{OPT}_{G}$

where (C.11) follows from (B1), (B2), (B6), and (C.12) follows by Lemma A.8.

Next we look at the second term of (C.10). Let $B_{j}\in\mathcal{B}$ be an
arbitrary bucket, and we study the cost of the edges between $B_{j}$ and all
the other buckets $B_{t}$ positioned lower in the tree, i.e.,
$|B_{t}|\leqslant|B_{j}|$. By construction, for every such edge $e$ we have
that

$\mathsf{cost}_{G}(e)=w_{e}\sum_{t=j+1}^{\ell}|B_{t}|\leqslant
w_{e}\cdot\ell\cdot|B_{j}|.$

Therefore, we can upper bound the total cost of the crossing edges adjacent to
$B_{j}$ by

$\sum_{t=j+1}^{\ell}\sum_{e\in
E(B_{j},B_{t})}\mathsf{cost}_{G}(e)\leqslant\ell\cdot|B_{j}|w(B_{j},\overline{B_{j}}).$

Hence, by summing over all buckets $B_{j}$ we have that

$\displaystyle\sum_{j=1}^{\ell-1}\sum_{t=j+1}^{\ell}\sum_{e\in
E(B_{j},B_{t})}\mathsf{cost}_{G}(e)$
$\displaystyle\leqslant\sum_{j=1}^{\ell-1}\ell\cdot|B_{j}|w(B_{j},\overline{B_{j}})$
$\displaystyle\leqslant\ell\left(\sum_{B_{j}\in\mathcal{B}_{\mathrm{H}}}|B_{j}|w(B_{j},\overline{B_{j}})+\sum_{B_{t}\in\mathcal{B}_{\mathrm{L}}}|B_{t}|\mathrm{vol}\\!\left(\\!\,B_{t}\,\\!\right)\right)$
$\displaystyle\leqslant\ell\left(\left(1+\eta_{S}\right)\cdot\frac{k\cdot
C_{\ref{lem:MS22+}}+\lambda_{k+1}}{\Upsilon(k)}\cdot\left(\sum_{i=1}^{k}|S_{i}|\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)\right)+\frac{4k^{2}\cdot
C_{\ref{lem:MS22+}}\cdot\eta_{S}}{3\Upsilon(k)}\cdot\left(\sum_{i=1}^{k}|S_{i}|\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)\right)\right)$
(C.13) $\displaystyle\leqslant\ell\left(\frac{2\eta_{S}\cdot 4k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}+\frac{4k^{2}\cdot
C_{\ref{lem:MS22+}}\cdot\eta_{S}}{3\Upsilon(k)}\right)\sum_{i=1}^{k}|S_{i}|\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)$
$\displaystyle\leqslant\ell\left(\frac{4k^{2}\cdot
C_{\ref{lem:MS22+}}\cdot\eta_{S}}{\Upsilon(k)}\right)\cdot\frac{18\cdot\eta_{S}}{\Phi_{\mathrm{in}}}\cdot\mathsf{OPT}_{G}$
(C.14) $\displaystyle\leqslant\frac{4k^{4}\cdot
C_{\ref{lem:MS22+}}}{\Upsilon(k)}\cdot\frac{36\cdot\eta_{S}^{2}}{\Phi_{\mathrm{in}}}\cdot\mathsf{OPT}_{G}$

where (C.13) follows by (B2) and (B3) for the heavy buckets and (B6) for the
light ones, and (C.14) follows by Lemma A.8. Finally, combining (C.10), (C.12)
and (C.14) we conclude that

$\displaystyle\mathsf{COST}_{G}\left(\mathcal{T}_{\mathrm{SCB}}\right)$
$\displaystyle\leqslant\left(1+\frac{k^{2}\cdot
C_{\ref{lem:MS22+}}}{\Upsilon(k)}\right)\cdot\frac{36\cdot\eta_{S}^{2}}{\Phi_{\mathrm{in}}}\cdot\mathsf{OPT}_{G}+\frac{4k^{4}\cdot
C_{\ref{lem:MS22+}}}{\Upsilon(k)}\cdot\frac{36\cdot\eta_{S}^{2}}{\Phi_{\mathrm{in}}}\cdot\mathsf{OPT}_{G}$
$\displaystyle\leqslant\left(1+\frac{5k^{4}\cdot
C_{\ref{lem:MS22+}}}{\Upsilon(k)}\right)\cdot\frac{36\cdot\eta_{S}^{2}}{\Phi_{\mathrm{in}}}\cdot\mathsf{OPT}_{G},$

which completes the proof. ∎

Finally, the following theorem summarises the performance of Algorithm 2.

######  Theorem C.7 (Formal Statement of Theorem 5.4).

Let $G=(V,E,w)$ graph of $n$ vertices, $m$ edges, and optimal clusters
$\\{S_{i}\\}_{i=1}^{k}$ corresponding to $\rho(k)$ satisfying
$k=O(\mathrm{poly}\log(n))$, $\Phi_{G[S_{i}]}\geqslant\Phi_{\mathrm{in}}$ for
$1\leqslant i\leqslant k$, and $\Upsilon(k)\geqslant C_{\ref{lem:MS22+}}\cdot
k$. Then, there is an $\widetilde{O}(m)$ time algorithm that returns both an
HC tree $\mathcal{T}_{\mathrm{SCB}}$ of $G$, and
$\mathsf{COST}\left(\mathcal{T}_{\mathrm{SCB}}\right)$. Moreover, it holds
that

$\displaystyle\mathsf{COST}_{G}\left(\mathcal{T}_{\mathrm{SCB}}\right)\leqslant\left(1+\frac{5k^{4}\cdot
C_{\ref{lem:MS22+}}}{\Upsilon(k)}\right)\cdot\frac{36\cdot\eta_{S}^{2}}{\Phi_{\mathrm{in}}}\cdot\mathsf{OPT}_{G}$

where $\eta_{S}$ is an upper bound of
$\max_{i}\left(\Delta(S_{i})/\delta(S_{i})\right)$.

###### Proof.

The approximation guarantee of the returned tree $\mathcal{T}_{\mathrm{SCB}}$
from Algorithm 2 follows from Lemma C.6. By a similar proof as the proof of
Lemma B.9, it holds that the time complexity of Algorithm 2 is
$\widetilde{O}(m)$ and the depth of $\mathcal{T}_{\mathrm{SCB}}$ is
$O(\operatorname{polylog}n)$. Therefore, by Lemma B.8, we can compute
$\mathsf{COST}_{G}(\mathcal{T}_{\mathrm{SCB}})$ in nearly-linear time
$\widetilde{O}(m)$.

It remains to deal with our assumption that the algorithm knows the number of
clusters $k$ and an upper bound

$\eta_{S}\geqslant\max_{1\leqslant i\leqslant
k}\frac{\Delta(S_{i})}{\delta(S_{i})}.$

If the number of clusters $k$ is unknown, we perform the technique described
before and run independent copies of Algorithm 2 with all possible values
$k^{\prime}$ ranging from $1$ to $O(\operatorname{polylog}(n))$. By adding an
extra $O(\operatorname{polylog}n)=\widetilde{O}(1)$ factor in the overall time
complexity, we ensure that one of the runs has the correct number of clusters
$k^{\prime}=k$.

Finally, in order to obtain an approximation of $\eta_{S}$, we additionally
run $O(\log(n))$ independent copies of Algorithm 2 with different values
$\widetilde{\eta_{S}}=2^{i}$, for all
$i\in\left[\log\delta_{G},\log\Delta_{G}\right]$. This process ensures that,
at least one such estimate satisfies that
$\widetilde{\eta_{S}}/2\leqslant\eta_{S}\leqslant\widetilde{\eta_{S}}$. By
introducing a factor of $O(\log n)$ to the overall running time, this ensures
that at least one of the constructed trees of Algorithm 2 satisfies the
promised approximation ratio, up to an additional factor of
$\left(\eta_{S}/\widetilde{\eta_{S}}\right)^{2}$. As a result, we return the
tree with the minimum cost among all different runs of our algorithm. ∎