On the complexity of the multicut problem in bounded tree-width graphs and digraphs

DOI10.1016/j.dam.2007.09.013zbMath1152.68038OpenAlexW2030340113MaRDI QIDQ944745

Cédric Bentz

Publication date: 10 September 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.09.013

zbMATH Keywords

multicutsNP-hardnessAPX-hardnessbounded tree-width

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Multicuts in planar and bounded-genus graphs with bounded number of terminals ⋮ Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability ⋮ An approximation algorithm for the generalized \(k\)-multicut problem ⋮ An FPT algorithm for planar multicuts with sources and sinks on the outer face ⋮ Disjoint paths in sparse graphs ⋮ On the hardness of finding near-optimal multicuts in directed acyclic graphs ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth ⋮ A simple algorithm for multicuts in planar graphs with outer terminals ⋮ New results on planar and directed multicuts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Minimal multicut and maximal integer multiflow: a survey
• On the Max-flow min-cut ratio for directed multicommodity flows
• Optimization, approximation, and complexity classes
• Directed tree-width
• On the hardness of approximating Multicut and Sparsest-Cut
• Hardness of cut problems in directed graphs
• Approximation Algorithms for Steiner and Directed Multicuts
• Graph minors. II. Algorithmic aspects of tree-width
• The Complexity of Multiterminal Cuts
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• SOFSEM 2006: Theory and Practice of Computer Science