Let G=(V,E) be an undirected connected graph with positive edge lengths. The vertex p-center problem is to find the optimal location of p 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. The paper will consider two modifications of this problem in which each center may be located in one of two predetermined vertices. It will show the NP-completeness of their recognition versions.
