Geek Answers Handbook

Np-completeness in a fenced degree

I understand why the Spanning Tree Associated Steppes is considered NP. Full with degree or 2 (this is a case of the Hamiltonian way problem), but I don’t understand why this applies to degrees> 2. If someone can explain why this is NP Full problem for degree> 2, It would be very useful

+8
graph tree np-complete
source share
1 answer

Well, I think you can make a simple shortcut from the instance limited to 2 to the instance of General k.

Intuitivly, we connect to each node of the original graph of the new k-2 nodes. Therefore, each spanning tree must contain edges k-2 from the original node to the new nodes that we connected to it, and a spanning tree of degree no higher than k exists if there is a spanning tree of degree no higher than 2 for the original graph.

The formal reduction will be:

F (V, E) = (V ', E') when: V '= {(v, i) | v is in the original graph, 0 <i <k + 1), E '= EU {((v, 0), (v, i))}, and I do not write a formal proof of correctness, because in the end we do not We are in the math forum.

Good luck and hope this helped :)

+10
source share

More articles:


All Articles