NP-completeness of the problem of constructing a graph with a minimum stretch factor

In this paper, we consider the problem of constructing a planar connected weighted graph on a given set of points in such a way that the sum of the shortest paths between all pairs of vertices is the minimum possible.In other words, the problem of constructing a graph with a minimum stretch factor. The euclidean distance between the ends is taken as the weight of the edge. It is proved that such a problem is NP-complete. This problem arises when planning transport networks, since it is the stretch factor of the graph of the transport network that directly indicates the level of overrun of transport, which should be as small as possible in order to minimize the resources spent. But since this problem is NP-complete, a heuristic algorithm for solving the problem under consideration is proposed, which is based on sorting some simple paths and has a recursive character. This algorithm always builds a triangulation, since only in this class of graphs is it possible to solve the problem. A number of experiments have been carried out on the statistical study of the stretch factor of the triangulation constructed as a result of the operation of the above algorithm on randomly generated points. Experiments show that the losses are about 1.5-7.8%, and for real cities this parameter is about 30%.