해밀턴 경로 문제에 대한 리프 제한 MST 문제의 감소

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 문제만큼 어렵다는 것을 증명하려는 반대입니다. 당신이 당신의 할당에서 해밀턴 경로 문제를 을 줄일 수 있었다 의견 진술하고 질문에 당신은 당신이 에 해밀턴 경로 문제를 줄이기 위해 노력하고 있다고 말했다

참고.

해밀턴 경로는 항상 2 (또는 해밀 토니안주기의 경우 0)가있는 스패닝 트리가되므로 제한된 MST 문제를 사용하여 쉽게 해밀턴 경로 문제를 해결할 수 있습니다.