Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419693 | Discrete Applied Mathematics | 2013 | 6 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yong Gao, Donovan R. Hare, James Nastos,