The complexity of an inverse shortest paths problem
Sándor Fekete, Winfried Hochstättler, S. Kromberg, Christoph Moll · DIMACS series in discrete mathematics and theoretical computer science · 1999
In this paper we study the complexity of an Inverse Shortest Paths Problem (ISPP). We show that the problem is intractable even in very restricted cases. In particular, we prove that the ISPP is NP-complete in the planar case. Furthermore, we give a characterization of the class of graphs G d of given distances for which the ISPP is tractable: we give polynomial algorithms for special classes of G d and provide evidence that no polynomial time algorithms exist if the structure of G d is only slightly more complicated in a well-defined graph-theoretical sense. Finally, we discuss the situation for directed graphs.