[COS02] Polynomial algorithms to solve the multiway cut and integer flow problems in trees

Conférence Internationale avec comité de lecture : CO'02 Combinatorial Optimization Paris, 8-10 avril and ECCO, Lugano, January 2002,

Auteurs: M.-C. Costa

Résumé: Consider a graph G=(V,E) with n vertices, m edges and a positive weight (or capacity) on each edge. Let X be a set of vertices in V called terminals. The multiterminal (or multiway) cut problem is to find a minimum weight set of edges that disconnects each pair of terminals. The multiterminal cut problem is a special case of the multicut problem where one wants to separate K given pairs of vertices. Let us recall the duality relationship linking both multicut and multicommodity flow problems and then associate a commodity with each vertex pair in X. Now we consider the multiterminal flow problem associated to the multiterminal cut problem: it consists in maximizing the total amount of flow routed between any pair of nodes in X. The multicut and integer multiflow problems are polynomial in directed trees but are NP-hard in undirected trees. On the other hand, the muliterminal cut problem, which is NP-hard for K>2 in unrestricted graphs becomes polynomial if the graph is a tree. P.L. Erdos and L.A. Szekely proposed an O(n2)algorithm to solve the problem in undirected trees. In fact their algorithm solves a more general problem which is to separate r disjoint subsets of vertices. Here, we present a procedure in O(n) to solve the multiterminal cut problem in undirected trees and a procedure in O(n2) to solve the multiterminal flow problem in undirected trees and we show that most often there exists a duality gap between the optimal integer multiterminal cut and flow values. Both algorithms are independant but their general schemes are similar: we first solve the problems on trees of height 1, i.e. stars. Then we consider a star connected to the tree by an only edge; we give a sub-solution on this star and reduce the tree before applying the same method recursively until we obtain a lonely star. Bibliography Costa M-C., Letocart L. and Roupin F. (2001) Multicut and integral multiflow duality. A polynomial algorithm in rooted trees. JOPT'01, Quebec, Canada. CEDRIC report 102. Costa M-C., Letocart L. and Roupin F. (2001) Minimal multicut and maximal integer muliflow: a survey. ECCO'01, Bonn, Germany. CEDRIC report. Dalhaus E., Johnson D.S., Papadimitriou C.H., Seymour P.D. and Yannakakis M. (1994) The complexity of multiway cuts. SIAM J. Comput. 23, 864-894. Erdos P. and Szekely L.A. (1994) On weighted multiway cuts in trees. Math. Programming 65, 93-105. Garg N., Vazirani V.V. and Yannakakis M. (1996) Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. Comput. 25,2, 235-251. Garg N., Vazirani V.V. and Yannakakis M. (1997) Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18, 3-20.

Commentaires: Rapport CEDRIC


@inproceedings {
title="{Polynomial algorithms to solve the multiway cut and integer flow problems in trees}",
author=" M.-C. Costa ",
booktitle="{CO'02 Combinatorial Optimization Paris, 8-10 avril and ECCO, Lugano}",
note="{Rapport CEDRIC}",