코스워크가 모두 끝난 요즘 과거에 제대로 이해하지 못했거나 미처 보지 못하고 넘어간 것들을 제대로 공부해 보고자 교과서를 처음부터 다시 보고 있습니다. 공부하는 중에 개인적으로 정리도 할 겸 공유할 만한 내용이 있으면 포스팅을 하고자 합니다.
이번에 다룰 문제는 슈타이너 트리 문제(Steiner tree problem)입니다. 이 문제는 잘 알려진 최소 스패닝 트리 문제(minimum spanning tree problem, MST)의 일반화된 문제입니다. MST는 크루스칼 알고리즘(Kruskal's algorithm)이나 프림 알고리즘(Prim's algorithm) 등을 활용하여 다항 시간에 해결할 수 있다는 것이 잘 알려져 있습니다. 하지만 슈타이너 트리 문제는 NP-난해(NP-hard)하다고 알려져 있죠. 따라서 P와 NP가 같지 않는 한 이 문제를 다항 시간에 풀 수 있는 방법은 없습니다.
그러므로 우리는 슈타이너 트리 문제를 근사적으로 해결하는 방법을 모색해야 합니다. 이번 시간에는 그 첫 번째 단계로서 슈타이너 트리 문제를 해결하는 2-근사 알고리즘에 대해서 알아보도록 하겠습니다. 아래는 다음과 같이 이루어져 있습니다.
- 문제 정의
- 삼각 부등식의 일반성
- 2-근사 알고리즘
문제 정의
최소 스패닝 트리 문제는 어떤 그래프 \(G = (V, E)\)와 간선 비용 \(c : E \rightarrow \mathbb{Q}\)가 주어졌을 때 모든 정점에 연결되어 있으면서(spanning) 순환이 없는(acyclic) 서브그래프(subgraph)(즉, 스패닝 트리) 중에서 비용이 가장 적은 것을 찾는 문제였습니다.
앞에서 설명한 대로 슈타이너 트리 문제는 이 문제를 일반화한 것입니다. 여기서는 모든 정점을 연결할 필요가 없고, 대신 입력과 함께 주어지는 특정한 정점들만 연결해 주면 됩니다. 다시 말해, 입력으로 그래프 \(G = (V, E)\)와 음이 아닌 간선 비용 \( c : E \rightarrow \mathbb{Q}_+ \)와 함께 특별한 정점의 집합 \( R \subseteq V \)이 주어집니다. 이때 우리는 \(R\)을 단말(terminal)이라고 부르고, 그외의 정점 \( V \setminus R \)을 슈타이너 정점(Steiner node)라고 부릅니다. 우리의 목표는 그래프 위에서 모든 단말을 연결하는 가장 비용이 적은 트리를 찾는 것입니다. 여기서 슈타이너 정점은 연결되어도 되고 연결되지 않아도 괜찮습니다. 그러한 트리를 우리는 슈타이너 트리(Steiner tree)라고 부릅니다.
슈타이너 트리가 최소 스패닝 트리 문제를 일반화한다는 것은 쉽게 보일 수 있는데, 그 이유는 만약 \( R = V \)라면 슈타이너 트리가 곧 스패닝 트리와 동일해지기 때문입니다.
삼각 부등식의 일반성
임의의 세 정점 \( u, v, w \in V \)에 대해, \( u \)와 \( v \)를 연결하는 데 들어가는 비용이 \( u \)와 \( w \)를 잇고 \( w \)와 \( v \)를 잇는 비용보다 비싸지 않을 때, 다시 말해, \[ c(u, v) \leq c(u, w) + c(w, v) \]를 만족할 때, 우리는 비용이 삼각 부등식(triangle inequality)을 만족한다고 말합니다. 참고로 이를 만족하기 위해서는 입력으로 주어지는 그래프는 모든 정점이 서로 연결된 완전 그래프여야 합니다.
어떤 비용에 대해 무언가를 최적화하는 문제에서는 주어지는 비용이 삼각 부등식을 만족한다고 가정하는 경우가 더러 있습니다. 실례로 제가 따로 포스팅한 외판원 문제(traveling salesman problem)나 k-센터 문제(k-center problem)에서도 입력으로 들어오는 비용이 삼각 부등식을 만족해야 적절한 근사 알고리즘을 얻을 수 있었죠. 그렇지 않으면 P와 NP가 같지 않는 한 근사 알고리즘이 존재하지 않기 때문입니다.
슈타이너 트리 문제는 어떨까요? 위 정의에 따르면 슈타이너 트리 문제에서는 비용이 삼각 부등식을 만족할 필요는 없습니다. 하지만 놀랍게도, 우리는 삼각 부등식을 만족하는 비용이 주어졌을 때만 고려해도 임의의 입력에 대해서 문제를 해결할 수 있다는 것을 보일 수 있습니다. 다시 말해, 일반성을 잃지 않고 비용이 삼각 부등식을 만족한다고 가정할 수 있다는 것입니다. 이는 삼각 부등식이 아니면 근사적으로 해결할 수 없는 외판원 문제나 k-센터 문제와는 결이 다르기는 하지만, 여전히 삼각 부등식을 가정한다면 분석할 때 큰 도움이 될 것입니다. 이번 절에서는 어째서 삼각 부등식을 가정해도 괜찮은지 알아보겠습니다.
이를 증명하기 위해서는 삼각 부등식을 만족하는 입력에 대한 \(\rho\)-근사 알고리즘 \(\mathcal{A}\)가 있다고 가정했을 때, 이를 가지고 임의의 입력에 대한 \( \rho \)-근사 알고리즘을 만들 수 있으면 됩니다. 그 방법은 다음과 같습니다.
알고리즘 1. Reduction
입력: 그래프 \(G = (V, E)\), 간선 비용 \( c : E \rightarrow \mathbb{Q}_+ \), 단말 \(R \subseteq V\)
출력: 슈타이너 트리
- \(H \gets ( V, \binom{V}{2} )\)
- 임의의 두 정점 \( u, v \in V \)에 대해 \(d(u, v)\)를 \(G\) 위에서 \(u\)에서 \(v\)로 가는 최단 경로(shortest path)의 비용으로 정의한다.
- \( T \gets \mathcal{A}(H, d, R) \)
- \( S \gets \emptyset \)
- \(T\) 위의 간선 \( (u, v) \)마다 다음을 수행한다.
- \( P_{u, v} \)를 \(G\) 위에서 \( u \)에서 \(v\)로 가는 최단 경로라고 한다.
- \( S \gets S \cup P_{u, v} \)
- 만약 \(S\)에 순환(cycle)이 있으면 순환 위의 간선 하나를 지우며, 이를 순환이 없을 때까지 반복한다.
- \(S\)를 반환한다.
이제 이 알고리즘이 슈타이너 문제를 해결하는 \( \rho \)-근사 알고리즘이라는 것을 증명해 봅시다. 먼저, \( d \)가 삼각 부등식을 만족한다는 것을 보이겠습니다.
정리 1. 최단 경로 메트릭
알고리즘 1에서 \(d\)는 삼각 부등식을 만족한다.
[증명] 만약 \( d(u, v) > d(u, w) + d(w, v) \)를 만족하는 어떤 \( u, v, w \in V \)가 있다고 합시다. \(d\)의 정의에 의해 \(u\)에서 \(v\)로 향하는 최단 경로의 비용보다 \( u \)에서 \(w\)로 향하는 최단 경로의 비용에 \( w \)에서 \(v\)로 향하는 최단 경로의 비용을 합한 것이 더 작다는 뜻입니다. 하지만 \( u \)에서 \(w\)를 거쳐 \(v\)로 향하는 경로도 \( u \)에서 \(v\)로 가는 경로이므로 \( d(u,v) \)가 저렇게 정의되었을 리 만무합니다. □
다음으로 보일 것은 알고리즘 1이 출력하는 결과가 슈타이너 트리이고 그 비용도 저렴하다는 것입니다. 아래에서는 어떤 간선의 집합 \(F \subseteq E\)에 대해, \( c(F) := \sum_{e \in F} c(e) \)로 정의합니다. \(d\)에 대해서도 동일하게 적용됩니다.
정리 2. 비싸지 않은 슈타이너 트리의 반환
알고리즘 1에서 \(S\)는 슈타이너 트리이며, \( c(S) \leq d(T) \)를 만족한다.
[증명] 알고리즘의 단계 6에서는 순환이 있는 경우에만 간선을 하나씩 제거하므로 단계 5가 끝난 후의 \(S\)와 단계 6이 끝난 후의 \(S\)의 도달성(reachability)의 차이는 없습니다. 따라서 단계 5가 끝난 후의 \(S\)에서 임의의 두 단말 \(s, t \in R\)가 연결되어 있으면 됩니다. \( T \)도 슈타이너 트리이므로 분명 \(s\)에서 \(t\)로 가는 경로 \[Q := \langle x_1= s, x_2, \cdots, x_\ell = t \rangle \]가 존재합니다. 그러면 \(G\) 위에서는 분명 \(P_{x_1, x_2}, P_{x_2, x_3}, \cdots, P_{x_{\ell - 1}, x_\ell}\)을 따라서 \( x_1 = s \)에서 \( x_\ell = t \)로 향하는 방법이 존재합니다. 따라서 \( s \)와 \(t\)는 연결되어 있습니다.
다음으로 \(d\)의 정의에 의해 우리는 임의의 \(u, v \in V\)에 대해 \( d(u, v) = c(P_{u, v}) \)임을 알 수 있습니다. 따라서,
\[ c(S) \leq \sum_{(u, v) \in T} c(P_{u, v}) = \sum_{(u, v) \in T} d(u, v) = d(T) \]
가 성립하게 됩니다. □
\(\mathcal{A}\)와 동일한 근사비를 얻기 위해서는 다음의 정리가 필요합니다.
정리 3. 최적해의 유지성
알고리즘 1에서 \( G, c \)의 최적해를 \(S^\star\), \( H, d \)의 최적해를 \(T^\star\)라고 할 때, \( c(S^\star) \geq d(T^\star) \)를 만족한다.
[증명] \( d \)의 정의에 의해서 \(S^\star\)의 각 간선 \( (u, v) \in S^\star \)에 대해, \( c(u, v) \geq d(u, v) \)를 만족합니다. 왜냐하면 \((u, v) \in E\) 그 자체가 \(u\)에서 \(v\)로 향하는 경로가 될 수 있기 때문입니다. 따라서 \( S^\star \)를 그대로 \(H\)에 가지고 오면 \(c(S^\star) \geq d(S^\star)\)임을 알 수 있습니다. 따라서 \(c(S^\star) \geq d(T^\star) \)도 자명합니다. □
이제 알고리즘 1이 동일한 근사비를 갖는 알고리즘이라는 사실을 증명할 수 있습니다.
정리 4. 알고리즘 1의 정확성
알고리즘 1은 슈타이너 트리 문제를 해결하는 \( \rho \)-근사 알고리즘이다.
[증명] 최단 경로를 구하는 것은 다항 시간에 가능하므로 알고리즘 1이 전체적으로도 다항 시간에 동작한다는 것은 쉽게 증명할 수 있습니다. 따라서 \(G, c\) 위의 최적해 \(S^\star\)에 대해, 알고리즘 1이 출력하는 \(S\)가 \( c(S) \leq \rho \cdot c(S^\star) \)를 만족함을 보이기만 하면 됩니다. \(H, d\) 위의 최적해를 \( T^\star \)라고 하면 알고리즘 1의 단계 3에서 반환되는 슈타이너 트리 \(T\)는 \( \mathcal{A} \)에 의해 \( d(T) \leq \rho \cdot d(T^\star) \)를 만족합니다. 따라서 정리 2와 3에 의해, \[ c(S) \leq d(T) \leq \rho \cdot d(T^\star) \leq \rho \cdot c(S^\star) \]가 성립합니다. □
2-근사 알고리즘
위 절에서 우리는 \(G, c\)가 삼각 부등식을 만족한다고 가정해도 일반성을 잃지 않는다는 것을 보였습니다. 이번 절에서는 해당 입력에 대한 2-근사 알고리즘을 소개하도록 하겠습니다.
앞에서 슈타이너 트리 문제가 MST의 일반화된 문제라는 사실을 논의하였습니다. 그러면 MST가 슈타이너 트리를 해결하는데 도움이 될 일은 없을까요? 흥미롭게도 단말만을 연결하는 트리 중에서 가장 작은 비용이 최적 비용의 두 배를 넘지 않는다는 사실을 증명할 수 있습니다. 따라서 다음의 간단한 알고리즘이 2-근사 알고리즘이 되는 것이죠.
알고리즘 2. A 2-approximation algorithm for the Steiner tree
입력: 그래프 \(G = (V, \binom{V}{2}\), 간선 비용 \( c : \binom{V}{2} \rightarrow \mathbb{Q}_+\), 단말 \( R \subseteq V \)
출력: 슈타이너 트리
- \(G\) 위에서 정확히 \(R\)만 연결하는 트리 중 비용이 가장 저렴한 것을 \(S\)라고 하자.
- \(S\)를 반환한다.
일단 이 알고리즘이 슈타이너 트리를 반환한다는 것과 다항 시간에 동작한다는 것은 쉽게 알 수 있습니다. 따라서 남은 것은 이 알고리즘이 출력하는 슈타이너 트리가 최적 비용의 두 배 이내의 비용을 갖는다는 것을 보이는 것입니다. 이를 위해서 우리는 어떤 최적해에서 그것의 비용을 최대 두 배만 내면서 정확히 단말만 연결하는 트리를 만들 수 있다는 것을 보이고자 합니다.
\(G, c\) 위의 한 최적 슈타이너 트리를 \(S^\star\)라고 하겠습니다. \(S^\star\)에 최소한 하나의 슈타이너 정점이 존재한다고 가정하겠습니다. 이렇게 가정해도 괜찮은 이유는 만약 모든 정점이 단말이면 알고리즘 2가 그 자체로 최적해를 출력하기 때문입니다.
우리는 여기서 일반성을 잃지 않고 몇 가지 더 가정할 수 있습니다.
- \(S^\star\)의 리프는 정확히 단말과 일치한다. 따라서, \(S^\star\)의 내부 정점(internal node)은 모두 슈타이너 정점이다.
- \(S^\star\)의 내부 정점의 차수는 항상 3 이상이다.
가정 A가 일반성을 잃지 않는 이유는 다음과 같습니다. 만약 어떤 단말 \(v \in R\)가 \(S^\star\)의 내부 정점이라면, 그 자리에 슈타이너 정점 \(u\)를 새로 만들어 \(v\)에 연결된 모든 \(S^\star\)의 간선을 \(u\)로 연결하고 대신 \(S^\star\)에 \( (u, v) \)를 추가하면 됩니다. 반대로 만약 어떤 슈타이너 정점 \(v \in V \setminus R\)가 리프라면 그 정점과 그에 딸린 \(S^\star\)의 간선을 지워도 여전히 \(S^\star\)는 슈타이너 트리입니다.
가정 B는 삼각 부등식 덕분에 일반성을 잃지 않습니다. 만약 \(v\)가 정확히 \(u\)와 \(w\)에 연결된 차수가 2인 내부 정점이라고 하겠습니다. \(S^\star\)에 \( (u, v) \)와 \( (v, w) \)를 지우고 대신 \( (u, w) \)를 넣어도 삼각 부등식에 의해서 그 비용은 증가하지 않습니다.
이제부터 \(S^\star\)가 위에서 언급한 가정을 모두 만족한다고 하겠습니다. \(S^\star\)의 아무 슈타이너 정점 \(r \in V(S^\star) \setminus R\)을 선택한 후 \(S^\star\)를 \(r\)을 루트(root)로 하는 루티드 트리(rooted tree)로 보겠습니다. 이때, \(S^\star\) 위의 아무 정점 \(u \in V(S^\star) \)에 대해, \(S^\star_u\)를 \(u\)가 루트인 서브트리(subtree)로 정의하고, \(S^\star_u\)의 리프를 \(R_u\)라고 부르겠습니다.
현재 우리의 목표는 \( S^\star \)를 기초로 최대 \(2c(S^\star)\)의 비용을 지불하면서 정확히 \(R\)만을 연결하는 트리 \(T\)를 찾는 것입니다. 놀랍게도 다음 정리는 우리의 목표보다 좀 더 강한 사실을 내포하고 있습니다. 바로 각 서브트리에 대해서 비슷한 명제가 성립한다는 것이죠.
정리 5. 귀납적 증명
한 슈타이너 정점을 루트로 하는 \(S^\star\)에 대해, 각 정점 \(u \in V(S^\star)\)은 다음을 만족하는 트리 \( T_u \)와 경로 \( P^u_1, P^u_2 \)가 항상 존재한다.
- \(T_u \subseteq R_u \times R_u \)는 정확히 \(R_u\)만을 연결하는 트리이다.
- \( P^u_1 \subseteq S^\star_u \)는 \(S^\star\) 위에서 \(R_u\)의 한 정점 \(t^u_1\)과 \(u\)를 잇는 경로이며, \(P^u_2 \subseteq S^\star_u\)는 \(t^u_2 \in R_u\)와 \(u\)를 잇는 경로이다. 이때, \(P^u_1, P^u_2\)는 서로 간선을 공유하지 않는다.
- \( c(T_u) + c(P^u_1) + c(P^u_2) \leq 2 c(S^\star_u) \)를 만족한다.
[증명] \(S^\star\)의 리프에서부터 점차 루트로 올라가면서 귀납적으로 증명하겠습니다. 먼저 \(u \in V(S^\star) \cap R\)가 리프라면, \(T_u = (\{u\}, \emptyset) \), \( P^u_1 = P^u_2 = \langle u \rangle \)로 두겠습니다. 조건 1은 쉽게 보일 수 있습니다. 조건 2는 두 경로 모두 공유할 간선이 없으므로 성립합니다. 마지막으로 조건 3은 모든 값이 0이기 때문에 성립하게 됩니다.
이제 아무 내부 정점 \(u \in V(S^\star) \setminus R\)를 가지고 오겠습니다. 가정 B에 의해서 \(u\)의 자식이 최소 두 개 이상이라는 것을 알 수 있습니다. 이를 모두 \( v_1, \cdots, v_k \)라고 하겠습니다.(단, \(k \geq 2\)) 귀납 가정(induction hypothesis)에 의해 이들은 정리의 조건을 모두 만족합니다.
먼저 \(T_u\)를 만들겠습니다. 이는 귀납 가정에 의해 얻은 \(T_{v_1}, \cdots, T_{v_k}\)를 하나씩 순서대로 연결해서 얻습니다. \(T_{v_1}\)과 \(T_{v_2}\)를 잇기 위해 \( (t^{v_1}_2, t^{v_2}_1) \)을 넣습니다. 또 \( T_{v_2} \)와 \( T_{v_3} \)를 연결하기 위해 \( (t^{v_2}_2, t^{v_3}_1) \)을 집어 넣습니다. 다시 쓰면,
\[ T_u := T_{v_1} \cup (t^{v_1}_2, t^{v_2}_1) \cup T_{v_2} \cup (t^{v_2}_2, t^{v_3}_1) \cup \cdots \cup (t^{v_{k - 1}}_2, t^{v_k}_1) \cup T_{v_K}\]
으로 정의할 수 있습니다. \(T_u\)가 조건 1을 만족한다는 사실은 쉽게 이끌어낼 수 있습니다.
다음은 \( P^u_1 \)과 \( P^u_2 \)를 만들 차례입니다. 이는 위에서 \(T_u\)를 만들 때 사용되지 않은 \( t^{v_1}_1 \)과 \( t^{v_k}_2 \)를 가지고 옵니다. 바로
\[ \begin{array}{rcl} P^u_1 & := & P^{v_1}_1 \cup (v_1, u), \\ P^u_2 & := & P^{v_k}_2 \cup (v_k, u) \end{array} \]로 정의하는 것이죠. \(k \geq 2\)이므로 \( P^{v_1}_1 \)과 \( P^{v_k}_2 \)는 서로 다른 서브트리에 있어서 서로 간선을 공유하지 않습니다. 게다가 \( v_1 \neq v_k \)이기도 하므로 \( P^u_1, P^u_2 \)가 조건 2를 만족한다는 것을 알 수 있습니다.
이렇게 만들어진 \(T_u\)와 \( P^u_1, P^u_2 \)가 조건 3을 만족한다는 것을 보이도록 하죠. 이는 삼각 부등식을 통해 증명할 수 있습니다. \(T_u\)를 만들 때 우리는 \( (t^{v_i}_2, t^{v_{i + 1}}_1) \)(단, \( i = 1, \cdots, k - 1 \))를 연결하여 귀납 가정에서 얻은 서브트리를 엮어 주었습니다. 재밌는 사실은 삼각 부등식에 의해서
\[ c(t^{v_i}_2, t^{v_{i + 1}}_1) \leq c(P^{v_i}_2) + c(v_i, u) + c(u, v_{i + 1}) + c(P^{v_{i + 1}}_1) \]
가 성립한다는 것입니다. 이를 모두 더해주면,
\[ \sum_{i = 1}^{k - 1} c(t^{v_i}_2, t^{v_{i+1}}_1) \leq c(P^{v_1}_2) + c(v_1, u) + \sum_{i = 2}^{k - 1} \left[ c(P^{v_i}_1) + c(P^{v_i}_2) + 2c(v_i, u)\right] + c(P^{v_k}_1) + c(v_k, u) \]
라는 사실을 얻을 수 있습니다. 따라서,
\[ c(T_u) + c(P^u_1) + c(P^u_2) \leq \sum_{i = 1}^k \left[ c(T_{v_i}) + c(P^{v_i}_1) + c(P^{v_i}_2) + 2c(v_i, u) \right] \leq 2 \sum_{i = 1}^k \left[ c(S^\star_{v_i}) + c(v_i, u) \right] = 2c(S^\star_u)\]
를 만족한다는 것을 알 수 있습니다. □
이를 통해 곧바로 우리가 원하는 결과를 얻을 수 있습니다.
정리 6. 알고리즘 2의 정확성
알고리즘 2는 슈타이너 트리 문제를 해결하는 2-근사 알고리즘이다.
[증명] 이 알고리즘이 슈타이너 트리를 출력하며 다항 시간에 동작하는 것은 쉽게 알 수 있습니다. 정리 5를 루트 \(r\)에 대해 적용하면, 조건 3에 의해서 \( c(T_r) \leq 2 c(S^\star) \)임을 알 수 있습니다. 이때, \(T_r\)은 정확히 \(R\)만을 연결하는 트리이고 알고리즘 2는 그러한 트리 중 가장 비용이 작은 것을 반환하므로 정리의 명제가 성립합니다. □
마치며
이것으로 유명한 NP-난해 문제인 슈타이너 트리 문제를 근사적으로 해결하는 방법에 대해서 알아보았습니다. 이 문제는 척 보기에도 실생활에서 매우 요긴하게 쓰일 법한 문제죠. 따라서 이 문제에 대해 수많은 연구가 진행되었습니다. 근사 알고리즘의 분야에서는 역시 근사비를 얼마큼 줄일 수 있냐가 큰 관건이죠. 제가 읽은 것 중에서 가장 좋은 것은 \( (\ln 4 + \epsilon) \approx 1.386 \)의 근사비를 갖는 알고리즘[2]이었습니다. 당시에 그 논문을 읽었을 때 매우 참신해서 경악을 금치 못했던 기억이 납니다. 논문의 난이도는 상당해서 이를 포스팅하기에는 좀 무리가 있지 않을까 싶습니다.
유명한 문제에는 항상 수많은 변형들이 존재합니다. 그 중 하나는 경품 수집 슈타이너 트리 문제(prize-collecting Steiner tree problem)입니다. 번역이 적절한지는 잘 모르겠네요. 이 문제에서는 반드시 연결해야 하는 단말을 주는 대신, 모든 정점이 들어갈 수도 있고, 들어가지 않을 수도 있습니다. 대신, 정점이 연결되지 못하면 벌금(penalty)가 발생하죠. 우리의 목표는 정점 중 몇 개를 골라서 트리로 연결하되, 트리의 간선 비용과 연결되지 못한 정점이 부과하는 벌금의 합이 최소가 되도록 하는 것입니다. 다음에는 이 문제에 대해서 한번 알아보도록 하겠습니다.
잘못된 점을 발견하셨거나 궁금하신 부분이 있으시면 언제든 알려주시기 바랍니다. 고맙습니다. :)
참조
[1] David P. Williamson and David B. Shmoys. The design of approximation algorithms. Cambridge university press, 2011.
[2] Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. "Steiner tree approximation via iterative randomized rounding." Journal of the ACM (JACM) 60, no. 1 (2013): 1-33.