Summary: We consider the Steiner Multicut problem, which asks, given an undirected graph \(G\), a collection \(\mathcal T = \{T_{1},\dots ,T_{t}\}\), \(T_i \subseteq V(G)\), of terminal sets of size at most \(p\), and an integer \(k\), whether there is a set \(S\) of at most \(k\) edges or nodes such that of each set \(T_{i}\) at least one pair of terminals is in different connected components of \(G \setminus S\). This problem generalizes several well-studied graph cut problems, in particular the Multicut problem, which corresponds to the case \(p = 2\). The Multicut problem was recently shown to be fixed-parameter tractable for parameter \(k\). The question whether this result generalizes to Steiner Multicut motivates the present work. We answer the question that motivated this work, and in fact provide a dichotomy of the parameterized complexity of Steiner Multicut on general graphs. That is, for any combination of \(k\), \(t\), \(p\), and the treewidth \(\operatorname{tw}(G)\) as constant, parameter, or unbounded, and for all versions of the problem (edge deletion and node deletion with and without deletable terminals), we prove either that the problem is fixed-parameter tractable or that the problem is hard (\(W[1]\)-hard or even (para-)NP-complete). Among the many results in the paper, we highlight that:
– The edge deletion version of Steiner Multicut is fixed-parameter tractable for parameter \(k+t\) on general graphs (but has no polynomial kernel, even on trees).
– In contrast, both node deletion versions of Steiner Multicut are \(W[1]\)-hard for the parameter \(k+t\) on general graphs.
– All versions of Steiner Multicut are \(W[1]\)-hard for the parameter \(k\), even when \(p=3\) and the graph is a tree plus one node.
Since we allow \(k\), \(t\), \(p\), and \(\operatorname{tw}(G)\) to be any constants, our characterization includes a dichotomy for Steiner Multicut on trees (for \(\operatorname{tw}(G) = 1\)) as well as a polynomial time versus NP-hardness dichotomy (by restricting \(k\), \(t\), \(p\), \(\operatorname{tw}(G)\) to constant or unbounded).
For the entire collection see [Zbl 1329.68033].