Abstract.
A k -spanner of a connected graph G=(V,E) is a subgraph G' consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two vertices in G' is larger than the distance in G by no more than a factor of k . This paper concerns the hardness of finding spanners with a number of edges close to the optimum. It is proved that for every fixed k , approximating the spanner problem is at least as hard as approximating the set-cover problem.
We also consider a weighted version of the spanner problem, and prove an essential difference between the approximability of the case k=2 and the case k\geq 5 .
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received October 30, 1998; revised March 4, 1999, and April 17, 2000.
Rights and permissions
About this article
Cite this article
Kortsarz, G. On the Hardness of Approximating Spanners. Algorithmica 30, 432–450 (2001). https://doi.org/10.1007/s00453-001-0021-y
Issue Date:
DOI: https://doi.org/10.1007/s00453-001-0021-y