The Power of Local Optimization: Approximation Algorithms for Maximum-Leaf Spanning Tree
Hsueh-I Lu, R. Raviy · 2007
Given an undirected graph G, finding a spanning tree of G with the maximum number of leaves is NP-complete [5]. 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 such 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. 1 Introduction Given a simple, undirected graph G = (V; E), suppose we wish to find a spanning tree of G with the maximum number of leaves. This problem finds applications in communication networks, circuit layouts and in other graph-theoretic problems[17]. An interest...