The complexity of multiway cuts

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

doi:10.1145/129712.129736

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 proceeding › Conference contribution

138 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 language	English (US)
Title of host publication	Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992
Publisher	Association for Computing Machinery
Pages	241-251
Number of pages	11
ISBN (Electronic)	0897915119
DOIs	https://doi.org/10.1145/129712.129736
State	Published - Jul 1 1992
Externally published	Yes
Event	24th Annual ACM Symposium on Theory of Computing, STOC 1992 - Victoria, Canada Duration: May 4 1992 → May 6 1992

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
Volume	Part F129722
ISSN (Print)	0737-8017

Other

Other	24th Annual ACM Symposium on Theory of Computing, STOC 1992
Country/Territory	Canada
City	Victoria
Period	5/4/92 → 5/6/92

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/129712.129736

Cite this

Dahlhaus, E., Johnson, D. S., Papadimitriou, C. H., Seymour, P. D., & Yannakakis, M. (1992). The complexity of multiway cuts. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992 (pp. 241-251). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F129722). Association for Computing Machinery. https://doi.org/10.1145/129712.129736

@inproceedings{a4475e3a475a4a3a88921570a2fb6e56,

title = "The complexity of multiway cuts",

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.",

author = "E. Dahlhaus and Johnson, {D. S.} and Papadimitriou, {C. H.} and Seymour, {P. D.} and M. Yannakakis",

note = "Publisher Copyright: {\textcopyright} 1992 ACM.; 24th Annual ACM Symposium on Theory of Computing, STOC 1992 ; Conference date: 04-05-1992 Through 06-05-1992",

year = "1992",

month = jul,

day = "1",

doi = "10.1145/129712.129736",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "241--251",

booktitle = "Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992",

}

Dahlhaus, E, Johnson, DS, Papadimitriou, CH, Seymour, PD & Yannakakis, M 1992, The complexity of multiway cuts. in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992. Proceedings of the Annual ACM Symposium on Theory of Computing, vol. Part F129722, Association for Computing Machinery, pp. 241-251, 24th Annual ACM Symposium on Theory of Computing, STOC 1992, Victoria, Canada, 5/4/92. https://doi.org/10.1145/129712.129736

The complexity of multiway cuts. / Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H. et al.
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992. Association for Computing Machinery, 1992. p. 241-251 (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F129722).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

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 -

The complexity of multiway cuts

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this