Finding maximum edge-disjoint paths between multiple terminals

Let G = (V, E) be a multigraph with a set T \subseteq V of terminals. A path in G is called a T-path if its ends are distinct vertices in T and no internal vertices belong to T. In 1978, Mader showed a characterization of the maximum number of edge-disjoint T-paths. In this paper, we provide a combinatorial, deterministic algorithm for finding the maximum number of edge-disjoint T-paths. The algorithm adopts an augmenting path approach. More specifically, we utilize a new concept of short augmenting walks in auxiliary labeled graphs to capture a possible augmentation of the number of edge-disjoint T-paths. To design a search procedure for a short augmenting walk, we introduce blossoms analogously to the matching algorithm of Edmonds [Canad. J. Math., 17, 1965, pp. 449--467]. When the search procedure terminates without finding a short augmenting walk, the algorithm provides a certificate for the optimality of the current edge-disjoint T-paths. From this certificate, one can obtain the Edmonds-Gallai type decomposition introduced by SeboH \ and SzegoH \ [Proceedings of the Tenth International Conference on Integer Programming and Combinatorial Optimization, LNCS 3064, Springer, Berlin, 2004, pp. 256--270]. The algorithm runs in O(1E12) time, which is much faster than the best known deterministic algorithm based on a reduction to linear matroid parity. We also present a strongly polynomial algorithm for the maximum integer free multiflow problem, which asks for a nonnegative integer combination of T-paths maximizing the sum of the coefficients subject to capacity constraints on the edges.