The k-bounded spanning tree problem is where you have an undirected graph G(V,E)

Question

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!

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.