|
 
|
[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,
motcle:
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
BibTeX
| @inproceedings { | |||
| COS02, | |||
| 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}", | |
| year | = | 2002, | |
| month | = | "January", | |
| note | = | "{Rapport CEDRIC}", | |
| } | |||
