Editing Minimum spanning tree (section)

== Fractional variant{{Anchor|fractional}} ==
There is a fractional variant of the MST, in which each edge is allowed to appear "fractionally". Formally, a '''fractional spanning set''' of a graph (V,E) is a nonnegative function ''f'' on ''E'' such that, for every non-trivial subset ''W'' of ''V'' (i.e., ''W'' is neither empty nor equal to ''V''), the sum of ''f''(''e'') over all edges connecting a node of ''W'' with a node of ''V''\''W'' is at least 1. Intuitively, ''f''(''e'') represents the fraction of e that is contained in the spanning set. A '''minimum fractional spanning set''' is a fractional spanning set for which the sum <math>\sum_{e\in E} f(e)\cdot w(e)</math> is as small as possible.

If the fractions ''f''(''e'') are forced to be in {0,1}, then the set ''T'' of edges with f(e)=1 are a spanning set, as every node or subset of nodes is connected to the rest of the graph by at least one edge of ''T''. Moreover, if ''f'' minimizes<math>\sum_{e\in E} f(e)\cdot w(e)</math>, then the resulting spanning set is necessarily a tree, since if it contained a cycle, then an edge could be removed without affecting the spanning condition. So the minimum fractional spanning set problem is a relaxation of the MST problem, and can also be called the '''fractional MST problem.'''

The fractional MST problem can be solved in polynomial time using the [[ellipsoid method]].<ref name=":1">{{Cite Geometric Algorithms and Combinatorial Optimization}}</ref>{{Rp|page=248}} However, if we add a requirement that ''f''(''e'') must be half-integer (that is, ''f''(''e'') must be in {0, 1/2, 1}), then the problem becomes [[NP-hard]],<ref name=":1" />{{Rp|page=248}} since it includes as a special case the [[Hamiltonian cycle problem]]: in an <math>n</math>-vertex unweighted graph, a half-integer MST of weight <math>n/2</math> can only be obtained by assigning weight 1/2 to each edge of a Hamiltonian cycle.