3
$\begingroup$

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

counterexample

${}$________________________________

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

$\endgroup$
  • 3
    $\begingroup$ There has been work on geometric versions in the plane (instead of a graph), and already this is complicated for placement of a single highway. E.g., Cardinal, J., Collette, S., Hurtado, F., Langerman, S., & Palop, B. (2008). Optimal location of transportation devices. Computational Geometry, 41(3), 219-229. PDF download $\endgroup$ – Joseph O'Rourke Sep 26 '17 at 13:45
  • $\begingroup$ Is the set $U$ fixed, but arbitrary and is it assumed that original paths are still used, after the cost of the tree edges has been set to 0? If that is the case, then an efficient algorithm exists $\endgroup$ – Manfred Weis Sep 27 '17 at 3:53
  • $\begingroup$ @ManfredWeis Unluckily the original paths does not need to be used after. $\endgroup$ – Lwins Sep 27 '17 at 3:56
  • $\begingroup$ So, could you please make more explicit, what is fixed and what has to be determined by the algorithm? Maybe you want to identify a tree of size $n < |V|$ in $G$, that minimizes the sum of pairwise distances of vertices in $G$ if its edge weights of $T$ are set to 0? $\endgroup$ – Manfred Weis Sep 27 '17 at 4:58
  • $\begingroup$ @ManfredWeis Yes, it is exactly what I meant. $\endgroup$ – Lwins Sep 27 '17 at 5:00
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think maybe there is some problem in it. We can not guarantee that if a path is not a shortest path in $G$, it will not appear in the final scheme. $\endgroup$ – Lwins Sep 27 '17 at 6:21
  • $\begingroup$ @Lwins that doesn't harm the algorithm; the new shortest paths may use an arbitrary number of the tree edges instead of shortcutting between two tree-vertices; I took that into account in my algorithm. $\endgroup$ – Manfred Weis Sep 27 '17 at 7:38
  • $\begingroup$ I could not understand to some extent. Would you be so kind to show how your algorithm succeeds on the case in my post? $\endgroup$ – Lwins Sep 27 '17 at 7:43
  • $\begingroup$ The basic idea is, that it brings most to replace edges where the product of weight and number of shortest paths they are on, bring the biggest gain when replacing their weight by 0, because all shortest paths that contain that edge will also contain it after its weight has been set to zero. The Kruskal algorithm grows trees in parallel and therefore allows one to find the heaviest subtree. Setting the edges of the heaviest subtree of size $n$ to 0 is the heuristic for the biggest decrease of summed shortest paths lengths. $\endgroup$ – Manfred Weis Sep 27 '17 at 8:56
  • $\begingroup$ Thanks for your patient explanation. While I still think there is some problem. My opinion is when $n=2$ or equivalently $T$ has only one edge, your algorithm is correct. But maybe we will meet some trouble when $n$ is large. Using your algorithm I could not get the best solution $ABCD$ in the OP. $\endgroup$ – Lwins Sep 27 '17 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.