<p>Check the following survey:</p>

<ul>
<li>Marie-Christine Costa, Lucas Létocart, and Frédéric Roupin, "<a href="https://www-lipn.univ-paris13.fr/~letocart/SURVEY.pdf" rel="nofollow">Multicut and integral multiflow: a survey</a>", 2005</li>
</ul>

<p>You can also check <a href="http://www.ime.usp.br/~juanguti/multicorte/" rel="nofollow">my dissertation</a> on the directed case.</p>

CC BY-SA 4.0
2019-08-29T17:53:59.263Z
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
Hao S
CC BY-SA 3.0
2014-08-03T18:26:16.923Z
2014-08-04T16:47:04.123Z
2014-08-04T16:47:04.123Z
arbolverde
<p>The multicut problem is the following.</p>

<p>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$.</p>

<p>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?</p>

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

<ul>
<li>Paths</li>
<li>Cycles</li>
<li>$n \times n$ grids</li>
<li>Outerplanar graphs</li>
<li>Planar graphs</li>
<li>Series-parallel graphs</li>
</ul>

<p>Any reference or survey paper will be highly appreciated.</p>

CC BY-SA 3.0
2013-09-17T17:59:14.683Z
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
CC BY-SA 3.0
2013-09-18T05:33:56.110Z
Thanks Yury for the info. Are there results known for other classes of graphs?
Arindam Pal
CC BY-SA 3.0
2013-09-18T07:07:56.567Z
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
<approximation-algorithms><optimization><approximation-hardness>
Approximation algorithms for multicut for special classes of graphs
Arindam Pal
# Approximation algorithms for multicut for special classes of graphs

(Asked by: username_0 on 2013-09-17)

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.

**Tags:** approximation-algorithms, optimization, approximation-hardness
> **Comments:**
> **username_1**: 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.  
> **username_0**: Thanks Yury for the info. Are there results known for other classes of graphs?  
> **username_1**: 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*.  

---

## 1 answers

### Answer by username_2 on 2014-08-03. Score: 2

Check the following survey:

* Marie-Christine Costa, Lucas Létocart, and Frédéric Roupin, "[Multicut and integral multiflow: a survey](https://www-lipn.univ-paris13.fr/~letocart/SURVEY.pdf)", 2005

You can also check [my dissertation](http://www.ime.usp.br/~juanguti/multicorte/) on the directed case.

> **Comments:**
> **username_3**: 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  

---

