Precedence‐Constrained Shortest Path

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.