Modifying edges of a network to obtain short subgraphs

AbstractThis paper considers problems of the following type: We are given an edge weighted graph G = (V,E). It is assumed that each edge e of the given network has an associated function ce that specifies the cost of shortening the edge by a given amount and that there is a budget B on the total reduction cost. The goal is to develop a reduction strategy satisfying the budget constraint so that the total length of a minimum spanning tree in the modified network is the smallest possible over all reduction strategies that obey the budget constraint.We show that in general the problem of computing an optimal reduction strategy for modifying the network as above is NP-hard even for simple classes of graphs and linear functions ce. We present the first polynomial time approximation algorithms for the problem, where the cost functions ce are allowed to be taken from a broad class of functions. We also present improved approximation algorithms for the class of treewidth-bounded graphs when the cost functions are linear. Our results can be extended to obtain approximation algorithms for more general network design problems such as Steiner trees and generalized Steiner networks