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 (EDP). 

(Pictures get from the Combinatorial Optimization & Graph Algorithms group site at the Technischen Universität Berlin. See their work at www.math.tuberlin.de/coga/research/routing/disjointrouting)  
Applications and interests:The EDP 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 EDP 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 EDP problem was proposed in [BB04]. The same authors are currently working on a more sophisticated version of the algorithm that is achieving better results and that enlarges the set of benchmark instances with some graphs that exemplify Internet topologies. 

Related Papers:[BB04] M. Blesa and C. Blum. Ant colony optimization for the maximum edgedisjoint paths problem. In Raidl et al., editor, 1st European Workshop on Evolutionary Computation in Communications, Networks, and Connected Systems (EvoCOMNET'04), in Applications of Evolutionary Computing (EvoWorkshops'04), volume 3005 of Lecture Notes in Computer Science, pages 160169, Coimbra, Portugal, April 2004. SpringerVerlag Heidelberg.
[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. 
