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
Contributor : Rémi Watrigant Connect in order to contact the contributor
Submitted on : Friday, May 4, 2012 - 5:24:01 PM
Last modification on : Monday, October 11, 2021 - 1:24:07 PM
Long-term archiving on: : Friday, March 31, 2017 - 6:54:18 AM


Files produced by the author(s)


  • HAL Id : lirmm-00694569, version 1


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



Record views


Files downloads