# Approximation algorithms for multicut for special classes of graphs

The multicut problem is the following.

Given a graph $G=(V,E)$ with edge costs $c_e$ for edge $e$ and a set of $k$ terminal pairs $\{(s_1,t_1),\ldots,(s_k,t_k)\}$, the objective is to find a set of edges $F \subseteq E$ of minimum cost, such that in the graph $H=(V,E \setminus F)$, no terminal pair $s_i,t_i$ are in the same connected component. In other words, deleting the edges in $F$ will remove all paths between any terminal pair $s_i,t_i$.

This problem is NP-hard. For general graphs, an $O(\log k)$-approximation is known. For trees, a 2-approximation is known. It is also known to be APX-hard. Is there any other results known for special classes of graphs?

I am particularly interested in the following graphs, but other classes of graphs will also be informative.

• Paths
• Cycles
• $n \times n$ grids
• Outerplanar graphs
• Planar graphs
• Series-parallel graphs

Any reference or survey paper will be highly appreciated.

• If the graph is a path, we can solve the problem exactly using LP. If the graph is a cycle, we can guess one cut edge and reduce the problem to the case when the graph is a path.
– Yury
Sep 17, 2013 at 17:59
• Thanks Yury for the info. Are there results known for other classes of graphs? Sep 18, 2013 at 5:33
• See E. Tardos and V. V. Vazirani. Improved bounds for the max-flow min-multicut ratio for planar and $K_{r,r}$-free graphs. Information Processing Letters, vol. 47 (2), 1993, pp. 77—80.
– Yury
Sep 18, 2013 at 7:07