Add edges to undirected graph to make connected and minimize longest path

Question

I am trying to find an efficient algorithm to solve to following problem: Given an undirected disconnected graph, I want to add as few as possible edges to make to graph connected while minimizing the number of vertices on the longest path in the resulting connected graph. As a result I need the number of vertices on the longest simple path in the resulting graph.

For example, given a graph with the following edges:

1 0
2 0
4 3
5 3

There are multiple ways to add edges to make it a connected graph. But since I want to minimize the number of vertices on the longest path in the resulting graph, I have to add an edge between 0 and 3. Now the path with the most vertices contains 4 vertices (2 -> 0 -> 3 -> 5). If I had added an edges between 2 and 4 then the path with the most vertices would've been 1 -> 0 -> 2 -> 4 -> 3 -> 5.

Another example, given a graph with the following edges:

0 1
1 2
3 4
5 6

Here two edges need to be added: between 1 and 3 and between 3 and 5. The path with the most vertices then contains 5 vertices.

My approach was to first use DFS to identify all components. Then, for each component, I find the longest path in that component, I take the vertex that is in the middle of each of those paths and connect them. This results in one connected graph. In that resulting graph I can find the path with the most vertices. I suspect that there must be a more efficient approach to this, especially since it needs to work for a disconnected graph with at most $10^6$ vertices. Hopefully someone has a better idea on how to solve this.

Answer 1

Clearly, the number of added edges is one less than the number of connected components in the graph, since we can decrease this number by one by adding an edge and we seek the minimum number of added edges.

The trick is to add the edges between central vertices of the connected components. A central vertex of a connected component is a vertex that has minimum distance to the farthest vertex to this vertex in the component (we call this distance the eccentricity). So it is a vertex that minimises the eccentricity.

Here goes the algorithm. In each step we find the connected components of the graph and we handle them as different graphs say $G_1, \dots, G_l$. Note that the task is to add $l-1$ edges between these graphs in a way that makes them connected. Each time we add an edge we will combine two graphs and decrease $l$ by one until it gets to the value 1.

After we found the connected component we find a central vertex in each of them (central vertices might not be unique but we can choose any of them). We keep for each component a central vertex and the value of its eccentricity. Now in each step we combine to graphs, we distinct two cases. - The minimum eccentricities are equal, then any of the two central vertices can be chosen as a central for the new graph and the new eccentricity is the previous one plus one. (Try to prove the correctness and optimality of this statement). - The minimum eccentricities differ. Keep the central with the greater eccentricitiy. Its eccentricity does not change. (Also try to prove this).

The eccentricity of each component can be built using a BFS from each vertex in total quadratic time in the size of the input graph. Each iteration can be implemented in constant ime (for example keep a stack of pairs (central, eccentricity) and in each step pop two elements, unify them and push thr new pair back to thr stack. each step decreases the size of the stack by one and hence we end after $l-1$ steps.

The correctness of the previous two cases implies the correctness of the algorithm and that it does not matter in which order you process the components. Hence we get a total quadratic running time. There are some heuristics to improve the running time of computing central vertices if connected components (which is the only quadratic factor in our algorithm and gence the bottleneck) including pruned BFS. However, as far as I know, this is the best achievable asymptotic running time.