Options
Parameterized complexity dichotomy for Steiner Multicut
Publikationstyp
Journal Article
Date Issued
2016-09-01
Sprache
English
TORE-URI
Volume
82
Issue
6
Start Page
1020
End Page
1043
Citation
Journal of Computer and System Sciences (2016)
Publisher DOI
We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T={T1,...,Tt}, 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 Ti at least one pair of terminals is in different connected components of G-S. We provide a dichotomy of the parameterized complexity of Steiner Multicut. For any combination of k, t, p, and the treewidth 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]-hard, or (para-)NP-complete. Our characterization includes a dichotomy for Steiner Multicut on trees as well as a polynomial time versus NP-hardness dichotomy (by restricting k,t,p,tw(G) to constant or unbounded).
Subjects
Cut problems
Kernelization
Parameterized complexity
Steiner multicut