Disjoint Paths in Graphs

We consider the well-known edge-disjoint path problem (EDP) where we are given a graph G and pairs of nodes (“demands”) s1t1, s2t2, . . . sktk. A subset F of {1, 2, . . . , k} is routable if there exists |F| edge-disjoint paths in G that connect the pairs siti for each i 2 F. We analyze the problem of finding a maximum (weight) routable subset F. The situation where G is a tree already includes several classical combinatorial optimization problems such as the knapsack and b-matching problems. We discuss what is known for this problem in the three cases where G is a tree, a planar graph, or a general graph. Several open problems will arise en-route.