The complexity of multiway cuts

E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, M. Yannakakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

129 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationProceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992
PublisherAssociation for Computing Machinery
Number of pages11
ISBN (Electronic)0897915119
StatePublished - Jul 1 1992
Externally publishedYes
Event24th Annual ACM Symposium on Theory of Computing, STOC 1992 - Victoria, Canada
Duration: May 4 1992May 6 1992

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129722
ISSN (Print)0737-8017


Other24th Annual ACM Symposium on Theory of Computing, STOC 1992

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'The complexity of multiway cuts'. Together they form a unique fingerprint.

Cite this