Efficient algorithms for the reverse shortest path problem on trees under the hamming distance

In this paper, we consider two special cases of this problem which are polynomially solvable. The first is the case with uniform lengths. It is shown that this case transforms to a minimum cost flow problem on an auxiliary network. | Yugoslav Journal of Operations Research 27 (2017), Number 1, 46–60 DOI: EFFICIENT ALGORITHMS FOR THE REVERSE SHORTEST PATH PROBLEM ON TREES UNDER THE HAMMING DISTANCE Javad TAYYEBI* Department of Industrial Engineering, Birjand University of Technology, Birjand, Iran javadtayyebi@, javadtayyebi@ Massoud AMAN Department of Mathematics, Faculty of Mathematical Sciences and Statistic, University of Birjand, Birjand, Iran mamann@ Received: June 2015 / Accepted: May 2016 Abstract: Given a network G(V, A, c) and a collection of origin-destination pairs with prescribed values, the reverse shortest path problem is to modify the arc length vector c as little as possible under some bound constraints such that the shortest distance between each origin-destination pair is upper bounded by the corresponding prescribed value. It is known that the reverse shortest path problem is NP-hard even on trees when the arc length modifications are measured by the weighted sum-type Hamming distance. In this paper, we consider two special cases of this problem which are polynomially solvable. The first is the case with uniform lengths. It is shown that this case transforms to a minimum cost flow problem on an auxiliary network. An efficient algorithm is also proposed for solving this case under the unit sum-type Hamming distance. The second case considered is the problem without bound constraints. It is shown that this case is reduced to a minimum cut problem on a tree-like network. Therefore, both cases studied can be solved in strongly polynomial time. Keywords: Inverse problems, Shortest path problem, Hamming distance, Combinatorial algorithms. MSC: 90C27, 90C35, 05C85. * Corresponding author J. Tayyebi, M. Aman / Efficient Algorithms for the Reverse Shortest Path Problem 47 1. INTRODUCTION Suppose that G(V, A, c) is a directed and connected network where V is the set of nodes, A is the set of arcs and c is the .