Metric TSP와 Christofides' algorithm

0. Introduction

TSP는 가장 잘 알려진 NP - complete 문제 중 하나고, 문제 형태가 간단하기 때문에 다양한 variation이 존재한다.

오늘 다룰 것은 거리 공간(Metric) 위에서의 TSP인데, Metric TSP란 정점들을 어떤 거리 공간 \(X\) 위의 점으로 생각할 수 있고, 간선의 weight가 다음의 조건을 만족하는 거리 함수의 형태로 주어지는 TSP를 말한다.

- \(d : X^2 \to \mathbb{R}\)

- \(d(x,x) = 0 \)

- \(d(x,y) = d(y,x) \)

- \(\color{blue}{d(x,y)+d(y,z) \ge d(x,z)}\) (삼각부등식)

논의가 어렵게 느껴진다면, 그냥 2차원 평면 위에서 TSP 문제를 푼다고 생각해도 좋다.

안타깝게도 Metric TSP 역시 NP-complete 문제이다. 하지만 일반적인 TSP에 비해 조건이 추가된 만큼, 다양한 근사 해법이 존재한다. 즉, 최적해의 TSP cost를 \(h(T)\)라고 두면, 어떤 양수 \(\epsilon\)에 대해

$$h(approx) \le \epsilon \cdot h(T)$$

를 만족하는 알고리즘들이 있고, 가장 간단한 2개를 오늘 소개할 것이다.

---

1. \(\epsilon = 2\)

간단한 관찰을 통해, TSP cost 가 최적해의 2배를 넘지 않는 알고리즘을 찾아낼 수 있다.

그래프의 MST (Minimum Spanning Tree)를 \(O(E\alpha (V))\) 시간 만에 구할 수 있는데, TSP는 결국 하나의 cycle이기 때문에 TSP의 cost는 MST의 모든 간선 cost를 다 더한 값보다 크거나 같다.

$$h(T) \ge h(MST) $$

이 때 MST 상의 임의의 점에서 DFS 탐색을 하는 방식으로 점을 순회하는데, 이미 방문한 점이 있다면 그 점을 제외하는 방식으로 순회를 하자. (그림 참조)

빨간색 간선이 실제 TSP 경로, 보라색 간선이 DFS 탐색 경로이다.

즉, 위의 방식으로 순회를 하면 TSP cost가 \(2h(M)\)이하임을 알 수 있다. 따라서

$$ h(\text{DFS}) \le 2h(M) \le 2h(T) $$

이다.

---

2. \(\epsilon = 1.5\) (Christofides' algorithm)

여기서 조금 더 관찰을 하면 1.5배까지 cost를 줄일 수 있다.

MST에서 차수가 홀수인 정점들의 집합을 \(O\)라고 하자.

그림에서는 노란색 정점이 \(O\)에 속한다.

이 때 정점의 차수를 다 더한 값은 짝수이므로, \(|O|\)는 짝수이다. \(|O| = 2k\)라고 하자.

따라서 \(O\)의 정점들을 모아놓은 완전그래프에서^[각주:1] Minimum Perfect Matching \(P\)를 찾을 수 있다. 

이는 \(O(V^2 E)\), 또는 \(O(E\sqrt{V})\)만에 수행될 수 있으므로 poly - time이다.

이 때 Minimum Perfect Matching은 Matching 중에 최소의 cost를 가지므로, 임의로 잡아준 Matching보다 항상 cost가 작거나 같다.

따라서 Optimal Tour \(T\)에서 \(O\)의 정점들만 뽑아서 순회하는 경로를 \(N\)이라고 하자. 그렇다면 $$h(N) \le h(T)$$가 성립하는데, \(N\)에서 

\(1, 3, \cdots 2k-1\)번째 edge를 선택한 Perfect Matching \(N_1\), 

\(2, 4, \cdots 2k\)번째 edge를 선택한 PM \(N_2\)를 생각할 수 있다.

이 때 \(h(P) \le min(h(N_1),h(N_2)) \le h(N)/2 \le h(T)/2\)이다.

마지막으로, MST에 \(P\)의 정점들을 추가한 새로운 그래프 \(G\)를 생각해 보자.

이 때 \(G\)의 모든 정점들은 짝수 차수를 가지기 때문에, TSP tour에 있는 모든 edge들과 그래프의 edge를 대응시킬 수 있다.

조금 더 설명하자면, 1.의 그림에서 가장 아래쪽의 3개 에지는 각각 (3,8), (4,9), (5,10)으로 2회씩 count된다. 하지만 \(G\) 상에서는 각각의 edge를 1회씩만 count하면 되도록 잘 피해갈 수 있다는 의미이다.

따라서 \(h(\text{Christofides}) \le h(M) + h(P) \le 1.5h(T)\)이다. \(\blacksquare\)

---

1. 모든 점들은 점 간의 '거리'를 cost로 갖는 에지로 연결되어 있다. MST에서 생략되어 있을 뿐 [본문으로]