TY - GEN

T1 - The complexity of multiway cuts

AU - Dahlhaus, E.

AU - Johnson, D. S.

AU - Papadimitriou, C. H.

AU - Seymour, P. D.

AU - Yannakakis, M.

N1 - Publisher Copyright:
© 1992 ACM.

PY - 1992/7/1

Y1 - 1992/7/1

N2 - In the Multiway Cut problem we are given an edge-weighted graph and a subset of the vertices called terminals, and 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 min-cut, max-flow problem, and can be solved in polynomial time. We show that the problem becomes NP-hard as soon as κ = 3, but can be solved in polynomial time for planar graphs for any fixed κ. The planar problem is NP-hard, however, if it is not fixed. We also describe a simple approximation algorithm for arbitrary graphs that is guaranteed to come within a factor of 2-2/κ of the optimal cut weight.

AB - In the Multiway Cut problem we are given an edge-weighted graph and a subset of the vertices called terminals, and 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 min-cut, max-flow problem, and can be solved in polynomial time. We show that the problem becomes NP-hard as soon as κ = 3, but can be solved in polynomial time for planar graphs for any fixed κ. The planar problem is NP-hard, however, if it is not fixed. We also describe a simple approximation algorithm for arbitrary graphs that is guaranteed to come within a factor of 2-2/κ of the optimal cut weight.

UR - http://www.scopus.com/inward/record.url?scp=0026966832&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026966832&partnerID=8YFLogxK

U2 - 10.1145/129712.129736

DO - 10.1145/129712.129736

M3 - Conference contribution

AN - SCOPUS:0026966832

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 241

EP - 251

BT - Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992

PB - Association for Computing Machinery

T2 - 24th Annual ACM Symposium on Theory of Computing, STOC 1992

Y2 - 4 May 1992 through 6 May 1992

ER -