  In the minimum Multicut problem, the input is an edge-weighted supply graph
$G=(V,E)$ and a simple demand graph $H=(V,F)$. Either $G$ and $H$ are directed
(DMulC) or both are undirected (UMulC). The goal is to remove a minimum weight
set of edges in $G$ such that there is no path from $s$ to $t$ in the remaining
graph for any $(s,t) \in F$. UMulC admits an $O(\log k)$-approximation where
$k$ is the vertex cover size of $H$ while the best known approximation for
DMulC is $\min\{k, \tilde{O}(n^{11/23})\}$. These approximations are obtained
by proving corresponding results on the multicommodity flow-cut gap. In
contrast to these results some special cases of Multicut, such as the
well-studied Multiway Cut problem, admit a constant factor approximation in
both undirected and directed graphs. Motivated by both concrete instances from
applications and abstract considerations, we consider the role that the
structure of the demand graph $H$ plays in determining the approximability of
Multicut.
  In undirected graphs our main result is a $2$-approximation in $n^{O(t)}$
time when the demand graph $H$ excludes an induced matching of size $t$. This
gives a constant factor approximation for a specific demand graph that
motivated this work.
  In contrast to undirected graphs, we prove that in directed graphs such
approximation algorithms can not exist. Assuming the Unique Games Conjecture
(UGC), for a large class of fixed demand graphs DMulC cannot be approximated to
a factor better than worst-case flow-cut gap. As a consequence we prove that
for any fixed $k$, assuming UGC, DMulC with $k$ demand pairs is hard to
approximate to within a factor better than $k$. On the positive side, we prove
an approximation of $k$ when the demand graph excludes certain graphs as an
induced subgraph. This generalizes the Multiway Cut result to a much larger
class of demand graphs.
