A linear programming approach to increasing the weight of all minimum spanning trees

Given a graph where increasing the weight of an edge has a nondecreasing convex piecewise linear cost, we study the problem of finding a minimum cost increase of the weights so that the value of all minimum spanning trees is equal to some target value. Frederickson and Solis-Oba gave an algorithm for the case when the costs are linear. We give a different derivation of their algorithm, and we slightly extend it to deal with convex piecewise linear costs. We formulate the problem as a combinatorial linear program and show how to produce primal and dual solutions. © 2008 Wiley Periodicals, Inc.