The Disjoint-paths Problem

Description:

Given a graph G and a collection T={(s₁,t₁)... (s_k,t_k)} of pairs of vertices in G (the requests or commodities), the Disjoint-paths 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 NP-complete ([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 Disjoint-paths Problem (EDP).

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 real-time 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 large-scale, high-speed 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. Greedy-like 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 edge-disjoint 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 160-169, Coimbra, Portugal, April 2004. Springer-Verlag Heidelberg.

[Kar72] R. Karp. Complexity of Computer Computations, chapter Reducibility among combinatorial problems, pages 85-103. 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:97-107, 1993.

[Vyg95] J.Vygen. NP-completeness of some edge-disjoint paths problems. Discrete Applied Mathematics, 61:83-90, 1995.

Click here to get the bibliography in bibtex fotmat.