Study: NP-Completeness Using the Hamilton Path

I'm preparing for the exams and the final course we need to cover the fullness of NP, but we never had real tutorials for them, and I was just given a bunch of "practice questions" for the exam. I've worked through everything except the last one, and I'm really not sure how to solve it (and asking on the internet so far have published published articles that I don't understand).

The previous 2 questions show that the Hamiltonian Put problem is in the class NP and then show that it was NP-complete, showing that the Hamiltonian cycle problem reduces to it.

This then leads to the 3rd question, in which I cannot seem to be moving forward:

A spanning tree of a graph bounded in length is a spanning tree of maximum degree k (each vertex in the tree is adjacent to at most k edges) for some fixed k. Deciding whether a graph G contains a spanning tree of degree bounded by k = 2 is a Hamiltonian way problem, which is an NP-complete problem, as you just showed. Show that deciding whether a graph G contains a spanning tree of degree bounded k for general k is also an NP-complete problem.

My current attempt at answering this was as follows:

For k = 2, for any vertex V, we can split the graph into 2 different subgraphs that only split the vertex V and return true for the Hamiltonian Track. For k = 3, there is a vertex V for which we can split the graph into 3 different subgraphs that have Hamiltonian paths.

I know this is not true, but I feel like this is on the right track, but not sure how to get to the final goal. Any help would be appreciated.

+3


source to share





All Articles