2

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

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

请为此问题提出多项式时间缩减建议。

4

1 回答 1

2

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

您尝试做的是相反的事情 - 证明哈密顿路径问题至少与受约束的 MST 问题一样难。

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

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

于 2013-04-04T09:15:28.427 回答