The Complexity of Max-Min $k$-Partitioning

Abstract

In this paper we study a max-min $k$-partition problem on a weighted graph, that could model a robust $k$-coalition formation. We settle the computational complexity of this problem as complete for class ${\Sigma }_2^P$. This hardness holds even for $k=2$ and arbitrary weights, or $k=3$ and non-negative weights, which matches what was known on \textsc{MaxCut} and \textsc{Min-3-Cut} one level higher in the polynomial hierarchy.

Personal part of a submission to AAMAS'19