The inverse p‐median problem with variable edge lengths on graphs is to modify the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified set of p vertices becomes a p‐median with respect to the new edge lengths. The problem is shown to be strongly NP‐hard on general graphs and weakly NP‐hard on series‐parallel graphs. Therefore, the special case on a tree is considered: It is shown that the inverse 2‐median problem with variable edge lengths on trees is solvable in polynomial time. For the special case of a star graph we suggest a linear time algorithm.
