ZIB PaperWeb

On the Complexity of Vertex-Disjoint Length-Restricted Path Problems

SC 98-20 Andreas Bley: On the Complexity of Vertex-Disjoint Length-Restricted Path Problems

Abstract: Let G=(V,E) be a simple graph and s and t be two distinct vertices of G. A path in G is called $\ell$-bounded for some $\ell\in\mathbb{N}$, if it does not contain more than $\ell$ edges. We study the computational complexity of approximating the optimum value for two optimization problems of finding sets of vertex-disjoint $\ell$-bounded s,t-paths in G.
First, we show that computing the maximum number of vertex-disjoint $\ell$-bounded s,t-paths is $\mathcal{AP\kern-1pt X}$-complete for any fixed length bound $\ell\geq 5$.
Second, for a given number $k\in\mathbb{N}$, $1\leq k \leq \vert V\vert-1$, and non-negative weights on the edges of G, the problem of finding k vertex-disjoint $\ell$-bounded s,t-paths with minimal total weight is proven to be $\mathcal{NPO}$-complete for any length bound $\ell\geq 5$.Furthermore, we show that, even if G is complete, it is $\mathcal{NP}$-complete to approximate the optimal solution value of this problem within a factor of $2^{\langle\phi\rangle^\epsilon}$ for any constant $0<\epsilon<1$, where $\langle\phi\rangle$ denotes the encoding size of the given problem instance $\phi$.
We prove that these results are tight in the sense that for lengths $\ell\leq 4$ both problems are polynomially solvable, assuming that the weights satisfy a generalized triangle inequality in the weighted problem.
All results presented also hold for directed and non-simple graphs. For the analogous problems where the path length restriction is replaced by the condition that all paths must have length equal to $\ell$ or where vertex-disjointness is replaced by edge-disjointness we obtain similar results.
Keywords: disjoint paths, length bounded paths, approximation, reducibility, completeness
MSC: 68Q25, 90C27, 05C38, 05C40