The complexity of multiway cuts (extended abstract)

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 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. We also describe a simple approximation algorithm for arbitrary graphs that is guaranteed to come within a factor of 2–2/k of the optimal cut weight.

References

1. 1.S. CHOPRA AND M. R. RAO, "On the multiway cut polyhedron," Networks 21 (1991), 51-89.
2. 2.W. H. CUNN#GHAM, "The optimal multiterminal cut problem," DIMACS Series in Disc. Math. and Theor. Comput. Sci. 5 (1991), 105-120.
3. 3.E. DAm.HAUS, D. S. JOHNSON, C. H. PAPAOIMn#OU, P. D. SEYMOUR, AND M. YANNAKAglS, "The complexity of multiway cuts," extended abstract (1983).
4. 4.P. L. # AND L. A. SZEKELY, "Evolutionary trees: An integer multicommodity max-flow rain-cut theorem," Adv./n Appl. Math., to appear.
5. 5.P. L. ERI3# AND L. A. SZEKELY, "On weighted multiway cuts," unpublished manuscript (1991).
6. 6.L. R. FORD, JR, AND D. R. FULKERSON, Flows in Networks, Princeton University Press, princeton, NJ, 1962.
7. 7.G. N. FREDERICKSON, "Fast algorithms for shortest paths in planar graphs, with applications," SIAM J. Comput. 16 (1987), 1004-1022.
8. 8.M. R. GAREY AND D. S. JOHNSON, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, New York, 1979.
9. 9.M. R. GAREY, D. S. JOHNSON, AND L. STOCKMEYER, "Some simplified NP-complete graph problems," Theor. Comput. $ci. 2 (1976), 237-267.
10. 10.A. V. GOLDBERG AND R. E. TARJAN, "A new approach to the maximum-flow problem," J. Assoc. Comput. Mach. 35 (1988), 921-940.
11. 11.O. GOLDSCHMmT AND D. S. HOCI#AUM, "Polynomial algorithm for the k-cut problem," in "proceedings 29th Ann. Symp. on Foundations of Computer Science," IEEE Computer Society, Los Angeles, Calif., 1988, 't.'t.'t.-451.
12. 12.M. GR'brscHEL, L. Lov#,sz, AND A. SCHRIJVER, "The ellipsoid method and its consequences in combinatorial optimization," Combinatorica 1 (1981), 169-198.
13. 13.D. S. HOClmAUM AND D. B. SHMOYS, "An o<lvIm) algorithm for the planar 3-cut problem," SIAM J. Algebraic and Discrete Methods 6 (1985), 707-712.
14. 14.T. C. Hu, integer Programming and Network Flows, Addison-Wesley Publishing Co., Reading, MA, 1969.
15. 15.E. L. LAWLER, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.
16. 16.D. LI#STEIN, "Planar formulae and their uses," SIAM J. ConqTut. 11 (1982), 329-343.
17. 17.C. H. PAPADIMn'mOU AND K. STEIGIffl2, Combinatorial Optimization: Algorithms and Complexity, prentice-Hall, Inc., Englewood Cliffs, NJ, 1982.
18. 18.C. H. PAPADIMrmIOU AND M. YnnNAKAKIS, "Optimization, approximation, and complexity classes," J. Comput. System Sci. 43 (1991), 425-440.
19. 19.H. SARAN AND V. V. VAZIRANI, "Finding k-cuts within twice the optimal," in "Proceedings 32nd Ann. Syrup. on Foundations of Computer Science," IEEE Computer Society, Los Angeles, Calif., 1991, 743-751.
20. 20.H. S. STONE, "Multiproeessor scheduling with the aid of network flow algorithms," IEEE Trans. Software Engineering SE-3 (1977), 85-93.
21. 21.M. YANNAKA#S, P. C. KANELLAKIS, S. C. COSMADAKIS, AND C. H. PAPADIMrFRIOU, "Cutting and partitioning a graph after a fixed pattern," in "Automata, Languages, and Programming," Lecture Notes in Computer Science, Vol. 154, Springer, Berlin, 1983, 712-722.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

• Theory of computation

  • Computational complexity and cryptography

    • Complexity classes