A characterization of linearizable instances of the quadratic minimum spanning tree problem

We investigate special cases of the quadratic minimum spanning tree problem (QMSTP) on a graph (G=(V,E)) that can be solved as a linear minimum spanning tree problem. We give a characterization of such problems when G is a complete graph, which is the standard case in the QMSTP literature. We extend our characterization to a larger class of graphs that include complete bipartite graphs and cactuses, among others. Our characterization can be verified in (O(|E|^2)) time. In the case of complete graphs and when the cost matrix is given in factored form, we show that our characterization can be verified in O(|E|) time. Related open problems are also indicated.