Approximating the Maximum Internal Spanning Tree problem

Given an undirected connected graph G$G$ we consider the problem of finding a spanning tree of G$G$ which has a maximum number of internal (non-leaf) vertices among all spanning trees of G$G$. This problem, called Maximum Internal Spanning Tree problem, is clearly NP-hard since it is a generalization of the Hamiltonian Path problem. From the optimization point of view the Maximum Internal Spanning Tree problem is equivalent to the Minimum Leaf Spanning Tree problem. However, the two problems have different approximability properties. Lu and Ravi proved that the latter has no constant factor approximation–unless P = NP–, while Salamon and Wiener gave a linear-time 2-approximation algorithm for the Maximum Internal Spanning Tree problem.