Maybe the title is confusing but I can not come up with a more appropriate one. Suppose we have an undirected graph $G = (V, E)$. Let $u$ be a specfic vertex in $G$. Then the sum of distances $$ \sum_{v \in V} d_G(u,v) $$ is determined. Now we want to decrease this value, by setting "main roads" in the graph. Imagine that there is a tree $T \subseteq G$ including $u$ and other $n - 1$ vertices ($n < |V|$) in $G$. Walking on edges of $T$ needs no cost. Formally, let $U$ satisfying $u \in U \subseteq V$ and $|U|=n$ is connected in $G$ (so actually $U$ is the vertex set of $T$). We would like to minimize $$ D=\sum_{v \in V} d_G(U,v) $$ for all possible $U$ with certain $n$.

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

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

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.)

Maybe the title is confusing but I can not come up with a more appropriate one. Suppose we have an undirected graph $G = (V, E)$. Let $u$ be a specfic vertex in $G$. Then the sum of distances $$ \sum_{v \in V} d_G(u,v) $$ is determined. Now we want to decrease this value, by setting "main roads" in the graph. Imagine that there is a tree $T \subseteq G$ including $u$ and other $n - 1$ vertices ($n < |V|$) in $G$. Walking on edges of $T$ needs no cost. Formally, let $U$ satisfying $u \in U \subseteq V$ and $|U|=n$ is connected in $G$ (so actually $U$ is the vertex set of $T$). We would like to minimize $$ D=\sum_{v \in V} d_G(U,v) $$ for all possible $U$ with certain $n$.

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

Maybe the title is confusing but I can not come up with a more appropriate one. Suppose we have an undirected graph $G = (V, E)$. Let $u$ be a specfic vertex in $G$. Then the sum of distances $$ \sum_{v \in V} d_G(u,v) $$ is determined. Now we want to decrease this value, by setting "main roads" in the graph. Imagine that there is a tree $T \subseteq G$ including $u$ and other $n - 1$ vertices ($n < |V|$) in $G$. Walking on edges of $T$ needs no cost. Formally, let $U$ satisfying $u \in U \subseteq V$ and $|U|=n$ is connected in $G$ (so actually $U$ is the vertex set of $T$). We would like to minimize $$ D=\sum_{v \in V} d_G(U,v) $$ for all possible $U$ with certain $n$.

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

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

Maybe the title is confusing but I can not come up with a more appropriate one. Suppose we have an undirected graph $G = (V, E)$. Let $u$ be a specfic vertex in $G$. Then the sum of distances $$ \sum_{v \in V} d_G(u,v) $$ is determined. Now we want to decrease this value, by setting "main roads" in the graph. Imagine that there is a spanning tree $T$ including $u$ and other $n - 1$ vertices ($n < |V|$) in $G$. Walking on edges of $T$ needs no cost. Formally, let $U$ satisfying $u \in U \subseteq V$ and $|U|=n$ is connected in $G$ (so actually $U$ is the vertex set of $T$). We would like to minimize $$ D=\sum_{v \in V} d_G(U,v) $$ for all possible $U$ with certain $n$.

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

Maybe the title is confusing but I can not come up with a more appropriate one. Suppose we have an undirected graph $G = (V, E)$. Let $u$ be a specfic vertex in $G$. Then the sum of distances $$ \sum_{v \in V} d_G(u,v) $$ is determined. Now we want to decrease this value, by setting "main roads" in the graph. Imagine that there is a tree $T \subseteq G$ including $u$ and other $n - 1$ vertices ($n < |V|$) in $G$. Walking on edges of $T$ needs no cost. Formally, let $U$ satisfying $u \in U \subseteq V$ and $|U|=n$ is connected in $G$ (so actually $U$ is the vertex set of $T$). We would like to minimize $$ D=\sum_{v \in V} d_G(U,v) $$ for all possible $U$ with certain $n$.

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