On the complexity of the multicut problem in bounded tree-width graphs and digraphs

Given an edge- or vertex-weighted graph or digraph and a list of source–sink pairs, the minimum multicut problem   consists in selecting a minimum weight set of edges or vertices whose removal leaves no path from each source to the corresponding sink. This is a classical NPNP-hard problem, and we show that the edge version becomes tractable in bounded tree-width graphs if the number of source–sink pairs is fixed, but remains NPNP-hard in directed acyclic graphs and APXAPX-hard in bounded tree-width and bounded degree unweighted digraphs. The vertex version, although tractable in trees, is proved to be NPNP-hard in unweighted cacti of bounded degree and bounded path-width.