Algorithms for multiflows



Gyula Pap
Cornell University, Department of Computer Science

Monday  September 29, 2008
4:00 PM, 5130 Upson Hall



One of my favorite areas in classical combinatorial optimization is that of multiflows. Given an undirected graph G=(V,E), and a set of terminals A contained in V, a multiflow is defined as a set of flows between all pairs of distinct terminals. The goal is to maximize the size of the multiflow, that is the sum of the size of all the |A|(|A|-1)/2 flows, subject to certain capacity constraints. Variations of the problem arise from edge- or node-capacities, and/or a (half-)integrality constraint. The problem is interesting even for the special case of all-one node capacities, which is characterized by Mader's min-max 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 node-capacities (the most general of all these variations). This improves on a result of Ibaraki, Karzanov and Nagamochi for the edge-capacitated, half-integral version, and on Keijsper, Pendavingh and Stougie's weakly polynomial time algorithm for the edge-capacitated, integral version. A weakly polynomial time algorithm is given in my STOC 2007 paper, which uses Lovász' algorithm to construct an augmentation algorithm, and a scaling-type argument motivated by Gerards' proximity lemma for b-matching. To improve this algorithm to strongly polynomial, one has to solve the half-integral version. Note that the LP always has a half-integral optimum, thus it looks like one could find a half-integral optimum by solving the LP, which may be done in strongly polynomial time by Frank and Tardos's diophantine approximation technique. This idea, however, doesn't work out: an example shows that an extremal optimum solution for the LP is not always half-integral, thus our goal of finding a half-integral optimum requires more than just solving the LP. The proposed algorithm, nevertheless, is based on the LP, but to make sure we get a half-integral solution, we grow certain regions around the terminals, and then apply a b-matching algorithm.

I worked on this area as a member of the Egerváry Research Group "EGRES" in Budapest.