An Approximation Algorithm for Max k-Uncut with Capacity Constraints

Clusters in protein interaction networks can potentially help identify functional relationships among proteins. The clustering problem can be modeled as a graph cut problem. Given an edge weighted graph the problem is to partition the vertices of the graph into k partitions of prescribed sizes such that the total weight of the edges within partitions are maximized. This problem is NP-complete for all k ges 2. We give a constant factor approximation for small k and uniform partition sizes. When the number of partitions k is 2, we give an approximation algorithm with performance ratio (p - 2)/p where p > 1 is the ratio of the sizes of the partitions. We evaluate the algorithms on the database of interacting proteins and on randomly generated graphs. Our experiments show that the algorithms are fast and have good performance ratio in practise.