Optimal distribution of power plants on a city

Question

I've searched both Google and Stack Overflow for an answer to my problem but I can't find one.

I need to find the optimal distribution for the power network of a city. The city is represented by a connected graph. I want to distribute power plants among some of those nodes in order to cover all of them in the electrical grid. The problem being that every power plant has a certain "range" (it can only cover for example in a "radius" of two nodes). My program needs to find the minimum number of power plants and their locations to cover the entire city.

I know from my searches that it should be related to MST's (minimum spanning trees) but the problem is in the limited range of the power plants.

I've thought about going through every node in the city and calculate the sub-graph containing all nodes within the range of a power plant in that node until I find the one that covers the most uncovered nodes and then keep doing that until the entire city is covered (basically brute forcing the problem) but that seems very unpractical and I was wondering if there is any other more effective way to solve this problem.

Thanks.

Answer 1

Unfortunately, this problem is known to be NP-hard by a reduction from the dominating set problem.

Given a graph G, a dominating set in G is a set of nodes D such that every node in the graph is either in D or is one hop away from D. The problem of finding the smallest dominating set in a graph is known to be NP-hard, and this problem easily reduces to the one you're trying to solve: given a graph G, produce a city (represented as a graph) that has the same structure as G, then give every power plant a radius of 1 (meaning that it can cover a node and all its neighbors). Finding the smallest set of power plants to cover the entire city then ends up producing a dominating set for the graph. Therefore, your problem is NP-hard.

As mentioned in this section of the Wikipedia page, it turns out that this problem is surprisingly hard to approximate. The Wikipedia page lists a few algorithms and approaches for approximating it, but it appears to be one of those NP-hard problems that resists polynomial-time approximation schemes.

Hope this helps!