In this talk we consider the \(k\) edge-disjoint paths problem (\(k\)-EDP), which is 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 disjoint paths so that each pair is connected by \(k\) edge disjoint paths. To the best of our knowledge, nothing nontrivial is known for this problem so far for \(k>1\). In order to measure the performance of our algorithms we will use the routing number of the graph, R. This parameter is known to fulfill \(R=O(\alpha^{-1} \log n)\), where \(\Delta\) is the maximum degree and \(\alpha\) is the edge expansion of \(G\). We show with the help of a simple, greedy online algorithm that it is possible to achieve a competitive ratio of \(O(k^3.\Delta.R)\). In order to achieve this competitive ratio, we introduce a new method to convert a system of \(k\) disjoint paths into a system of \(k\) short disjoint paths. We also show that our class of online algorithms have a competitive ratio of \(\Omega(k.R)\).
In addition, we study the \(k\) disjoint flows problem (\(k\)-DFP), which is a generalization of the well-known unsplittable flow problem (UFP): the \(k\)-DFP is similar to the \(k\)-EDP with the difference that now the graph has edge capacities and the requests can have arbitrary demands \(d_i\). The aim is to find a subset of requests of maximum total demand for which it is possible to select flow paths so that all the capacity constraints are kept and each selected request with demand \(d_i\) is connected by \(k\) disjoint paths of flow value \(d_i/k\).
The \(k\)-EDP and \(k\)-DFP problems have important applications in fault-tolerant (virtual) circuit switching, which plays an important role in optical networks.
This talk is based on work done jointly with Christian Scheideler and Amitabh Chaudhary of Johns Hopkins University and Petr Kolman of Charles University.