Publication Date:
2014-02-26
Description:
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 |V|-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:
ddc:000
Language:
English
Type:
reportzib
,
doc-type:preprint
Format:
application/postscript
Format:
application/pdf
Permalink
