The Disjoint-paths Problem

[network with demands]

Network platform
with demands
[enlarged] [eps]
[embedded demands]

Optimal realization
as pairwise
node-disjoint paths
[enlarged] [eps]


Given a graph G and a collection T={(s1,t1)... (sk,tk)} 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 si-- ti 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 (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 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 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 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.

Last Updated: 5/4/03                                                                              For any question or suggestion, click here to contact with us.