Editing K-minimum spanning tree

[[Image:K-mst 1.pdf|thumb|An example of an undirected graph <math> G </math> with edge costs]]
[[Image:K-mst 2.pdf|thumb|The 4-MST of <math> G </math>]]
[[Image:K-mst 3.pdf|thumb|The 6-MST of <math> G </math>]]
{{DISPLAYTITLE:''k''-minimum spanning tree}}
The '''{{mvar|k}}-minimum spanning tree problem''', studied in [[theoretical computer science]], asks for a tree of minimum cost that has exactly {{mvar|k}} [[vertex (graph theory)|vertices]] and forms a subgraph of a larger graph. It is also called the '''{{mvar|k}}-MST''' or '''edge-weighted {{mvar|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 {{nowrap|number {{mvar|k}}.}} The output is a tree with {{mvar|k}}  vertices and {{math|''k'' &minus; 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 {{harvtxt|Lozovanu|Zelikovsky|1993}}<ref name="lz">{{citation|first1=D.|last1=Lozovanu|first2=A.|last2=Zelikovsky|contribution=Minimal and bounded tree problems|title=Tezele Congresului XVIII al Academiei Romano-Americane, Kishniev|year=1993|page=25}}. As cited by {{harvtxt|Ravi|Sundaram|Marathe|Rosenkrantz|1996}}.</ref> and by {{harvtxt|Ravi|Sundaram|Marathe|Rosenkrantz|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 {{mvar|k}}-minimum spanning tree problem, the input is a set of points in the plane. Again, the output should be a tree with {{mvar|k}} of the points as its vertices, minimizing the total [[Euclidean distance|Euclidean length]] of its edges. That is, it is a graph {{mvar|k}}-minimum spanning tree on a [[complete graph]] with Euclidean distances as weights.<ref name="rsmr">{{citation
 | last1 = Ravi | first1 = R. | last2 = Sundaram | first2 = R. | last3 = Marathe | first3 = M. | last4 = Rosenkrantz | first4 = D. | last5 = Ravi | first5 = S.
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | title = Spanning trees short or small
 | arxiv = math/9409222
 | doi = 10.1137/S0895480194266331 | volume = 9 | issue = 2 | pages = 178–200
 | year = 1996| 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.</ref>

==Computational complexity==
When {{mvar|k}} is a fixed constant, the {{mvar|k}}-minimum spanning tree problem can be solved in [[polynomial time]] by a [[brute-force search]] algorithm that tries all {{mvar|k}}-tuples of vertices.
However, for variable {{mvar|k}}, the {{mvar|k}}-minimum spanning tree problem has been shown to be [[NP-hard]] by a [[Reduction (complexity)|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 {{mvar|k}}-minimum spanning tree problem, {{harvtxt|Ravi|Sundaram|Marathe|Rosenkrantz|1996}} attach to each terminal a tree of zero-weight edges with a large number {{mvar|t}} of vertices per tree. (For a graph with {{mvar|n}} vertices and {{mvar|r}} terminals, they use {{math|1=''t'' = ''n'' &minus; ''r'' &minus; 1}} added vertices per tree.) Then, they ask for the {{mvar|k}}-minimum spanning tree in this augmented graph with {{math|1=''k'' = ''rt''}}. The only way to include this many vertices in a {{mvar|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  {{mvar|k}}, it is possible for {{mvar|k}}-spanning tree to include only as few edges of the original graph as are needed to connect all the terminals. Therefore, the {{mvar|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.<ref name="rsmr"/>

Even for a graph whose edge weights belong to the set {{math|{1, 2, 3}}}, testing whether the optimal solution value is less than a given threshold is [[NP-complete]]. It remains NP-complete for [[planar graph]]s. 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 {{mvar|k}}-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 algorithms==
Because of the high computational complexity of finding an optimal solution to the {{mvar|k}}-minimum spanning tree, much of the research on the problem has instead concentrated on [[approximation algorithm]]s 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 {{mvar|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,<ref>{{citation
 | last1 = Chlebík | first1 = Miroslav
 | last2 = Chlebíková | first2 = Janka | author2-link = Janka Chlebíková
 | doi = 10.1016/j.tcs.2008.06.046
 | issue = 3
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | pages = 207–214
 | title = The Steiner tree problem on graphs: Inapproximability results
 | volume = 406
 | year = 2008| doi-access = free
 }}.</ref> the same is true for the {{mvar|k}}-minimum spanning tree problem.

The best approximation known for the general problem achieves an approximation ratio of 2, and is by {{harvtxt|Garg|2005}}.<ref>{{citation
 | last = Garg | first = Naveen
 | title = Proceedings of the 37th Annual ACM Symposium on Theory of Computing
 | contribution = Saving an epsilon: a 2-approximation for the k-MST problem in graphs
 | pages = 396–402 | doi = 10.1145/1060590.1060650
 | year = 2005| title-link = Symposium on Theory of Computing
 | s2cid = 17089806
 }}.</ref> This approximation relies heavily on the primal-dual schema of {{harvtxt|Goemans|Williamson|1992}}.<ref>{{citation
 | last1 = Goemans | first1 = M. | author1-link = Michel Goemans
 | last2 = Williamson | first2 = P.  
 | journal = [[SIAM Journal on Computing]]
 | title = A general approximation technique for constrained forest problems
 | volume = 24 | issue = 2 | pages = 296–317 | doi = 10.1137/S0097539793242618
 | year = 1992| citeseerx = 10.1.1.55.7342| s2cid = 1796896 }}.</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 {{harvtxt|Arora|1998}}.<ref>{{citation
 | last = Arora | first = Sanjeev  | authorlink = Sanjeev Arora
 | journal = [[Journal of the ACM]]
 | title = Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
 | volume = 45 | issue = 5 | pages = 753–782 | doi = 10.1145/290179.290180
 | year = 1998| s2cid = 3023351 | doi-access = free}}.</ref>

==References==
{{reflist}}

==External links==
* [https://www.csc.kth.se/~viggo/wwwcompendium/node71.html Minimum k-spanning tree in "A compendium of NP optimization problems"]
* [https://web.archive.org/web/20060505084136/http://iridia.ulb.ac.be/~cblum/kctlib/ KCTLIB], KCTLIB -- A Library for the Edge-Weighted K-Cardinality Tree Problem


[[Category:Spanning tree]]
[[Category:NP-hard problems]]