Approximation algorithms for the Bipartite Multicut problem

We introduce the Bipartite Multicut problem. This is a generalization of the st-Mincut problem is similar to the Multicut problem and also turns out to be an immediate generalization of the Min UnCut problem. We prove that this problem is NP-hard and then present an SDP based approximation algorithm. The SDP based approximation algorithm uses the structure theorem of metrics along with region growing techniques.