English

# Item

ITEM ACTIONSEXPORT

Parameterized Complexity Dichotomy for Steiner Multicut

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.

Item is

### Basic

show hide
Genre: Paper
Latex : Parameterized Complexity Dichotomy for {Steiner} {Multicut}

### Files

show Files
hide Files
:
arXiv:1404.7006.pdf (Preprint), 575KB
Name:
arXiv:1404.7006.pdf
Description:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
-
-

show

### Creators

show
hide
Creators:
Bringmann, Karl1, Author
Hermelin, Danny2, Author
Mnich, Matthias2, Author
van Leeuwen, Erik Jan1, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019
2External Organizations, ou_persistent22

### Content

show
hide
Free keywords: Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Discrete Mathematics, cs.DM
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).

### Details

show
hide
Language(s): eng - English
Dates: 2014-04-282014-04-28
Publication Status: Published online
Pages: 26 p.
Publishing info: -
Rev. Type: -
Identifiers: arXiv: 1404.7006
URI: http://arxiv.org/abs/1404.7006
BibTex Citekey: bringmann_parameterized_2013
Degree: -

show

show

show

show