On the sum-max graph partitioning problem

Rémi Watrigant 1 Marin Bougeret 1 Rodolphe Giroudeau 1 Jean-Claude König 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : This paper tackles the following problem: given a connected graph with a weight function on its edges and an integer , 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 unless , and cannot admit an algorithm unless . Next, we develop several algorithms: we first present a greedy algorithm and prove that it achieves a tight approximation ratio smaller than . 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 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.
Complete list of metadatas

Contributor : Rodolphe Giroudeau <>
Submitted on : Tuesday, January 5, 2016 - 3:11:42 PM
Last modification on : Friday, May 3, 2019 - 12:08:04 PM




Rémi Watrigant, Marin Bougeret, Rodolphe Giroudeau, Jean-Claude König. On the sum-max graph partitioning problem. Theoretical Computer Science, Elsevier, 2014, Combinatorial Optimization: Theory of algorithms and Complexity, 540, pp.143-155. ⟨10.1016/j.tcs.2013.11.024⟩. ⟨lirmm-01251016⟩



Record views