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

123 Scopus citations

Abstract

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
Pages241-251
Number of pages11
ISBN (Electronic)0897915119
DOIs
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

Other

Other24th Annual ACM Symposium on Theory of Computing, STOC 1992
CountryCanada
CityVictoria
Period5/4/925/6/92

All Science Journal Classification (ASJC) codes

  • Software

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

Cite this