[Algorithms] Hamiltonian Cycle Problem | 해밀토니안 사이클 문제

Hamiltonian Cycle Problem

해밀토니안 사이클 문제

[Input]
- Undirected Graph \(G = (V, E)\)

[Query]
- \(G\)에 해밀토니안 사이클이 존재하는가?

- 해밀토니안 사이클 결정 문제는 TSP로 Reduction(변환)하여 해결할 수 있다.
  그 근거는 아래 포스트를 참고하자.

* NP-Completeness Theory (NP-완비성 이론) (URL)

[Algorithms] NP-Completeness Theory | NP-완비성 이론

* Traveling Sales Person Problem (TSP) (방문 판매원 문제) (URL)

[Algorithms] Traveling Sales Person Problem (TSP) | 방문 판매원 문제

* No-Hamiltonian Cycle Problem (역해밀토니안 사이클 문제)

[Input]
- Undirected Graph \(G = (V, E)\)

[Query]
- \(G\)에 해밀토니안 사이클이 존재하지 않는가?

- 이 문제는 Co-NP에 속한다.

---

Reduction : HAM-Cycle \(\to\) TSP Decision Problem (해밀토니안 사이클 문제에서 TSP 결정 문제로의 변환)

- 왼쪽 그림과 같은 그래프에서 해밀토니안 사이클이 존재하는지를 조사한다.
- 해밀토니안 사이클을 조사하기 위해, HAM-CYCLE 문제 사례의 그래프를 TSP 문제로 변환하여 풀이하는데,
  TSP의 필요조건으로, 주어진 그래프가 Complete Graph(완전 그래프)이어야 하므로,
  없는 간선은, Weight가 \(\infty\)인 간선으로 대치하여 생각한다.
- 그리고, HAM-CYCLE 문제의 사례에서 이미 존재해있던 간선들의 Weight는 1로 초기화한다.
  (TSP 문제에서는 주어진 그래프가 Weighted Graph이어야 한다.)

1) TSP 문제상에서 \(\infty\)인 간선을 포함하지 않고 Cycle을 찾은 경우 (그림 (b))
- 이 경우, HAM-Cycle 문제에 대한 답은 Yes이다. (그림 (a))
  (HAM-Cycle의 길이가 유한하다.)

2) TSP 문제상에서 \infty인 간선을 포함하여 Cycle을 찾은 경우 (그림 (d))
- 이 경우, HAM-Cycle 문제에 대한 답은 No이다. (그림 (c))
  (HAM-Cycle의 길이가 무한하다.)

- 즉, HAM-Cycle의 문제 사례가 주어지면,
  이를 TSP 문제로 변환하여 해결할 수 있다.
- 즉, HAM-Cycle 문제 사례 그래프에서 "해밀토니안 사이클이 존재하는가?"는
  TSP 문제 사례 그래프에서 "길이가 \(|V|\)인 해밀토니안 사이클이 존재하는가?"로
  변환하여 문제를 풀 수 있다.
- 즉, TSP 문제를 다항식 시간에 풀 수 있는 방법이 발견되면,
  HAM-Cycle 문제도 다항식 시간에 풀 수 있게 된다.
  (그러나 NP-완비성 이론에서 언급했던 것 처럼,
   TSP와 같은 NP-완비군 문제를 다항식 시간에 풀 수 있는 방법은 아직까지 발견되지 않았다.)

---

Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)

Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)