Inverse p-median problems with variable edge lengths

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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$${\mathcal{NP}}$$</EquationSource> </InlineEquation>-hard on general graphs and weakly <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$${\mathcal{NP}}$$</EquationSource> </InlineEquation>-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. Copyright Springer-Verlag 2011