Tech Report CS-96-06

A Near-linear-time Approximation Algorithm for Maximum-leaf Spanning Tree

Hsueh-I Lu and R. Ravi

January 1996


Given an undirected graph $G$, finding a spanning tree of $G$ with maximum number of leaves is not only NP-complete but also MAX~SNP-complete. The approximation ratio of the previously best known approximation algorithm for maximum leaf spanning tree is three. However, the high-order running time required by the previous algorithm makes it impractical. In this paper we give a new factor-three approximation algorithm for the same problem. The running time required by our algorithm is almost linear in the size of $G$. This improves the previous algorithm by a factor of $\tilde{\Omega}(mn^3)$, where $n$ is the number of nodes and $m$ is the number of edges.

(complete text in pdf or gzipped postscript)