(r,p)-centroid problems on paths and trees

An instance of the (r,p)-centroid problem is given by an edge and node weighted graph. Two competitors, the leader and the follower, are allowed to place p and r facilities, respectively, into the graph. Users at the nodes connect to the closest facility. A solution of the (r,p)-centroid problem is a leader placement such that the maximum total weight of the users connecting to any follower placement is as small as possible.We show that the absolute (r,p)-centroid problem is NP-hard even on a path which answers a long-standing open question of the complexity of the problem on trees (Hakimi, 1990 [10]). Moreover, we provide polynomial time algorithms for the discrete (r,p)-centroid on paths and the (1,p)-centroid on trees, and complementary hardness results for more complex graph classes.