Given graph \(G=(V,E)\) with vertex set V and edge set E, the max k-cut problem seeks to partition the vertex set V into at most k subsets that maximize the weight (number) of edges with endpoints in different parts. This paper proposes a graph folding procedure (i.e., a procedure that reduces the number of the vertices and edges of graph G) for the weighted max k-cut problem that may help reduce the problem’s dimensionality. While our theoretical results hold for any \(k \ge 2\) , our computational results show the effectiveness of the proposed preprocess only for \(k=2\) and on two sets of instances. Furthermore, we observe that the preprocess improves the performance of a MIP solver on a set of large-scale instances of the max cut problem.
