The Disjointpaths Problem

Network platform with demands [enlarged] [eps] 
Optimal realization as pairwise nodedisjoint paths [enlarged] [eps] 
Description:Given a graph G and a collection T={(s_{1},t_{1})... (s_{k},t_{k})} of pairs of vertices in G (the requests or commodities), the Disjointpaths Problem consist of determining whether the pairs of vertices in T can be linked in G by vertex (or edge) disjoint s_{i} t_{i} paths. In both cases (edge and vertex disjointness), deciding wheter the pairs can be disjointedly connected is NPcomplete ([Kar72,MP93,Vyg95]). We will care about its optimization version, which consists of finding a maximum number of pairs in T that can be disjointedly connected in G. We will denote optimization version as the Maximum Disjointpaths Problem (MDP). 

(Pictures get from the Combinatorial Optimization & Graph Algorithms group site at the Technischen Universität Berlin)  
Applications and interests:The MDP is interesting from several different view points, including combinatorial optimization, algorithmic graph theory and operations research. This problem has a multitude of applications in areas such as realtime communications, VLSI design, scheduling, bin packing, load balancing, and it has been brought into focus recently in papers discussing applications to routing and admission control in modern networks, namely largescale, highspeed and optical networks, where much of the difficulty in establishing virtual circuits comes from a lack of understanding the problem and the lack of good heuristics for finding disjoint paths. Greedylike algorithms are commonly used for routing applications, despite their bad performance on a number of very common interconnection patterns. The MDP problem is also related to general information dissemination in networks (e.g., broadcasting and multicasting). In this case, it is especially desirable to establish more than one disjoint path between each pair of vertices. Multiple disjoint paths can increase the effective bandwidth between pairs of nodes, reduce congestion in the network and increase the probability of receiving the information. Furthermore, the most efficient way of transmitting information consisting of a high volume of data (e.g., multimedia applications) is achieved by maintaining, during the whole duration of the connection, disjoint paths of exclusive dedication. With the aim of keeping the computation overhead low, disjoint paths should be efficiently constructed. 

Instances and best known solutions for those instances:The first set of benchmark instances available for the MDP problem are those proposed in [BB03]. 

Related Papers:[BB03] M. Blesa and C. Blum. Ant Colony Optimization for the maximum disjoint paths problem. Manuscript in preparation, 2003. [Kar72] R. Karp. Complexity of Computer Computations, chapter Reducibility among combinatorial problems, pages 85103. R.E. Miller and J.W.Thatcher (Eds.). Plenum Press, New York, 1972. [Kle96] J.Kleinberg. Approximation algorithms for disjoint paths problems. PhD Thesis, MIT, Cambridge, USA, May 1996. [MP93] M.Middendorf and F.Pfeiffer. On the complexity of the disjoint paths problem. Combinatorica, 13:97107, 1993. [Vyg95] J.Vygen. NPcompleteness of some edgedisjoint paths problems. Discrete Applied Mathematics, 61:8390, 1995. Click here to get the bibliography in bibtex fotmat. 
