Algorithm for MST connecting a subgraph

Question

I already know how to find the MST of a connected graph. This MST will have the least total weight and will connect all nodes in the graph.

However, this is a problem I have to deal with:

Given a weighted graph $G=\{V,E\}$ and one of its subgraph $H$. Find a subset $E'$ of $E$ such that

• If we clear out every edge outside of $E'$, $H$ is still connected.

• The total weight of $E'$ is lowest possible.

Note that $E'$ may contain edges that don't join two vertices in $H$, and any two vertices in $H$ may not necessarily be joined by an edge.

It is little different from the MST problem.

Firstly I thought that I only have to run MST algorithm in $H$, but I later found that this only work if any two vertices of $H$ is joined by an edge, not a series of edges.

How can I solve this problem? Thanks in advance.

• 喜欢算法和数学: "H may be unconnected". However, "If we clear out every edges outside of E′, H is still connected." Anyway, $H$ is connected initially, isn't it?
• user100482: @Apass.Jack I think I rephrase the question wrongly, and I tried to edit it. Please let me know if my question is still unclear, and I will make it clearer. Thank you very much!
• 喜欢算法和数学: "I only have to run MST algorithm in H, but I later found that this only work if any two vertices of H is joined by an edge, not a series of edge". Since $H$ is connected, you can run an MST algorithm on $H$ to get $T$. Let $E'=E\setminus T,ドル as you planned.
• user100482: @Apass.Jack But I think using, for example, Kruskal's algorithm, only allows me to run on edges that connected two vertices in $H$. If I want to run MST on $H,ドル I think I have to change many edges like a--1--b--3--c to a--4--c, and so the algorithm is not efficient anymore.
• 喜欢算法和数学: "Kruskal's algorithm only allows me to run on edges that connected two vertices in $H$." That is exactly what we wanted.

Answer 1

This is the Steiner Tree problem, specifically the Steiner Tree problem in graphs: the vertices in $H$ are the terminals. Unfortunately it's NP-hard, so it's very unlikely that a polynomial-time algorithm exists.

If $E$ describes a metric, then the minimum spanning tree on $H$ gives a 2-approximation.

• 喜欢算法和数学: If this is the right answer, then the problem should have been stated as "... Given a weighted graph $G=\{V,E\}$ and $H$ that is a subset of $V$...$H$ is still connected by the remaining edges".
• j_random_hacker: @Apass.Jack: Right, my answer is only for the special case where $H$ contains only vertices and no edges. But if the intention is that $H$ can contain edges, and that these must appear in $E',ドル then my answer can be adapted simply: Before solving ST, add all edges in $H$ to $E',ドル and merge the endpoints of these edges in $G$.