Zuse Institute Berlin,
Berlinborndoerfer@zib.dehttps://orcid.org/0000-0001-7223-9174 Hasso Plattner
Institute, University of Potsdam,
GermanyKatrin.Casel@hpi.dehttps://orcid.org/0000-0001-6146-8684 Hasso Plattner
Institute, University of Potsdam,
GermanyDavis.Issac@hpi.dehttps://orcid.org/0000-0001-5559-7471 Hasso Plattner
Institute, University of Potsdam,
GermanyAikaterini.Niklanovits@hpi.dehttps://orcid.org/0000-0002-4911-4493 Zuse
Institute Berlin, Berlinschwartz@zib.dehttps://orcid.org/0000-0003-2901-5065
Hasso Plattner Institute, University of Potsdam,
GermanyZiena.Zeif@hpi.dehttps://orcid.org/0000-0003-0378-1458 Ralf Borndörfer,
Katrin Casel, Davis Issac, Aikaterini Niklanovits, Stephan Schwartz and Ziena
Zeif [500]Theory of computation Graph algorithms analysis John Q. Open and
Joan R. Access 2 42nd Conference on Very Important Topics (CVIT 2016) CVIT
2016 CVIT 2016 December 24–27, 2016 Little Whinging, United Kingdom 42 23

# Connected $k$-partition of $k$-connected graphs and $c$-claw-free graphs

Ralf Borndörfer  Katrin Casel  Davis Issac  Aikaterini Niklanovits  Stephan
Schwartz  Ziena Zeif

###### Abstract

A _connected partition_ is a partition of the vertices of a graph into sets
that induce connected subgraphs. Such partitions naturally occur in many
application areas such as road networks, and image processing. In these
settings, it is often desirable to partition into a fixed number of parts of
roughly of the same size or weight. The resulting computational problem is
called Balanced Connected Partition (BCP). The two classical objectives for
BCP are to maximize the weight of the smallest, or minimize the weight of the
largest component. We study BCP on $c$-claw-free graphs, the class of graphs
that do not have $K_{1,c}$ as an induced subgraph, and present efficient
$(c-1)$-approximation algorithms for both objectives. In particular, for
$3$-claw-free graphs, also simply known as claw-free graphs, we obtain a
$2$-approximation. Due to the claw-freeness of line graphs, this also implies
a $2$-approximation for the edge-partition version of BCP in general graphs.

A harder connected partition problem arises from demanding a connected
partition into $k$ parts that have (possibly) heterogeneous target weights
$w_{1},\ldots,w_{k}$. In the 1970s Győri and Lovász showed that if $G$ is
$k$-connected and the target weights sum to the total size of $G$, such a
partition exists. However, to this day no polynomial algorithm to compute such
partitions exists for $k>4$. Towards finding such a partition
$T_{1},\ldots,T_{k}$ in $k$-connected graphs for general $k$, we show how to
efficiently compute connected partitions that at least approximately meet the
target weights, subject to the mild assumption that each $w_{i}$ is greater
than the weight of the heaviest vertex. In particular, we give a
3-approximation for both the lower and the upper bounded version i.e. we
guarantee that each $T_{i}$ has weight at least $\frac{w_{i}}{3}$ or that each
$T_{i}$ has weight most $3w_{i}$, respectively. Also, we present a both-side
bounded version that produces a connected partition where each $T_{i}$ has
size at least $\frac{w_{i}}{3}$ and at most $\max(\\{r,3\\})w_{i}$, where
$r\geq 1$ is the ratio between the largest and smallest value in
$w_{1},\dots,w_{k}$. In particular for the balanced version, i.e.
$w_{1}=w_{2}=,\dots,=w_{k}$, this gives a partition with $\frac{1}{3}w_{i}\leq
w(T_{i})\leq 3w_{i}$.

###### keywords:

connected partition, Győri-Lovász, balanced partition, approximation
algorithms

###### category:

##  1 Introduction

Partitioning a graph into connected subgraphs is a problem that arises in many
application areas such as parallel processing, road network decomposition,
image processing, districting problems, and robotics [34, 35, 4, 1, 39]. Often
in these applications, it is required to find a partition into a specified
number $k$ of connected subgraphs. For instance, in the parallel processing
applications, the number of processors is restricted, and in robotics
applications, the number of robots available is restricted. Formally, we call
a partition $T_{1},T_{2},\cdots,T_{k}$ of the vertex set of graph, a
_connected $(k$-$)$partition_, if the subgraph induced by the vertices in
$T_{i}$ is connected for each $1\leq i\leq k$.

The typical modeling objective in such connected partition problems is to
balance sizes among the $k$ parts. Sometimes one needs to consider a vertex-
weighted generalization e.g. weights representing the required amount of work
at the entity corresponding to the vertex. The two classical balancing
objectives for such $k$-partitions are to maximize the total weight of the
lightest part, or to minimize the weight of the heaviest part. These
objectives yield the following two versions of the _balanced connected
partition problem_ (BCP).

######  Problem 1.1.

Max-Min BCP (Min-Max BCP) Input:& A vertex-weighted graph $G=(V,E,w)$ where
$w:V\rightarrow\mathbb{N}$, and $k\in\mathbb{N}$.
Task: Find a connected $k$-partition $T_{1},\dots,T_{k}$ of $G$ maximizing
$\min_{i\in[k]}w(T_{i})$ (minimizing $\max_{i\in[k]}w(T_{i})$ resp.).

On general graphs, both variants of BCP are NP-hard [5], and hence the
problems have been mostly studied from the viewpoint of approximation
algorithms [6, 8, 9, 11, 12]. Most of the known results are for small values
of $k$, and there are some results also for special classes like grid graphs
or graphs of bounded treewidth (see related work section for further details).
The currently best known polynomial-time approximation for general graphs for
any $k$ is a $3$-approximation for both Max-Min and Min-Max BCP by Casel et.
al. [6].

Intuitively, an obstacle for getting a balanced connected partition is a large
induced star, i.e. a tree with one internal node and $c$ leaves, denoted by
$K_{1,c}$. We say a graph is _$c$ -claw-free_ or _$K_{1,c}$ -free_ if it does
not contain an induced $K_{1,c}$ as subgraph. For such graphs, we give a very
efficient $(c-1)$-approximation algorithm for both the min-max and max-min
objective. In particular by setting $c=3$, we get a $2$-approximation on
$K_{1,3}$-free graphs, better known as _claw-free graphs_.

Claw free graphs have been widely studied by Seymour and Chudnovsky in a
series of seven papers under the name _Claw-free graphs I-VII_ ([14]-[20]),
who also provide a structure theorem for these graphs [21]. Some interesting
examples of such graphs are line graphs, proper circular interval graphs and
de-Brujin graphs [22]. Apart from their structural properties, claw-free
graphs have been studied in the context of obtaining efficient algorithms for
several interesting problems, see e.g. [27, 24, 23].

Although, for $c>3$ our algorithm gives a worse guarantee than the algorithm
by Casel et. al. [6], we note that their algorithm runs in
$\mathcal{O}(\log(X^{*})k^{2}|V||E|)$ time for Max-Min BCP and in
$\mathcal{O}\left(\log\left(X^{*}\right)|V|\,|E|\left(\log\log
X^{*}\log\left(|V|w_{max}\right)+k^{2}\right)\right)$ time for Min-Max BCP,
where $X^{*}$ denotes the optimum value and $w_{\max}:=\max_{v\in V}w(v)$ the
maximum weight of a vertex, whereas our algorithms give an
$\mathcal{O}(\log(X^{*})|E|)$ runtime for Max-Min BCP and an
$\mathcal{O}(|E|)$ runtime for Min-Max BCP. Moreover, our algorithms are less
technical and hence much easier to implement. We prove the following
statements.

######  Theorem 1.2.

Given a vertex-weighted $K_{1,c}$-free graph $G=(V,E,w)$ and $k\in\mathbb{N}$,
a $(c-1)$-approximation for Min-Max BCP can be computed in $\mathcal{O}(|E|)$
time.

######  Theorem 1.3.

Given a vertex-weighted $K_{1,c}$-free graph $G=(V,E,w)$ and $k\in\mathbb{N}$,
a $(c-1)$-approximation for Max-Min BCP can be computed in time
$\mathcal{O}(\log(X^{*})|E|)$, where $X^{*}$ is the optimum value.

Since line graphs are $K_{1,3}$-free, these results directly imply efficient
approximations for the following edge-partition versions of BCP. A
$k$-partition of the edges of a graph, is called a _connected edge
$k$-partition_, if the subgraph induced by the edges in each part is
connected. In the problem Min-Max (Max-Min) balanced connected edge partition
(BCEP), one searches for a connected edge $k$-partition of an edge-weighted
graph minimizing the maximum (resp. maximimzing the minimum) weight of the
parts. This problem is equivalent to finding a connected $k$-partition of the
vertices in the line graph of the input graph. The best known approximation
for BCEP is for graphs with no edge weight larger than $w(G)/2k$. For such
graphs, [13] give an algorithm that finds a connected edge $k$-partition, such
that the weight of the heaviest subgraph is at most twice as large as the
weight of the lightest subgraph, implying a $2$-approximation for Min-Max and
Max-Min BCEP. In comparison, our algorithms achieve the same approximation
guarantee without restrictions on the edge weights.

######  Corollary 1.4.

Min-Max BCEP and Max-Min BCEP have $2$-approximations in polynomial time.

An extension of BCP is demanding for fixed (possibly heterogeneous) size
targets for each of the $k$ parts. More precisely, given a graph $G$ and
$w_{1},\dots,w_{k}$ with $\sum_{i=1}^{k}w_{i}=n$, the task is to find a
partition $T_{1},\cdots,T_{k}$ where each $T_{i}$ has size $w_{i}$ and induces
a connected subgraph. Such a connected $k$-partition with the fixed target
weights exists for $G$ only if $G$ meets certain structural properties; a
$K_{1,3}$ for example has no connected $2$-partition $T_{1},T_{2}$ with
$|T_{1}|=|T_{2}|=2$. A characterization of when such a connected partition
always exists was independently proved by Győri [26] and Lovász [32]: They
showed that in any $k$-connected graph a connected $k$-partition satisfying
the target weights always exists. This result is the famous Győri-Lovász
Theorem (GL theorem, for short):

######  Theorem 1.5 (Győri-Lovász Theorem [26, 32]).

Given a $k$-connected graph $G=(V,E,w)$, $n_{1},\dots,n_{k}\in\mathbb{N}$ such
that $\sum_{i=1}^{k}n_{i}=|V|$, and $k$ terminal vertices
$t_{1},\cdots,t_{k}\in V$, there exists a connected $k$-partition
$T_{1},\cdots,T_{k}$ of $V$ such that for each $i\in[k]$, $|T_{i}|=w_{i}$ and
$t_{i}\in T_{i}$.

Recently, the theorem was generalized to vertex-weighted graphs as:

######  Theorem 1.6 (Weighted Győri-Lovász Theorem [7, 10, 28]).

Given a vertex-weighted $k$-connected graph $G=(V,E,w)$,
$w_{1},\dots,w_{k}\in\mathbb{N}$ such that $\sum_{i=1}^{k}w_{i}=w(V)$, and $k$
terminal vertices $t_{1},\cdots,t_{k}$, there exists a connected $k$-partition
$T_{1},\cdots,T_{k}$ of $V$ such that
$w_{i}-w_{\max}<w(T_{i})<w_{i}+w_{\max}$, and $t_{i}\in T_{i}$ for each
$i\in[k]$, where $w_{\max}$ is the largest vertex weight.

We will refer to the partition guaranteed by the (weighted) GL theorem as _GL
partition_. We will however not consider the terminal vertices in the GL
partitions in this work.

The GL theorem has found some applications in the field of algorithms. Chen
et. al. [10] use it for proving the existence of low-congestion _confluent
flows_ in $k$-connected graphs. Further, Löwenstein et. al. [33] and Chandran
et. al. [7] use it for finding spanning trees with low _spanning tree
congestion_. Perhaps, the reason why such a strong combinatorial statement has
not found further applications is that we do not know how to efficiently
compute GL partitions. About five decades after the discovery of the GL
theorem, polynomial time algorithms for finding a GL partition (even in the
unweighted case without terminals) are only known for $k\leq 4$ [37, 38, 28].
The fastest algorithm for general $k$ takes $\Omega(2^{n})$ time [7, 29].
Neither there are any impossibility results to exclude efficient computability
of such partitions. Even when $k$ is part of the input, a polynomial time
algorithm is not ruled out.

The absence of efficient algorithms for finding exact GL partitions motivates
finding GL-style partitions that approximately satisfy the weight targets. In
this paper we present polynomial time algorithms that does this. First we give
an algorithm for a “half-bounded” GL partition, in the sense that we can
guarantee an approximate upper or lower bound on the weight of the parts.

######  Theorem 1.7.

Let $G=(V,E,w)$ be a $k$-connected vertex-weighted graph and
$w_{1},\dots,w_{k}\in\mathbb{N}$ with $\sum_{i=1}^{k}w_{i}=w(G)$, and
$\min_{i\in[k]}w_{i}\geq\max_{v\in V}w(v)$. A connected $k$-partition
$T_{1},\dots,T_{k}$ of $V$ such that either $w(T_{i})\geq\frac{1}{3}w_{i}$ for
every $i\in[k]$ (lower-bound version) or $w(T_{i})\leq 3w_{i}$ for every
$i\in[k]$ (upper-bound version) can be computed in time
$\mathcal{O}(k|V|^{2}|E|)$.

We then extend this result to a lower and upper bounded partition.

######  Theorem 1.8.

Let $G=(V,E,w)$ be a $k$-connected vertex-weighted graph and
$w_{1},\dots,w_{k}\in\mathbb{N}$ with $\sum_{i=1}^{k}w_{i}=w(G)$, and
$\min_{i\in[k]}w_{i}\geq\max_{v\in V}w(v)$, and
$r:=\frac{\max_{i\in[k]}w_{i}}{\min_{j\in[k]}w_{j}}$. Then, a connected
$k$-partition $T_{1},\dots,T_{k}$ of $V$ such that $\frac{1}{3}w_{i}\leq
w(T_{i})\leq\max\\{r,3\\}w_{i}$ for every $i\in[k]$ can be found in time
$\mathcal{O}(k|V|^{2}|E|)$.

In particular, Theorem 1.8 implies the following approximately balanced
partition of $k$-connected graphs.

######  Corollary 1.9.

Let $G=(V,E,w)$ be a $k$-connected vertex-weighted graph such that
${w(G)}\geq{k}\max_{v\in V}w(v)$. Then, a connected $k$-partition
$T_{1},\dots,T_{k}$ of $V$ such that
$\frac{1}{3}\left\lfloor\frac{w(G)}{k}\right\rfloor\leq w(T_{i})\leq
3\left\lceil\frac{w(G)}{k}\right\rceil$ for every $i\in[k]$ can be found in
time $\mathcal{O}(k|V|^{2}|E|)$.

To the best of our knowledge, these are the first polynomial time algorithms
that _approximate_ the GL theorem. We believe that such an efficient
approximation will result in the theorem being used for developing algorithms
in the future. Especially, we are hopeful that the both-side approximation for
balanced connected partition of $k$-connected graphs will find applications.
We remark, however that for the above mentioned applications of confluent
flows and spanning tree congestion, the terminal vertices are essential and
hence our algorithms cannot be used. An interesting future direction would be
to extend our results to the setting with terminals.

Observe that Corollary 1.9 in some sense yields a 3-approximation
simultaneously for Min-Max and Max-Min BCP in $k$-connected graphs. In this
regard, it is interesting to note that the $+/-w_{\max}$ slack given in the
weighted GL theorem is enough to retain hardness in the following sense: even
for $k=2$, Min-Max BCP and Max-Min BCP remain strongly NP-hard when restricted
to $2$-connected graphs; and the corresponding hardness-proof given in [8]
also constructs an instance with ${w(G)}\geq{k}\max_{v\in V}w(v)$. This
hardness can be extended to $k$-connected graphs for any fixed $k\geq 2$ (see
[8][Theorem 3] for more details).

###  1.1 Related work

Both variants of BCP were first introduced for trees [36, 31]. Under this
restriction, a linear time algorithm was provided for both variants in [25].
This is particularly important since different heuristics transform the
original instance to a tree to efficiently solve the problem, see [13, 39].
For both variants of BCP, a $3$-approximation is given in [6], which is the
best known approximation in polynomial time. With respect to lower bounds, it
is known that there exists no approximation for Max-Min BCP with a ratio below
$6/5$, unless $\textsf{P}\neq\textsf{NP}$ [8]. For the unweighted case, a
$\frac{k}{2}$-approximation for Min-Max BCP with $k\geq 3$, is given in [11].

Balanced connected partitions for fixed small values of $k$, denoted
$\textsc{BCP}_{k}$, have also been studied extensively. The restriction
$\textsc{BCP}_{2}$, i.e. balanced connected bipartition, is already NP-hard
[5]. On the positive side, a $\frac{4}{3}$-approximation for $\textsc{Max-Min
BCP}_{2}$ is given in [12], and in [11] this result is used to derive a
$\frac{5}{4}$-approximation for $\textsc{Min-Max BCP}_{2}$. Considering
tripartitions, $\textsc{Max-Min BCP}_{3}$ and $\textsc{Min-Max BCP}_{3}$ can
be approximated with ratios $\frac{5}{3}$ and $\frac{3}{2}$, respectively [9].

Regarding special graph classes, BCP has been investigated in grid graphs and
series-parallel graphs. While it was shown that BCP is NP-hard for arbitrary
grid graphs [3], the Max-Min BCP can be solved in polynomial time for ladders,
i.e., grid graphs with two rows [2]. For the class of series-parallel graphs,
Ito et. al. [30] observed that BCP remains weakly NP-hard (by a simple
reduction from the Partition problem) and gave a pseudo-polynomial-time
algorithm for both variants of BCP. They also showed that their algorithm can
be extended to graphs with bounded tree-width.

The GL Theorem was independently proved by Győri [26] and Lovász [32]. Győri
used an elementary graph theoretic approach while Lovász used ideas from
topology. Lovász’s proof also works for directed graphs. The Győri-Lovász
Theorem is extended to weighted directed graphs by Chen et. al. [10] and
Győri’s original proof was generalized to weighted undirected graphs by
Chandran et. al. [7]. Both papers only gave upper bounds of $w_{i}+w_{\max}$
on the weight of partition $T_{i}$ and did not provide any lower bounds. Later
Hoyer [28] showed that the method of Chandran et. al. [7] can be also extended
to give the lower bound $w_{i}-w_{\max}$, even for directed graphs. Polynomial
algorithms to also compute GL partitions are only known for the particular
cases $k=2,3,4$ [37, 38, 28] and all $k\geq 5$ are still open.

##  2 Preliminaries

By $\mathbb{N}$ we denote the natural numbers without zero. We use
$\left[k\right]$ to denote the set $\left\\{1,\ldots,k\right\\}$.

All the graphs that we refer to in this paper are simple, finite and
connected. Consider a graph $G=(V,E)$. We denote by $V(G)$ and $E(G)$ the set
of vertices and edges of $G$ respectively, and if the graph we refer to is
clear, we may simply write $V$ and $E$. For a set of vertex sets
$\mathcal{S}\subseteq 2^{V}$ we use $V(\mathcal{S})$ to denote
$\bigcup_{S\in\mathcal{S}}S$. We denote an edge $e=\left\\{u,v\right\\}\in
E(G)$ by $uv$ and the neighborhood of a vertex $v\in V$ in $G$ by
$N_{G}\left(v\right)=\left\\{u\in V\mid uv\in E(G)\right\\}$. Similarly we
denote the neighborhood of a vertex set $V^{\prime}\subseteq V$ in $G$ by
$N_{G}\left(V^{\prime}\right)$, that is $\bigcup_{v\in
V^{\prime}}N_{G}\left(v\right)\setminus V^{\prime}$. We may omit the subscript
$G$ when the graph is clear from the context. We use $\Delta(G)$ to denote the
maximum degree of $G$.

We denote a _vertex-weighted graph_ by $G=\left(V,E,w\right)$ where $w$ is a
function assigning integer weights to vertices $w\colon
V\rightarrow\mathbb{N}$, and $V$ and $E$ are vertex and edge sets. We denote
by $w_{\text{min}}$ and by $w_{\text{max}}$, $\text{min}_{v\in
V}w\left(v\right)$ and $\text{max}_{v\in V}w\left(v\right)$, respectively. For
any $V^{\prime}\subseteq V$, we use $w(V^{\prime})$ to denote the sum of
weights of the vertices in $V^{\prime}$. For a subgraph $H$ of $G$ we use
$w\left(H\right)$ to denote $w(V(H))$, and refer to it as the _weight of the
subgraph $H$_. For a rooted tree $T$ and a vertex $x$ in $T$, we use $T_{x}$
to denote the rooted subtree of $T$ rooted at $x$.

For $V^{\prime}\subseteq V$ we denote by $G[V^{\prime}]$ the graph induced by
$V^{\prime}$, i.e. $G[V^{\prime}]=(V^{\prime},E^{\prime})$ with
$E^{\prime}=E\cap(V^{\prime}\times V^{\prime})$. For vertex-weighted graphs,
induced subgraphs inherit the vertex-weights given by $w$. For
$V^{\prime}\subseteq V$ we also use $G-V^{\prime}$ to denote the subgraph
$G[V\setminus V^{\prime}]$. Similarly, if $V^{\prime}$ is a singleton
$\left\\{v\right\\}$ we also write $G-v$. For graphs $G_{1}$ and $G_{2}$, we
use $G_{1}\cup G_{2}$ to denote the graph on vertices $V(G_{1})\cup V(G_{2})$
with edge set $E(G_{1})\cup E(G_{2})$.

Let $\mathcal{U}=\left\\{U_{1},\dots,U_{r}\right\\}$ be such that each
$U_{i}\subseteq V$. We call $\mathcal{U}$ a _connected packing_ of $V$ if each
$G[U_{i}]$ is connected, and the sets in $\mathcal{U}$ are pairwise disjoint.
A connected packing $\mathcal{U}$ is called _connected vertex partition_ (CVP)
of $V$, if also $\cup_{i=1}^{r}U_{i}=V(G)$. We denote a CVP that has $k$
vertex sets as CVPk. For any $\mathcal{U}^{\prime}\subseteq\mathcal{U}$, we
define
$V\left(\mathcal{U}^{\prime}\right):=\bigcup_{U^{\prime}\in\mathcal{U}^{\prime}}U^{\prime}$,
and the weight
$w\left(\mathcal{U}^{\prime}\right):=w\left(V\left(\mathcal{U}^{\prime}\right)\right)$.
Let $\mathcal{I}$ be an interval. If $\mathcal{U}$ is a CVP and
$w\left(U_{i}\right)\in\mathcal{I}$ for all $i\in[r]$, then we say that
$\mathcal{U}$ is an _$\mathcal{I}$ -connected vertex $(r$-$)$partition_
($\mathcal{I}$-$\textsc{CVP}_{k}$ or just $\mathcal{I}$-CVP) of $V$. If
$\mathcal{U}$ is a connected-packing and $w\left(U_{i}\right)\in\mathcal{I}$
for all $i\in[r]$, then we say that $\mathcal{U}$ is a _$\mathcal{I}$
-connected packing_ of $V$.

##  3 Approximation for BCP on $c$-claw-free graphs

In this section we give an idea of how to prove Theorems 1.2 and 1.3 by giving
a $(c-1)$-approximation for Max-Min BCP and Min-Max BCP on $K_{1,c}$-free
graphs, full proofs of these results can be found in Appendix A. We assume
$c\geq 3$ as $c\leq 2$ gives trivial graph classes. We first show that a
connected partition for $K_{1,c}$-free graphs with parts of size in
$[\lambda,(c-1)\lambda)$ for some fixed $\lambda$ can be found in linear time.
For Max-Min BCP, this algorithm has to be called many times while doing a
binary search for the optimum value. We point out that it is not difficult to
adapt these algorithms to unconnected graphs achieving the same approximation
results.

Exploiting that each vertex in any DFS-tree of a $K_{1,c}$-free graph has at
most $c-1$ children, we can carefully extract connected components of a fixed
size while also maintaining a DFS-tree for the remaining graph. Also, this can
be done very efficiently, as stated in the following result.

######  Lemma 3.1.

Given a $K_{1,c}$-free graph $G$ and a DFS-tree of $G$. For any
$w(G)\geq\lambda\geq w_{\max}$, there is an algorithm that finds a connected
vertex set $S$ such that $\lambda\leq w(S)<(c-1)\lambda$ and $G-S$ is
connected, in $\mathcal{O}(|V|)$ time. Furthermore, the algorithm finds a DFS-
tree of $G-S$.

We use BalancedPartition to denote the algorithm that exhaustively applies
Lemma 3.1. Observe that BalancedPartition produces a connected partition
$S_{1},\dots,S_{m}$ where $w(S_{i})\in[\lambda,(c-1)\lambda)$ for every
$i\in[m-1]$ and $w(S_{m})<(c-1)\lambda$ in linear time, where the achieved
runtime follows by saving already processed subtrees.

Theorem 1.2 now follows from running BalancedPartition with
$\lambda=\max\\{w_{\max},\frac{w(G)}{k}\\}$. Note that this choice of
$\lambda$ is a trivial lower bound for the optimum value.

As already mentioned, to prove Theorem 1.3, we first need to find an input
parameter $\lambda$ for Algorithm BalancedPartition that provides the desired
$(c-1)$-approximation.

Let $(G,k)$ be an instance of Max-Min BCP, where $G$ is a $K_{1,c}$-free
graph. Let $X^{*}$ be the optimal value for the instance $(G,k)$. For any
given $X\leq w(G)/k$, we design an algorithm that either gives a $[\lfloor
X/(c-1)\rfloor,\infty)$-$\textsc{CVP}_{k}$, or reports that $X>X^{*}$. Note
that $X^{*}\leq w(G)/k$. Once we have this procedure in hand, a binary search
for the largest $X$ in the interval $\left(0,\left\lceil
w(G)/k\right\rceil\right]$ for which we find a $[\lfloor
X/(c-1)\rfloor,\infty)$-$\textsc{CVP}_{k}$ can be used to obtain an
approximate solution for Max-Min BCP.

Algorithm MaxMinApx: First remove all vertices of weight more than
$\lambda=\lfloor X/(c-1)\rfloor$ and save them in $H$. Then save the connected
components of weight less than $\lambda$ in $\mathcal{Q}$. Let
$\mathcal{V}=\\{V_{1},\dots,V_{\ell}\\}$ be the connected components of
$G-(H\cup V(\mathcal{Q}))$. Apply algorithm BalancedPartition on each
$G[V_{i}]$ with $\lambda$ as input parameter to obtain
$\mathcal{S}^{i}=\\{S^{i}_{1},\dots,S^{i}_{m_{i}}\\}$ for every $i\in[\ell]$.
If for some $i\in[\ell]$ the weight $w(S_{m_{i}})$ is less than $\lambda$,
then merge this vertex set with $S_{m_{i}-1}$ and accordingly update
$\mathcal{S}^{i}$. Further, compute a $(\lambda,\infty)$-$\textsc{CVP}_{|H|}$
$\mathcal{S}^{H}$ of $G[H\cup V(\mathcal{Q})]$ as follows: for each $h\in H$,
we will have a set $S^{h}\in\mathcal{S}^{H}$ with $h\in S^{h}$; we add each
$Q\in\mathcal{Q}$ to some $S^{h}$ such that $h\in N(Q)$. Let
$\mathcal{S}=\mathcal{S}^{H}\cup\bigcup_{i=1}^{\ell}\mathcal{S}^{i}$. If
$|\mathcal{S}|\geq k$, then merge connected sets arbitrarily in $\mathcal{S}$
until $|\mathcal{S}|=k$ and return $\mathcal{S}$. If $|\mathcal{S}|<k$, report
that $X>X^{*}$.

We point out that a $[\lambda,\infty)$-$\textsc{CVP}_{j}$ with $j>k$, can
easily be transformed to a $[\lambda,\infty)$-$\textsc{CVP}_{k}$, since the
input graph is connected. It is not hard to see that if algorithm MaxMinApx
returns $\mathcal{S}$ then this is a $[\lambda,\infty)$-$\textsc{CVP}_{k}$ of
$V$. The most complicated part of proving that MaxMinApx works correctly is
showing that if it terminates with $|\mathcal{S}|<k$ and reports $X>X^{*}$
that this is indeed true.

######  Lemma 3.2.

If Algorithm MaxMinApx terminates with $|\mathcal{S}|<k$, then $X>X^{*}$.

######  Proof 3.3.

Let $H,\mathcal{Q},\mathcal{V}=\\{V_{1},\dots,V_{\ell}\\}$ be the computed
vertices and connected vertex sets in the algorithm for $\lambda=\lfloor
X/(c-1)\rfloor$, respectively. Recall that $w(V_{i})\geq\lambda$ for every
$V_{i}\in\mathcal{V}$ and $w(Q)<\lambda$ for every $Q\in\mathcal{Q}$. Let
$\mathcal{S}^{*}=\left\\{S^{*}_{1},\dots,S^{*}_{k}\right\\}$ be an optimal
solution of $(G,k)$, i.e., $\mathcal{S}^{*}$ is an
$[X^{*},\infty)$-$\textsc{CVP}_{k}$ of $V$. Consider the sets
$\mathcal{V}^{H\cup\mathcal{Q}}:=\left\\{S^{*}_{i}\in\mathcal{S}^{*}|S^{*}_{i}\cap(H\cup
V(\mathcal{Q}))\neq\varnothing\right\\}$,
$\mathcal{V}^{1}:=\left\\{S^{*}_{i}\in\mathcal{S}^{*}|S^{*}_{i}\cap
V_{1}\neq\varnothing\right\\}\setminus\mathcal{V}^{H\cup\mathcal{Q}}$,
$\dots$,
$\mathcal{V}^{\ell}:=\left\\{S^{*}_{i}\in\mathcal{S}^{*}|S^{*}_{i}\cap
V_{\ell}\neq\varnothing\right\\}\setminus\mathcal{V}^{H\cup\mathcal{Q}}$. We
claim that these sets are a partition of $\mathcal{S}^{*}$. This follows
directly from the fact that $H$ separates all $V_{i}\in\mathcal{V}$ and all
$Q\in\mathcal{Q}$ from each other. That is, for an $i\in[k]$ and $j\in[\ell]$
the connected vertex set $S^{*}_{i}$ with $S^{*}_{i}\cap V_{j}\neq\varnothing$
and $S^{*}_{i}\cap V\setminus V_{j}\neq\varnothing$ contains at least one
$h\in H$ and hence $S^{*}_{i}\in\mathcal{V}^{H\cup\mathcal{Q}}$. Otherwise, if
$S^{*}_{i}\subseteq V_{j}$, then $S^{*}_{i}\in\mathcal{V}^{j}$.

Suppose MaxMinApx terminates with $|\mathcal{S}|<k$ although $X\leq X^{*}$. We
show that $\left|\mathcal{V}^{H\cup\mathcal{Q}}\right|\leq|H|$ and
$\left|\mathcal{V}^{i}\right|\leq|\mathcal{S}^{i}|$ for every $i\in[\ell]$,
implying that
$\left|\mathcal{S}^{*}\right|\leq|H|+\sum_{i=1}^{\ell}|\mathcal{S}^{i}|=|\mathcal{S}|<k$,
which contradicts $\left|\mathcal{S}^{*}\right|=k$.

First, we show $\left|\mathcal{S}^{H\cup\mathcal{Q}}\right|\leq|H|$. For this,
it is sufficient to prove that $S^{*}_{i}\cap H\neq\varnothing$ for each
$S^{*}_{i}\in\mathcal{V}^{H\cup\mathcal{Q}}$ as $\mathcal{S}^{*}$ is a
partition of $V$. We prove this by contradiction. Suppose there is an
$S^{*}_{i}\in\mathcal{V}^{H\cup\mathcal{Q}}$, such that $S^{*}_{i}\cap
H=\varnothing$. This implies that $S^{*}_{i}\subseteq Q$ for some
$Q\in\mathcal{Q}$, since $H$ separates every $Q\in\mathcal{Q}$ from every
other $Q^{\prime}\in\mathcal{Q}\setminus\\{Q\\}$ and from the vertices
$V\setminus(H\cup V(\mathcal{Q}))$. Thus, $w(S_{i}^{*})\leq w(Q)<\lambda$ by
the definition of $\mathcal{Q}$ and therefore $w(S_{i}^{*})<\lambda=\lfloor
X/(c-1)\rfloor\leq\lfloor X^{*}/(c-1)\rfloor$, contradicting
$\min_{i\in[k]}w(S^{*}_{i})=X^{*}$.

It remains to show that $\left|\mathcal{V}^{i}\right|\leq|\mathcal{S}^{i}|$
for every $i\in[\ell]$. Fix an $i\in[\ell]$ and let $G[V_{i}]$ with $\lambda$
be the input when calling algorithm BalancedPartition. Observe that the input
is valid, since $G[V_{i}]$ is connected by definition and
$w(G[V_{i}])\geq\lambda\geq\max_{v\in V_{i}}w(v)$ as $H$ contains all vertices
that have weight more than $\lambda$. Algorithm BalancedPartition provides a
CVP $\mathcal{S}^{i}=\\{S^{i}_{1},\dots,S^{i}_{m_{i}}\\}$ of $V_{i}$ with
$w(S^{i}_{j})\in[\lambda,(c-1)\lambda)$ for every $j\in[m_{i}-1]$ and
$w(S^{i}_{m_{i}})<(c-1)\lambda$. Consider $\mathcal{S}^{i}$ before merging,
i.e. we do not merge $S^{i}_{m_{i}}$ to $S^{i}_{m_{i}-1}$ in the algorithm
MaxMinApx if $w(S_{m_{i}})<\lambda$. That is, $w(S_{m})<\lambda$ is possible,
and we need to show $\left|\mathcal{V}^{i}\right|\leq
m_{i}-1=|\mathcal{S}^{i}|-1$. Observe for $S^{*}\in\mathcal{V}^{i}$ that
$S^{*}\subseteq V_{i}$, i.e.
$\sum^{m_{i}}_{j=1}w(S^{i}_{j})\geq\sum_{S^{*}\in\mathcal{V}^{i}}w(S^{*})$. As
a result, we have
$|\mathcal{S}^{i}|X\geq|\mathcal{S}^{i}|(c-1)\lambda>\sum^{m_{i}}_{j=1}w(S^{i}_{j})\geq\sum_{S^{*}\in\mathcal{V}^{i}}w(S^{*})\geq|\mathcal{V}^{i}|X^{*}$.
Consequently, by $X\leq X^{*}$ we obtain
$|\mathcal{V}^{i}|<|\mathcal{S}^{i}|$, which leads to
$|\mathcal{V}^{i}|\leq|\mathcal{S}^{i}|-1$.

##  4 Approximation of the Győri-Lovász Theorem for $k$-connected Graphs

Our algorithms for the approximate GL theorems are based mainly on the
following combinatorial lemma concerning certain vertex separators, that leads
to useful structures in $k$-connected graphs. Let $G=(V,E,w)$ be a connected
vertex-weighted graph and let $\lambda$ be an integer. We say $s\in V$ is a
$\lambda$-separator if all connected components of $G-\\{s\\}$ weigh less than
$\lambda$. We say $G$ is _$\lambda$ -dividable_ if there is a
$[\lambda,\infty)$-CVP2 of $V$.

######  Lemma 4.1 ([6]).

Let $G=(V,E,w)$ be a connected vertex-weighted graph and let
$\lambda>w_{\max}$ be an integer. If $w(G)>3(\lambda-1)$, then either $G$ is
$\lambda$-dividable or there is a $\lambda$-separator. Furthermore, finding
the connected vertex sets in case $G$ is $\lambda$-dividable and finding the
$\lambda$-separator in the other case can be done in $\mathcal{O}(|V|\,|E|)$
time.

###  4.1 Bounded Partition for $k$-connected Graphs

In this section, we give an algorithm for computing approximate GL partitions
with one-side approximation bound (either lower bound or upper bound), thus
proving Theorem 1.7. For this, we first prove the following theorem, from
which Theorem 1.7 follows as below.

######  Theorem 4.2.

Let $G=(V,E,w)$ be a $k$-connected vertex-weighted graph and let
$w_{1},\dots,w_{k}\in\mathbb{N}$ with $\sum_{i=1}^{k}w_{i}=w(G)$, and
$\min_{i\in[k]}w_{i}\geq\max_{v\in V}w(v)$. A set of connected vertex sets
$\mathcal{T}=\\{T_{1},\dots,T_{\ell}\\}$ with $\ell\leq k$ and $\alpha
w_{i}\leq w(T_{i})\leq 3\alpha w_{i}$ for every $i\in[\ell]$ can be computed
in time $\mathcal{O}(k|V|^{2}|E|)$. Moreover, if $\ell<k$, then $\mathcal{T}$
is also a CVP of $V$.

By Theorem 4.2 we can derive Theorem 1.7 using $\alpha=1/3$ and $\alpha=1$ for
the lower bound and upper bounded version, respectively. Section B.2 gives a
detailed proof.

In the following we always assume that $w_{1},\dots,w_{k}$ is sorted in
descending order. To now give the algorithm proving Theorem 4.2, we make use
of Lemma 4.1. For this, we first need to ensure that $w_{\max}<\alpha w_{k}$.
Therefore, we perform a preprocessing step until we reach an instance that
satisfies $w_{\max}<\alpha w_{k}$. We give this preprocessing step in Section
B.1. After this step, we can assume that we have a $k$-connected graph
$G=(V,E,w)$ and natural numbers $w_{1},\dots,w_{k}$ sorted in descending
order, where $\sum_{i=1}^{k}w_{i}\leq w(G)$ and $w_{\max}<\alpha w_{k}$.

On such a graph $G$ we then gradually build a packing $\mathcal{T}$ with the
help of Lemma 4.1. During our algorithm to build $\mathcal{T}$ we ensure that
at each step $\mathcal{T}=\left\\{T_{1},T_{2},\dots,T_{i-1}\right\\}$ where
each $T_{j}\in\mathcal{T}$ is a connected vertex set with weight in $[\alpha
w_{j},3\alpha w_{j}]$ for each $j\in[i-1]$. We then search in the remaining
graph for the next set $T_{i}$ and always use $\overline{G}$ to denote the
graph $G\setminus V(\mathcal{T})$. We say a connected subgraph is $i$-_small_
if it has weight less than $\alpha w_{i}$ and $i$-_big_ otherwise. In case we
reach a situation, where $\overline{G}$ has no connected component that is
$i$-_big_ , we have to alter the already built sets
$T_{1},T_{2},\dots,T_{i-1}$ to build $T_{i}$. For this, we use
$\mathcal{T}_{a}$ to denote the set of all $T_{j}\in\mathcal{T}$ that have
_no_ $(\alpha w_{j})$-separator, and $\mathcal{T}_{b}$ to denote the set of
all $T_{j}\in\mathcal{T}$ that have an $(\alpha w_{j})$-separator. For
$T_{j}\in\mathcal{T}_{b}$ with an $(\alpha w_{j})$-separator $s$ we use
$C(T_{j})$ to denote the connected components of
$G[T_{j}\setminus\left\\{s\right\\}]$ (if there is more than one $(\alpha
w_{j})$-separator, fix one of them arbitrarily). The following Algorithm
BoundedGL formally explains our routine to build $\mathcal{T}$.

#### Algorithm BoundedGL

  1. 1.

Initialize $\mathcal{T}:=\varnothing$ as container for the desired connected-
vertex-packing $T_{1},\dots,T_{k}$ of $G$ and initialize $i:=1$ as an
increment-variable.

  2. 2.

While $\overline{G}=G\setminus V(\mathcal{T})$ is not the empty graph: //main
loop

    1. 2.1.

Find a connected vertex set $T_{i}$ having weight in $[\alpha w_{i},3\alpha
w_{i}]$, add $T_{i}$ to $\mathcal{T}$, and increment $i$ by one. If $i=k+1$
then terminate the algorithm.
// See Lemma B.5 for correctness of this step

    2. 2.2.

While $\overline{G}$ is not empty and has no $i$-big connected component:
//inner loop
Pick an $i$-small connected component $Q$ of $\overline{G}$. Pick a
$T_{j}\in\mathcal{T}$ such that either $T_{j}\in\mathcal{T}_{a}$ and $Q$ has
an edge to $T_{j}$ (Case 1), or $T_{j}\in\mathcal{T}_{b}$ and $Q$ has an edge
to some component $Q^{\prime}\in C(T_{j})$ (Case 2). // The occurrence of at
least one of these cases is shown in Lemma B.3.
If $w(T_{j}\cup Q)\leq 3\alpha w_{j}$ then update $T_{j}$ to $T_{j}\cup Q$.
Otherwise:

      1. 2.2.1.

Case 1 ($T_{j}\in\mathcal{T}_{a}$): Apply the following _Divide-routine_ on
$T_{j}\cup Q$: Use Lemma 4.1 to compute a $[\alpha w_{j},\infty)$-CVP2
$V_{1},V_{2}$ of $T_{j}\cup Q$. Set $T_{j}=V_{2}$ (i.e. $V_{1}$ goes to
$\overline{G}$).

      2. 2.2.2.

Case 2 ($T_{j}\in\mathcal{T}_{b}$): remove $Q^{\prime}$ from $T_{j}$ (i.e.
$Q^{\prime}$ goes back to $\overline{G}$) if $T_{j}\cup Q$ is not $\alpha
w_{j}$-dividable. Otherwise, apply divide routine on $T_{j}\cup Q$.

To prove the correctness of the algorithm, we show that the following
invariant is maintained.

######  Lemma 4.3.

Algorithm BoundedGL maintains a packing
$\mathcal{T}=\left\\{T_{1},T_{2},\dots,T_{i-1}\right\\}$ where each
$T_{j}\in\mathcal{T}$ is a connected vertex set having weight in $[\alpha
w_{j},3\alpha w_{j}]$.

######  Proof 4.4.

We increment $i$ only in Step 22.1. Before incrementing $i$, we add $T_{i}$ to
$\mathcal{T}$ while ensuring that $w(T_{i})\in[\alpha w_{i},3\alpha w_{i}]$
and $G[T_{i}]$ is connected. In Lemma B.5, we prove that whenever the divide
routine is about to be executed, there is an $i$-big component in
$\overline{G}$, ensuring the existence of such a $T_{i}$. Once a $T_{j}$ is
added to $\mathcal{T}$, it is then modified only in Step 22.2. So let us look
into how it gets modified in Step 22.2. If the condition $w(T_{j}\cup Q)\leq
3\alpha w_{i}$ is satisfied then it is clear that the new $T_{j}=T_{j}\cup Q$
also satisfies the weight constraints. Since $Q$ has an edge to $T_{j}$ and
$T_{j}$ and $Q$ each were connected, it is also clear that the new $T_{j}$
remains connected. So now consider the case when $w(T_{j}\cup Q)>3\alpha
w_{i}$. In Case 1 ($T_{j}\in\mathcal{T}_{a}$), we call the divide routine and
the new $T_{j}$ is the set $V_{2}$ returned by the routine. The set $V_{2}$ is
connected due to the property of the divide routine. To see that it also
satisfies the weight constraints, observe that $w(V_{1}\cup V_{2})$ is at most
$4\alpha w_{j}$ as $w(T_{j})$ was at most $3\alpha w_{j}$ and $w(Q)<\alpha
w_{i}\leq\alpha w_{j}$. Since $w(V_{1}),w(V_{2})\geq\alpha w_{j}$, we then
have $w(V_{2})\in[\alpha w_{j},3\alpha w_{j}]$. So it only remains to consider
Case 2 ($T_{j}\in\mathcal{T}_{b}$). The case when $T_{j}\cup Q$ is $\alpha
w_{j}$-dividable is analog to Case 1. We know $w(Q^{\prime})<\alpha w_{j}$ by
definition. Also, since $w(T_{j}\cup Q)$ was more than $3\alpha w_{j}$ and
$w(Q)<\alpha w_{j}$, we have that $w(T_{j})$ was at least $2\alpha w_{j}$.
Thus the new $T_{j}=T_{j}\setminus Q^{\prime}$ has weight in $[\alpha
w_{j},3\alpha w_{j}]$. Also, the new $T_{j}$ is connected by the definition of
$Q^{\prime}$.

It is clear from the algorithm that termination occurs only if $\overline{G}$
is empty or $i=k+1$. Then using Lemma 4.3, it is clear that $\mathcal{T}$
contains the required packing as claimed in Theorem 4.2, provided that Step
22.2 runs correctly and terminates, which we prove below.

######  Lemma 4.5.

The inner loop runs correctly and terminates after at most $|V|^{2}$
iterations.

The idea for the proof of Lemma 4.5 is that if the divide routine is executed
in the inner loop then an $i$-big component is created, terminating the inner
loop, and in the other case either a connected component is deleted from
$\overline{G}$ or new vertices are added to a connected component in
$\overline{G}$. A full proof and the runtime analysis are given in Section B.2
and B.3, respectively.

It is tempting to think that one could use Theorem 4.2 to derive a CVP
$\mathcal{T}=\\{T_{1},\dots,T_{k}\\}$ such that $\alpha w_{i}\leq w(T_{i})\leq
3\alpha w_{i}$ for each $i\in[k]$. If Algorithm BoundedGL terminates with
$\ell<k$, then $\mathcal{T}$ is a partition of the vertices in $G$, and we
only have trouble with the lower bound on $T_{j}$ for $\ell<j\leq k$.
Otherwise, if it terminates with $\ell=k$, then $\mathcal{T}$ satisfies all
lower bounds, but might not be a partition. Assigning the remaining vertices
in $G$ to turn $\mathcal{T}$ into a CVP in this case might yield violations of
the upper bound. Since $\alpha=1$ yields the first, and $\alpha=\frac{1}{3}$
the second case, one might think that choosing the correct $\alpha$ in between
would result in a CVP with $\ell=k$. Unfortunately, Algorithm BoundedGL does
not have a monotone behaviour w.r.t. $\alpha\in(\frac{1}{3},1)$ in the sense
that for two values $\frac{1}{3}<\alpha_{1}<\alpha_{2}<1$, the case $\ell=k$
for $\alpha_{1}$ does not imply $\ell=k$ for $\alpha_{2}$. Thus, even if we
could prove the existence of an optimal value for $\alpha$, we have no way to
search for it.

###  4.2 Both-side Bounded Partition for $k$-connected Graphs

In this section, we prove Theorem 1.8 by giving a both-side bounded
approximate GL partition. The full correctness and runtime proofs of the
algorithm can be found in Appendix C.

For achieving a simultaneous lower and upper bounded partition, as a starting
point, we apply Theorem 4.2 with $\alpha=\frac{1}{3}$ obtaining a lower and
upper bounded packing $\mathcal{T}=\\{T_{1},\dots,T_{k}\\}$ with
$\frac{1}{3}w_{i}\leq w(T_{i})\leq w_{i}$ for every $i\in[k]$. As long as
$\mathcal{T}$ is not a CVP of $V$ yet, we transfer a subset of the remaining
vertices $V\setminus V(\mathcal{T})$ through a path in an auxiliary graph to
elements in $\mathcal{T}$, while making sure that for each $i$,
$\frac{1}{3}w_{i}\leq w(T_{i})\leq\max\\{r,3\\}w(T_{i})$. We call one such
transfer a _transferring-iteration_. We define
$\mathcal{T}^{*}:=\\{T_{1},T_{2},\dots,T_{j}\\}$ where $j$ is the smallest
number such that $w(T_{i})\geq w_{i}$ for $i\in[j]$ and $w(T_{j+1})<w_{j+1}$.
In case of $w_{a}=w_{b}$ and $w(T_{a})\geq w_{a}$, but $w(T_{b})<w_{b}$ we
assume that $a<b$. Note that this is easily realizable by a relabeling of
indices. Observe that $\mathcal{T}^{*}=\varnothing$ if $w(T_{1})<w_{1}$. As a
measure of progress, we guarantee in each transferring-iteration that either
the cardinality of $\mathcal{T}^{*}$ increases, or the number of vertices in
$V(\mathcal{T})$ increases. Also, the cardinality of $\mathcal{T}^{*}$ is non-
decreasing throughout the algorithm. Note that if $T_{i}\in\mathcal{T}^{*}$
for all $i$, then it follows that $w(T_{i})=w_{i}$ for all $i$ and moreover,
$\mathcal{T}$ is a CVP.

Let $\mathcal{T}=\\{T_{1},\dots,T_{k}\\}$ be a connected packing of $V$ in $G$
with $w(T_{i})\leq\max\\{r,3\\}w_{i}$ for every $i\in[k]$. We use
$\mathcal{Q}$ to denote the vertex sets forming the connected components of
$G[V\setminus V(\mathcal{T})]$. We define
$\mathcal{T}^{+}:=\\{T_{i}\in\mathcal{T}\mid w(T_{i})\geq w_{i}\\}$ and
$\mathcal{T}^{-}:=\mathcal{T}\setminus\mathcal{T}^{+}$. Note that
$\mathcal{T}^{*}\subseteq\mathcal{T}^{+}$. Analogous to section 4.1, we define
$\mathcal{T}^{+}_{a}$ as the set of $T_{i}\in\mathcal{T}^{+}$ that do _not_
have a $w_{i}$-separator vertex and $\mathcal{T}^{+}_{b}$ to be the ones in
$\mathcal{T}^{+}$ having a $w_{i}$-separator. For
$T_{i}\in\mathcal{T}^{+}_{b}$, we use $s(T_{i})$ to denote its
$w_{i}$-separator (if there are multiple we fix one arbitrarily) and
$C(T_{i})$ to denote the vertex sets forming the connected components of
$G[T_{i}\setminus\\{s(T_{i})\\}]$. We say a vertex $v\in V$ or a vertex set
$V^{\prime}\subseteq V$ is _$\mathcal{T}$ -assigned_ if $v\in V(\mathcal{T})$
or $V^{\prime}\subseteq V(\mathcal{T})$, respectively. That is, the set of
$\mathcal{T}$-assigned vertices is $V(\mathcal{T})$ and $V(\mathcal{Q})$ is
the set of _not $\mathcal{T}$-assigned_ vertices. We say _$\mathcal{T}$ is
pack-satisfied_ if $|\mathcal{T}|=k$, each $T_{j}\in\mathcal{T}$ is connected,
$w(T_{j})\in[\frac{1}{3}w_{j},\max\\{r,3\\}w_{j}]$, and the vertex sets in
$\mathcal{T}$ are pairwise disjoint.

We define the _transfer-graph_ $H=(\mathcal{V}_{H},E_{H})$ as
$\mathcal{V}_{H}:=(\bigcup_{T\in\mathcal{T}^{+}_{b}}C(T))\cup\mathcal{T}^{+}_{a}\cup\mathcal{T}^{-}\cup\mathcal{Q}$
and $E_{H}:=\\{(V_{1},V_{2})\in\binom{\mathcal{V}_{H}}{2}\mid N_{G}(V_{1})\cap
V_{2}\neq\varnothing\\}$.

#### Algorithm DoubleBoundedGL

  1. 1.

Apply Theorem 4.2 with $\alpha=\frac{1}{3}$ on $G$ to obtain a connected
packing $\mathcal{T}=\\{T_{1},\dots,T_{k}\\}$ with
$w(T_{i})\geq\frac{1}{3}w_{i}$ for every $i\in[k]$.

  2. 2.

While $\mathcal{Q}\neq\varnothing$:

    1. 2.1.

Find a minimal path in $H$ from $\mathcal{Q}$ to $\mathcal{T}^{-}$. Let this
path be $P_{Q}^{T_{i}}$ where $Q\in\mathcal{Q}$ and $T_{i}\in\mathcal{T}^{-}$.
// Note that all vertices in $P_{Q}^{T_{i}}$ except the start and end vertex
are in $\mathcal{T}^{+}_{a}\ \cup\ \bigcup_{T\in\mathcal{T}^{+}_{b}}C(T)$ by
minimality of the path. The existence of a path
from $\mathcal{Q}$ to $\mathcal{T}^{-}$ is shown in Lemma C.1.

    2. 2.2.

Execute the TransferVertices routine given below, which augments vertices
through the path $P_{Q}^{T_{i}}$ such that $\mathcal{T}$ stays pack-satisfied,
and either $|\mathcal{T}^{*}|$ increases, or $|\mathcal{T}^{*}|$ remains the
same and the number of $\mathcal{T}$-assigned vertices increases.

We need some more notations for describing the TransferVertices routine. For
$\mathcal{V}_{H}^{\prime}\subseteq\mathcal{V}_{H}$ and
$\mathcal{T}^{\prime}\subseteq\mathcal{T}$ we define
$\mathcal{T}^{\prime}(\mathcal{V}_{H}^{\prime})$ as the set
$\\{T_{i}\in\mathcal{T}^{\prime}\mid V(T_{i})\cap
V(\mathcal{V}_{H}^{\prime})\neq\varnothing\\}$. For $H^{\prime}\subseteq H$ we
define
$\mathcal{T}^{\prime}(H^{\prime}):=\mathcal{T}^{\prime}(\mathcal{V}_{H}(H^{\prime}))$,
and $V(H^{\prime}):=V(\mathcal{V}_{H}(H^{\prime}))$. With $|P_{Q}^{T_{i}}|$ we
denote the length of the path $P_{Q}^{T_{i}}$, i.e. the number of edges in
$P_{Q}^{T_{i}}$. We define $P_{Q}^{\ell}$ as the vertex with distance $\ell$
to $Q$ in $P_{Q}^{T_{i}}$, where $P_{Q}^{0}=Q$, and define $T(P_{Q}^{\ell})$
for $\ell\in[|P_{Q}^{T_{i}}|]$ as the function which returns $T_{j}$ with
$P_{Q}^{\ell}\subseteq T_{j}$. For $\mathcal{T}^{\prime}\subseteq\mathcal{T}$
we define $I(\mathcal{T}^{\prime}):=\left\\{i\mid
T_{i}\in\mathcal{T}^{\prime}\right\\}$.

The TransferVertices routine transfers vertices through the path
$P_{Q}^{T_{i}}$. Our input is a pack-satisfied $\mathcal{T}$ and a
$P_{Q}^{T_{i}}$ path according to Step 22.2 in algorithm DoubleBoundedGL. By
the minimality of the path $T_{Q}^{T_{i}}$, it is clear that
$V_{H}(P_{Q}^{T_{i}})\setminus\\{Q,T_{i}\\}\subseteq\mathcal{T}^{+}_{a}\cup\bigcup_{T\in\mathcal{T}^{+}_{b}}C(T)$.
That is, except for the destination $T_{i}$ we run only through vertex sets
from $\mathcal{T}^{+}$ in $\mathcal{T}(P_{Q}^{T_{i}})$. Roughly, our goal is
to transfer vertices of $V(P_{Q}^{T_{i}}-T_{i})$ to $T_{i}$, thereby changing
the division of the vertex sets $\mathcal{T}(P_{Q}^{T_{i}})$ and preserving
the vertex sets in $\mathcal{T}^{*}$.

We often need to do a _truncate_ operation on sets $T_{j}$ with
$w(T_{j})>\max\\{r,3\\}w_{j}$. We mean by _truncate $T_{j}$_ that we remove
vertices from $T_{j}$ until $w_{j}\leq w(T_{j})\leq\max\\{r,3\\}w_{j}$ such
that $T_{j}$ remains connected. This can be done by removing a non-seperator
vertex from $T_{j}$ until the weight drops below $\max\\{r,3\\}w(T_{j})$. Note
that any connected graph has at least one non-seperator vertex. Since
$w_{\max}\leq w_{j}$ we know that the weight does not go below $w_{j}$ during
the last deletion.

#### Algorithm TransferVertices:

  1. 1.

Initialize $X:=Q$ and let $u=\min(I(\mathcal{T}^{-}))$.

  2. 2.

For $\ell=1$ to $|P_{Q}^{T_{i}}|$ do:

    1. 2.1.

Let $T_{j}=T(P_{Q}^{\ell})$.

    2. 2.2.

If $w(X)\geq w_{u}$: set $T_{u}=X$. Truncate $T_{u}$ if necessary and
terminate the algorithm.

    3. 2.3.

If $w(X\cup T_{j})\leq\max\\{r,3\\}w_{j}$: update $T_{j}$ to $X\cup T_{j}$ and
terminate the algorithm.

    4. 2.4.

If $T_{j}\notin\mathcal{T}^{*}$: Set $T_{j}^{\prime}=T_{j}\cup X$,
$T_{j}=T_{u}$ and $T_{u}=T_{j}^{\prime}$. Truncate $T_{j}$ and $T_{u}$ if
necessary and terminate the algorithm.

    5. 2.5.

If $T_{j}\in\mathcal{T}_{a}^{+}$: divide $T_{j}\cup X$ into connected vertex
sets $V_{1},V_{2}$ with $w(V_{1}),w(V_{2})\geq w_{j}$ using the construction
given by Lemma 4.1. Set $T_{j}=V_{1}$ and $T_{u}=V_{2}$. Truncate $T_{j}$ and
$T_{u}$ if necessary and terminate the algorithm.

    6. 2.6.

We know $T_{j}\in\mathcal{T}_{b}^{+}\cap\mathcal{T}^{*}$. Set $X=X\cup
P_{Q}^{\ell}$ and remove $P_{Q}^{\ell}$ from $T_{j}$.

## References

  * [1] Curtis A Barefoot, Roger Entringer, and Henda Swart.  Vulnerability in graphs a comparative survey.  Journal of Combinatorial Mathematics and Combinatorial Computing, 1:13–22, 1998.
  * [2] R Becker, Isabella Lari, Mario Lucertini, and Bruno Simeone.  A polynomial-time algorithm for max-min partitioning of ladders.  Theory of Computing Systems, 34(4):353–374, 2001.
  * [3] Ronald Becker, Isabella Lari, Mario Lucertini, and Bruno Simeone.  Max-min partitioning of grid graphs into connected components.  Networks: An International Journal, 32(2):115–125, 1998.
  * [4] Aydın Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz.  Recent advances in graph partitioning.  In Algorithm Engineering, pages 117–158. Springer, 2016.
  * [5] Paolo M Camerini, Giulia Galbiati, and Francesco Maffioli.  On the complexity of finding multi-constrained spanning trees.  Discrete Applied Mathematics, 5(1):39–50, 1983.
  * [6] Katrin Casel, Tobias Friedrich, Davis Issac, Aikaterini Niklanovits, and Ziena Zeif.  Balanced crown decomposition for connectivity constraints.  arXiv preprint arXiv:2011.04528, 2020.
  * [7] L. Sunil Chandran, Yun Kuen Cheung, and Davis Issac.  Spanning tree congestion and computation of generalized györi-lovász partition.  In 45th International Colloquium on Automata, Languages, and Programming, volume 107 of LIPIcs, pages 32:1–32:14, 2018.
  * [8] Frédéric Chataigner, Liliane Benning Salgado, and Yoshiko Wakabayashi.  Approximation and inapproximability results on balanced connected partitions of graphs.  Discrete Mathematics and Theoretical Computer Science, 9(1), 2007\.
  * [9] Guangting Chen, Yong Chen, Zhi-Zhong Chen, Guohui Lin, Tian Liu, and An Zhang.  Approximation algorithms for the maximally balanced connected graph tripartition problem.  Journal of Combinatorial Optimization, pages 1–21, 2020.
  * [10] Jiangzhuo Chen, Robert D Kleinberg, László Lovász, Rajmohan Rajaraman, Ravi Sundaram, and Adrian Vetta.  (almost) tight bounds and existence theorems for single-commodity confluent flows.  Journal of the ACM (JACM), 54(4):16, 2007.
  * [11] Yong Chen, Zhi-Zhong Chen, Guohui Lin, Yao Xu, and An Zhang.  Approximation algorithms for maximally balanced connected graph partition.  In International Conference on Combinatorial Optimization and Applications, pages 130–141. Springer, 2019.
  * [12] Janka Chlebíková.  Approximating the maximally balanced connected partition problem in graphs.  Information Processing Letters, 60(5):225–230, 1996.
  * [13] An-Chiang Chu, Bang Ye Wu, and Kun-Mao Chao.  A linear-time algorithm for finding an edge-partition with max-min ratio at most two.  Discrete Applied Mathematics, 161(7-8):932–943, 2013.
  * [14] Maria Chudnovsky and Paul Seymour.  Claw-free graphs. i. orientable prismatic graphs.  Journal of Combinatorial Theory, Series B, 97(6):867–903, 2007\.
  * [15] Maria Chudnovsky and Paul Seymour.  Claw-free graphs. ii. non-orientable prismatic graphs.  Journal of Combinatorial Theory, Series B, 98(2):249–290, 2008\.
  * [16] Maria Chudnovsky and Paul Seymour.  Claw-free graphs. iii. circular interval graphs.  Journal of Combinatorial Theory, Series B, 98(4):812–834, 2008\.
  * [17] Maria Chudnovsky and Paul Seymour.  Claw-free graphs. iv. decomposition theorem.  Journal of Combinatorial Theory, Series B, 98(5):839–938, 2008\.
  * [18] Maria Chudnovsky and Paul Seymour.  Claw-free graphs. v. global structure.  Journal of Combinatorial Theory, Series B, 98(6):1373–1410, 2008\.
  * [19] Maria Chudnovsky and Paul Seymour.  Claw-free graphs vi. colouring.  Journal of Combinatorial Theory, Series B, 100(6):560–572, 2010\.
  * [20] Maria Chudnovsky and Paul Seymour.  Claw-free graphs. vii. quasi-line graphs.  Journal of Combinatorial Theory, Series B, 102(6):1267–1294, 2012\.
  * [21] Maria Chudnovsky and Paul D Seymour.  The structure of claw-free graphs.  Surveys in combinatorics, 327:153–171, 2005.
  * [22] Phillip EC Compeau, Pavel A Pevzner, and Glenn Tesler.  How to apply de bruijn graphs to genome assembly.  Nature biotechnology, 29(11):987–991, 2011.
  * [23] Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk.  Dominating set is fixed parameter tractable in claw-free graphs.  Theoretical Computer Science, 412(50):6982–7000, 2011.
  * [24] Yuri Faenza, Gianpaolo Oriolo, and Gautier Stauffer.  Solving the weighted stable set problem in claw-free graphs via decomposition.  Journal of the ACM (JACM), 61(4):1–41, 2014.
  * [25] Greg N. Frederickson.  Optimal algorithms for tree partitioning.  In Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, pages 168–177. ACM/SIAM, 1991.
  * [26] E Gyori.  On division of graphs to connected subgraphs, combinatorics.  In Colloquia Mathematica Societatis Janos Bolyai, 1976, 1976.
  * [27] Danny Hermelin, Matthias Mnich, and Erik Jan van Leeuwen.  Parameterized complexity of induced graph matching on claw-free graphs.  Algorithmica, 70(3):513–560, 2014.
  * [28] Alexander Hoyer.  On the Independent Spanning Tree Conjectures and Related Problems.  PhD thesis, Georgia Institute of Technology, 2019.
  * [29] Davis Issac.  On some covering, partition and connectivity problems in graphs.  2019\.
  * [30] Takehiro Ito, Xiao Zhou, and Takao Nishizeki.  Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size.  Journal of discrete algorithms, 4(1):142–154, 2006.
  * [31] Sukhamay Kundu and Jayadev Misra.  A linear tree partitioning algorithm.  SIAM Journal on Computing, 6(1):151–154, 1977.
  * [32] László Lovász.  A homology theory for spanning tress of a graph.  Acta Mathematica Academiae Scientiarum Hungarica, 30(3-4):241–251, 1977.
  * [33] Christian Löwenstein, Dieter Rautenbach, and Friedrich Regen.  On spanning tree congestion.  Discrete mathematics, 309(13):4653–4655, 2009.
  * [34] Mario Lucertini, Yehoshua Perl, and Bruno Simeone.  Most uniform path partitioning and its use in image processing.  Discrete Applied Mathematics, 42(2-3):227–256, 1993.
  * [35] Rolf H Möhring, Heiko Schilling, Birk Schütz, Dorothea Wagner, and Thomas Willhalm.  Partitioning graphs to speedup dijkstra’s algorithm.  Journal of Experimental Algorithmics (JEA), 11:2–8, 2007.
  * [36] Yehoshua Perl and Stephen R Schach.  Max-min tree partitioning.  Journal of the ACM (JACM), 28(1):5–15, 1981.
  * [37] Hitoshi Suzuki, Naomi Takahashi, and Takao Nishizeki.  A linear algorithm for bipartition of biconnected graphs.  Information Processing Letters, 33(5):227–231, 1990.
  * [38] Koichi Wada and Kimio Kawaguchi.  Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 132–143. Springer, 1993.
  * [39] Xing Zhou, Huaimin Wang, Bo Ding, Tianjiang Hu, and Suning Shang.  Balanced connected task allocations for multi-robot systems: An exact flow-based integer program and an approximate tree-based genetic algorithm.  Expert Systems with Applications, 116:10–20, 2019.

##  Appendix A Missing details from Section 3

###  A.1 Full Proof of Theorem 1.2

Let $G=(V,E,w)$ be a vertex-weighted $K_{1,c}$-free graph. Consider DFS-tree
$T_{r}$ of $G$ rooted at $r\in V(G)$. We state the following easy to see fact
without proof.

######  Lemma A.1.

In $T_{r}$, each vertex has at most $c-1$ children.

Using this property, the following lemma finds a balanced connected vertex
set, whose removal does not disconnect the graph.

We now prove this slight reformulation of Lemma 3.1.

######  Lemma A.2.

Given a $K_{1,c}$-free graph $G$ and a DFS-tree $T_{r}$ of $G$. If
$w(G)\geq\lambda\geq w_{\max}$, then there is an algorithm that finds a
connected vertex set $S$ such that $\lambda\leq w(S)<(c-1)\lambda$ and $G-S$
is connected, in $\mathcal{O}(|V|)$ time. Furthermore, the algorithm also
finds a DFS-tree of $G-S$.

######  Proof A.3.

There exist a vertex $v$ with children $v_{1},\dots,v_{\ell}$ such that
$w(T_{v})\geq\lambda$, and that $w(T_{v_{i}})<\lambda$ for each $i\in[\ell]$.
Such a vertex can be easily found by a bottom up traversal from the leaves in
$\mathcal{O}(|T_{v}|)\subseteq\mathcal{O}(|V|)$ time. If $\lambda\leq
w(T_{v})<(c-1)\lambda$, then we set $S=V(T_{v})$ and $T_{r}-S$ is a spanning
DFS-tree in $G-S$, and we are done.

The remaining case is when $w(T_{v})\geq(c-1)\lambda$ and
$w(T_{v_{i}})<\lambda$ for every $i\in[\ell]$. By Lemma A.1, we obtain
$\ell\leq c-1$. In fact $\ell=c-1$ as otherwise $w(v)$ needs to have more than
$\lambda\geq w_{\max}$ weight in order for $T_{v}$ to have $(c-1)\lambda$
weight, a contradiction.

If $v=r$, then we choose $S=\\{r\\}\cup\bigcup_{i=1}^{c-2}V(T_{v_{i}})$. $S$
is a connected subgraph with
$w(S)=w(v)+\sum_{i=1}^{c-2}w(T_{v_{i}})<w_{\max}+(c-2)\lambda\leq(c-1)\lambda$
and
$w(S)=w(T_{v})-w(T_{c-1})\geq(c-1)\lambda-\lambda=(c-2)\lambda\geq\lambda$.
Moreover, $T_{v_{c-1}}$ is a DFS-tree for $G-S$.

Now, consider $v\neq r$. Let $u$ be the parent of $v$ in $T_{r}$. By
$\ell=c-1$ we obtain that
$T_{r}[\\{u\\}\cup\\{v\\}\cup\bigcup_{i=1}^{c-1}\\{v_{i}\\}]$ is a $K_{1,c}$.
Consequently, there exists an edge $uv_{j}\in E\setminus E(T_{r})$ for at
least one $j\in[c-1]$, since $G$ is $K_{1,c}$-free. We set
$S=\\{v\\}\cup\bigcup_{i\in[c-1]\setminus\\{j\\}}V(T_{v_{i}})$ as connected
vertex set and obtain analogously to the case $v=r$ the desired weight
conditions for $S$. Finally, we remove $S$ from $T_{r}$ and add the edge
$uv_{j}$ to $T_{r}$ to obtain a DFS-tree of $G-S$.

We now give the algorithm BalancedPartition that takes as input a connected
vertex-weighted $K_{1,c}$-free graph $G(V,E,w)$ and an integer $\lambda\geq
w_{\max}$.

Algorithm BalancedPartition: Compute a DFS-tree $T_{r}$ rooted at $r\in V$ in
$G$ and initialize $\mathcal{S}^{\prime}=\varnothing$. Until
$w(T_{r})<(c-1)\lambda$ use Lemma 3.1 to remove a connected set $S$ from $G$,
add it to $\mathcal{S}^{\prime}$, and update $T_{r}$ to be the DFS-tree of
$G-S$ given by Lemma 3.1. Finally, return
$\mathcal{S}=\mathcal{S}^{\prime}\cup\\{V\setminus
V(\mathcal{S}^{\prime})\\}$.

The following lemma follows easily from the construction of Algorithm
BalancedPartition and Lemma 3.1.

######  Lemma A.4.

Given $G$ and $\lambda\geq w_{\max}$, algorithm BalancedPartition provides a
CVP $\mathcal{S}=\\{S_{1},\dots,S_{m}\\}$ of $V$ such that
$w(S_{i})\in[\lambda,(c-1)\lambda)$ for every $i\in[m-1]$ and
$w(S_{m})<(c-1)\lambda$ in linear time.

######  Proof A.5.

Let $w(G)\geq(c-1)\lambda$. First of all, observe that the preconditions of
Lemma 3.1 are satisfied at the first application of it. Generally, if an
iteration is executed, then we obtain a connected subgraph $S$ with
$w(S)\in[\lambda,(c-1)\lambda)$, which we add to $\mathcal{S}^{\prime}$, and a
DFS-tree $T_{r}$ in $G[V\setminus V(\mathcal{S}^{\prime})]$. Thus, the
preconditions of Lemma 3.1 are still maintained after an iteration if the
working tree $T_{r}$ weighs at least $\lambda$.

We only remove vertices $S$ from $T_{r}$ and add $S$ to
$\mathcal{S}^{\prime}$. Hence, the vertex sets in $\mathcal{S}^{\prime}$ are
pairwise disjoint. We apply Lemma 3.1 until $w(T_{r})$ is less than
$(c-1)\lambda$. Since $S_{m}=V\setminus V(\mathcal{S}^{\prime})=V(T_{r})$, the
vertex set $S_{m}$ is a connected vertex set disjoint from the vertex sets in
$\mathcal{S}^{\prime}$ and by the termination criteria $S_{m}$ weighs less
than $(c-1)\lambda$. As a result, $\\{S_{1},\dots,S_{m}\\}$ is the desired
CVP.

Lastly, we analyze the running time. Computing a DFS-tree $T_{r}$ runs in time
$\mathcal{O}(|V|+|E|)$. By starting from the leaves and using suitable data
structures we can find $T_{v}$ according to Lemma 3.1 in
$\mathcal{O}(|T_{v}|)$. Note that in case we add an edge $ux\in E$ as
explained in the proof of Lemma 3.1, where $u$ is the parent of $v$ and $x$ a
child of $v$ in the modified $T_{r}$, we have already the subtree $T_{x}$ with
its corresponding weight $w(T_{x})<\lambda$ in hand, i.e. we do not need to
proceed a second time through the vertices $V(T_{x})$. Thus, filling
$\mathcal{S}^{\prime}$ by the resulting vertex sets from Lemma 3.1 can be
performed in time $\mathcal{O}(|V|)$, since the vertex sets in
$\mathcal{S}^{\prime}$ are pairwise disjoint and we see them once in the
algorithm. As a result, the algorithm runs in time $\mathcal{O}(|E|)$.

We now prove Theorem 1.2 by appropriately choosing $\lambda$ in algorithm
BalancedPartition.

######  Proof A.6 (Proof of Theorem 1.2).

Set $\lambda=\max\\{w_{\max},\frac{w(G)}{k}\\}$. Let $X^{*}$ be the optimal
value of Min-Max BCPk on $G$. Observe that $\lambda\leq X^{*}$. Now, apply
algorithm BalancedPartition with $\lambda$ as input parameter to obtain a CVP
$\mathcal{S}=\\{S_{1},\dots,S_{m}\\}$, where
$w(S_{i})\in[\lambda,(c-1)\lambda)$ for $i\in[m-1]$ and
$w(S_{m})<(c-1)\lambda$. By $\lambda\leq X^{*}$ we obtain that
$\max_{i\in[m]}w(S_{i})<(c-1)\lambda\leq(c-1)X^{*}$. It remains to show that
$m\leq k$. We have $w(G)=w(S_{m})+\sum_{i=1}^{m-1}w(S_{i})\geq
w(S_{m})+(m-1)\lambda>\frac{m-1}{k}w(G)$, which implies $m\leq k$.

###  A.2 Full Proof of Theorem 1.3

We also use the algorithm BalancedPartition for the max-min objective. The
following property is immediate but useful.

######  Corollary A.7.

Let $\mathcal{S}$ be the output of algorithm BalancedPartition. For every
$j\in[|\mathcal{S}|]$ the subgraph $G-\bigcup_{i=1}^{j}S_{i}$ is connected.

Let $(G,k)$ be an instance of Max-Min BCP, where $G$ is a $K_{1,c}$-free
graph. Let $X^{*}$ be the optimal value for the instance $(G,k)$. For any
given $X\leq w(G)/k$, we design an algorithm that either gives a $[\lfloor
X/(c-1)\rfloor,\infty)$-$\textsc{CVP}_{k}$, or reports that $X>X^{*}$. Note
that $X^{*}\leq w(G)/k$. Once we have this procedure in hand, a binary search
for the largest $X$ in the interval $\left(0,\left\lceil
w(G)/k\right\rceil\right]$ for which we find a $[\lfloor
X/(c-1)\rfloor,\infty)$-$\textsc{CVP}_{k}$ can be used to obtain an
approximate solution for Max-Min BCP.

Algorithm MaxMinApx: First remove all vertices of weight more than
$\lambda=\lfloor X/(c-1)\rfloor$ and save them in $H$. Then save the connected
components of weight less than $\lambda$ in $\mathcal{Q}$. Let
$\mathcal{V}=\\{V_{1},\dots,V_{\ell}\\}$ be the connected components of
$G-(H\cup V(\mathcal{Q}))$. Apply algorithm BalancedPartition on each
$G[V_{i}]$ with $\lambda$ as input parameter to obtain
$\mathcal{S}^{i}=\\{S^{i}_{1},\dots,S^{i}_{m_{i}}\\}$ for every $i\in[\ell]$.
If for some $i\in[\ell]$ the weight $w(S_{m_{i}})$ is less than $\lambda$,
then merge this vertex set with $S_{m_{i}-1}$ and accordingly update
$\mathcal{S}^{i}$. Further, compute a $(\lambda,\infty)$-$\textsc{CVP}_{|H|}$
$\mathcal{S}^{H}$ of $G[H\cup V(\mathcal{Q})]$ as follows: for each $h\in H$,
we will have a set $S^{h}\in\mathcal{S}^{H}$ with $h\in S^{h}$; we add each
$Q\in\mathcal{Q}$ to some $S^{h}$ such that $h\in N(Q)$. Let
$\mathcal{S}=\mathcal{S}^{H}\cup\bigcup_{i=1}^{\ell}\mathcal{S}^{i}$. If
$|\mathcal{S}|\geq k$, then merge connected sets arbitrarily in $\mathcal{S}$
until $|\mathcal{S}|=k$ and return $\mathcal{S}$. If $|\mathcal{S}|<k$, report
that $X>X^{*}$.

We point out that a $[\lambda,\infty)$-$\textsc{CVP}_{j}$ with $j>k$, can
easily be transformed to a $[\lambda,\infty)$-$\textsc{CVP}_{k}$, since the
input graph is connected. To prove that the algorithm works correctly, we need
to show that MaxMinApx returns the desired
$[\lambda,\infty)$-$\textsc{CVP}_{k}$ if $|\mathcal{S}|=k$, where
$\lambda=\lfloor X/(c-1)\rfloor$. Furthermore, we need to show that if the
algorithm terminates with $|\mathcal{S}|<k$ and reports $X>X^{*}$ that this is
indeed true. These facts will finally lead us to a successful application of a
binary search and in turn to an approximate solution.

######  Lemma A.8.

If algorithm MaxMinApx returns $\mathcal{S}$, then $\mathcal{S}$ is a
$[\lambda,\infty)$-$\textsc{CVP}_{k}$ of $V$.

######  Proof A.9.

If algorithm MaxMinApx returns $\mathcal{S}$, then we have $|\mathcal{S}|=k$.
Therefore, we only need to show that $w(S)\geq\lambda$ and that every
$S\in\mathcal{S}$ is connected. Consider $S\in\mathcal{S}^{H}$. By
construction $S$ contains exactly one $h\in H$ and some $Q\in\mathcal{Q}$ with
$h\in N(Q)$. Hence, $S$ is connected. Moreover, $w(h)>\lambda$ for every $h\in
H$ by the choice of those vertices and hence $w(S)>\lambda$.

Let $G[V_{i}]$ for $i\in[\ell]$ be a connected component of $G-(H\cup
V(\mathcal{Q}))$ with $w(V_{i})\geq\lambda$. We applied algorithm
BalancedPartition for $G[V_{i}]$ with $\lambda$ as input and obtained a CVP
$\overline{\mathcal{S}}=\\{S_{1},\dots,S_{m}\\}$ of $V_{i}$ with
$w(S_{i})\in[\lambda,(c-1)\lambda)$ for every $i\in[m-1]$ and
$w(S_{m})<(c-1)\lambda$ (cf. Lemma A.4). Thus,
$S_{i}\in\\{S_{1},\dots,S_{m-1}\\}$ is connected and weighs at least
$\lambda$. If $w(S_{m})<\lambda$, then we merge $S_{m-1}$ with $S_{m}$, where
$G[S_{m}\cup S_{m-1}]$ is connected, which we derive from Corollary A.7 as
$G[S_{m}\cup S_{m-1}]=G[V_{i}]-\bigcup_{i=1}^{m-2}S_{i}$.

For completeness, we repeat.

######  Lemma A.10.

If Algorithm MaxMinApx terminates with $|\mathcal{S}|<k$, then $X>X^{*}$.

######  Proof A.11.

Let $H,\mathcal{Q},\mathcal{V}=\\{V_{1},\dots,V_{\ell}\\}$ be the computed
vertices and connected vertex sets in the algorithm for $\lambda=\lfloor
X/(c-1)\rfloor$, respectively. Recall that $w(V_{i})\geq\lambda$ for every
$V_{i}\in\mathcal{V}$ and $w(Q)<\lambda$ for every $Q\in\mathcal{Q}$. Let
$\mathcal{S}^{*}=\left\\{S^{*}_{1},\dots,S^{*}_{k}\right\\}$ be an optimal
solution of $(G,k)$, i.e., $\mathcal{S}^{*}$ is an
$[X^{*},\infty)$-$\textsc{CVP}_{k}$ of $V$. Consider the sets
$\mathcal{V}^{H\cup\mathcal{Q}}:=\left\\{S^{*}_{i}\in\mathcal{S}^{*}|S^{*}_{i}\cap(H\cup
V(\mathcal{Q}))\neq\varnothing\right\\}$,
$\mathcal{V}^{1}:=\left\\{S^{*}_{i}\in\mathcal{S}^{*}|S^{*}_{i}\cap
V_{1}\neq\varnothing\right\\}\setminus\mathcal{V}^{H\cup\mathcal{Q}}$,
$\dots$,
$\mathcal{V}^{\ell}:=\left\\{S^{*}_{i}\in\mathcal{S}^{*}|S^{*}_{i}\cap
V_{\ell}\neq\varnothing\right\\}\setminus\mathcal{V}^{H\cup\mathcal{Q}}$. We
claim that these sets are a partition of $\mathcal{S}^{*}$. This follows
directly from the fact that $H$ separates all $V_{i}\in\mathcal{V}$ and all
$Q\in\mathcal{Q}$ from each other. That is, for an $i\in[k]$ and $j\in[\ell]$
the connected vertex set $S^{*}_{i}$ with $S^{*}_{i}\cap V_{j}\neq\varnothing$
and $S^{*}_{i}\cap V\setminus V_{j}\neq\varnothing$ contains at least one
$h\in H$ and hence $S^{*}_{i}\in\mathcal{V}^{H\cup\mathcal{Q}}$. Otherwise, if
$S^{*}_{i}\subseteq V_{j}$, then $S^{*}_{i}\in\mathcal{V}^{j}$.

Suppose MaxMinApx terminates with $|\mathcal{S}|<k$ although $X\leq X^{*}$. We
show that $\left|\mathcal{V}^{H\cup\mathcal{Q}}\right|\leq|H|$ and
$\left|\mathcal{V}^{i}\right|\leq|\mathcal{S}^{i}|$ for every $i\in[\ell]$,
implying that
$\left|\mathcal{S}^{*}\right|\leq|H|+\sum_{i=1}^{\ell}|\mathcal{S}^{i}|=|\mathcal{S}|<k$,
which contradicts $\left|\mathcal{S}^{*}\right|=k$.

First, we show $\left|\mathcal{S}^{H\cup\mathcal{Q}}\right|\leq|H|$. For this,
it is sufficient to prove that $S^{*}_{i}\cap H\neq\varnothing$ for each
$S^{*}_{i}\in\mathcal{V}^{H\cup\mathcal{Q}}$ as $\mathcal{S}^{*}$ is a
partition of $V$. We prove this by contradiction. Suppose there is an
$S^{*}_{i}\in\mathcal{V}^{H\cup\mathcal{Q}}$, such that $S^{*}_{i}\cap
H=\varnothing$. This implies that $S^{*}_{i}\subseteq Q$ for some
$Q\in\mathcal{Q}$, since $H$ separates every $Q\in\mathcal{Q}$ from every
other $Q^{\prime}\in\mathcal{Q}\setminus\\{Q\\}$ and from the vertices
$V\setminus(H\cup V(\mathcal{Q}))$. Thus, $w(S_{i}^{*})\leq w(Q)<\lambda$ by
the definition of $\mathcal{Q}$ and therefore $w(S_{i}^{*})<\lambda=\lfloor
X/(c-1)\rfloor\leq\lfloor X^{*}/(c-1)\rfloor$, contradicting
$\min_{i\in[k]}w(S^{*}_{i})=X^{*}$.

It remains to show that $\left|\mathcal{V}^{i}\right|\leq|\mathcal{S}^{i}|$
for every $i\in[\ell]$. Fix an $i\in[\ell]$ and let $G[V_{i}]$ with $\lambda$
be the input when calling algorithm BalancedPartition. Observe that the input
is valid, since $G[V_{i}]$ is connected by definition and
$w(G[V_{i}])\geq\lambda\geq\max_{v\in V_{i}}w(v)$ as $H$ contains all vertices
that have weight more than $\lambda$. Algorithm BalancedPartition provides a
CVP $\mathcal{S}^{i}=\\{S^{i}_{1},\dots,S^{i}_{m_{i}}\\}$ of $V_{i}$ with
$w(S^{i}_{j})\in[\lambda,(c-1)\lambda)$ for every $j\in[m_{i}-1]$ and
$w(S^{i}_{m_{i}})<(c-1)\lambda$. Consider $\mathcal{S}^{i}$ before merging,
i.e. we do not merge $S^{i}_{m_{i}}$ to $S^{i}_{m_{i}-1}$ in the algorithm
MaxMinApx if $w(S_{m_{i}})<\lambda$. That is, $w(S_{m})<\lambda$ is possible,
and we need to show $\left|\mathcal{V}^{i}\right|\leq
m_{i}-1=|\mathcal{S}^{i}|-1$. Observe for $S^{*}\in\mathcal{V}^{i}$ that
$S^{*}\subseteq V_{i}$, i.e.
$\sum^{m_{i}}_{j=1}w(S^{i}_{j})\geq\sum_{S^{*}\in\mathcal{V}^{i}}w(S^{*})$. As
a result, we have
$|\mathcal{S}^{i}|X\geq|\mathcal{S}^{i}|(c-1)\lambda>\sum^{m_{i}}_{j=1}w(S^{i}_{j})\geq\sum_{S^{*}\in\mathcal{V}^{i}}w(S^{*})\geq|\mathcal{V}^{i}|X^{*}$.
Consequently, by $X\leq X^{*}$ we obtain
$|\mathcal{V}^{i}|<|\mathcal{S}^{i}|$, which leads to
$|\mathcal{V}^{i}|\leq|\mathcal{S}^{i}|-1$.

#### Running time:

Finding the heavy vertices $H$ and computing the resulting connecting
components $\mathcal{V}=\\{V_{1},\dots,V_{\ell}\\}$ of $G-H$ can be performed
in time $\mathcal{O}(|E|)$. The algorithm BalancedPartition runs in time
$\mathcal{O}(|E(G[V_{i}])|)$ by Lemma A.4 for every $i\in[\ell]$ and
consequently, in $\mathcal{O}(|E|)$ in total as the vertex sets in
$\mathcal{V}$ are pairwise disjoint. Hence, algorithm MaxMinApx runs in time
$\mathcal{O}(|E|)$.

We modify slightly the binary search to optimize the total running time. Let
$g(\ell):=2^{\ell}$, $\mathbb{N}\ni\ell\geq 1$. We increase stepwise $\ell$ in
$g(\ell)$ until we find an $\ell^{*}$ with
$g(\ell^{*})<X^{*}\leq\min\left(g\left(\ell^{*}+1\right),w(G)/k\right)=:\widehat{X}\leq
2X^{*}$. Afterwards, we perform a binary search in the interval
$X\in\left[g(\ell^{*}),\widehat{X}\right]$. As a result, finding the
$(c-1)$-approximate solution $\mathcal{S}$ runs in time
$\mathcal{O}\left(\left(\log X^{*}+logX^{*}\right)|E|\right)$ and thus, we
obtain a running time in $\mathcal{O}\left(log\left(X^{*}\right)|E|\right)$.
This completes the proof of Theorem 1.3.

##  Appendix B Missing details from Section 4.1

###  B.1 Preprocessing to get $w_{\max}<\alpha w_{k}$

Suppose $w_{\max}\geq\alpha w_{\ell}$, where $\ell$ is the smallest index in
$[k]$ that satisfies this inequality. We remove a vertex $v_{\max}$ with
$w(v_{\max})=w_{\max}$ from $G$ and $w_{\ell}$ from $\mathcal{W}$. Further, we
set $T_{\ell}=\\{v_{\max}\\}$ and consider the set for index $\ell$ to be
finished, i.e., we now aim to find a set
$\mathcal{T}=\\{T_{1},\dots,T_{\ell-1},T_{\ell+1},\dots,T_{k}\\}$ according to
$\mathcal{W}=\\{w_{1},\dots,w_{\ell-1},w_{\ell+1},\dots,w_{k}\\}$. Observe
that since we only deleted one vertex, $G$ now is at least $(k-1)$-connected,
and $|\mathcal{W}|=k-1$. Note that since $w_{\max}\leq w_{k}\leq w_{\ell}\leq
3\alpha w_{\ell}$, we have $w(T_{\ell})\in[\alpha w_{\ell},3\alpha w_{\ell}]$
as required. Also, we obtain $w(G)\geq\sum_{w_{j}\in\mathcal{W}}w_{j}$ after
removing $w_{\ell}$ from $\mathcal{W}$ and $v_{\max}$ from $G$. After this
preprocessing step, we can assume that we have a $k$-connected graph
$G=(V,E,w)$ and natural numbers $w_{1},\dots,w_{k}$ sorted in descending
order, where $\sum_{i=1}^{k}w_{i}\leq w(G)$ and $w_{\max}<\alpha w_{k}$.

###  B.2 Missing lemmas for correctness of BoundedGL

######  Proof B.1 (Proof of Theorem 1.7 given Theorem 4.2).

First we prove the lower-bound version. Apply Theorem 4.2 on $G$ with
$\alpha=\frac{1}{3}$ and let $\mathcal{T}=\\{T_{1},\dots,T_{\ell}\\}$ be the
resulting vertex sets. For each $T_{i}\in\mathcal{T}$, we have that
$\frac{1}{3}w_{i}\leq w(T_{i})\leq w_{i}$. We claim that $\ell=k$. Indeed, if
$\ell<k$, then since $w(T_{i})\leq w_{i}$ for every $i\in[\ell]$, we have that
$\sum_{i=1}^{\ell}w(T_{i})<\sum_{i=1}^{k}w_{i}=w(G)$, and hence $\mathcal{T}$
is not a CVP, a contradiction to Theorem 4.2. Note that each
$T_{i}\in\mathcal{T}$ already satisfies the required lower bound of
$w(T_{i})\geq\frac{1}{3}w_{i}$. Now, we can obtain the desired CVP
$\mathcal{T}^{*}$ by adding each connected component $Q$ of $G\setminus
V(\mathcal{T})$ to an arbitrary vertex set in $\mathcal{T}$ that has an edge
to $Q$.

Now, we prove the upper-bound version. Apply Theorem 4.2 on $G$ with
$\alpha=1$ and let $\mathcal{T}=\\{T_{1},\dots,T_{\ell}\\}$ be the resulting
vertex sets. For each $T_{i}\in\mathcal{T}$, we have that $w_{i}\leq
w(T_{i})\leq 3w_{i}$. We claim that $\mathcal{T}$ is a CVP of $V$. Indeed, by
Theorem 4.2, if $\mathcal{T}$ is not a CVP, then $\ell=k$ but then since
$w(T_{i})\geq w_{i}$ for every $i\in[\ell]$, we get
$\sum_{i=1}^{\ell}w(T_{i})=w(G)$, a contradiction. Note that each
$T_{i}\in\mathcal{T}$ already satisfies the required upper bound of
$w(T_{i})\leq 3w_{i}$. If $\ell=k$, then $w(T_{i})=w_{i}$ for every $i\in[k]$
and we are done. In case $\ell<k$ we remove an arbitrary vertex $v$ from a
vertex set $T\in\mathcal{T}$ with $|T|\geq 2$ (at least one such set exists
due to $k$-connectivity), such that $T$ is still a connected vertex set, and
we add $\\{v\\}$ as a new set to $\mathcal{T}$. We repeat this till
$|\mathcal{T}|=k$. Now, the resulting $\mathcal{T}$ is a CVP with the desired
upper bound conditions, since we only remove vertices from already existing
sets in $\mathcal{T}$ and since $w_{\max}\leq w_{k}$ the new singleton vertex
sets in $\mathcal{T}$ satisfy the required upper bound conditions. Observe
that this last step does not work, if we do not require $w_{\max}\leq w_{k}$.

######  Proof B.2 (Proof of Lemma 4.5).

The occurrence of one of the two cases in Step 22.2 is shown in Lemma B.3. For
the correctness of Case 1, observe that we can use Lemma 4.1 to divide
$T_{j}\cup Q$, as $T_{j}\cup Q$ cannot have an $(\alpha w_{j})$-separator
(this would give an ($\alpha w_{j})$-separator for $T_{j}$ implying that
$T_{j}\in\mathcal{T}_{b}$). It remains to prove that the inner loop terminates
as claimed. If Step 2(2.2)2.2.1 is executed, then an $i$-big component is
created in $\overline{G}$ as $\overline{G}$ now contains $V_{1}$ returned by
the divide-routine, and hence the loop is terminated. The same yields if we
apply the divide routine in Step 2(2.2)2.2.2. So, suppose the inner loop never
executes the divide routine. In the other cases, either a connected component
is deleted from $\overline{G}$ or new vertices are added to a connected
component in $\overline{G}$. Also note that new connected components are not
introduced to $\overline{G}$ and vertices are not deleted from existing
connected components (except when the whole connected component is removed;
also, two or more connected components may merge due to the introduction of
new vertices to $\overline{G}$). Thus, after $|V|^{2}$ iterations either there
is an $i$-big component or $\overline{G}$ is empty.

######  Lemma B.3.

In Step 22.2 at least Case 1 or Case 2 occurs.

######  Proof B.4.

Suppose Case 1 does not occur i.e., $Q$ does not have an edge to any
$T_{j}\in\mathcal{T}_{a}$. For $T_{j}\in\mathcal{T}_{b}$, let $s_{j}$ denote
the fixed $(\alpha w_{j})$-seperator vertex. Since $G$ is $k$-connected and
$|\mathcal{T}|<k$, there is an edge from $Q$ to at least one vertex in
$\bigcup_{T_{j}\in\mathcal{T}_{b}}T_{j}\setminus\\{s_{j}\\}$. Thus, Case 2
occurs.

######  Lemma B.5.

Whenever the divide routine in algorithm BoundedGL is to be executed, there is
at least one $i$-big component in $\overline{G}$.

######  Proof B.6.

When $i=1$ i.e. in the first main loop iteration, this holds because
$\overline{G}=G$ is connected and $\alpha w_{1}\leq
w_{1}\leq\sum_{i=1}^{k}w_{i}\leq w(G)$. For the subsequent iterations, the
divide routine is only applied after the inner loop is terminated which only
happens if either $\overline{G}$ is empty or has an $i$-big component. In case
$\overline{G}$ is empty, then the algorithm terminates. So, if the algorithm
applies the divide routine in the inner loop, then $\overline{G}$ has an
$i$-big component.

###  B.3 Runtime analysis of BoundedGL

######  Lemma B.7.

The algorithm BoundedGL runs in $\mathcal{O}(k|V|^{2}|E|)$ time.

######  Proof B.8.

Clearly, the main loop has at most $k$ iterations and the inner loop has at
most $|V|^{2}$ iterations by Lemma 4.5.

We categorize only the elements in $\mathcal{T}$ that satisfy $w(T_{j})\geq
2\alpha w_{j}$ into $\mathcal{T}_{a}$ and $\mathcal{T}_{b}$. Note that
$w(Q)<w_{i}$ as $Q$ is $i$-small. That is, at the point where some
$T_{j}\in\mathcal{T}$ exceeds $2\alpha w_{j}$, its weight is less than
$3\alpha w_{j}$ and the category of $T_{j}$ can be computed. Consequently,
reaching Step 2(2.2)2.2.2 means that we have $w(T_{j})\geq 2\alpha w_{j}$.
Otherwise, we have $w(T_{j}\cup Q)\leq 3\alpha w_{j}$ and would iterate with
the next $i$-small connected component of $\overline{G}$. Now, in case we
remove $Q^{\prime}$ from $T_{j}$ in Step 2(2.2)2.2.2 will show that the weight
still satisfies $w(T_{j}\setminus Q^{\prime})\geq 2\alpha w_{j}$ to avoid a
re-categorization of $T_{j}$. This finally will ensure that we can bound the
number of categorizations of $T\in\mathcal{T}$ into $\mathcal{T}_{a}$ and
$\mathcal{T}_{b}$ throughout the whole algorithm by $2k$. Moreover, that we
can realize a check whether $T_{j}\cup Q$ is $\alpha w_{j}$-dividable in Step
2(2.2)2.2.2 in linear time. Observe by Lemma 4.1 that a
$T_{j}\in\mathcal{T}_{a}$ will never change its category except when we
execute the divide routine on $T_{j}$ in Step 2(2.2)2.2.1. Now, we want to
ensure the same for the elements in $\mathcal{T}_{b}$ in Step 2(2.2)2.2.2.

######  Claim 1.

Let $T_{j}\in\mathcal{T}_{b}$ with $w(T_{j})\geq 2\alpha w_{j}$ and
$w(T_{j}\cup Q)\geq 3\alpha w_{j}$, where $w(Q)<w_{j}$. If $G[V(C(T_{j}))\cup
Q]$ contains a component $R\subset T_{j}\cup Q$ with weight at least $\alpha
w_{j}$, then $T_{j}\cup Q$ is $\alpha w_{j}$-dividable.

######  Proof B.9.

Clearly $R$ contains $Q$ as $T_{j}\in\mathcal{T}_{b}$ and $Q$ connects some
components in $\mathcal{Q}\subseteq C(T_{j})$. As long $Q$ weigh less than
$\alpha w_{j}$ we add individual $Q^{\prime\prime}\in\mathcal{Q}$ to $Q$. By
$w(Q^{\prime\prime})<\alpha w_{j}$ we can ensure that the resulting $Q$ weighs
less than $2\alpha w_{j}$ and thus $w(T_{j}\setminus Q)\geq\alpha w_{j}$ as
$w(T_{j}\cup Q)\geq 3\alpha w_{j}$. Since every component of $C(T_{j})$ is
connected to $s_{j}$, we produce with $Q$ and $T_{j}\setminus Q$ two connected
vertex sets each of weight at least $\alpha w_{j}$.

######  Claim 2.

Let $T_{j}\in\mathcal{T}_{b}$ with $w(T_{j})\geq 2\alpha w_{j}$ and
$w(T_{j}\cup Q)\geq 3\alpha w_{j}$, where $w(Q)<w_{j}$. If $G[V(C(T_{j}))\cup
Q]$ contains no component with weight at least $\alpha w_{j}$, then in Step
2(2.2)2.2.2 we have $w(T_{j}\setminus Q^{\prime})\geq 2\alpha w_{j}$.
Furthermore, after removing $Q^{\prime}$ from $T_{j}$ we have
$T_{j}\in\mathcal{T}_{b}$ with the same $\alpha w_{j}$-separator $s_{j}$.

######  Proof B.10.

$Q^{\prime}$ is connected to $Q$ and $w(Q\cup Q^{\prime})<\alpha w_{j}$ as
$G[V(C(T_{j}))\cup Q]$ contains no component with weight of at least $\alpha
w_{j}$. Thus, $w(T_{j}\setminus Q^{\prime})<2\alpha w_{j}$ contradicts
$w(T_{j}\cup Q)\geq 3\alpha w_{j}$. The second part of the claim is obviously
true as we remove only $Q^{\prime}$ from $C(T_{j})$.

As a result, once a $T\in\mathcal{T}$ is categorized, then a re-categorization
is only necessary if we apply the divide routine on $T$. Since this can happen
once in the outer loop and this loop is executed at most $k$ times, we get at
most $k$ additional re-categorizations and therefore in total at most $2k$
categorizations. Hence, by Lemma 4.1 we may realize this in
$\mathcal{O}(k|V||E|)$.

It remains to analyze the steps in the inner loop. Applying the divide routine
in Step 2(2.2)2.2.1 or in Step 2(2.2)2.2.2 can be performed in
$\mathcal{O}(|V||E|)$ by Lemma 4.1. This occurs at most once per iteration of
the outer loop as the inner loop terminates once a divide routine is executed;
note that the divide routine creates the $i$-big component $V_{1}$ in
$\overline{G}$. All other individual steps can be easily realized in time
$\mathcal{O}(|E|)$, also the check, whether $T_{j}\cup Q$ is $\alpha
w_{j}$-dividable in Step 2(2.2)2.2.2 (cf. 1). Thus the claimed runtime
follows.

##  Appendix C Missing details from Section 4.2

First we show the existence of the required path in Step 22.1 of
DoubleBoundedGL.

######  Lemma C.1.

In the algorithm DoubleBoundedGL, whenever Step 22.1 is reached, the sets
$\mathcal{Q}$ and $\mathcal{T}^{-}$ are non-empty and there is a path from
$\mathcal{Q}$ to $\mathcal{T}^{-}$ in $H$.

######  Proof C.2.

We know that $\mathcal{Q}\neq\varnothing$ due to the while loop condition.
Note that if $|\mathcal{T}^{+}|=k$, then we have a _perfect partition_ , i.e.
$w(T_{i})=w_{i}$ for every $i\in[k]$ as $\sum_{i=1}^{k}w_{i}=w(G)$, and hence
$\mathcal{Q}=\varnothing$. Thus, we have that $|\mathcal{T}^{+}|<k$ and
$\mathcal{T}^{-}\neq\varnothing$. Since $|s(\mathcal{T}^{+})|<k$,
$G-s(\mathcal{T}^{+})$ is connected. Hence, the transfer-graph $H$ is
connected by construction. Since $\mathcal{Q},\mathcal{T}^{-}\neq\varnothing$,
there is a path from $\mathcal{Q}$ to $\mathcal{T}^{-}$ in $H$.

Now we show the correctness of TransferVertices.

######  Lemma C.3.

After a call of algorithm TransferVertices, either $|\mathcal{T}^{*}|$
increases, or $|\mathcal{T}^{*}|$ remains same and the number of
$\mathcal{T}$-assigned vertices increases. Furthermore, the resulting
$\mathcal{T}$ is still pack-satisfied.

######  Proof C.4.

Note that if the precondition of any of the steps 22.2 to 22.5 is satisfied
then the algorithm terminates. Suppose $\ell$ is the last iteration of the for
loop. Then in all of the iterations $1,2,\cdots,\ell-1$, Step 22.6 was
executed, and none of the Steps 22.2 to 22.5 are executed. Let
$\mathcal{T}_{0}$ be the $\mathcal{T}$ input to the TransferVertices routine.
Let $I^{*}_{0}=I(\mathcal{T}_{0})$. We show that after the iteration $p$ for
each $p\in[0,\ell-1]$, the following invariants are satisfied:

  1. 1.

$I(\mathcal{T}^{*})=I^{*}_{0}$,

  2. 2.

$\mathcal{T}$ is pack-satisfied,

  3. 3.

$X\supseteq Q$,

  4. 4.

$X\cap V(\mathcal{T})=\varnothing$ ,

  5. 5.

$V(\mathcal{T})\cup X=V(\mathcal{T}_{0})\cup Q$,

  6. 6.

$G[X]$ is connected.

  7. 7.

$X$ has an edge in $G$ to $P_{Q}^{p+1}$,

We prove by induction on $p$. It is easy to see that all the invariants are
satisfied for $p=0$ (i.e. before the first iteration). Now, we do the
induction step. In the iteration $p$, we remove $P_{Q}^{p}$ from $T_{j}$.
Since $w(P_{Q}^{p})\leq w_{j}$, and $w(T_{j}\cup X)\geq 3w_{j}$ (otherwise
precondition of Step 22.3 would have been satisfied) and $w(X)\leq w_{u}\leq
w_{j}$ (if $w(X)\geq w_{u}$ then precondition of Step 22.2 would have been
satisfied; the inequality $w_{u}\leq w_{j}$ is because
$T_{j}\in\mathcal{T}^{*}$), we have that $T_{j}$ still has at least $w_{j}$
weight after the iteration. Also, $w(T_{j})\leq\max\\{r,3\\}w_{j}$ after
truncation. Thus $T_{j}\in\mathcal{T}^{+}$ and it follows that invariants 1, 2
are satisfied. Since we only add vertices to $X$, invariant 3 is satisfied.
Invariant 4 and 5 are satisfied because of the corresponding induction
assumptions and that the vertex set newly added to $X$ is removed from $T_{j}$
(and hence from $V(\mathcal{T}))$. Invariant 6 follows as $X$ was connected
before (by induction assumption), the newly added set $P_{Q}^{p}$ is
connected, and there is an edge from $X$ to $P_{Q}^{p}$ (by induction
assumption). Since $P_{Q}^{p}$ has an edge to $P_{Q}^{p+1}$, invariant 7
follows.

Now, we analyze the final iteration $\ell$. In this iteration, clearly one of
the steps 22.2 to 22.5 satisfies the precondition and the algorithm terminates
after this step. Note that if $\ell=|P_{Q}^{T_{i}}|$, then the precondition of
Step 22.4 is satisfied (if that step is reached without termination). We
branch on which of the terminating steps is executed. For each of the steps
22.2 to 22.5 we show that during the step:

  1. (a)

each $T_{j}\in\mathcal{T}^{*}$ remains in $\mathcal{T}^{+}$

  2. (b)

either $T_{u}$ moves from $\mathcal{T}^{-}$ to $\mathcal{T}^{+}$ or the
vertices that were in $V(\mathcal{T})\cup X$ before the step ends up in
$V(\mathcal{T})$ after the step.

  3. (c)

$\mathcal{T}$ remains pack-satisfied.

The above three statements are sufficient to prove the lemma because: from (a)
and (b), we have that either $|\mathcal{T}^{*}|$ increases or
$|\mathcal{T}^{*}|$ remains same and all the vertices in $V(\mathcal{T})\cup
X$ becomes $\mathcal{T}$-assigned, during the terminating step. Recall that by
invariant 1, we have that $\mathcal{T}^{*}$ remains the same during previous
iterations and that $V(\mathcal{T})\cup X=V(\mathcal{T}_{0})\cup Q$ before the
terminating step. Thus, we get that during the TransferVertices routine,
either $\mathcal{T}^{*}$ increases, or $|\mathcal{T}^{*}|$ remains same and
the number of $\mathcal{T}$-assigned vertices increase. From (c), we get the
pack-satisfiability of $\mathcal{T}$.

It only remains to show that for each of the steps 22.2 to 22.5, (a), (b), and
(c) are satisfied.

Step 22.2:

We have $w(X)\geq w_{u}$. Hence, setting $T_{u}=X$ and truncating $T_{u}$
ensures that $w_{u}\leq T_{u}\leq\max\\{r,3\\}w_{u}$. Since $X$ is connected
by invariant 6, we have that $T_{u}$ is connected. Thus $T_{u}$ moves from
$\mathcal{T}^{-}$ to $\mathcal{T}^{+}$. Thus (b) is satisfied. Since the only
set in $\mathcal{T}$ that is modified is $T_{u}$, (a) and (c) are also
satisfied.

Step 22.3:

Observe that $X$ has an edge to $T_{j}$ by invariant 7, and hence $X\cup
T_{j}$ is connected. We have $w(T_{j}\cup X)\leq\max\\{r,3\\}w_{i}$ by the
precondition of the step. Also, $w(T_{j}\cup X)\geq w(T_{j})\geq w_{j}$ where
the latter inequality follows from that $\mathcal{T}$ was pack-satisfied.
Since no other set in $\mathcal{T}$ is modified, we have that (a) and (c) are
satisfied. Also, (b) is satisfied as all vertices that were in $X$ are now
$\mathcal{T}$-assigned.

Step 22.4:

Observe that $X$ has an edge to $T_{j}$ by invariant 7, and hence $X\cup
T_{j}$ is connected. We have $w(T_{j}^{\prime})=w(X\cup
T_{j})>\max\\{r,3\\}w_{j}\geq w_{u}$ where the former inequality is by using
that precondition of Step 22.3 is not satisfied and the latter is because
$\max\\{r,3\\}w_{j}\geq w_{1}\geq w_{u}$. Thus $w(T_{u})$ after the step
becomes greater than $w_{u}$, thus moving $T_{u}$ to $\mathcal{T}^{+}$. The
only other set in $\mathcal{T}$ that is modified is $T_{j}$. We know
$w_{j}<w_{u}$ as $T_{j}$ was not in $\mathcal{T}^{*}$ (using the definition of
$u$ and $\mathcal{T}^{*}$). Thus, before the step we had
$w(T_{u})\geq\frac{1}{3}w_{u}\geq\frac{1}{3}w_{j}$, where the first inequality
uses that $\mathcal{T}$ was pack-satisfied by invariant 2. This implies that
after the step $w(T_{j})\geq\frac{1}{3}w_{j}$. Also, $T_{j}$ is connected
after the step as $T_{u}$ was connected before the step. Truncating $T_{j}$
and $T_{u}$ if necessary leads to $\mathcal{T}$ being pack-satisfied.

Step 22.5:

Note that we have $w_{j}\geq w_{u}$ as $T_{j}\in\mathcal{T}^{*}$ (otherwise
the Step 22.4 would have been executed). The only sets of $\mathcal{T}$ that
are modified in this step are $T_{j}$ and $T_{u}$. Since $V_{1}$ and $V_{2}$
are connected and $w(V_{1}),w(V_{2})\geq w_{j}\geq w_{u}$, we have that
$T_{j}$ and $T_{u}$ are each connected and has weight at least $w_{j}$ and
$w_{u}$ respectively. Thus $T_{j}$ remains in $\mathcal{T}^{+}$ and $T_{u}$
moves to $\mathcal{T}^{+}$. Truncating $T_{j}$ and $T_{u}$ if necessary leads
to $\mathcal{T}$ being still pack-satisfied.

Now, we show the correctness of DoubleBoundedGL.

######  Lemma C.5.

At the end of DoubleBoundedGL, the packing $\mathcal{T}$ is a CVPk with the
weight bounds as required by Theorem 1.8.

######  Proof C.6.

For this, first observe that after at most $k|V|$ iterations of the while-loop
$V(\mathcal{T})=V(G)$. This is because we guarantee that in each iteration,
either $|\mathcal{T}^{*}|$ increases, or $|\mathcal{T}^{*}|$ remains same and
the number of $\mathcal{T}$-assigned vertices increase. So, the while loop
terminates after $k|V|$ iterations and hence the algorithm terminates with
$V(\mathcal{T})=V(G)$. Since we maintained that $\mathcal{T}$ is pack-
satisfied, we get that $\mathcal{T}$ satisfies the required conditions for the
partition required by Theorem 1.8.

Finally, we analyze the total running time of algorithm DoubleBoundedGL.

#### Running time:

We show that the algorithm DoubleBoundedGL runs in time
$\mathcal{O}(k|V|^{2}|E|)$. Step 1 of algorithm DoubleBoundedGL runs in time
$\mathcal{O}(k|V|^{2}|E|)$ by Theorem 1.7. The dominating steps in the while
loop of Step 2 are the categorization of sets in $\mathcal{T}$ into
$\mathcal{T}_{a}^{+}$ and $\mathcal{T}_{b}^{+}$ (including finding the
seperator $s(T_{i})$) and the Step 22.2 that applies algorithm
TransferVertices. The former can be done in time $\mathcal{O}(|V||E|)$ by
Lemma 4.1.

In algorithm TransferVertices we invoke the divide algorithm of Lemma 4.1 at
most once as the algorithm terminates in that case (Step 22.5). This costs
$\mathcal{O}(|V||E|)$ time by 4.1. It is easy to see that each of the other
steps in the for loop of algorithm TransferVertices needs only
$\mathcal{O}(|E|)$ time. Since $|P_{Q}^{T_{i}}|\leq|V|$, the number of
iterations of for loop is at most $|V|$. Thus, algorithm TransferVertices runs
in time $\mathcal{O}(|V||E|)$.

The while-loop of DoubleBoundedGL iterates at most $k|V|$ times by Lemma C.5.
As a result, algorithm DoubleBoundedGL runs in time
$\mathcal{O}(k|V|^{2}|E|)$.