On the Approximability of the Minimum Subgraph Diameter Problem

  • Arthur Pratti Dadalto
  • Fábio Luiz Usberti
  • Mário César San Felice
DOI: https://doi.org/10.5753/etc.2018.3169

Resumo


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.

Publicado
26/07/2018
Como Citar

Selecione um Formato
DADALTO, Arthur Pratti; USBERTI, Fábio Luiz; FELICE, Mário César San. On the Approximability of the Minimum Subgraph Diameter Problem. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3169.