On the sum-max graph partitioning problem

This paper tackles the following problem: given a connected graph G=(V,E)G=(V,E) with a weight function on its edges and an integer k⩽|V|k⩽|V|, find a partition of V into k   clusters such that the sum (over all pairs of clusters) of the heaviest edges between the clusters is minimized. We first prove that this problem (and even the unweighted variant) cannot be approximated within a factor of O(n1−ϵ)O(n1−ϵ) unless P=NPP=NP, and cannot admit an FPTFPT algorithm unless FPT=W[1]FPT=W[1]. Next, we develop several algorithms: we first present a greedy algorithm and prove that it achieves a tight approximation ratio smaller than k2. Concerning the unweighted version of the problem, we study how the diameter of the input graph can influence its complexity, by obtaining negative results for graphs of low diameter, positive results for graphs of high diameter, and a polynomial-time approximation algorithm with an approximation ratio smaller than k2 and depending on the diameter. We also highlight a link between the k-sparsest subgraph problem and the unweighted version. This allows us to develop several constant ratio approximation algorithms running in exponential time for general graphs, and in polynomial time in some restricted graph classes. Finally, we discuss the exact resolution for fixed k and the connections to a graph homomorphism problem.