Reducing the diameter of a unit disk graph via node addition

• We want to reduce the diameter of a unit disk graph by adding as few nodes as possible.
• We prove the NP-hardness of the problem.
• We provide a bi-criteria logarithmic approximation algorithm for the general case.
• We provide a bi-criteria constant approximation algorithm for a large set of instances.

This paper addresses a hop-constrained graph design optimization problem which is related to efficiency and reliability issues of communication protocols in wireless networks. In particular, we study the problem of adding a minimum size set of points to a given unit disk graph in such a way that in the resulting graph any two original points have hop-distance at most a given bound D  . After having proved the hardness of the problem, we propose two different bi-criteria algorithms that, conjunctively, provide logarithmic approximation ratio on both criteria. We remark that our first algorithm, while unable to provide any approximation guarantee in the general case, does yield an (O(1),O(1))(O(1),O(1))-approximation for a wide set of instances.