 Theoretical Computer Science

# NP completeness of classes of spanning trees

I am teaching a complexity course, and I want to give some examples of similar looking problems such that one is in P, and the other is NP complete.

This made me think of the following problem: does a given graph contain a spanning tree with a given degree sequence? This is obviously easy for the sequence \$n-1,1,...,1\$ and hard for \$2,...,2,1,1\$. Is there a general answer? ## Solution

Lemke has shown that it is NP-hard to decide whether a cubic graph on \$n=2k\$ vertices has a spanning tree in which \$k+1\$ vertices have degree \$1\$ and \$k-1\$ vertices have degree \$3\$.

P. Lemke:
"The maximum-leaf spanning tree problem in cubic graphs is NP-complete."
IMA publication no. 428, University of Minnesota, Mineapolis, 1988.
https://www.ima.umn.edu/Maximum-Leaf-Spanning-Tree-Problem-Cubic-Graphs-NP-Complete

• Lemke's result implies the NP-completeness of deciding whether there exists a spanning tree without vertices of degree \$2\$.
• A slight modification of Lemke's reduction shows that the following problem is NP-complete for every fixed integer \$p\ge4\$: Decide whether there exists a spanning tree, in which every non-leaf vertex has degree at least \$p\$.
• The same modification shows that the following problem is NP-complete for every fixed integer \$p\ge4\$: Decide whether there exists a spanning tree, in which every vertex degree lies in \$\{1,p\}\$.