Augmenting forests to meet odd diameter requirements

Given a graph G=(V,E)G=(V,E) and an integer D≥1D≥1, we consider the problem of augmenting GG by the smallest number of new edges so that the diameter becomes at most DD. It is known that no constant approximation algorithms to this problem with an arbitrary graph GG can be obtained unless P=NPP=NP. For a forest GG and an odd D≥3D≥3, it was open whether the problem is approximable within a constant factor. In this paper, we give the first constant factor approximation algorithm to the problem with a forest GG and an odd DD; our algorithm delivers an 8-approximate solution in O(|V|3)O(|V|3) time. We also show that a 4-approximate solution to the problem with a forest GG and an odd DD can be obtained in linear time if the augmented graph is additionally required to be biconnected.