The computational complexity of the relative robust shortest path problem with interval data

The paper deals with the relative robust shortest path problem in a directed arc weighted graph, where arc lengths are specified as intervals containing possible realizations of arc lengths. The complexity status of this problem has been unknown in the literature. We show that the problem is NP-hard. (C) 2003 Elsevier B.V. All rights reserved.