Short length Menger's theorem and reliable optical routing

The underlying problem is that of finding several disjoint paths between a given pair of vertices. Menger's theorem provides a necessary and sufficient condition for the existence of k such paths. However, it does not say anything about the length of the paths although in communication problems the number of links used is an issue. We show that any two k-connected vertices are connected by k edge disjoint paths of average length O(kF) which improves an earlier result of Galil and Yu (Proceedings of the 27th Annual ACM Symposium on Theory of Computing, 1995) for several classes of graphs. In fact, this is only a corollary of a stronger result for multicommodity flow on networks with unit edge capacities: any multicommodity flow with k units for each commodity can be rerouted such that the flow for each commodity is shipped through k-tuples of edge disjoint paths of average length O(kF) without exceeding the edge capacities significantly.