0
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ You should use dominating set in this case $\endgroup$ – Gilad Jan 2 '17 at 2:45
  • 1
    $\begingroup$ If you can't seem to work out a reduction from one problem, try another. There aren't nice and direct reductions between every pair of NP-complete problems. $\endgroup$ – Yuval Filmus Jan 2 '17 at 5:26
  • $\begingroup$ @YuvalFilmus Three problems are suggsted for the reduction in the assignment: vertex cover, Hamiltonian path problem and the clique problem. Vertex cover seems to me to match this problem best judging also by the answer to this question. I am stuck on the details however. $\endgroup$ – pseudomarvin Jan 2 '17 at 13:36
  • 1
    $\begingroup$ Are the spots and houses constrained to be points in the plane, with the distance measure the Euclidean distance? If so, this makes encoding another NP-hard problem more difficult. If not (so that, e.g., it's possible for two houses to be 50m from each other, with one of them being 10m from a bin while the other is 70m from the same bin) this problem is basically another NP-hard problem in disguise... Hint: Think of a spot as the set of houses that it's in range of... $\endgroup$ – j_random_hacker Jan 3 '17 at 17:16
  • $\begingroup$ It is the second case. $\endgroup$ – pseudomarvin Jan 4 '17 at 19:56
1
$\begingroup$

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.

Improve this answer
$\endgroup$
-1
$\begingroup$

I have come up with the following solution:

We transform an instance of vertex cover $(V, E,k)$ to a specific instance of k containers are sufficient in which the the available spots for containers are equivalent to the set $V$ and in which the set of houses that have to be near containers is exactly equal to $V$ (the available spots for containers are exactly where the houses are located). The edges connect houses-spots which are within 100 ms of each other.

It shouldn't then be difficult to see (since the k containers are sufficient problem formulated in this way is basically identical to vertex cover) that the graph $G=(V,E)$ has a vertex cover of size $k$ exactly when $k$ containers suffices to serve all the houses.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ You still have to spell out the reduction. An idea is not enough. $\endgroup$ – Yuval Filmus Jan 3 '17 at 4:53
  • $\begingroup$ I don't think this works. If your original vertex cover instance is for a non-planar graph, how do you plan to create an instance of k containers are sufficient that corresponds to it? Where are you going to place the houses so that the distances between them are consistent with $E$? I'm not sure that's doable in all cases. $\endgroup$ – D.W.♦ Feb 1 '17 at 23:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.