k-minimum spanning tree

An example of an undirected graph G with edge costs
The 4-MST of G
The 6-MST of G

The k-minimum spanning tree problem, studied in theoretical computer science, asks for a tree of minimum cost that has exactly k vertices and forms a subgraph of a larger graph. It is also called the k-MST or edge-weighted k-cardinality tree. Finding this tree is NP-hard, but it can be approximated to within a constant approximation ratio in polynomial time.

Problem statement

The input to the problem consists of an undirected graph with weights on its edges, and a number k. The output is a tree with k vertices and k − 1 edges, with all of the edges of the output tree belonging to the input graph. The cost of the output is the sum of the weights of its edges, and the goal is to find the tree that has minimum cost. The problem was formulated by Lozovanu & Zelikovsky (1993)[1] and by Ravi et al. (1996), who also considered a geometric version of the problem in which the input is a set of points in the plane. Again, the output should be a tree with k vertices, minimizing the total Euclidean length of its edges.[2]

Computational complexity

The k-minimum spanning tree problem has been shown to be NP-hard by a reduction from the Steiner tree problem.[1][2] More precisely, even for a graph whose edge weights belong to the set {1, 2, 3}, testing whether the optimal solution value is less than a given threshold is NP-complete. It remains NP-complete for planar graphs. The geometric version of the problem is also NP-hard, but not known to belong to NP, because of the difficulty of comparing sums of square roots; instead it lies in the class of problems reducible to the existential theory of the reals.[2]

The k-minimum spanning tree may be found in polynomial time for graphs of bounded treewidth.[2]

Approximation algorithms

The best approximation known for the problem achieves an approximation ratio of 2, and is by Garg (2005).[3] This approximation relies heavily on the primal-dual schema of Goemans & Williamson (1992).[4] When the input consists of points in the Euclidean plane (any two of which can be connected in the tree with cost equal to their distance) there exists a polynomial time approximation scheme devised by Arora (1998).[5]

References

  1. 1 2 Lozovanu, D.; Zelikovsky, A. (1993), "Minimal and bounded tree problems", Tezele Congresului XVIII al Academiei Romano-Americane, Kishniev, p. 25. As cited by Ravi et al. (1996).
  2. 1 2 3 4 Ravi, R.; Sundaram, R.; Marathe, M.; Rosenkrantz, D.; Ravi, S. (1996), "Spanning trees short or small", SIAM Journal on Discrete Mathematics 9 (2): 178–200, doi:10.1137/S0895480194266331. A preliminary version of this work was presented earlier, at the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, 1994, pp. 546–555.
  3. ↑ Garg, Naveen (2005), "Saving an epsilon: a 2-approximation for the k-MST problem in graphs", Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 396–402, doi:10.1145/1060590.1060650..
  4. ↑ Goemans, M.; Williamson, P. (1992), "A general approximation technique for constrained forest problems", SIAM Journal on Computing 24 (2): 296–317, doi:10.1137/S0097539793242618.
  5. ↑ Arora, Sanjeev (1998), "Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems", Journal of the ACM 45 (5): 753–782, doi:10.1145/290179.290180.

External links

This article is issued from Wikipedia - version of the Tuesday, December 15, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.