47

I have an undirected, positive-edge-weight graph (V,E) for which I want a minimum spanning tree covering a subset k of vertices V (the Steiner tree problem).

I'm not limiting the size of the spanning tree to k vertices; rather I know exactly which k vertices must be included in the MST.

Starting from the entire MST I could pare down edges/nodes until I get the smallest MST that contains all k.

I can use Prim's algorithm to get the entire MST, and start deleting edges/nodes while the MST of subset k is not destroyed; alternatively I can use Floyd-Warshall to get all-pairs shortest paths and somehow union the paths. Are there better ways to approach this?

13
  • 4
    If I remove the unwanted vertices I might also lose intermediate edges that connect k vertices that are far apart. For example if I have: k--o--o--o--k where o represents an unnecessary vertex and k represents one I need, if I deleted the middle o there would be no way to construct the MST between my k vertices.
    – rxmnnxfpvg
    Oct 7, 2011 at 9:32
  • 1
    So you interested in the minimum spanning tree, which doesn't necessarily span all vertices, only the vertices in k?
    – aioobe
    Oct 7, 2011 at 9:35
  • 1
    Exactly. The MST that includes all of k at least, and then as little else as possible.
    – rxmnnxfpvg
    Oct 7, 2011 at 9:36
  • 2
    Hi could you solve your problem? If possible can you help with the pseudo code/code? I have similar problem but the graph is unweighted.
    – phoenix
    Mar 14, 2015 at 12:13
  • 1
    The question is unclear about whether k is a number or a set. Will you please clarify?
    – Palec
    Dec 31, 2015 at 10:34

3 Answers 3

25

There's a lot of confusion going on here. Based on what the OP says:

I'm not limiting the size of the spanning tree to k vertices; rather I know exactly which k vertices must be included in the MST.

This is the Steiner tree problem on graphs. This is not the k-MST problem. The Steiner tree problem is defined as such:

Given a weighted graph G = (V, E), a subset S ⊆ V of the vertices, and a root r ∈ V , we want to find a minimum weight tree which connects all the vertices in S to r. 1

As others have mentionned, this problem is NP-hard. Therefore, you can use an approximation algorithm.

Early/Simple Approximation Algorithms

Two famous methods are Takahashi's method and Kruskal's method (both of which have been extended/improved by Rayward-Smith):

  • Takahashi H, Matsuyama A: An approximate solution for the Steiner problem in graphs. Math. Jap 1980, 24:573–577.
  • Kruskal JB: On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. In Proceedings of the American Mathematical Society, Volume 7. ; 1956:48–50.
  • Rayward-Smith VJ, Clare A: On finding Steiner vertices. Networks 1986, 16:283–294.

Shortest path approximation by Takahashi (with modification by Rayward-Smith)

enter image description here


Kruskal's approximation algorithm (with modification by Rayward-Smith)

enter image description here


Modern/More Advanced Approximation Algorithms

In biology, more recent approaches have treated the problem using the cavity method, which has led to a "modified belief propagation" method that has shown good accuracy on large data sets:

  • Bayati, M., Borgs, C., Braunstein, A., Chayes, J., Ramezanpour, A., Zecchina, R.: Statistical mechanics of steiner trees. Phys. Rev. Lett. 101(3), 037208 (2008) 15.
  • For an application: Steiner tree methods for optimal sub-network identification: an empirical study. BMC Bioinformatics. BMC Bioinformatics 2013 30;14:144. Epub 2013 Apr 30.

In the context of search engine problems, approaches have focused on efficiency for very large data sets that can be pre-processed to some degree.

  • G. Bhalotia, A. Hulgeri, C. Nakhe, S. Chakrabarti, and S. Sudarshan. Keyword Searching and Browsing in Databases using BANKS. In ICDE, pages 431–440.
  • G. Kasneci, M. Ramanath, M. Sozio, F. M. Suchanek, and G. Weikum. STAR: Steiner-tree approximation in relationship graphs. In ICDE’09, pages 868–879, 2009
1
  • Thank you so much for this. This post led me to a nice R implementation in the SteinerNet package
    – Jeff Bezos
    Apr 18, 2020 at 3:58
11

The problem you stated is a famous NP-hard problem, called Steiner tree in graphs. There are no known solutions in polynomial time and many believe no such solutions exist.

3
  • Actually, Steiner tree in graphs has a fixed set of k vertices as input, while the OP gives just the k and lets the algorithm find the set. This problem is called k-MST and is also NP-hard. See also problems related to MST on Wikipedia.
    – Palec
    Dec 31, 2015 at 10:26
  • @Palec Actually, that is wrong. "I'm not limiting the size of the spanning tree to k vertices; rather I know exactly which k vertices must be included in the MST." This problem is the Steiner tree problem. Jan 28, 2016 at 1:26
  • 3
    Also, -1 to @meh because the fact that the problem is NP-hard doesn't mean we can't get useful solutions with approximation algorithms. This answer does not help the OP in solving his problem. Jan 28, 2016 at 1:54
1

Run Prim's algorithm on the restricted graph (k, E') where E' = {(x, y) ∈ V : xk and yk}). Constructing that graph takes O(|E|).

4
  • This might work alright some of the time, but it's not even guaranteed that the E' is connected -- and even if it is, it might be possible to save arbitrarily much distance by introducing a Steiner point (i.e., a vertex not in k). (Less than "arbitrarily much" if the distances obey the Triangle Inequality, but nothing says they have to.) Dec 21, 2015 at 14:17
  • @j_random_hacker interested in posting an alternative solution? Dec 25, 2015 at 5:46
  • @user2398029: I upvoted meh's answer (and I don't know why "Bill the Lizard" deleted adi's much earlier answer saying mostly the same thing). Basically this is an NP-hard problem to solve optimally; if you google "Steiner tree approximation" you can probably get some OK algorithms. Dec 25, 2015 at 14:30
  • @user2398029: It might be helpful to look at chapter 3 of this link from adi's answer: cc.gatech.edu/fac/Vijay.Vazirani/book.pdf. (I (re)post this here since I can see deleted posts, but I'm not sure what the rep cutoff is for that.) Dec 25, 2015 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.