k-minimum spanning tree
The Template:Mvar-minimum spanning tree problem, studied in theoretical computer science, asks for a tree of minimum cost that has exactly Template:Mvar vertices and forms a subgraph of a larger graph. It is also called the Template:Mvar-MST or edge-weighted Template:Mvar-cardinality tree. Finding this tree is NP-hard, but it can be approximated to within a constant approximation ratio in polynomial time.
Problem statementEdit
The input to the problem consists of an undirected graph with weights on its edges, and a Template:Nowrap The output is a tree with Template:Mvar vertices and Template:Math 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 Template:Harvtxt<ref name="lz">Template:Citation. As cited by Template:Harvtxt.</ref> and by Template:Harvtxt.
Ravi et al. also considered a geometric version of the problem, which can be seen as a special case of the graph problem. In the geometric Template:Mvar-minimum spanning tree problem, the input is a set of points in the plane. Again, the output should be a tree with Template:Mvar of the points as its vertices, minimizing the total Euclidean length of its edges. That is, it is a graph Template:Mvar-minimum spanning tree on a complete graph with Euclidean distances as weights.<ref name="rsmr">Template:Citation. A preliminary version of this work was presented earlier, at the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, 1994, pp. 546–555.</ref>
Computational complexityEdit
When Template:Mvar is a fixed constant, the Template:Mvar-minimum spanning tree problem can be solved in polynomial time by a brute-force search algorithm that tries all Template:Mvar-tuples of vertices. However, for variable Template:Mvar, the Template:Mvar-minimum spanning tree problem has been shown to be NP-hard by a reduction from the Steiner tree problem.<ref name="lz"/><ref name="rsmr"/>
The reduction takes as input an instance of the Steiner tree problem: a weighted graph, with a subset of its vertices selected as terminals. The goal of the Steiner tree problem is to connect these terminals by a tree whose weight is as small as possible. To transform this problem into an instance of the Template:Mvar-minimum spanning tree problem, Template:Harvtxt attach to each terminal a tree of zero-weight edges with a large number Template:Mvar of vertices per tree. (For a graph with Template:Mvar vertices and Template:Mvar terminals, they use Template:Math added vertices per tree.) Then, they ask for the Template:Mvar-minimum spanning tree in this augmented graph with Template:Math. The only way to include this many vertices in a Template:Mvar-spanning tree is to use at least one vertex from each added tree, for there are not enough vertices remaining if even one of the added trees is missed. However, for this choice of Template:Mvar, it is possible for Template:Mvar-spanning tree to include only as few edges of the original graph as are needed to connect all the terminals. Therefore, the Template:Mvar-minimum spanning tree must be formed by combining the optimal Steiner tree with enough of the zero-weight edges of the added trees to make the total tree size large enough.<ref name="rsmr"/>
Even for a graph whose edge weights belong to the set Template:Math}, 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.<ref name="rsmr"/>
The Template:Mvar-minimum spanning tree may be found in polynomial time for graphs of bounded treewidth, and for graphs with only two distinct edge weights.<ref name="rsmr"/>
Approximation algorithmsEdit
Because of the high computational complexity of finding an optimal solution to the Template:Mvar-minimum spanning tree, much of the research on the problem has instead concentrated on approximation algorithms for the problem. The goal of such algorithms is to find an approximate solution in polynomial time with a small approximation ratio. The approximation ratio is defined as the ratio of the computed solution length to the optimal length for a worst-case instance, one that maximizes this ratio. Because the NP-hardness reduction for the Template:Mvar-minimum spanning tree problem preserves the weight of all solutions, it also preserves the hardness of approximation of the problem. In particular, because the Steiner tree problem is NP-hard to approximate to an approximation ratio better than 96/95,<ref>Template:Citation.</ref> the same is true for the Template:Mvar-minimum spanning tree problem.
The best approximation known for the general problem achieves an approximation ratio of 2, and is by Template:Harvtxt.<ref>Template:Citation.</ref> This approximation relies heavily on the primal-dual schema of Template:Harvtxt.<ref>Template:Citation.</ref> 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 Template:Harvtxt.<ref>Template:Citation.</ref>
ReferencesEdit
External linksEdit
- Minimum k-spanning tree in "A compendium of NP optimization problems"
- KCTLIB, KCTLIB -- A Library for the Edge-Weighted K-Cardinality Tree Problem