1865. Precedence-constrained shortest path
Invited abstract in session WB-20: Complexity and Approximation, stream Combinatorial Optimization.
Wednesday, 10:30-12:00Room: Esther Simpson 2.11
Authors (first author is the speaker)
| 1. | Corinna Mathwieser
|
| RWTH Aachen University | |
| 2. | Christina Büsing
|
| Lehr- und Forschungsgebiet Kombinatorische Optimierung, RWTH Aachen University |
Abstract
We study a variation of the shortest path problem in which the sequence of visited vertices must satisfy precedence constraints. The problem generalizes Graphic TSP Path, making it APX-hard.
We discuss the complexity of finding a feasible precedence-constrained path between two vertices and compare different variants of defining precedence-constraints in shortest paths. We propose a dynamic programming approach and identify specific input classes where the dynamic program provides an optimal solution in polynomial time. Furthermore, we analyse the problem’s computational limits by demonstrating that it remains hard even under structural restrictions. Surprisingly, we prove that the problem is NP-hard even when the graph is constrained to spiders.
Keywords
- Algorithms
- Complexity and Approximation
- Combinatorial Optimization
Status: accepted
Back to the list of papers