A further alternative is that of finding only an approximate solution for the multi-cut problem. For the fractional relaxation of the min multi-cut problem a fully polynomial time approximation scheme can be given with a fast combinatorial algorithm.

---