
Discrete Mathematics and Optimization Seminar

Oct. 19th, 2009
Algorithms for integral and halfintegral multiflows
Gyula Pap
Cornell University

A classical problem in combinatorial optimization is that of maximum multiflows. We are given an undirected graph G=(V,E), and a set of terminals A subset of V. A multiflow is defined as a set of A(A1)/2 flows between all pairs of distinct terminals. The goal is to maximize the total size of the multiflow, that is the sum of the size of all the A(A1)/2 flows, subject to certain capacity constraints. Variations of the problem arise from edge or nodecapacities, and/or adding a (half)integrality constraint. The problem is really interesting even for the special case of allone node capacities, which is characterized by Mader's minmax formula, and solved by Lovász' linear matroid matching algorithm. Mader's formula also applies for arbitrary capacities, but matroid matching, in the obvious way of expanding the graph, only implies an exponential time algorithm.
The main result presented in this talk is a strongly polynomial time algorithm to find a maximum integral multiflow subject to nodecapacities (the most general of all these variations). This improves on a result of Ibaraki, Karzanov and Nagamochi for the edgecapacitated, halfintegral version, and on Keijsper, Pendavingh and Stougie's weakly polynomial time algorithm for the edgecapacitated, integral version. These results are generalized to the nodecapacitated version, although using completely different tehniques. The halfintegral nodecapacitated multiflow problem is solved based on a recent result saying that the polytope of shortest maximum multiflows is halfintegral, which implies a strongly polynomial algorithm via ellipsoid method and Frank and Tardos' diophantine approximation. To solve the integral nodecapacitated multiflow problem, we first solve it to halfintegrality, and then use a scalingtype argument motivated by Gerards' proximity lemma for bmatching to reduce the problem to small capacities. In the presentation we will also take a look at related results and techniques, such as a splittingoff algorithm for Lov\'asz' and Cherkassky's result, a divideandconquertype argument for the edgecapacitated version.



