Building Minimum warehouses

Question

A big international retailer is setting up shop in India and plans to open stores in N towns (3 ≤ N ≤ 1000), denoted by 1, 2, . . . , N.

There are direct routes connecting M pairs among these towns. The company decides to build warehouses to ensure that for any town X, there will be a warehouse located either in X or in an immediately neighboring town of X.

I need to find the minimum number of warehouses the company has to build.

Example : If we have N=10 towns and 7 routes between :

1 2
2 4
2 5
3 6
8 6
9 7
10 7

Here answer will be 3. Help me device an algorithm to do this problem.

Answer 1

Use Algorithm to find the number of connected components in a graph. The number of components in the graph will show how many warehouses are needed.So, that every places is reachable.

Answer 2

This problem is equivalent to finding the domination number of the graph, i.e., the smallest set $S$ of vertices such that every vertex of the graph lies in $S$ or its neighborhood $N(S)$. Different graphs with the same $M$ (number of edges) may have different domination numbers.

I would thus try to find a domination number algorithm. The problem is NP hard, so it's not going to be fast for large graphs.

The brute force way to do this would be as follows. Let $G$ be the graph whose vertices are towns, and whose edges are direct routes. Run through every vertex set $S\subset V(G)$ of the graph from smallest to largest (so first check all single vertices, then all pairs, etc), and check if every vertex not in $S$ is adjacent to something in $S$ (so check if $V(G) \subseteq N(S)\cup S$). As soon as you find a set $S$ that is adjacent to everything, stop the algorithm, and take the number of vertices in $S$ to be your answer. It is important that you stop as soon as you find one, because this algorithm is already going to be painfully slow.