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.
This work was done in collaboration with Romolo Marotta during preparation for the exam of Theoretical Computer Science at University “La Sapienza” – Italy