English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Parameterized Complexity Dichotomy for Steiner Multicut

MPS-Authors
/persons/resource/persons44182

Bringmann,  Karl
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons98374

van Leeuwen,  Erik Jan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)

arXiv:1404.7006.pdf
(Preprint), 575KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Bringmann, K., Hermelin, D., Mnich, M., & van Leeuwen, E. J. (2014). Parameterized Complexity Dichotomy for Steiner Multicut. Retrieved from http://arxiv.org/abs/1404.7006.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0024-4068-A
Abstract
The Steiner Multicut problem asks, given an undirected graph G, terminals sets T1,...,Tt $\subseteq$ V(G) of size at most p, and an integer k, whether there is a set S of at most k edges or nodes s.t. of each set Ti at least one pair of terminals is in different connected components of G \ S. This problem generalizes several graph cut problems, in particular the Multicut problem (the case p = 2), which is fixed-parameter tractable for the parameter k [Marx and Razgon, Bousquet et al., STOC 2011]. We provide a dichotomy of the parameterized complexity of Steiner Multicut. That is, 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 or that the problem is hard (W[1]-hard or even (para-)NP-complete). We highlight that: - The edge deletion version of Steiner Multicut is fixed-parameter tractable for the parameter k+t on general graphs (but has no polynomial kernel, even on trees). The algorithm relies on several new structural lemmas, which decompose the Steiner cut into important separators and minimal s-t cuts, and which only hold for the edge deletion version of the problem. - 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. Hence, the results of Marx and Razgon, and Bousquet et al. do not generalize to Steiner Multicut. Since we allow k, t, p, and tw(G) to be any constants, our characterization includes a dichotomy for Steiner Multicut on trees (for tw(G) = 1), and a polynomial time versus NP-hardness dichotomy (by restricting k,t,p,tw(G) to constant or unbounded).