Minimum Diameter Spanning Tree

Before learning about Minimum Diameter Spanning Tree, it is recommended to first read the content on Tree Diameter.

Definition

Among all spanning trees of an undirected graph, the one with the smallest diameter is called the Minimum Diameter Spanning Tree.

Absolute Center of a Graph

To find the minimum diameter spanning tree, we first need to locate the absolute center of the graph. The absolute center can lie on an edge or at a vertex, and it minimizes the maximum shortest distance to all vertices.

From the definition of the absolute center, we know that there are at least two vertices farthest from the absolute center.

Let \(d(i,j)\) be the shortest path length between vertices \(i\) and \(j\), computed via an all-pairs shortest path algorithm.

Let \(\textit{rk}(i,j)\) denote the \(j\)-th closest vertex to vertex \(i\) among all other vertices.

The absolute center may lie on an edge. For each edge \(w=(u,v)\), suppose the absolute center \(c\) lies on this edge. Let the distance from \(c\) to \(u\) be \(x\) (where \(x \leq w\)), then the distance to \(v\) is \(w - x\).

For any vertex \(i\) in the graph, the distance from the absolute center \(c\) to \(i\) is \(d(c,i)=\min(d(u,i) + x, d(v,i) + (w - x))\).

Consider a vertex \(i\); its positional relationship with the absolute center is illustrated below.

mdst1

As the absolute center \(c\) moves along the edge, a function of distance versus \(c\)'s position is generated. Clearly, the function \(d(c,i)\) is a piecewise linear function composed of two segments with the same slope.

mdst2

For any vertex in the graph, the function of the farthest distance from the absolute center is written as \(f = \max\{ d(c,i)\},i \in[1,n]\), and its graph is as follows.

mdst3

The lowest point among the intersections of these piecewise linear functions corresponds to the position of the absolute center.

The absolute center may also lie at a vertex. In that case, update using the farthest vertex from the candidate vertex: \(\textit{ans}\leftarrow \min(\textit{ans},d(i,\textit{rk}(i,n))\times 2)\).

Procedure

Use an all-pairs shortest path algorithm (Floyd, Johnson, etc.) to compute the \(d\) array.
Compute \(\textit{rk}(i,j)\) and sort it in ascending order.
The absolute center may lie at a vertex. Update using the farthest vertex from each candidate vertex: iterate over all vertices and update the minimum with \(\textit{ans}\leftarrow \min(\textit{ans},d(i,\textit{rk}(i,n)) \times 2)\).
The absolute center may lie on an edge. Enumerate all edges. For an edge \(w(u,v)\), start updating from the vertex farthest from \(u\). When \(d(v,\textit{rk}(u,i)) > \max_{j=i+1}^n d(v,\textit{rk}(u,j))\) occurs, update with \(\textit{ans}\leftarrow \min(\textit{ans}, d(u,\textit{rk}(u,i))+\max_{j=i+1}^n d(v,\textit{rk}(u,j))+w(u,v))\), because this situation changes the absolute center.

Implementation

bool cmp(int a, int b) { return val[a] < val[b]; }

void Floyd() {
  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

void solve() {
  Floyd();
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      rk[i][j] = j;
      val[j] = d[i][j];
    }
    sort(rk[i] + 1, rk[i] + 1 + n, cmp);
  }
  int ans = INF;
  // The absolute center may be at a vertex
  for (int i = 1; i <= n; i++) ans = min(ans, d[i][rk[i][n]] * 2);
  // The absolute center may be on an edge
  for (int i = 1; i <= m; i++) {
    int u = a[i].u, v = a[i].v, w = a[i].w;
    for (int p = n, i = n - 1; i >= 1; i--) {
      if (d[v][rk[u][i]] > d[v][rk[u][p]]) {
        ans = min(ans, d[u][rk[u][i]] + d[v][rk[u][p]] + w);
        p = i;
      }
    }
  }
}

Example Problems

CodeForce 266D BerDonalds