A fast algorithm for the bipartite node weighted matching problem on path graphs with application to the inverse spanning tree problem

In this paper, we consider the bipartite node weighted matching problem on a special class of graphs, called path graphs, and develop a highly efficient algorithm for solving it. This matching problem arose while solving the inverse spanning tree problem defined as follows. Given an undirected graph G O = (NO, A 0) with n nodes, m arcs, and an arc cost vector c, and a spanning tree T, the inverse spanning tree problem is to perturb the arc cost vector c to a vector d so that T O is a minimum spanning tree with respect to the cost vector d and the cost of perturbation given by id- cl = (ij)EAldij-cijl is minimum. We show that the dual of the inverse spanning tree problem is-a bipartite node weighted matching problem- on a path graph that contains m nodes and as many as (m-n+l)(n-l) = O(nm) arcs. We first transform the node weighted matching problem into a specially structured minimum cost flow problem and use its special structure to develop an O(n³) algorithm. We next use its special structure more effectively and use a more sophisticated transformation to solve the node weighted matching problem in O(n² log n) time. This approach also yields an O(n² log n) algorithm for the inverse spanning tree problem and improves the previous O(n³) algorithm