imeimi / Algorithm DB Stoer-Wagner Algorithm
1정의
무방향 가중치 그래프 G = (V, E) (n = |V|, m = |E|, w(u,v) ≥ 0)에서 전역 최소 컷(global minimum cut)은 V를 두 비공집합 S, T = V\S로 분리할 때 S와 T를 연결하는 간선 가중치 합을 최소화하는 분리다. 소스, 싱크를 특정하지 않고 모든 컷 중 최솟값을 구한다.
2알고리즘
key(v, A) = ∑u ∈ A w(u,v)로 정의한다.
Maximum Adjacency Order(MAO): A = ∅에서 시작해 n번 정점을 추가한다. 매번 key(v, A)가 가장 큰 v를 A에 추가한다.
MAO 결과 v1, ⋯, vn에서 마지막 두 정점 s = vn-1, t = vn을 구한다.
2.1보조 정리
MAO v1, ⋯, vn (s = vn-1, t = vn)에 대해, 임의의 s-t 컷 (S, T)에 대해 cap(S, T) ≥ key(t, V\{t}).
vi-1과 vi가 컷의 서로 다른 쪽에 속하면 vi가 활성이라고 정의한다. s ∈ S, t ∈ T이므로 vn은 항상 활성이다. Ai = {v1, ⋯, vi}로 정의한다.
첫 번째 활성이 vi라고 할 때, v1, ⋯, vi-1이 모두 같은 쪽에 있으므로 Ai-1의 모든 간선이 컷을 가로지른다. 따라서 cap(S ∩ Ai, T ∩ Ai) = key(vi, Ai-1).
어떤 활성 vi에 대해 cap(S ∩ Ai, T ∩ Ai) ≥ key(vi, Ai-1)라고 가정하자. vi의 직후 활성을 vj라고 쓰자.
vi+1, ⋯, vj-1은 vi와 같은 쪽에 있으므로 vi, ⋯, vj-1이 모두 같은 쪽에 있다. WLOG vi, ⋯, vj-1 ∈ S, vj ∈ T라고 하자.
- vj ∈ T가 추가될 때 생기는 교차 간선은 S ∩ Aj-1에 있고, vi, ⋯, vj-1 ∈ S이므로 T ∩ Ai-1 = T ∩ Aj-1이다. 따라서 cap(S ∩ Aj, T ∩ Aj) = cap(S ∩ Aj-1, T ∩ Aj-1) + key(vj, Aj-1) − ∑u ∈ T ∩ Ai-1 w(u, vj).
- vi, ⋯, vj-1가 추가될 때 cap(S ∩ A, T ∩ A)가 감소하지 않으므로 cap(S ∩ Aj-1, T ∩ Aj-1) ≥ cap(S ∩ Ai, T ∩ Ai).
- vi의 가정과 MAO 조건에서 cap(S ∩ Ai, T ∩ Ai) ≥ key(vi, Ai-1) ≥ key(vj, Ai-1) ≥ ∑u ∈ T ∩ Ai-1 w(u, vj).
따라서 cap(S ∩ Aj, T ∩ Aj) ≥ key(vj, Aj-1).
vn이 활성이므로 귀납적으로 cap(S, T) = cap(S ∩ An, T ∩ An) ≥ key(vn, An-1) = key(t, V\{t}). ■
2.2전역 최소 컷
전역 최소 컷 C*은 s, t를 같은 쪽 또는 다른 쪽에 두게 된다.
2.2.1s와 t를 다른 쪽에 두는 경우
C*는 어떤 s-t 컷이므로 보조 정리에 의해 cap(C*) ≥ key(t, V\{t}). {t} 대 V\{t}로 고립시키는 컷이 정확히 key(t, V\{t})를 달성하므로, 이 경우 최소 컷은 key(t, V\{t}).
2.2.2s와 t를 같은 쪽에 두는 경우
s와 t를 합친다. 즉 t의 모든 간선을 s로 이동하고 t를 V에서 제거한다. 즉 w'(s,v) = w(s,v) + w(t,v). 그래프의 정점 수가 감소했으므로 재귀적으로 최소 컷을 구할 수 있다.
3시간 복잡도
페이즈는 n−1번이고, 각 페이즈에서 MAO와 합병을 수행한다.
- 단순 구현: MAO에서 매번 key 최댓값 탐색 O(n), 갱신 O(n) → 페이즈당 O(n2). 전체 O(n3).
- 피보나치 힙: extract-max O(log n), decrease-key O(1) 분할 상환. 페이즈당 O(n log n + m). 전체 O(n2 log n + nm).
4참고 문헌
- Stoer, M., & Wagner, F. (1997). A simple min-cut algorithm. Journal of the ACM, 44(4), 585–591.