Precedence‐Constrained Shortest Path

Networks, vol. 86, pp. 282–295

Abstract

ABSTRACT We propose a variant of the shortest path problem where the order in which vertices occur in the path is subject to precedence constraints. Precedence constraints are defined in terms of vertex pairs which indicate that a vertex is the predecessor of a vertex . A feasible (not necessarily simple) path may visit a vertex only upon having covered all its predecessors. The problem generalizes the graphic TSP Path, which makes it APX‐hard. We propose a dynamic program and identify input classes for which the dynamic program yields an optimal solution in polynomial time. We also explore the limits of efficient solvability by proving that the problem remains hard even when significantly restricting the structure of the graph or the structure of the precedence constraints: Surprisingly, the problem remains hard even when restricted to spiders.

Authors 3

1. Christina Büsing Aachen Lehr‐ und Forschungsgebiet Kombinatorische Optimierung

   RWTH Aachen University

   Affiliation as printed

   Lehr‐ und Forschungsgebiet Kombinatorische Optimierung RWTH Aachen University Aachen Germany

   Lehr- und Forschungsgebiet Kombinatorische Optimierung, RWTH Aachen University, Aachen, Germany

2. Dennis John Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University Aachen Germany

   RWTH Aachen University, Aachen, Germany

3. Corinna Mathwieser corresponding Aachen Lehr‐ und Forschungsgebiet Kombinatorische Optimierung

   RWTH Aachen University

   Affiliation as printed

   Lehr‐ und Forschungsgebiet Kombinatorische Optimierung RWTH Aachen University Aachen Germany

   Lehr- und Forschungsgebiet Kombinatorische Optimierung, RWTH Aachen University, Aachen, Germany