ON THE APPROXIMABILITY OF SOME MAXIMUM SPANNING TREE PROBLEMS

We study the approximability of some problems which aim at finding spa nning trees in undirected graphs which maximize, rather than minimize, a single objective function representing a form of benefit or usefuln ess of the tree. We prove that the problem of finding a spanning tree which maximizes the number of paths which connect pairs of vertices an d pass through a common are can be polynomially approximated within 9/ 8. It is known that this problem can be solved exactly in polynomial t ime if the graph is 2-connected; we extend this result to graphs havin g at most two articulation points. We leave open whether in the genera l case the problem admits a polynomial time approximation scheme or is MAX-SNP hard and therefore not polynomially approximable within 1 + e psilon, 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 di ameter, 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 no t polynomially approximable within any constant factor, unless P=NP. T he 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).