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

- these "main roads" must constitute a sub
*tree*$T$ of $G$.^{(note)} - $u\in V(T)$
- $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.)

Computational Geometry, 41(3), 219-229. PDF download $\endgroup$ – Joseph O'Rourke Sep 26 '17 at 13:45