  An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called
linearizable iff it is equivalent to an instance of the classic Shortest Path
Problem (SPP) on the same input digraph. The linearization problem for the QSPP
(LinQSPP) decides whether a given QSPP instance is linearizable and determines
the corresponding SPP instance in the positive case. We provide a novel linear
time algorithm for the LinQSPP on acyclic digraphs which runs considerably
faster than the previously best algorithm. The algorithm is based on a new
insight revealing that the linearizability of the QSPP for acyclic digraphs can
be seen as a local property. Our approach extends to the more general
higher-order shortest path problem.
