A linear time algorithm for linearizing quadratic and higher-order shortest path problems

Mathematical Programming, vol. 210, pp. 165–188

Abstract

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.

Authors 5

1. Eranda Çela

   Graz University of Technology

   Affiliation as printed

   Institute of Discrete Mathematics, Graz University of Technology, Graz, Austria

2. Bettina Klinz

   Graz University of Technology

   Affiliation as printed

   Institute of Discrete Mathematics, Graz University of Technology, Graz, Austria

3. Stefan Lendl

   University of Graz

   Affiliation as printed

   Institut of Operations and Information Systems, University of Graz, Graz, Austria

4. Gerhard J. Woeginger Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen, Aachen, Germany

5. Lasse Wulf corresponding

   Graz University of Technology

   Affiliation as printed

   Institute of Discrete Mathematics, Graz University of Technology, Graz, Austria