General vertex disjoint paths in series-parallel graphs
The vertex disjoint path problem is NP-complete even for planar graphs. Robertson and Seymour proved that this problem becomes polynomial when the number of paths is a fixed integer. A linear time algorithm for solving the decision version of the general problem when the input graph is a series-parallel graph is presented.
scientific article; zbMATH DE number 166470
scientific article