Skip to Main content Skip to Navigation

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 : In this paper we consider the classical combinatorial optimization graph partitioning problem, with Sum-Max as objective function. Given a weighted graph $G=(V,E)$ and a integer $k$, our objective is to find a $k$-partition $(V_1,\dots,V_k)$ of $V$ that minimizes $\sum_{i=1}^{k-1}\sum_{j=i+1}^{k} \max_{u \in V_i, v \in V_j} ~w(u, v)$, where $w(u,v)$ denotes the weight of the edge $\{u,v\} \in E$. We establish the $\mathcal{NP}$-completeness of the problem and its unweighted version, and the $W[1]$-hardness for the parameter $k$. Then, we study the problem for small values of $k$, and show the membership in $\mathcal{P}$ when $k=3$, but the $\mathcal{NP}$-hardness for all fixed $k \geq 4$ if one vertex per cluster is fixed. Lastly, we present a natural greedy algorithm with an approximation ratio better than $\frac{k}{2}$, and show that our analysis is tight.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Rémi Watrigant <>
Submitted on : Tuesday, October 2, 2012 - 2:14:10 PM
Last modification on : Thursday, June 11, 2020 - 8:56:02 PM
Long-term archiving on: : Friday, March 31, 2017 - 1:52:01 PM


Files produced by the author(s)


  • HAL Id : lirmm-00694569, version 2



Rémi Watrigant, Marin Bougeret, Rodolphe Giroudeau, Jean-Claude König. Sum-Max Graph Partitioning Problem. RR-12015, 2012. ⟨lirmm-00694569v2⟩



Record views


Files downloads