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.

Improve this question
$\endgroup$
8
  • $\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$
    – John L.
    Commented Feb 15, 2019 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$
    – user100482
    Commented Feb 15, 2019 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$
    – John L.
    Commented Feb 15, 2019 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$
    – user100482
    Commented Feb 15, 2019 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$
    – John L.
    Commented Feb 15, 2019 at 7:45

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 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$
    – John L.
    Commented Feb 15, 2019 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
    Commented Feb 15, 2019 at 13:17

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.