4
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yury
    Sep 17, 2013 at 17:59
  • $\begingroup$ Thanks Yury for the info. Are there results known for other classes of graphs? $\endgroup$
    – Arindam Pal
    Sep 18, 2013 at 5:33
  • 2
    $\begingroup$ 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. $\endgroup$
    – Yury
    Sep 18, 2013 at 7:07

1 Answer 1

Reset to default
2
$\begingroup$

Check the following survey:

You can also check my dissertation on the directed case.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Would you mind just summarizing what is known for the directed case? or just what it is for planar graphs? (hardness of apx and current best) as I don't understand portuagese $\endgroup$
    – Hao S
    Aug 29, 2019 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.