Multibojective problems on the spanning trees of a graph

In this note, the authors establish for multiobjective problems on spanning trees the exponential computational complexity (intractability) of the problem of determining a complete set of alternatives; in the case of two heterogeneous criteria they prove that this problem is NP-hard. The authors establish in some sense a hierarchy of complexities of such problems and single out classes of problems which are solvable with the help of statistically effective (polynomial) algorithms.