<p>Does anyone know how well directed multicut can be approximated in planar and minor free graphs?  Also any survey of approximability of directed multicut and multicut in various graph classes would be appreciated  Also if anyone can recommend</p>

CC BY-SA 4.0
2020-08-24T20:34:20.547Z
As far as I know nothing better than general graph results are known for planar directed multicut other than in some very special cases. An important open problem.
Chandra Chekuri
CC BY-SA 4.0
2020-08-24T22:41:29.780Z
@ChandraChekuri  could you elaborate on the very special cases?  I assume that the general graph result your refering to is  the logn loglogn of  G.  Even,  J.  (Seffi)  Naor,  B.  Schieber,  and  M.  Sudan.   Approximating  minimum  feedback  sets  andmulticuts in directed graphs?
user122938
<reference-request><approximation-algorithms><approximation-hardness><approximation><max-flow-min-cut>
polytime approximability of directed multicut
user122938
# polytime approximability of directed multicut

(Asked by: username_0 on 2020-08-24)

Does anyone know how well directed multicut can be approximated in planar and minor free graphs? Also any survey of approximability of directed multicut and multicut in various graph classes would be appreciated Also if anyone can recommend

**Tags:** reference-request, approximation-algorithms, approximation-hardness, approximation, max-flow-min-cut
> **Comments:**
> **username_1**: As far as I know nothing better than general graph results are known for planar directed multicut other than in some very special cases. An important open problem.  
> **username_0**: @ChandraChekuri  could you elaborate on the very special cases?  I assume that the general graph result your refering to is  the logn loglogn of  G.  Even,  J.  (Seffi)  Naor,  B.  Schieber,  and  M.  Sudan.   Approximating  minimum  feedback  sets  andmulticuts in directed graphs?  

---

## 0 answers

