2019/02/12 by Anisse Ismaïli, Ismaili, Anisse
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1902.06812
openalex publication_date 2019/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Σ2P. This hardness holds even for k=2 and arbitrary weights, or k=3 and non-negative weights, which matches what was known on MaxCut and Min-3-Cut one level higher in the polynomial hierarchy.