Some Polynomially Solvable Cases of the Inverse Ordered 1-Median Problem on Trees

Abstract

We consider the problem of modifying the edge lengths of a tree in minimum cost such that a prespecified vertex become an ordered 1-median of the perturbed tree. We call this problem the inverse ordered 1-median problem on trees. Gassner showed in 2012 that the inverse ordered 1-median problem on trees is, in general, NP-hard. We however address some situations, where the corresponding inverse 1-median problem is polynomially solvable. For the problem on paths with n vertices, we develop an O(n^3 ) algorithm based on a greedy technique. Furthermore, we prove the NP-hardness of the inverse ordered 1-median problem on star graphs and propose a quadratic algorithm that solves the inverse ordered 1-median problem on unweighted stars.