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

  • 1
    $\begingroup$ 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. $\endgroup$ Commented Aug 24, 2020 at 20:34
  • $\begingroup$ @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? $\endgroup$
    – user122938
    Commented Aug 24, 2020 at 22:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.