Question

Show that the following problem is NP-Complete (Hint: reduce from 3-SAT or Vertex Cover).

Given an undirected graph G with positive integer distances on the edges, and two integers f and d, is there a way to select f vertices on G on which to locate firehouses, so that no vertex of G is at distance more than d from a firehouse?

Answer 1

To show that a given problem is NP-complete, we need to show that the problem belongs to the class NP (i.e., a candidate solution for the problem can be verified in polynomial time) and there is another known NP-complete problem which can be reduced to the current problem in polynomial time.

In the current problem, we first transform the given graph G into a new graph G’ (pronounced G-prime). Let V denote the vertex set and E denote the edge set of the original graph G. Analogously, let V’ and E’ denote the vertex and edge sets of the new graph G’.

While transforming G into G’, we use the same vertex set, i.e., V = V’. However, we add an edge between two vertices u’ and w’ in G’ only if the corresponding vertices u and w in the original graph G are connected by an edge with distance less than d (Note d is the parameter given in the question). So the newly transformed graph G’ will connect only those vertices which have the distance at most d (i.e., d or less than d). Note in the newly created graph G’, we do not need to label the edges in E’ with the distance because all of those edges will have distance less than or equal to d.

Now, to know “is there a way to select f vertices on G on which to locate firehouses, so that no vertex of G is at distance more than d from a firehouse?”, all that we need to do is to run an algorithm for solving the Vertex Cover problem in the newly transformed graph G’. That is, if there is a vertex cover of size f or less than f in the new graph G’, then the vertices in the vertex cover of G’ give us the way to select the f vertices in the original graph G to locate the firehouses (so that no vertex in G is at distance d or more from a firehouse).

Note that finding a Vertex Cover of an undirected graph is an already known NP-complete problem (as mentioned in the question itself. See the Hint.). We have provided a polynomial time transformation from the Vertex cover problem to the problem given in the question. Thus we have reduced a known NP-complete problem (i.e., Vertex cover) to this problem. We have also shown that this problem is in class NP because if someone provides us a set of candidate f vertices in the original graph G, we can easily verify in polynomial time that remaining vertices of G (original graph) are at a distance d or less from these candidate vertices.

Thus, we have proved both conditions necessary to show that this is an NP-complete problem. Hence the proof.