Problem Detail: The $k$-bounded spanning tree problem is where you have an undirected graph $G(V,E)$ and you have to decide whether or not it has a spanning tree such that each vertex has a degree of at most $k$. I realize that for the case $k=2$, this is the Hamiltonian path problem. However I’m having trouble with cases where $k>2$. I tried thinking about it in the sense that you can add more nodes onto an existing spanning tree where $k=2$ and maybe since the base is NP complete, adding things on will make it NP-complete as well, but that doesn’t seem right. I’m self-studying CS and am having trouble with theory, so any help will be appreciated!
Asked By : user17199
Answered By : Yuval Filmus
The question has been asked before on stackoverflow, where it has also been answered. The idea is to connect each vertex to $k-2$ new vertices. The new graph has a $k$-bounded spanning tree iff the original graph has a hamiltonian path. Mohit Singh and Lap Chi Lau gave a polytime algorithm which find a $(k+1)$-bounded spanning tree if a $k$-bounded spanning tree exists. So we can determine the minimum degree of a spanning tree up to an uncertainty of $1$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/24246
