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
- 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?)
- A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
- A logical approach to multicut problems
- A partial k-arboretum of graphs with bounded treewidth
- 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 Steiner and Directed Multicuts
- Approximation algorithms for feasible cut and multicut problems
- Approximation algorithms for requirement cut on graphs
- 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
- FPT algorithms for path-transversal and cycle-transversal problems
- Fast Algorithms for Finding Nearest Common Ancestors
- Finding small separators in linear time via treewidth reduction
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- Fixed-parameter tractability and data reduction for multicut in trees
- Graph-Theoretic Concepts in Computer Science
- 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.
- SOFSEM 2006: Theory and Practice of Computer Science
- Simple and improved parameterized algorithms for multiterminal cuts
- The Complexity of Multiterminal Cuts
- The Pathwidth and Treewidth of Cographs
- The minimum \(k\)-way cut of bounded size is fixed-parameter tractable
- The multi-multiway cut problem
- Vertex sparsification and oblivious reductions
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- \textsc{Multicut} is FPT
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
- scientific article; zbMATH DE number 7559431 (Why is no real title available?)
- 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)
