Abstract: We consider the k edge-disjoint paths problem (k-EDP), a generalization of the well known edge-disjoint paths problem. Given a graph G=(V,E) and a set of terminal pairs (or requests) T, the problem is to find a maximum subset of the pairs in T for which it is possible to select paths such that each pair is connected by k edge-disjoint paths and the paths for different pairs are mutually disjoint. To the best of our knowledge, no nontrivial result is known for this problem for k>1. To measure the performance of our algorithms we use the recently introduced flow number F of a graph. This parameter is known to fulfill F=O(Delta alpha-1 log n), where Delta is the maximum degree and alpha is the edge expansion of G. We show that a simple, greedy online algorithm achieves a competitive ratio of O(k3 F), which naturally extends the best known bound of O(F) for k=1 to higher k. To achieve this competitive ratio, we introduce a new method of converting a system of k disjoint paths into a system of k length-bounded disjoint paths.
In addition, we study the k disjoint flows problem (k-DFP), which is a generalization of the previously studied unsplittable flow problem (UFP). The difference between the k-DFP and the k-EDP is that now we consider a graph with edge capacities and our requests are allowed to have arbitrary demands di. The aim is to find a subset of requests of maximum total demand for which it is possible to select flow paths such that all the capacity constraints are maintained and each selected request with demand di is connected by k disjoint paths, each of flow value di/k.
This talk is based on work done jointly with Amitabh Chaudhary, Christian Scheideler and Petr Kolman.