On the inverse problem of minimum spanning tree with partition constraints

In this paper the authors first discuss the properties of minimum spanning tree and minimum spanning tree with partition constraints. They then concentrate on the inverse problem of minimum spanning tree with partition constraints in which the authors need to adjust the weights of the edges in a network as little as possible so that a given spanning tree becomes the minimum one among all spanning trees that satisfy the partition restriction. Based on the calculation of maximum cost flow in networks, they propose a strongly polynomial algorithm for solving the problem.