众所周知，计算具有最小可能叶数的生成树是NP完全的但是我不能求出这个问题的多项式时间约化为哈密顿路径问题。
我的指数减少：
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.
因此，在最坏的情况下，该算法将使
(N choose 1) + (N choose 2) + (N choose 3) + ....(N choose N) = 2^N
对哈密顿路径问题的调用。因此减少是指数的。
请对此问题建议多项式时间缩减。
最佳答案
减少算法的思想是，如果你能证明哈密顿路径问题可以用约束的mst问题来解决（用多项式时间减少），那么任何多项式时间的mst问题的解都可以让你在多项式时间内解决哈密顿路径问题。由于这是不可能的，它将证明约束MST问题不能在多项式时间内求解。
你要做的是相反的——证明哈密顿路径问题至少和约束mst问题一样困难。
注意，你在评论中说，你的任务是从哈密顿路径问题减少，在这个问题上，你说你试图减少到哈密顿路径问题。
使用约束mst问题可以很容易地解决哈密顿路径问题，因为哈密顿路径始终是具有2个（或0个哈密顿循环）叶的生成树。