Minimize total distance using k links among n nodes

Question

I came up with the following problem that I do not know the solutions to nor can I find the 'lookup' term to investigate further.

Say we have N ordered nodes (n_1,n_2....n_N) each with a fixed distance of 1 between them. So dist(n_1,n_N) = N-1. Now we are are allowed to connect any two nodes, thus effectively reducing their distance to 1. Assume we can have k such connections.

The problem is : how do we choose which nodes to connect to minimize the total distance between any two nodes ?

Is this problem a known variant of some well-studied problem ? Does an efficient solution exist for this (or a variant where we only want to minimize the max distance between any two nodes)

Thanks

Answer 1

You may be interested in "On the sum of all distances in a graph or digraph". That paper refers to your "total distance" as the "transmission" of a graph. Your "max distance" is generally called the "diameter" of a graph. It discusses the two, proves some properties of a graph's transmission, and shows that the transmission and diameter are independent of one another.

Naively, you've got n-choose-k options to try. That's pretty bad if n and k are large. Not too bad if one of them is small.

There is work on doing better than that. This Mathoverflow question asks about reducing the mean distance between vertices, which is proportional to the transmission of the graph. There are two answers, neither of which I can vouch for. It also refers to a paper that directly addresses this question.

Minimizing the diameter of a graph is dealt with in this paper.

You might consider addressing this question to the Math stackexchange.