The balanced connected
k-partition problem (BCP) is a classic problem which
consists in partitioning the set of vertices of a vertex-weighted connected
graph into a collection of
k sets such that each of them induces a connected
subgraph of roughly the same weight. There exists a vast literature on BCP that
includes hardness results, approximation algorithms, integer programming
formulations, and a polyhedral study. We investigate edge-weighted variants of
BCP where we are given a connected graph
G,
k∈Z≥, and an
edge-weight function
w:E(G)→Q≥, and the goal is to
compute a spanning
k-forest
T of
G (i.e., a forest with exactly
k trees) that minimizes the weight of the heaviest tree in
T in
the min-max version, or maximizes the weight of the lightest tree in
T in the max-min version. We show that both versions of this
problem are
NP-hard on complete graphs with
k=2, unweighted split
graphs, and unweighted bipartite graphs with
k≥2 fixed. Moreover, we
prove that these problems do not admit subexponential-time algorithms, unless
the Exponential-Time Hypothesis fails. Finally, we devise compact and
non-compact integer linear programming formulations, valid inequalities, and
separation algorithms.