Reduction of Leaf constrained MST p‌r‌o‌b‌l‌e‌m to Hamiltonian path p‌r‌o‌b‌l‌e‌m

Question

It is well known that computing a spanning tree that has the minimum possible number of leaves is NP complete. But I cannot figure out a polynomial time reduction of this problem to the hamiltonian path problem.

My exponential reduction:

if(hamiltonian path exists for whole graph) 
    min leaves = 1;
    return;
else
    for each vertex of the graph
        if(hamiltonian path exists for this graph after removing the vertex and its incident edges)
            min leaves = 2;
            return;
    continue similarly for the graph deleting 2 vertices, 3 vertices, 4vertices,... until you get a minimum spanning tree with some minimum number of leaves.

So, in the worst case, this algorithm will make a total of

(N choose 1) + (N choose 2) + (N choose 3) + ....(N choose N) = 2^N

calls to the hamiltonian path problem . Hence reduction is exponential.

Please suggest a polynomial time reduction for this problem.

Answer 1

The idea of reducing the algorithm is that if you can show that the Hamiltonian Path problem can be solved using the constrained MST problem, (with a polynomial time reduction), then any polynomial time solution to the MST problem would allow you to solve the Hamiltonian Path problem in polynomial time. As this is impossible, it would prove the constrained MST problem cannot be solved in polynomial time.

What you are trying to do is the opposite - proving that the Hamiltonian Path problem is at least as hard as the constrained MST problem.

Note that you stated in the comments that your assignment was to reduce from the Hamiltonian Path problem, and in the question you said you were trying to reduce to the Hamiltonian Path problem.

You can easily solve the Hamiltonian Path problem using the constrained MST problem, as a Hamiltonian Path will always be a spanning tree with 2 (or 0 for a Hamiltonian Cycle) leaves.