Augmenting trees to meet biconnectivity and diameter constraints

Given a graph G = (V, E) and a positive integer D, we consider the problem of finding a minimum number of new edges E' such that the augmented graph G' = (V, E boolean OR E') is biconnected and has diameter no greater than D. In this note we show that this problem is NP-hard for all fixed D, by employing a reduction from the DOMINATING SET problem. We prove that the problem remains NP-hard even for forests and trees. but in this case we present approximation algorithms with worst-case bounds 3 (for even D) and 6 (for odd D). A closely related problem of finding a minimum number of edges such that the augmented graph has diameter no greater than D has been shown to be NP-hard by Schoone et al. [21] when D = 3, and by Li et al. [17] when D = 2.