1
$\begingroup$

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

$\endgroup$
  • 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$ – Chandra Chekuri Aug 24 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 Aug 24 at 22:41

Your Answer

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

Browse other questions tagged or ask your own question.