Let G=(V,E) be an undirected graph and let (si,ti), 1•i•k be k pairs of vertices in G. The vertex disjoint paths problem is to find k paths P1,...,Pk such that Pi connects si and ti and any two of these paths may intersect only at a common endpoint. This problem is NP-complete even for planar graphs. Robertson and Seymour proved that when k is a fixed integer this problem becomes polynomial. The authors present a linear time algorithm for solving the decision version of the general problem when the input graph is a series-parallel graph.
