The parametric complexity of graph diameter augmentation

The diameter of a graph is the maximum distance between any pair of vertices in the graph. The Diameter-ttAugmentation problem takes as input a graph G=(V,E)G=(V,E) and a positive integer kk and asks whether there exists a set E2E2 of at most kk new edges so that the graph G2=(V,E∪E2)G2=(V,E∪E2) has diameter tt. This problem is NP-hard (Schoone et al. 1987) [10], even in the t=2t=2 case (Li et al. 1992) [7]. We give a parameterized reduction from Dominating Set to Diameter-ttAugmentation to prove that Diameter-ttAugmentation is W[2]W[2]-hard for every tt.