On alternativep-center problems

LetG=(V, E) be an undirected connected graph with positive edge lengths. The vertexp-center problem is to find the optimal location ofp centers so that the maximum distance to a vertex from its nearest center is minimized, where the centers may be placed at the vertices. Kariv and Hakimi have shown that this problem is NP-hard. We will consider two modifications of this problem in which each center may be located in one of two predetermined vertices. We will show the NP-completeness of their recognition versions.