On the complexity of vertex-disjoint length-restricted path problems

Let G = (V; E) be a simple graph and s and t be two distinct vertices of G. A path in G is called l-bounded for some l is an element of N if it does not contain more than l edges. We prove that computing the maximum number of vertex-disjoint l-bounded s; t-paths is APX-complete for any l greater than or equal to 5. This implies that the problem of finding k vertex-disjoint l-bounded s; t-paths with minimal total weight for a given number k is an element of N, 1 less than or equal to k \V\ - 1, and nonnegative weights on the edges of G is NPO-complete for any length bound l greater than or equal to 5. Furthermore, we show that these results are tight in the sense that for l less than or equal to 4 both problems are polynomially solvable, assuming that the weights satisfy a generalized triangle inequality in the weighted problem. Similar results are obtained for the analogous problems with path lengths equal to l instead of at most l and with edge-disjointness instead of vertex-disjointness.