Parameterized complexity dichotomy for Steiner Multicut

• Steiner multicut seeks k elements to disconnect a pair from each of t terminal sets.
• Parameterized complexity dichotomy for k, t, treewidth and size p of terminal sets.
• Edge Steiner multicut is FPT for parameter k+tk+t but node versions are W[1]W[1]-hard.
• Edge Steiner multicut is W[1]W[1]-hard for parameter k  , treewidth 2, and p=3p=3.
• The results also imply a dichotomy on the classical complexity.

We consider the Steiner Multicut problem, which asks, given an undirected graph G  , a collection T={T1,…,Tt}T={T1,…,Tt}, Ti⊆V(G)Ti⊆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 TiTi at least one pair of terminals is in different connected components of G−SG−S. We provide a dichotomy of the parameterized complexity of Steiner Multicut. For any combination of k, t, p  , and the treewidth tw(G)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, W[1]W[1]-hard, or (para-)NPNP-complete. Our characterization includes a dichotomy for Steiner Multicut on trees as well as a polynomial time versus NPNP-hardness dichotomy (by restricting k,t,p,tw(G)k,t,p,tw(G) to constant or unbounded).