68Q25 Analysis of algorithms and problem complexity [See also 68W40]
Refine
Year of publication
Document Type
- ZIB-Report (16)
- Habilitation (1)
- Master's Thesis (1)
Has Fulltext
- yes (18)
Is part of the Bibliography
- no (18)
Keywords
- computational complexity (3)
- NP-completeness (2)
- approximation (2)
- approximation algorithm (2)
- contraction degeneracy (2)
- online algorithms (2)
- polynomial-time approximation algorithms (2)
- stacker-crane problem (2)
- treewidth lower bounds (2)
- Approximation (1)
- Approximation Algorithms (1)
- Call Admission (1)
- Colorability (1)
- Competitive Analysis (1)
- Computational Complexity (1)
- Dial-a-Ride problem (1)
- Dial-a-Ride problem on trees (1)
- Dimensionierung (1)
- Eulerian Cycle (1)
- IGNORE strategy (1)
- Inverse Shortest Paths (1)
- Komplexität (1)
- Komplexitätstheorie (1)
- Mehrfachausfälle (1)
- NP-hardness (1)
- Network (1)
- Netzplanung (1)
- Optical Networks (1)
- P=NP (1)
- Ramachandramurthi parameter (1)
- Routing and Wavelength Allocation (1)
- Shortest Path Routing (1)
- Shortest path routing (1)
- Spaltengenerierung (1)
- budgeted maximum coverage (1)
- column generation (1)
- competitive analysis (1)
- completeness (1)
- complexity (1)
- disjoint paths (1)
- dynamic programming (1)
- elevator system (1)
- genus of a graph (1)
- graph algorithms (1)
- length bounded paths (1)
- lower bounds (1)
- maximum cardinality search (1)
- online algorithm (1)
- online optimization (1)
- planar graphs (1)
- pricing (1)
- probabilistic analysis (1)
- probabilistic competitive analysis (1)
- reducibility (1)
- routing (1)
- shortest path routing (1)
- survivable network design (1)
- treewidth (1)
- unsplittable flow (1)
- vehicle (1)
- vehicle routing (1)
Institute
- ZIB Allgemein (15)
- Mathematical Optimization (4)
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.