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)叶子的生成树。