[Algorithms] Bounded Degree-Spanning Tree Problem | 제한된 차수를 가진 신장 트리 문제

Bounded Degree-Spanning Tree Problem (BD-ST Problem)

제한된 차수를 가진 신장 트리 문제

[Input]
Graph \(G = (V,E)\)
Positive Real Number \(k\)

[Query]
모든 정점의 차수가 \(k\) 이하인 \(G\)의 신장 트리가 존재하는가?

---

Mechanism (원리)

---

Implementation (구현)

---

Performance (성능)

---

Verification (검증)

Theorem. Bounded Degree Spanning Tree Problem는 NP-Complete이다.

* 어떤 문제가 NP-Complete이려면, NP이고 NP-Hard이어야 한다.
- 이 때, NP-Hard임을 증명하는 것은
  기존에 NP-Hard임이 증명된 문제를 해당 문제로 Reduction하여 논리적 관계를 보이는 것으로 이루어진다.

* 최장 경로 문제가 NP-완비임을 보이기 위해,
  기존에 NP-완비임이 증명된 "해밀토니안 경로 문제"를 이용한다.

pf)
1. BD-ST Problem이 NP(Nondeterministic Polynomial) 임을 증명한다.
모든 정점의 차수가 \(k\) 이하인 신장 트리가 주어질 때,
(즉, BD-ST 문제의 Query에 Yes로 답할 수 있는 근거가 주어질 때)
트리임을 확인하고,
모든 정점의 차수가 \(k\) 이하임을 확인하는 작업은
\(O(|V|)\) 시간에 가능하다.
(즉, 다항식 시간에 가능하다.)
그러므로, BD-ST Problem은 NP이다.
(BD-ST Problem의 최적해를 찾는데 다항식 시간이 걸린다는 뜻이 아니라,
최적해가 이미 주어져있다면, 그것이 최적해라는 근거를 보이는데 다항식 시간이 걸린다는 의미이다.
이것이 "Nondeterministic"의 의미이다.)

2. Hamiltonian Path Problem \(\leq_{p}\) BD-ST Problem 임을 증명한다.
BD-ST 문제보다 먼저 NP-Complete임이 밝혀진 Hamiltonian Path 문제를 통해
BD-ST 문제가 NP-Hard임을 보인다.

Hamiltonian Path 문제의 Instance \(G = (V, E)\)가 주어지면,
이를 그대로 BD-ST 문제의 Instance로 사용한다.
(즉, Reduction에는 시간이 소요되지 않는다.)

Hamiltonian Path 문제에서의
"해밀토니안 경로가 존재하는가?"에 해당되는 Query는
BD-ST 문제에서의
"모든 정점의 차수가 2 이하인 \(G\)의 신장 트리가 존재하는가?"에 해당되는 Query로
대치할 수 있다.

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

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

---

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

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