Parameterized complexity dichotomy for \textsc{Steiner Multicut}

DOI10.1016/J.JCSS.2016.03.003zbMATH Open1342.68155arXiv1404.7006OpenAlexW1569731655MaRDI QIDQ295637FDOQ295637

Authors: Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen 

Publication date: 13 June 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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). We present two proofs: one using the randomized contractions technique of Chitnis et al, and one relying on new structural lemmas that decompose the Steiner cut into important separators and minimal s-t cuts. - 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).

Full work available at URL: https://arxiv.org/abs/1404.7006

Recommendations

• Parameterized complexity dichotomy for Steiner Multicut
• SOFSEM 2006: Theory and Practice of Computer Science
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Fixed-parameter tractability of multicut parameterized by the size of the cutset

zbMATH Keywords

parameterized complexitykernelizationcut problemsSteiner multicut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Maximal Flow Through a Network
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• On problems without polynomial kernels
• A partial k-arboretum of graphs with bounded treewidth
• Parametrized complexity theory.
• Approximation Algorithms for Steiner and Directed Multicuts
• Easy problems for tree-decomposable graphs
• The Complexity of Multiterminal Cuts
• FPT algorithms for path-transversal and cycle-transversal problems
• Parameterized algorithms
• Parameterized graph separation problems
• Title not available (Why is that?)
• Kernelization lower bounds through colors and IDs
• Infeasibility of instance compression and succinct PCPs for NP
• An approximate max-Steiner-tree-packing min-Steiner-cut theorem
• On the hardness of approximating Multicut and Sparsest-Cut
• Graph-Theoretic Concepts in Computer Science
• On the parameterized complexity of multiple-interval graph problems
• A logical approach to multicut problems
• An improved parameterized algorithm for the minimum node multiway cut problem
• An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
• Finding small separators in linear time via treewidth reduction
• Clique Cover and Graph Separation
• Important separators and parameterized algorithms
• Title not available (Why is that?)
• Fast Algorithms for Finding Nearest Common Ancestors
• Title not available (Why is that?)
• Fixed-parameter tractability and data reduction for multicut in trees
• New limits to classical and quantum instance compression
• A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game
• Multicut in trees viewed through the eyes of vertex cover
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• The Pathwidth and Treewidth of Cographs
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
• Vertex sparsification and oblivious reductions
• \textsc{Multicut} is FPT
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• The minimum \(k\)-way cut of bounded size is fixed-parameter tractable
• SOFSEM 2006: Theory and Practice of Computer Science
• Approximation algorithms for feasible cut and multicut problems
• Kernel bounds for disjoint cycles and disjoint paths
• Approximation algorithms for requirement cut on graphs
• The multi-multiway cut problem
• Simple and improved parameterized algorithms for multiterminal cuts
• An improved approximation algorithm for requirement cut

Cited In (9)

• Parameterized complexity dichotomy for Steiner Multicut
• On Covering Segments with Unit Intervals
• Complexity of Steiner tree in split graphs -- dichotomy results
• Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
• A survey of parameterized algorithms and the complexity of edge modification
• Romeo and Juliet meeting in forest like regions
• Title not available (Why is that?)
• Parameterized complexity of critical node cuts
• Odd multiway cut in directed acyclic graphs

This page was built for publication: Parameterized complexity dichotomy for \textsc{Steiner Multicut}

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q295637)