Sum-Max Graph Partitioning Problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports Year : 2012

Sum-Max Graph Partitioning Problem


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.
Fichier principal
Vignette du fichier
RR.pdf (2.28 Mo) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-00694569 , version 1 (04-05-2012)
lirmm-00694569 , version 2 (02-10-2012)


  • 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⟩
154 View
834 Download


Gmail Mastodon Facebook X LinkedIn More