Complexity of multiterminal cuts

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

doi:10.1137/S0097539792225297

Complexity of multiterminal cuts

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

Research output: Contribution to journal › Article › peer-review

433 Scopus citations

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 guaranteed to come within a factor of 2 - 2/k of the optimal cut weight is also described.

Original language	English (US)
Pages (from-to)	864-894
Number of pages	31
Journal	SIAM Journal on Computing
Volume	23
Issue number	4
DOIs	https://doi.org/10.1137/S0097539792225297
State	Published - 1994
Externally published	Yes

All Science Journal Classification (ASJC) codes

Computer Science(all)
Mathematics(all)

Access to Document

10.1137/S0097539792225297

Fingerprint Dive into the research topics of 'Complexity of multiterminal cuts'. Together they form a unique fingerprint.

Cite this

@article{4ca23cc1746b4df3b418749e2ad818cc,

title = "Complexity of multiterminal cuts",

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 guaranteed to come within a factor of 2 - 2/k of the optimal cut weight is also described.",

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

year = "1994",

doi = "10.1137/S0097539792225297",

language = "English (US)",

volume = "23",

pages = "864--894",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

TY - JOUR

T1 - Complexity of multiterminal cuts

AU - Dahlhaus, E.

AU - Johnson, D. S.

AU - Papadimitriou, C. H.

AU - Seymour, P. D.

AU - Yannakakis, M.

PY - 1994

Y1 - 1994

N2 - 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 guaranteed to come within a factor of 2 - 2/k of the optimal cut weight is also described.

AB - 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 guaranteed to come within a factor of 2 - 2/k of the optimal cut weight is also described.

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

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

U2 - 10.1137/S0097539792225297

DO - 10.1137/S0097539792225297

M3 - Article

AN - SCOPUS:0028484228

VL - 23

SP - 864

EP - 894

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 4

ER -