Tech Report CS-96-05

The Power of Local Optimizations: Approximation Algorithms for Maximun-leaf Spanning Tree (DRAFT)*

Hsueh-I Lu and R. Ravi

January 1996

Abstract:

Given an undirected graph $G$, finding a spanning tree of $G$ with maximum number of leaves is NP-complete. We use the simple technique of local optimization to provide the first approximation algorithms for this problem. Our algorithms run in polynomial time to produce locally optimal solutions. We prove that locally optimal solutions to this problem are globally near-optimal. In particular, we prove that two such algorithms have performance ratios of 5 and 3. The latter algorithm employs more powerful local-improvement steps than the former and hence has higher running time. This may indicate an interesting trade-off between the performance ratios and the running times of the series of algorithms we describe.

(complete text in pdf or gzipped postscript)