Search code examples
algorithmnp

how do I reduce this spanning tree problem to np-completeness?

I have the following algorithmic problem:

If I have a graph G=(V,E), does G have a spanning tree with exactly k leaves? Leaves being a vertex with only one neighbor in the spanning tree. Also, i'm not looking for a minimum spanning tree, just a spanning tree.

TO sum up, a solution algortihm would take as inputs a graph G and a number k, and return either true or false, depending on whether G has a spanning tree of k leaves

Example: For this graph:

enter image description here

if k is 6, then my algorithm would output "True" because:

enter image description here

Now I am pretty sure that this problem is np-complete, so I need to perform a reduction from a know np-complete problem.

I just have no idea which problem, and how the reduction should look like, can you help out?

Solution

  • The Hamiltonian path problem is a special case of your problem - a spanning tree with exactly k = 2 leaves is a Hamiltonian path. Testing for the existence of one is NP-complete.