Minimum spanning tree problem

In graph theory and combinatorial optimization, the minimum spanning tree problem (MST problem) is the computational problem of finding a minimum spanning tree of a given connected edge-weighted undirected graph.

Definition

---

Definition 1 (Minimum spanning tree problem)

Input: A connected edge-weighted undirected graph $G=(V,E)$ with weight function $w:E\to \mathbb{R}$.

Task: Solve

$$\begin{array}{rl}\underset{T\subseteq E}{\min }& w(T)\\ \text{s.t.}& T\text{is a spanning tree of }G\end{array}$$

i.e. find a minimum spanning tree of $G$.

Definition 2 (Minimum spanning tree decision problem)

Input: A connected edge-weighted undirected graph $G=(V,E)$ with weight function $w:E\to \mathbb{R}$, and a bound $k\in \mathbb{R}$.

Question: Does $G$ have a spanning tree $T$ with $w(T)\le k$?

Corollary 1 (Membership in P)

The minimum spanning tree decision problem (Definition 2) lies in P: given a candidate tree $T$, checking $T$ is spanning and computing $w(T)$ takes polynomial time, and by Corollary 1 of Minimum spanning tree a minimizer $T^{\ast }$ can be computed directly in polynomial time using any of the algorithms below, so the two problems are polynomial-time equivalent.

Algorithms

---

Each algorithm below builds a minimum spanning tree by repeatedly adding an edge justified by the cut property (Lemma 1); they differ in how that edge is chosen. Let $n=|V|$ and $m=|E|$.

Algorithm	Strategy	Time complexity
Kruskal’s algorithm	Consider edges in increasing order of weight, adding each edge that does not close a cycle with the edges already chosen	$O(m\log n)$
Prim’s algorithm	Grow a single tree from an arbitrary root, repeatedly adding a minimum-weight edge leaving the tree	$O(m\log n)$ with a binary heap, $O(m+n\log n)$ with a Fibonacci heap
Borůvka’s algorithm	In each round, simultaneously add a minimum-weight edge leaving every current component	$O(m\log n)$