CJTCS Volume 1997 Article 2

On the Hardness of Approximating Max k-Cut and Its Dual

Viggo Kann (Royal Institute of Technology, Sweden), Sanjeev Khanna (Bell Laboratories), Jens Lagergren (Royal Institute of Technology, Sweden), Alessandro Panconesi (The Swedish Institute of Computer Science) 3 June 1997

Abstract

We study the Max k -Cut problem and its dual, the Min k -Partition problem. In the Min k -Partition problem, given a graph G =( V , E ) and positive edge weights, we want to find an edge set of minimum weight whose removal makes G k -colorable. For the Max k -Cut problem we show that, if P &neq