Minimal Spanning Tree Search Problem

Definition

Minimal Spanning Tree Search Problem

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

Output: An edge set $F^{\ast }\subseteq E$ such that $T^{\ast }=(V,F^{\ast })$ is a minimal spanning tree of $G$:

$$F^{\ast }\in \underset{\begin{array}{c}F\subseteq E\\ (V,F)\text{ is a spanning tree of }G\end{array}}{\mathrm{argmin}}\sum _{e\in F}w(e).$$

Any edge set attaining this minimum is a valid output. The task is therefore to construct an optimal tree, rather than merely determine whether one exists.