Efficient algorithm for graph-partitioning problem using a problem transformation method

This paper shows that the uniform k-way partitioning problem can be transformed into the max-cut problem using a graph modification technique. An iterative algorith, based on Kernighan-Lin's (KL) method, for partitioning graphs is presented that exploits the problem equivalence property. The algorithm deals with nodes of various sizes without any performance degradation. The computing time per pass of the algorithm is O(itkN²), where N is the number of nodes in the given graph. In practice, only a small number of passes are typically needed, leading to a fast approximation algorithm for k-way partitioning. Experimental results show that the proposed algorithm outperforms the KL algorithm in the quality of solutions. The performance gap between the proposed and KL algorithms becomes much bigger as the amount of size differences between nodes increases.