On the Approximability of the Minimum Subgraph Diameter Problem - Dadalto, Arthur Pratti; Usberti, Fábio Luiz; San Felice, Mário César (Anais do Encontro de Teoria da Computação (ETC), 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.