# Algorithm for MST connecting a subgraph

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.

• "𝐻 may be unconnected". However, "If we clear out every edges outside of 𝐸′, 𝐻 is still connected." Anyway, $H$ is connected initially, isn't it? – John L. Feb 15 '19 at 7:23
• @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! – user100482 Feb 15 '19 at 7:32
• "I only have to run MST algorithm in 𝐻, but I later found that this only work if any two vertices of 𝐻 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. – John L. Feb 15 '19 at 7:36
• @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. – user100482 Feb 15 '19 at 7:42
• "Kruskal's algorithm only allows me to run on edges that connected two vertices in $H$." That is exactly what we wanted. – John L. Feb 15 '19 at 7:45

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". – John L. Feb 15 '19 at 13:00
• @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$. – j_random_hacker Feb 15 '19 at 13:17