K-minimum spanning tree

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).

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 $k$ -minimum spanning tree problem, the input is a set of points in the plane. Again, the output should be a tree with $k$ of the points as its vertices, minimizing the total Euclidean length of its edges. That is, it is a graph $k$ -minimum spanning tree on a complete graph with Euclidean distances as weights.^[2]

Computational complexity

When $k$ is a fixed constant, the $k$ -minimum spanning tree problem can be solved in polynomial time by a brute-force search algorithm that tries all $k$ -tuples of vertices. However, for variable $k$ , the $k$ -minimum spanning tree problem has been shown to be NP-hard by a reduction from the Steiner tree problem.^[1]^[2]

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 $k$ -minimum spanning tree problem, Ravi et al. (1996) attach to each terminal a tree of zero-weight edges with a large number $t$ of vertices per tree. (For a graph with $n$ vertices and $r$ terminals, they use $t = n - r - 1$ added vertices per tree.) Then, they ask for the $k$ -minimum spanning tree in this augmented graph with $k = rt$ . The only way to include this many vertices in a $k$ -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 $k$ , it is possible for $k$ -spanning tree to include only as few edges of the original graph as are needed to connect all the terminals. Therefore, the $k$ -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.^[2]

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, and for graphs with only two distinct edge weights.^[2]

Approximation algorithms

Because of the high computational complexity of finding an optimal solution to the $k$ -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 $k$ -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,^[3] the same is true for the $k$ -minimum spanning tree problem.

The best approximation known for the general problem achieves an approximation ratio of 2, and is by Garg (2005).^[4] This approximation relies heavily on the primal-dual schema of Goemans & Williamson (1992).^[5] 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).^[6]

References

^ ^a ^b 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).
^ ^a ^b ^c ^d ^e 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, arXiv:math/9409222, doi:10.1137/S0895480194266331, S2CID 8253322. A preliminary version of this work was presented earlier, at the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, 1994, pp. 546–555.
^ Chlebík, Miroslav; Chlebíková, Janka (2008), "The Steiner tree problem on graphs: Inapproximability results", Theoretical Computer Science, 406 (3): 207–214, doi:10.1016/j.tcs.2008.06.046.
^ 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, S2CID 17089806.
^ Goemans, M.; Williamson, P. (1992), "A general approximation technique for constrained forest problems", SIAM Journal on Computing, 24 (2): 296–317, CiteSeerX 10.1.1.55.7342, doi:10.1137/S0097539793242618, S2CID 1796896.
^ 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, S2CID 3023351.