On the Approximability of the Minimum Subgraph Diameter Problem

• Arthur Pratti Dadalto Unicamp
• Fábio Luiz Usberti Unicamp
• Mário César San Felice UFSCar

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.

Referências

Bálint, V. (2003). The non-approximability of bicriteria network design problems. Journal of Discrete Algorithms, 1:339–355.

Papadimitriou, C. H. and Steiglitz, K. (1998). Combinatorial Optimization: Algorithms and Complexity. Courier Corporation.

Plesnik, J. (1981). The complexity of designing a network with minimum diameter. Networks, 11:77–85.

Trevisan, L. (2014). Inapproximability of Combinatorial Optimization Problems. In: Paradigms of Combinatorial Optimization, chapter 13, pages 381–434. Wiley-Blackwell.

Williamson, D. P. and Shmoys, D. B. (2011). The Design of Approximation Algorithms. Cambridge University Press, New York, NY, USA, 1st edition.