On the Approximability of the Minimum Subgraph Diameter Problem
Arthur Pratti Dadalto, Fábio Luiz Usberti, Mário César San Felice · 2018
This work addresses the minimum subgraph diameter problem (MSDP) by answering an open question with respect to its approximability. Given a graph with lengths and costs associated to its edges, the MSDP consists in finding a spanning subgraph with total cost limited by a given budget, such that its diameter is minimum. We prove that there is no β-approximation algorithm for the MSDP, for any constant β, unless P = NP. Our proof is grounded on the non-approximability of the minimum spanning tree diameter problem, proven by Bálint in 2013.