Parameterized complexity dichotomy for \textsc{Steiner Multicut}
From MaRDI portal
Publication:295637
Abstract: The Steiner Multicut problem asks, given an undirected graph G, terminals sets T1,...,Tt 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).
Recommendations
Cites work
- \textsc{Multicut} is FPT
- A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A logical approach to multicut problems
- A partial k-arboretum of graphs with bounded treewidth
- A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
- An O^(1.84ᵏ) parameterized algorithm for the multiterminal cut problem
- An approximate max-Steiner-tree-packing min-Steiner-cut theorem
- An improved approximation algorithm for requirement cut
- An improved parameterized algorithm for the minimum node multiway cut problem
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Approximation algorithms for feasible cut and multicut problems
- Approximation algorithms for requirement cut on graphs
- Approximation Algorithms for Steiner and Directed Multicuts
- Clique Cover and Graph Separation
- 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
- Easy problems for tree-decomposable graphs
- Fast Algorithms for Finding Nearest Common Ancestors
- Finding small separators in linear time via treewidth reduction
- Fixed-parameter tractability and data reduction for multicut in trees
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- FPT algorithms for path-transversal and cycle-transversal problems
- Graph-Theoretic Concepts in Computer Science
- scientific article; zbMATH DE number 3121292 (Why is no real title available?)
- scientific article; zbMATH DE number 3876616 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- Important separators and parameterized algorithms
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Kernelization lower bounds through colors and IDs
- Maximal Flow Through a Network
- Multicut in trees viewed through the eyes of vertex cover
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- New limits to classical and quantum instance compression
- On problems without polynomial kernels
- On the hardness of approximating Multicut and Sparsest-Cut
- On the parameterized complexity of multiple-interval graph problems
- Parameterized algorithms
- Parameterized graph separation problems
- Parametrized complexity theory.
- Simple and improved parameterized algorithms for multiterminal cuts
- SOFSEM 2006: Theory and Practice of Computer Science
- The Complexity of Multiterminal Cuts
- The minimum k-way cut of bounded size is fixed-parameter tractable
- The multi-multiway cut problem
- The Pathwidth and Treewidth of Cographs
- Vertex sparsification and oblivious reductions
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
Cited in
(10)- Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
- Complexity of Steiner tree in split graphs -- dichotomy results
- Parameterized complexity dichotomy for Steiner Multicut
- Odd multiway cut in directed acyclic graphs
- scientific article; zbMATH DE number 7559431 (Why is no real title available?)
- Parameterized complexity of critical node cuts
- On Covering Segments with Unit Intervals
- A survey of parameterized algorithms and the complexity of edge modification
- Romeo and Juliet meeting in forest like regions
- On the parameterized complexity of multiway near-separator
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)
