Given a graph and a set of terminal vertices, a multiway-cut is a set of edges such that in , no path exists between any two nodes of . The multiway-cut problem is defined as finding the multiway-cut where is minimal. Multi-way cut terminal problem is known to be NP-hard for .
Again, using approximation we can make a faster algorithm.