Maximum Leaf Spanning Tree

Input

Graph $G = (V, E)$, positive integer $K \leq |V|$.

Question

Is there a spanning tree for $G$ in which $K$ or more vertices have degree 1?

Classes

• NP-complete

Comments

Remains NP-complete if $G$ is regular of degree 4 or if $G$ is planar with no degree exceeding 4.

Proofs

NP-complete

Transformation from Dominating Set (Garey & Johnson, 1979).

Reducible from

• Dominating Set

References

• Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co.