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: S. CHOPRA AND M. R. RAO, "On the multiway cut polyhedron," Networks 21 (1991), 51-89.
• 2: W. H. CUNN#GHAM, "The optimal multiterminal cut problem," DIMACS Series in Disc. Math. and Theor. Comput. Sci. 5 (1991), 105-120.
• 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: P. L. # AND L. A. SZEKELY, "Evolutionary trees: An integer multicommodity max-flow rain-cut theorem," Adv./n Appl. Math., to appear.
• 5: P. L. ERI3# AND L. A. SZEKELY, "On weighted multiway cuts," unpublished manuscript (1991).
• 6: L. R. FORD, JR, AND D. R. FULKERSON, Flows in Networks, Princeton University Press, princeton, NJ, 1962.
• 7: Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: M. R. GAREY, D. S. JOHNSON, AND L. STOCKMEYER, "Some simplified NP-complete graph problems," Theor. Comput. $ci. 2 (1976), 237-267.
• 10: Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
• 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: M. GR'brscHEL, L. Lov#,sz, AND A. SCHRIJVER, "The ellipsoid method and its consequences in combinatorial optimization," Combinatorica 1 (1981), 169-198.
• 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: T. C. Hu, integer Programming and Network Flows, Addison-Wesley Publishing Co., Reading, MA, 1969.
• 15: E. L. LAWLER, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.
• 16: D. LI#STEIN, "Planar formulae and their uses," SIAM J. ConqTut. 11 (1982), 329-343.
• 17: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 18: C. H. PAPADIMrmIOU AND M. YnnNAKAKIS, "Optimization, approximation, and complexity classes," J. Comput. System Sci. 43 (1991), 425-440.
• 19: Huzur Saran , Vijay V. Vazirani, Finding k-cuts within twice the optimal, Proceedings of the 32nd annual symposium on Foundations of computer science, p.743-751, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185443]
• 20: H. S. STONE, "Multiproeessor scheduling with the aid of network flow algorithms," IEEE Trans. Software Engineering SE-3 (1977), 85-93.
• 21: Mihalis Yannakakis , Paris C. Kanellakis , Stavros S. Cosmadakis , Christos H. Papadimitriou, Cutting and Partitioning a Graph aifter a Fixed Pattern (Extended Abstract), Proceedings of the 10th Colloquium on Automata, Languages and Programming, p.712-722, July 18-22, 1983

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Performance, Theory