License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.157
URN: urn:nbn:de:0030-drops-49115
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4911/
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 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 [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 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 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 NP-hardness 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 = {157--170},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-78-1},
ISSN = {1868-8969},
year = {2015},
volume = {30},
editor = {Ernst W. Mayr and Nicolas Ollinger},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4911},
URN = {urn:nbn:de:0030-drops-49115},
doi = {10.4230/LIPIcs.STACS.2015.157},
annote = {Keywords: graph cut problems, Steiner cut, fixed-parameter tractability}
}
|
Keywords: |
|
graph cut problems, Steiner cut, fixed-parameter tractability |
|
Collection: |
|
32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
26.02.2015 |
