For directed graphs, Garg et al. show that the multi-way cut
problem is NP-Hard and propose an approximation algorithm that
achieves a performance ratio . Costs et al. give
a polynomial time algorithm for acyclic directed graphs .
J.Naor et al. present an improved approximation algorithm which achieves
approximation factor of 2, based on finding an optimal relaxed multi-way cut.
Their approach is to take multi-way cut problem as an integer linear program
where the relaxation is done by giving edges between terminals a length of at least