  For complexity of the heterogeneous minimum spanning forest problem has not
been determined, we reduce 3-SAT which is NP-complete to 2-heterogeneous
minimum spanning forest problem to prove this problem is NP-hard and spread
result to general problem, which determines complexity of this problem. It
provides a theoretical basis for the future designing of approximation
algorithms for the problem.
