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에 대해 cap(S ∩ Ai, T ∩ Ai) ≥ key(vi, Ai−1)임을 보이면, vn이 활성이고 An = V이므로 i = n에서 cap(S, T) = cap(S ∩ An, T ∩ An) ≥ key(vn, An−1) = key(t, V\{t})를 얻는다.

활성 정점을 등장 순서대로 나열한 것에 대한 귀납법을 사용한다.

기저 (첫 번째 활성): 첫 번째 활성이 vi이면 v1, ⋯, vi−1이 모두 같은 쪽에 있으므로 Ai−1 안에는 컷을 가로지르는 간선이 없다. Ai에서 컷을 가로지르는 간선은 vi와 Ai−1 사이의 간선뿐이고 그 합은 key(vi, 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).
  • 귀납 가설과 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)이다. ■

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). s와 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.