Enumeration of Pareto optimal multi-criteria spanning trees – a proof of the incorrectness of Zhou and Gen's proposed algorithm

The minimum spanning tree (MST) problem is a well-known optimization problem of major significance in operational research. In the multi-criteria MST (mc-MST) problem, the scalar edge weights of the MST problem are replaced by vectors, and the aim is to find the complete set of Pareto optimal minimum-weight spanning trees. This problem is NP-hard and so approximate methods must be used if one is to tackle it efficiently. In an article previously published in this journal, a genetic algorithm (GA) was put forward for the mc-MST. To evaluate the GA, the solution sets generated by it were compared with solution sets from a proposed (exponential time) algorithm for enumerating all Pareto optimal spanning trees. However, the proposed enumeration algorithm that was used is not correct for two reasons: (1) It does not guarantee that all Pareto optimal minimum-weight spanning trees are returned. (2) It does not guarantee that those trees that are returned are Pareto optimal. In this short paper we prove these two theorems.