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: Anais do III Encontro de Teoria da Computação, 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.