Inverse $$k$$ k -centrum problem on trees with variable vertex weights

This paper considers a generalization of the inverse 1-median problem, the inverse $$k$$ k -centrum problem, on trees with variable vertex weights. In contrast to the linear time solvability of the inverse 1-median problem on trees, we prove that the inverse $$k$$ k -centrum problem on trees is $$\textit{NP}$$ NP -hard. Particularly, the inverse 1-center problem, a special case of the mentioned problem with $$k=1$$ k = 1 , on a tree with $$n$$ n vertices can be solved in $$O(n^{2})$$ O ( n 2 ) time. Copyright Springer-Verlag Berlin Heidelberg 2015