The Complexity of an Inverse Shortest Path Problem

Fekete, Sandor P. and Hochstättler, Winfried and Kromberg, Stephan and Moll, Christoph (1999) The Complexity of an Inverse Shortest Path Problem.
Published In: Contemporary trends in discrete mathematics : from DIMACS and DIMATIA to the future ; DIMATIA-DIMACS conference, May 19 - 25, 1997, Štiřín Castle, Czech Republic ; [contains papers from a DIMATIA/DIMACS Conference on the Future of Discrete Mathematics], DIMACS series in discrete mathematics and theoretical computer science. 49 American Mathematical Society (AMS) 1999, pp. 113-127.


In this paper we study the complexity of an Inverse Shortest Paths Problem (ISPP). We show that this problem is intractable even in very restricted cases. In particular, we prove that this Inverse Shortest Paths Problem is NP-complete in the planar case. Furthermore, we give a characterization of the class of graphs Gd of given distances for which the ISPP is tractable: we give polynomial algorithms for special classes of Gd and provide evidence that no polynomial time algorithms exist if the structure of Gd is only slightly more complicated in a well-defined graph-theoretical sense. Finally, we discuss the situation for directed graphs.

Download: [img] Postscript - Preprinted Version
Download (334kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr96-226
Depositing User: Winfried Hochstättler
Date Deposited: 02 Apr 2001 00:00
Last Modified: 16 Jan 2012 14:26