The Complexity of Multiterminal Cuts
- 1 August 1994
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 23 (4) , 864-894
- https://doi.org/10.1137/s0097539792225297
Abstract
In the multiterminal cut problem one is given an edge-weighted graph and a subset of the vertices called terminals, and is asked for a minimum weight set of edges that separates each terminal from all the others. When the number k of terminals is two, this is simply the mincut, max-flow problem, and can be solved in polynomial time. It is shown that the problem becomes NP-hard as soon as k = 3, but can be solved in polynomial time for planar graphs for any fixed k. The planar problem is NP-hard, however, if k is not fixed. A simple approximation algorithm for arbitrary graphs that is g guaranteed to come within a factor of 2 - 2/k of the optimal cut weight is also described.Keywords
This publication has 15 references indexed in Scilit:
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- A Polynomial Algorithm for the k-cut Problem for Fixed kMathematics of Operations Research, 1994
- Evolutionary trees: An integer multicommodity max-flow-min-cut theoremAdvances in Applied Mathematics, 1992
- The optimal multiterminal cut problemPublished by American Mathematical Society (AMS) ,1991
- An improved algorithm for the planar 3-cut problemJournal of Algorithms, 1991
- On the multiway cut polyhedronNetworks, 1991
- A new approach to the maximum-flow problemJournal of the ACM, 1988
- Fast Algorithms for Shortest Paths in Planar Graphs, with ApplicationsSIAM Journal on Computing, 1987
- An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut ProblemSIAM Journal on Algebraic Discrete Methods, 1985
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981