Multi-way cut in directed graphs

For directed graphs, Garg et al. show that the multi-way cut problem is NP-Hard and propose an approximation algorithm that achieves a $2logk$ performance ratio [4]. Costs et al. give a polynomial time algorithm for acyclic directed graphs [7]. 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 one [5].

Alg. for Directed Graphs App. Ratio
Multi-way Cuts in Directed Graphs[4] $2logk$
Directed Multi-Way Cut [5] 2
Directed Acyclic [7] O($n^3$)

Ali Salehi 2005-04-29