The city council would like to place trash bins around the city and has a list of suitable spots (street crossroads, supermarkets etc.) but the number of these spots is greater than the number of available bins. The council's goal is to place the limited number of bins so that the distance from each house to a bin is at most 100 m. Prove that the problem k containers are sufficient is NP-hard using reduction from a known NP-hard problem.I came up with vertex cover (could we alternatively use dominating set?). We then need to transform an instance of vertex cover $(V, E, k)$ to an instance of this problem. It's not clear to me how. This is how I thought I would represent the k containers are sufficient problem by a graph:My first step would be to create a graph where the set of nodes contains both the spots for containers and all the houses. I would then connect each spot node with all the house nodes that it is close enough to (100 m). This seems quite close to vertex cover except that there are 2 types of nodes:The house nodes cannot be used as a part of the vertex cover set since bins cannot be placed in front of houses but they need to be covered by the vertex cover set.The bin spots can be used as a part of the vertex cover set but do need to be covered at all by it.How could I deal with this in the reduction? I thought about using some vertex to edge transformation to represent these relationships but came up short.
Reduction from Vertex Cover
complexity theory;reductions;np hard;decision problem
This is known as the $k$-center problem or the planar minmax Euclidean facility location problem.  It is a special case of the minimax facility location problem for the Euclidean metric.The $k$-center problem is known to be NP-hard.  Wikipedia has references to the literature, where you should be able to find an explicit reduction.The special case where $k=1$ can be solved in polynomial time.