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 N Phard 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 N P-hard in directed acyclic graphs and APX -hard in bounded tree-width and bounded degree unweighted digraphs. The vertex version, although tractable in trees, is proved to be N P-hard in unweighted cacti of bounded degree and bounded path-width.
Bentz REF studied the complexity of the Multicut problem and its many variants in bounded tree-width graphs and digraphs.
On the complexity of the multicut problem in bounded tree-width graphs and digraphs
Discret. Appl. Math.
Discret. Appl. Math.
Computer Science Mathematics