Bringmann, Karl ;
Hermelin, Danny ;
Mnich, Matthias ;
van Leeuwen, Erik Jan
Parameterized Complexity Dichotomy for Steiner Multicut
Abstract
We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = \{T_{1},...,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 \ S. This problem generalizes several wellstudied graph cut problems, in particular the Multicut problem, which corresponds to the case p = 2. The Multicut problem was recently shown to be fixedparameter tractable for parameter k [Marx and Razgon, Bousquet et al., STOC 2011]. 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 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 fixedparameter tractable or that the problem is hard (W[1]hard or even (para)NPcomplete). Among the many results in the paper, we highlight that:
 The edge deletion version of Steiner Multicut is fixedparameter 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 tw(G) to be any constants, our characterization includes a dichotomy for Steiner Multicut on trees (for tw(G) = 1) as well as a polynomial time versus NPhardness dichotomy (by restricting k,t,p,tw(G) to constant or unbounded).
BibTeX  Entry
@InProceedings{bringmann_et_al:LIPIcs:2015:4911,
author = {Karl Bringmann and Danny Hermelin and Matthias Mnich and Erik Jan van Leeuwen},
title = {{Parameterized Complexity Dichotomy for Steiner Multicut}},
booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
pages = {157170},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897781},
ISSN = {18688969},
year = {2015},
volume = {30},
editor = {Ernst W. Mayr and Nicolas Ollinger},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4911},
URN = {urn:nbn:de:0030drops49115},
doi = {10.4230/LIPIcs.STACS.2015.157},
annote = {Keywords: graph cut problems, Steiner cut, fixedparameter tractability}
}
2015
Keywords: 

graph cut problems, Steiner cut, fixedparameter tractability 
Seminar: 

32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Issue date: 

2015 
Date of publication: 

2015 