English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  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
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0024-4068-A Version Permalink: http://hdl.handle.net/11858/00-001M-0000-002C-54D3-B
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:
File downloaded from arXiv at 2014-11-26 09:03
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

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: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1404.7006
URI: http://arxiv.org/abs/1404.7006
BibTex Citekey: bringmann_parameterized_2013
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show