Free multiflows in bidirected and skew-symmetric graphs

A graph (digraph) G=(V,E) with a set T⊆V of terminals is called inner Eulerian if each nonterminal node v has even degree (resp. the numbers of edges entering and leaving v are equal). Cherkassky and Lovász, independently, showed that the maximum number of pairwise edge-disjoint T-paths in an inner Eulerian graph G is equal to , where λ(s) is the minimum number of edges whose removal disconnects s and T-{s}. A similar relation for inner Eulerian digraphs was established by Lomonosov. Considering undirected and directed networks with “inner Eulerian” edge capacities, Ibaraki, Karzanov, and Nagamochi showed that the problem of finding a maximum integer multiflow (where partial flows connect arbitrary pairs of distinct terminals) is reduced to O(logT) maximum flow computations and to a number of flow decompositions.In this paper we extend the above max-min relation to inner Eulerian bidirected graphs and inner Eulerian skew-symmetric graphs and develop an algorithm of complexity for the corresponding capacitated cases. In particular, this improves the best known bound for digraphs. Our algorithm uses a fast procedure for decomposing a flow with O(1) sources and sinks in a digraph into the sum of one-source-one-sink flows.