algorithm - 将叶约束 MST p‌r‌o‌b‌l‌e‌m 简化为哈密顿路径 p‌r‌o‌b‌l‌e‌m

Question

众所周知，计算具有尽可能少的叶子数的生成树是 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

调用哈密尔顿路径问题。因此减少是指数级的。

请建议针对此问题减少多项式时间。

Answer 1

减少算法的想法是，如果您可以证明哈密顿路径问题可以使用约束 MST 问题(通过多项式时间减少)来解决，那么 MST 问题的任何多项式时间解决方案都将允许您在多项式时间内解决哈密顿路径问题。由于这是不可能的，因此证明约束 MST 问题无法在多项式时间内求解。

您想要做的恰恰相反 - 证明哈密顿路径问题至少与约束 MST 问题一样困难。

请注意，您在评论中表示您的任务是减少自哈密顿路径问题，并且在问题中您说您试图减少哈密顿量路径问题。

您可以使用约束 MST 问题轻松解决哈密顿路径问题，因为哈密顿路径始终是具有 2 个(或哈密顿循环为 0 个)叶子的生成树。