On the approximability of some maximum spanning tree problems

We study the approximability of some problems which aim at finding spanning trees in undirected graphs which maximize, rather than minimize, a single objective function representing a form of benefit or usefulness of the tree. We prove that the problem of finding a spanning tree which maximizes the number of paths which connect pairs of vertices and pass through a common are can be polynomially approximated within 9/8. It is known that this problem can be solved exactly in polynomial time if the graph is 2-connected; we extend this result to graphs having at most two articulation points. We leave open whether in the general case the problem admits a polynomial time approximation scheme or is MAX-SNP hard and therefore not polynomially approximable within 1 + epsilon, for any fixed epsilon > 0, unless P=NP, On the other hand, we show that the problems of finding a spanning tree which has maximum diameter, or maximum height with respect to a specified root, or maximum sum of the distances between all pairs of vertices, or maximum sum of the distances from a specified root to all remaining vertices, are not polynomially approximable within any constant factor, unless P=NP. The same result holds for the problem of finding a lineal spanning tree with maximum height, and this solves a problem which was left open in Fellows et al, (1988).