Reference Request: designing a tree of "main roads" in a graph

Question

Let $G = (V, E)$ be an undirected finite connected graph. Let $u$ be a specified vertex of $G$. Then the sum of distances $$ \sum_{v \in V} d_G(u,v) $$ is defined. Now we want to decrease this value, by defining "main roads" in the graph.

We require that

1. these "main roads" must constitute a subtree $T$ of $G$.^(note)
2. $u\in V(T)$
3. $s:=\lvert V(T)\rvert < \lvert V\rvert$

The idea is that traversing edges of $T$ is cost-free, and that therefore the size of the sum of distances drops to the sum of distances from vertices outside $T$ to the nearest vertex of $T$.

Formally, the aim is to minimize (or course, $d_G(U,v):=\min\{d_G(u,v)\colon u\in U\}$) $$ D=\sum_{v \in V\setminus U} d_G(U,v) $$ over all $U\subseteq V$ with

(bc.1) $\qquad\lvert U\rvert=s<\lvert V\rvert$,

(bc.2) $\qquad G[U]:=(U,\{e\in E\colon e\subset U\})$ is connected.

My question. Was this problem studied before? Is there any result of an algorithm to calculate or estimate the minimum of $D$ with tolerable errors?

---

A counterexample for Manfred's algorithm, in which $u$ is $A$ and $s=4$.

${}$________________________________

^(note) Not spanning tree though, because of condition 3. (Also compare the condition $n<\lvert V\rvert$ in the original version of thie post; there, $n$ unambiguously meant the number of vertices of the tree, so, curiously, the 'main-road-subtree' is required not to be a spanning tree.)

Answer 1

My suggestion would be to

• remove all edges of $G$ that are not on some shortest path
• multiply the weight of each edge with the number of shortest paths it is on
• incrementally construct the maximum weight spanning tree via Kruskal's algorithm until one of the generated sub-trees has $n$ or more vertices and select that tree for the next step.
• if the size of the selected tree is bigger than $n$ then recursively delete the leaf vertex that is adjacent to the shortest of the edges that are adjacent to a leaf vertex, until size $n$ is reached
• report the so generated tree as a heuristic answer.

the complexity of the algorithm is governed by the $O(n^3)$ estimate for the all pairs shortest paths calculations, plus $O(n^3)$ for determining the number of shortest paths, on which an edge is.