1
$\begingroup$

Let $G$ be an undirected weighted connected graph with non-negative weights on the edges,
and let $v_1, v_2, v_3, v_4$ be 4 vertecies in $V[G]$.

The goal: find a connected subgraph of $G$ with minimal weight (the sum of weights of the edges in the graph) that includes $v_1, v_2, v_3, v_4$.

Any polynomial algorithm will suffice.
A correctness claim will be appriciated.


I've come up with an example that any shortest path between $v_{1-4}$ isn't in the subgraph:example picture

In this example, the best subgraph would contain all the vertecies, and the edges in the middle of weight $2$, and not the direct shortest paths between $v_{1-4}$ of length $3$, so running Dijkstra's algorithms between the $4$ edges doesn't directly help with the solution.

Also, the solution is a tree because any cycles only add cost.

$\endgroup$
  • 1
    $\begingroup$ Look at Steiner tree. $\endgroup$ – Juho Jan 31 '15 at 19:58
  • $\begingroup$ @Juho Can you find me where I can read about the $O(2^k*n^2)$ algorithm for computing a Steiner Tree with $k$ required vertecies and $n$ total vertecies (using dynamic programming)? Also, this problem doesn't exhibit a metric space.. $\endgroup$ – NightRa Jan 31 '15 at 21:42

Your Answer

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

Browse other questions tagged or ask your own question.