Approximating minimum spanning tree of depth 2
Laurent Alfandari, Vangélis Th. Paschos · International Transactions in Operational Research · 1999
Abstract We prove that the problem of finding, in an undirected graph with non‐negative costs on edges, a minimum cost rooted spanning tree of depth 2 is NP‐hard. We then prove that, in a graph of ordern, this problem cannot be approximated within better thanO)lnn), unless problems in NP can be solved by slightly superpolynomial algorithms. We also prove that the metric version of the problem is MAX‐SNP‐hard and, consequently, cannot be approximated by polynomial time approximation schemes, unless P=NP. We devise approximation algorithms for several restricted cases and, finally, a polynomial time algorithm approximating the general problem within ratio lnn.