Approximation algorithms for forests augmentation ensuring two disjoint paths of bounded length

Given a forest F=(V,E) and a positive integer D, we consider the problem of finding a minimum number of new edges E′ such that in the augmented graph H=(V,E∪E′) any pair of vertices can be connected by two vertex-disjoint paths of length ≤D. We show that this problem and some of its variants are NP-hard, and we present approximation algorithms with worst-case bounds 6 and 4. These algorithms can be implemented in O(|V|log|V|) time.