Description
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 by a nonconstructive proof.
We provide an augmenting type algorithm for finding a maximum number of edge-disjoint T-paths.
We introduce a novel concept of 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 an augmenting walk, we introduce
blossoms analogously to the matching algorithm of Edmonds (1965), while it is neither a special case nor
a generalization of the present problem. The algorithm runs in $O(|V|\cdot |E|^2)$ time, which is substantially faster
than the best known deterministic algorithm based on a reduction to the linear matroid parity problem.
We also extend our algorithm to the integer free multiflow problem.
(joint work with Satoru Iwata)