Parameterized complexity dichotomy for \textsc{Steiner Multicut}

DOI10.1016/j.jcss.2016.03.003zbMath1342.68155arXiv1404.7006OpenAlexW1569731655MaRDI QIDQ295637

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)

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

zbMATH Keywords

parameterized complexitykernelizationcut problemsSteiner multicut

Mathematics Subject Classification ID

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

Related Items (6)

A survey of parameterized algorithms and the complexity of edge modification ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ Parameterized complexity of critical node cuts ⋮ Unnamed Item ⋮ Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers ⋮ On Covering Segments with Unit Intervals

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multicut in trees viewed through the eyes of vertex cover
• FPT algorithms for path-transversal and cycle-transversal problems
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel bounds for disjoint cycles and disjoint paths
• Parameterized graph separation problems
• Approximation algorithms for requirement cut on graphs
• The multi-multiway cut problem
• An approximate max-Steiner-tree-packing min-Steiner-cut theorem
• Simple and improved parameterized algorithms for multiterminal cuts
• An improved approximation algorithm for requirement cut
• On the parameterized complexity of multiple-interval graph problems
• On problems without polynomial kernels
• A partial k-arboretum of graphs with bounded treewidth
• 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
• On the hardness of approximating Multicut and Sparsest-Cut
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• Parametrized complexity theory.
• On Multiway Cut Parameterized above Lower Bounds
• Finding small separators in linear time via treewidth reduction
• Clique Cover and Graph Separation
• Important Separators and Parameterized Algorithms
• Approximation Algorithms for Steiner and Directed Multicuts
• Maximal Flow Through a Network
• Fast Algorithms for Finding Nearest Common Ancestors
• Easy problems for tree-decomposable graphs
• 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
• The Complexity of Multiterminal Cuts
• 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
• Kernelization Lower Bounds Through Colors and IDs
• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
• Vertex Sparsification and Oblivious Reductions
• 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
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Graph-Theoretic Concepts in Computer Science
• Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
• SOFSEM 2006: Theory and Practice of Computer Science
• Approximation algorithms for feasible cut and multicut problems

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