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 問題と同じくらい難しいことを証明します。

コメントで、あなたの割り当てはハミルトニアン パスの問題から還元することであると述べたことに注意してください。質問では、ハミルトン パスの問題に還元しようとしていると述べました。

ハミルトニアン パスは常に 2 (ハミルトニアン サイクルの場合は 0) の葉を持つスパニング ツリーであるため、制約付き MST 問題を使用してハミルトン パスの問題を簡単に解くことができます。

于 2013-04-04T09:15:28.427 に答える