3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "𝐻 may be unconnected". However, "If we clear out every edges outside of 𝐸′, 𝐻 is still connected." Anyway, $H$ is connected initially, isn't it? $\endgroup$ – Apass.Jack Feb 15 at 7:23
  • $\begingroup$ @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! $\endgroup$ – JouleV Feb 15 at 7:32
  • $\begingroup$ "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. $\endgroup$ – Apass.Jack Feb 15 at 7:36
  • $\begingroup$ @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. $\endgroup$ – JouleV Feb 15 at 7:42
  • $\begingroup$ "Kruskal's algorithm only allows me to run on edges that connected two vertices in $H$." That is exactly what we wanted. $\endgroup$ – Apass.Jack Feb 15 at 7:45
1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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". $\endgroup$ – Apass.Jack Feb 15 at 13:00
  • $\begingroup$ @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$. $\endgroup$ – j_random_hacker Feb 15 at 13:17

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.