leejseo's profile image

leejseo

July 11, 2023 12:00

이 글에서는 cost function이 metric인 경우에 대해서만 논의한다.

1. Introduction

외판원 문제(Traveling Salesman Problem)와 s-t 경로 외판원 문제(s-t path TSP)는 다음과 같이 정의된다.

Traveling Salesman Problem. 완전 그래프 $G = (V, E)$ 와 간선 집합 $E$ 상의 metric cost function $c$가 있을 때, $G$의 모든 정점을 순회하고 돌아오는 최소 cost의 cycle을 구하여라.

s-t Path Traveling Salesman Problem. 완전 그래프 $G = (V, E)$ 와 그 상의 두 정점 $s$, $t$ 및 간선 집합 $E$ 상의 metric cost(length) function $\ell$ 이 있을 때, $s$ 에서 시작하여 $G$ 의 나머지 모든 정점을 순회하고 $t$ 에서 끝나는 최소 cost의 path를 구하여라.

이 둘은 모두 NP-완전 문제로, 다항 시간 내에 해결할 수 있는 가능성이 희박한 것으로 간주된다. 고로, 이 두 문제 모두 근사 알고리즘을 찾기 위한 여러 연구가 진행되었다. 잘 생각해보면, s-t 경로 외판원 문제를 근사하는 것이 외판원 문제를 근사하는 것 보다 어려움이 알려져 있다.

가장 유명한 결과로는 최소 스패닝 트리를 찾고, “잘못된 차수의 정점”들을 매칭을 통해 고치는 Christofides’ Algorithm이 있으며, 이는 1.5-approximation algorithm임(최악의 경우에도 최적 cycle의 1.5배 이내의 cost를 가지는 cycle을 찾음)이 알려져 있다. Christofides’ algorithm은 1976년 부터 최근까지 TSP 문제에 대해 가장 좋은 근사 알고리즘이었다.

반면, Christofides’ algorithm은 s-t 경로 외판원 문제에 대해서는 1.5의 근사비를 제시하지는 못한다. Christofides’ algorithm의 근사비가 5/3(=1.666…)이 되는 입력 또한 존재하기 때문이다. 이를 뛰어넘는 추가적인 개선은 오랜 기간 없었으나, 최근 10여년간 An, Kleinberg, and Shmoys의 연구를 필두로 후술할 Linear Programming에 기반한 많은 연구가 진행되었다. Linear Programming(LP)을 이용하여 여러 문제들을 할 때 다음과 같은 framework이 널리 활용되며, s-t 경로 외판원 문제에 대한 연구 또한 마찬가지이다.

• 문제를 Integer Linear Programming의 형태로 나타낸다.
• 정수 조건을 실수 조건으로 완화한 LP relaxation을 해결하여 “fractional” solution을 얻는다.
• LP를 풀어서 얻은 fractional solution을 기반으로 여러 기법을 적용하여 원래 문제의 제약 조건을 만족하는 정수 해를 하나 얻어낸다. 이 때, (당연하지만) 최대한 좋은 정수해를 찾아내도록 노력한다.

2010년대 후반에는 s-t 경로 외판원 문제에 대한 1.5-approximation algorithm 또한 제시되었다. 이 글에서는 s-t 경로 외판원 문제에 대한 1.5-approximation algorithm을 소개한다.

참고로, s-t 경로 외판원 문제가 외판원 문제보다 근사하기 어려움은 자명하나, 2010년대 후반, 그 역 또한 성립한다는 사실이 알려졌다. 그 후, 2020년대 들어 $(1.5-\varepsilon)$-approximation algorithm에 대한 결과가 소개되며, 두 문제 모두 1.5의 벽이 깨지게 되었다. 다만, 이 부분은 글의 scope를 벗어난다.$\newcommand{\T}{\mathcal{T}} \newcommand{\B}{\mathcal{B}}$

2. Preliminaries

Path-variant Held-Karp relaxation은 s-t 경로 외판원 문제의 입력에 대해 답을 찾는 것을 linear programming 형태로 formulation 한 것이다. 아래의 제약 조건에서 정수 조건을 추가하면 s-t 경로 외판원 문제에 대한 답을 찾는 것과 정확하게 동일함을 알 수 있다.

\[\begin{align*} \text{minimize} & & \sum_{e \in E} \ell(x_e) & \\ \text{subject to} & & x(\delta(S)) \ge 1 & & \forall S \subsetneq V, \lvert\{s, t\} \cap S\rvert = 1, S \neq \varnothing\\ & & x(\delta(S)) \ge 2 & & \forall S \subsetneq V, \lvert\{s, t\} \cap S\rvert \neq 1, S \neq \varnothing\\ & & x(\delta(\{s\})) = x(\delta(\{t\})) = 1\\ &&x(\delta(\{v\})) = 2 & & \forall v \in V \setminus \{s, t\}\\ & & x \ge \vec 0. \end{align*}\]

여기에서, $\delta(S)$ 는 정점 컷 $(S, \bar S)$ 에 대응되는 간선 집합을 나타내며, 벡터 $x$와 집합 $A$에 대해 $x(A) = \sum_{a \in A} x_a$ 를 나타낸다.

Held-Karp relaxation의 feasible region을 나타내는 polytope을 $P_{HK}$ 로 표기하자. Spanning tree polytope $P_{ST}$ 를 다음과 같이 정의 한다면,

\[P_{ST} = \left\{ x \in \mathbb{R}^E_{\ge0} : \begin{align*} x (E) &= \vert V\vert - 1 \\ x(E[W]) &\le \vert W\vert - 1 & \forall W \subseteq V, W \neq \varnothing \end{align*} \right\}\]

$P_{HK}$를 $P_{ST}$ 기반으로 다음과 같이 나타낼 수도 있음을 쉽게 확인할 수 있다:

\[P_{HK} = \left\{x \in \mathbb{R}_{\ge 0}^E : \begin{align*} x \in P_{ST} \\ x(\delta(v)) = 2 && \forall v \neq s,t \\ x(\delta(v)) = 1 & &v = s, t\end{align*} \right\}.\]

Held-Karp relaxation을 통해 LP 식을 얻었으니 ellipsoid method 등을 이용해 다항 시간에 fractional solution을 구할 수 있겠다고 생각할 수 있겠으나, 사실 이는 자명하지 않다. 왜냐하면, constraint의 개수가 exponential 하게 많기 때문이다. 다행히도, 어떤 점이 위반하는 constraint들이 있을 때 그 중 하나를 찾는 것은 minimum cut을 계산하여 다항 시간에 할 수 있기 때문에, 결론적으로 이 LP는 다항 시간에 해결할 수 있다.

어떤 정점 집합 $T$에 대해 minimum $T$-join 은 다음과 같이 정의된다:

• $T \subseteq V$ 와 $J \subseteq E$ 에 대해 $J$가 $T$-join 임은 $G’ = (V, J)$ 상에서의 홀수 차수 정점 집합이 정확하게 $T$ 임을 의미한다.

악수 정리에 의해 minimum $T$-join 은 $T$ 의 크기가 짝수일 때만 정의됨을 알 수 있다.

다음 조건을 만족하는 임의의 벡터 $y$에 대해 $y$의 cost는 minimum $T$-join의 cost 이상임을 쉽게 확인할 수 있다.

• $y(\delta(S)) \ge 1$ for every $S\subseteq V,\vert S\cap T \vert \equiv 1 \pmod 2$
• $y \ge \vec 0$

이러한 $y$ 들은 $T$-join에 대응되는 incidence vector들의 convex hull과 $\mathbb{R}_{\ge 0}^E$ 의 민코프스키 합으로 나타낼 수 있음을 쉽게 확인할 수 있고, fractional $T$-join dominator라고 부르며, minimum $T$-join의 크기를 분석하는 용도로 주로 활용된다.

3. Algorithm

LP 기반 s-t 경로 외판원 문제에 대한 근사 알고리즘은 기본적으로 다음과 같은 framework을 따라간다.

• Held-Karp relaxation을 통해 정의된 LP의 최적해 $x^\star$ 를 구한다.
• $x^\star$를 바탕으로 spanning tree $\T$를 구한다.
• $\T$에서 차수가 “잘못된” 정점 집합 $T$ 를 구한다.
  • $T$ 의 원소는 차수가 짝수인 ${s, t}$ 의 원소이거나 차수가 홀수인 $V \setminus {s, t}$ 의 원소임으로 정의된다.
• minimum $T$-join $J$를 구한다.
• $\T \cup J$ 상에서 $s$ 에서 $t$ 로의 Eulerian path를 구할 수 있다.
• 위에서 구한 오일러 경로를 따라가며 중복 방문 정점은 건너뛰는 방식으로 Hamiltonian path $H$를 얻는다.

여기에서 가장 중요한 단계는 spanning tree $\T$ 를 구하는 것이다. 좋은 $\T$ 를 구할 수 있다면, $\ell(\T)$가 작을 뿐만 아니라 $\ell(J)$ 또한 작아 좋은 approximation ratio를 얻을 수 있을 것이기 때문이다.

1.5-approximation 알고리즘에서는 다음을 만족하는 $\T$, $z$를 찾는 것에 주목한다:

• $\ell(\T) \le OPT$
• $\ell(z) \le OPT$
• $z/2$ 가 fractional $T$-join dominator

여기에서, $OPT$ 는 원래 문제의 최적해의 길이를 의미한다.

이러한 $\T$, $z$를 찾을 수 있다면, $\ell(H) \le \ell(T) + \ell(z/2) \le 1.5OPT$ 의 결과를 얻을 수 있을 것이다. 저자들의 motivation은 $x^\star$ 외의 다른 좋은 $y \in P_{HK}$ 를 들고와서 $z := x^\star/2 + y/2$ 로 정의하는 것이다. 이렇게 정의 했을 때 $z$ 가 위의 조건들을 만족하려면 $y$ 는 어떤 성질을 만족해야 할까?

• 먼저, $\ell(x^\star) \le OPT$ 가 성립하기 때문에, $\ell(y) \le OPT$ 면 $\ell(z) \le OPT$ 는 만족한다.

• $z/2$ 가 fractional $T$-join dominator 이기 위해서는 모든 odd cut $C$ 에 대해 $x^\star(\delta(C)) + y(\delta(C)) \ge 4$ 를 만족해야 한다.

  • 만약, $C$ 가 $s$-$t$ cut이 아니라면, $x^\star(\delta(C)) + y(\delta(C)) \ge 2 + 2 = 4$ 가 된다.
  • $C$가 $s$-$t$ cut이고, $x^\star(\delta(C)) \ge 3$ 이라면, 역시 $x^\star(\delta(C)) + y(\delta(C)) \ge 3 + 1 = 4$ 가 된다.
  • 따라서, odd $s$-$t$ cut $C$가 $x^\star(\delta(C)) < 3$ 인 경우에 대해서만 cut의 capacity가 큰 $y$ 를 찾으면 된다.

$x \in P_{HK}$ 에 대해 $\B(x)$를 다음과 같이 정의하자:

\[\B(x) = \{ C \subseteq V : s \in C, t \not\in C, x^\star(\delta(C)) < 3 \}.\]

그리고 $s$-$t$ cut의 어느 family $\B$ 에 대해 $y \in P_{HK}$ 가 $\B$-good 임을 모든 $B \in \B$ 에 대해 다음 중 하나 이상이 성립함으로 정의하자:

• $y(\delta(B)) \ge 3$
• $y(\delta(B)) = 1$ 이고, $\delta(B)$ 의 간선들 중 단 하나만 $y$ 값이 1이고 나머지는 $y$ 값이 0이다

이렇게 family $\B$ 를 정의해주면, Hamiltonian path 그 자체 또한 $\B$-good이 되므로, $y$ 를 $\B(x^\star)$-good points 중 $\ell(y)$를 minimize 하는 것으로 잡으면 $\ell(y) \le OPT$ 를 얻을 수 있다. 이를 바탕으로 저자들은 다음과 같은 알고리즘을 제시했다.

• Path-variant Held-Karp relaxation을 해결하여 $x^\star$ 를 구한다.
• $\ell(y)$를 최소화 하는 $\B(x^\star)$-good point $y \in P_{HK}$를 찾는다.
• $y$에 대한 support graph에서 shortest spanning tree $\T$를 구한다.
• $\T$의 차수가 잘못된 정점 $T$들에 대한 minimum $T$-join $J$를 구하고, $\T \cup J$ 를 shortcut 한다.

참고로, 2번째 단계에서 찾는 $y \in P_{HK}$ 의 존재성은 앞서 확인했고, (Hamiltonian path 그 자체가 $\B(x^\star)$-good 임) $y \in P_{HK}$ 이므로 $y$의 support graph가 연결되어 있으므로 3번째 단계 또한 잘 정의된다.

3.1. Approximation Ratio

이 알고리즘의 approximation ratio가 1.5임을 보이기 위해서는 $z := x^\star/2 + y/2$ 에 대해 $z/2$가 fractional $T$-join dominator 임을 보이면 충분하고, 이는 앞서 살펴본 바와 같이 $C$가 odd $s$-$t$ cut 이고 $x^\star(\delta(C)) < 3$ 인 경우에 대해서만 확인해보면 충분하다.

Lemma 1. 알고리즘의 approximation ratio는 1.5다.

Proof. $x^\star(\delta(C)) < 3$ 이라 가정하자. 그러면 (1) $y(\delta(C)) > 3$ 이거나, (2) $\delta(C)$ 의 간선들 중 단 하나만 $y$ 값이 1이고, 나머지는 $y$ 값이 0일 것이다.

• Case 1: $x^\star(\delta(C)) \ge 1$ 이므로, $\frac{z}{2}(\delta(C)) \ge 1$
• Case 2: $y_e > 0$ 인 유일한 $e \in \delta(C)$를 잡자. $\vert \T \cap \delta(C) \vert > 0$ 이므로, $\T \cap \delta(C) = {e}$ 가 된다. 그런데, 간단한 논증을 통해 $\vert \T \cap \delta(C)\vert$ 가 0이 아닌 짝수임을 확인할 수 있고, 고로 이 경우는 애초에 불가능하다. $\square$

이로써, 실제로 위 알고리즘이 1.5의 approximation ratio를 가짐을 살펴봤다.

3.2. Finding a $\B(x^\star)$-good Point Minimizing $\ell(y)$

이제, 알고리즘이 다항 시간에 작동함을 확인하기 위해서는 2번째 단계인 $\ell(y)$ 를 최소화 하는 $\B(x^\star)$-good point를 찾는게 다항 시간에 가능함을 확인하면 된다. 여기에서 다음 성질이 사용된다.

Lemma 2. Held-Karp polytope의 원소 $z$에 대해 $\B(z)$ 는 $n^4$ 이하의 크기를 가지며, $O(mn^4)$ 시간 내지는 랜덤 알고리즘을 기반으로 $O(n^4 \log^2 n)$ 시간에 계산할 수 있다.

Proof. $H$를 $V$를 정점 집합으로 하며 $F := supp(z) \cup { st }$를 간선 집합으로 하는 그래프로 정의하자. $z_H \in \mathbb{R}^F$를 $z_H(e) = z(e)$ for $e \in supp(z)$ and $z_H(st) = 1$ 로 하여 정의하자. 그러면 $\B(z) = { C \subseteq V : s \in C, t \not\in C, z_H(\delta_H(C)) < 4}$ 로 다시 쓸 수 있음을 알 수 있다. 따라서, $\B(z)$의 모든 cut의 $z_H$ 값은 가장 작은 컷의 최대 2배인데, Karger’s algorithm의 증명을 생각해보면 최대 $n^4$개 이내로 존재할 수 있음을 알 수 있고, 이를 응용하여 계산 또한 할 수 있다. $\square$

논문에서는 이를 기반으로 $\B$가 주어졌을 때 다이나믹 프로그래밍을 통해 shortest $\B$-good point를 계산하는데 집중한다.

3.2.1. Observations

어떤 $y \in P_{HK}$가 있다고 생각해보자. $y$에 대해 하나의 coordinate만 1이고 나머지가 0인 $\B$의 원소 $B_1, B_2, \cdots, B_k$를 전부 모아놓고 생각해보면, 이들은 chain을 이루어야 한다. 왜냐하면, 만약 $B_i, B_j$가 intersecting 한다면, $2 = y(\delta(B_i)) + y (\delta(B_j)) \ge y(\delta(B_i - B_j)) + y(\delta(B_j - B_i)) \ge 4$가 되어 모순이기 때문이다. 따라서, $B_0 = \varnothing \subsetneq B_1 (={s}) \subsetneq B_2 \subsetneq \cdots \subsetneq B_k (={t})\subsetneq V = B_{k+1}$ 로 쓸 수 있다. 그러고 $B_{i}$에서 $B_{i+1}$로의 유일한 간선의 두 끝점을 $v_i \in B_i, u_i \in B_{i+1}$ 로 표기하자. ($u_0$와 $v_{k+1}$도 정의하자. 참고로 $u_i = v_{i+1}$ 일 수도 있음에 유의하라.)

앞에서 정의한 $B_i$ 들과 $v_i, u_i$ 들이 주어졌을 때 이걸 실제로 가지는 $\B$-good point 중 가장 짧은 것을 계산하는 상황을 고려하자. $y \in P_{HK}$가 그러한 것이 될 수 있으려면, 최소한 다음의 조건은 만족해야 할 것이다.

• $y(v_iu_i) = 1$
• $y(e) = 0$ for all $e \in \delta(B_i) - {v_iu_i}$
• $y$를 $B_{i+1} - B_i$로 induced 된 $G$의 subgraph로 restrict 했을 때 $u_i$-$v_{i+1}$ path TSP에 대한 Held-Karp solution이 되고, $B_i \cup {u_i} \subseteq B \subseteq B_{i+1} - v_{i+1}$인 cut $B$ 들에 대한 $y$-load들이 3 이상이다.
  • 참고: $u_i = v_{i+1}$ 일 수 있으므로, 시작점과 끝점이 같은 Held-Karp relaxation도 정의해야 하며, 이 경우에는 empty (if $\lvert V \rvert \ge 2$) 혹은 ${0}$ (if $\lvert V \rvert = 1$) 으로 정의한다고 생각하자.

3.2.2. Dynamic Programming

이제 이 관찰들을 바탕으로 $B_i, v_i, u_i$ 들을 찾아보자.

먼저, 다음과 같이 directed graph $H = (N, A)$를 정의하자:

• $N = N^+ \cup N^-$ where
  • $N^+ = {(B, u) \in \B \times V : u \not \in B} \cup {(\varnothing, s)}$
  • $N^- = {(B, v) \in \B \times V : v \in B} \cup { (V, t)}$
• $A = A_{HK} \cup A_E$ where
  • $A_{HK} = {((B^+, u), (B^-, v)) \in N^+ \times N^- : B^+ \subseteq B^-; u, v \in B^- - B^+}$
  • $A_E = {((B^-, v), (B^+, u)) \in N^- \times N^+ : B^- = B^+}$

이 그래프의 간선에 가중치를 줄 것인데, $A_E$의 간선들에는 원본 그래프를 기반으로, $A_{HK}$의 간선들에는 Held-Karp relaxation을 기반으로 가중치를 주자.

• $d(a) = \ell(v, u)$ for $((B, v), (B, u)) \in A_E$
• $a = ((B^+, u), (B^-, v)) \in A_{HK}$에 대해서는 다음 벡터의 길이($\ell$값)으로 $d(a)$를 정의한다.
  • $B^- - B^+$에서의 $u$-$v$ TSP에 대한 Held-Karp solution 중 모든 $B^+$과 $B^-$ 사이의 컷에 대해 크기가 3 이상인 것들 중 길이가 최소인 것

3.2.3. Construction

이제, $H$에서 $(\varnothing, s) - (V, t)$ 최단 경로를 다이나믹 프로그래밍을 통해 구했다고 가정하자.

이 최단 경로상의 정점들을 순서대로 $(B_0 = \varnothing, u_0 = s), (B_1, v_1), \cdots, (B_k, u_k), (V = B_{k+1}, t = v_{k+1})$로 쓰자. $H$의 정의에서 $B_0 \subsetneq B_1 \subsetneq \cdots \subsetneq B_{k+1}$ 임을 알 수 있다.

이제, 각 $0 \le i \le k$ 에 대해 $x^i \in \mathbb{R}^E$ 를 $a = ((B_i, u_i), (B_{i+1}, v_{i+1})) \in E_{HK}$ 에 대해 $d(a)$ 값을 주는 $B^- - B^+$ 에서 $u$-$v$ TSP에 대한 Held-Karp solution이라 하자. (단, 이를 $E$ 차원으로 확장해서 생각하자.)

이제, $y$를 $y := \sum_{i=0}^k x^i + \sum_{i=1}^k \chi^{v_iu_i}$ 로 하여 정의하자. 그러면, $H$ 상에서의 거리 함수 정의에 의해 $\ell(y)$와 최단 경로의 길이가 같게 된다. 이제 우리는 다이나믹 프로그래밍이 잘 정의되며, 이러한 $y$가 우리가 찾는 $y$임을 보일 것이다.

3.2.4. Proofs

우리가 구한 $y$가 Held-Karp polytope에 속함과 $\B$-good 임은 간단한 논증을 통해 확인할 수 있다. 이제, $y$가 optimal 함을 보이자.

Lemma 3. $H$ 상에서 $(\varnothing, s)-(V, t)$ 최단 경로의 길이를 $d^\star $ 라 할 때,
$ d^\star \le \min {\ell(z) : z \in P_{HK}, z \text{ is } \B-good }$.

Proof. 임의의 $\B$-good point $z \in P_{HK}$를 고정하고, $d^\star \le \ell(z)$를 보이자. 먼저, $\B_z \subseteq \B$를 $\delta(B)$가 $z$ 상에서 정확히 하나의 간선에서만 1이고 나머지에서 0인 $B \in \B$ 들의 집합으로 정의하자. 앞에서와 같은 argument로 $\B_z$의 원소들이 chain을 이룸을 확인할 수 있고, 앞에서와 같이 $B_i, v_i, u_i$를 $\B_z$에 대해 정의할 수 있다.

이제, $d^\star \le \ell(z)$임을 보여야 하는데, 이를 위해서는 $H$ 상에서 “어떤” 경로의 길이가 $\ell(z)$ 이하임을 보이면 된다. $(B_0, u_0), \cdots, (B_{k+1}, v_{k+1})$ 경로의 길이 $\bar d$가 $\ell(z)$ 이하임을 보이자.

각 $0 \le i \le k$ 에 대해 다음과 같이 정의된 벡터 $z^i \in \mathbb{R}^E$가 $B_{i+1} - B_i$ 에서 $u_i$-$v_{i+1}$ path TSP에 대한 Held-Karp polytope에 속함은 간단한 계산을 통해 확인할 수 있다.

• $z^i(e) = z(e)$ for all $e \in E[B_{i+1} - B_i]$
• $z^i(e) = 0$ for all the other edges

따라서, 간선 $a = ((B_i, u_i), (B_{i+1}, v_{i+1}))$의 길이를 정하는데 사용된 LP solution $x^i$ 에 대해 $\ell(x^i) \le \ell(z^i)$가 되므로, $ \ell(z) = \sum_{i=0}^k \ell(z^i) + \sum_{i=1}^k \ell(v_iu_i) \ge \sum_{i=0}^k \ell(x^i) + \sum_{i=1}^k \ell(v_iu_i) = \bar d \ge d^\star $ 이 된다. $\square$

참고로, 다이나믹 프로그래밍으로 최단 경로를 구하는 과정에서 해결하는 LP의 개수는 $O(\lvert N \rvert ^ 2) = O(\lvert \B \rvert^2 n^2)$ 으로 bound 되기 때문에 다항 시간에 최단 경로를 구할 수 있다.

Reference

• https://arxiv.org/pdf/1805.04131.pdf
• https://arxiv.org/abs/1110.4604