Stoer-Wagner 전역 최소 컷 (Global Minimum Cut)

정의

Stoer-Wagner 알고리즘 은 무방향 가중치 그래프 에서 source/sink 없이 가장 작은 컷 (global minimum cut) 을 찾는 알고리즘. 시간 복잡도 O(VE + V^2 log V) with adjacency list + heap. 1994 년 Mechthild Stoer 와 Frank Wagner 가 고안.

문제 상황과 동기

그래프를 두 컴포넌트로 나누는 간선 가중치 합이 최소 인 partition 찾기.

• naive: 가능한 모든 partition (2^(V-1) 개) 검사. 지수 시간.
• flow 기반: 임의의 s-t 쌍 고정 → min s-t cut (max-flow). 모든 쌍 (O(V^2)) 에 대해 flow 를 돌리면 O(V^2 * maxflow). 너무 느림.
• Stoer-Wagner: s-t min cut 을 V-1 번 만 계산 (한 번의 phase 당 한 쌍), 전체 O(VE + V^2 log V).

핵심 통찰: 임의의 두 정점 s, t 에 대해 min s-t cut 을 구하고, 그 컷이 global min cut 이 아니면 s 와 t 를 병합해도 상관없다 (global min cut 은 s 와 t 를 분리하지 않는다면 두 정점이 같은 쪽에 있으므로 병합해도 무방).

시각화

핵심 아이디어

Phase (Minimum s-t Phase Cut)

각 phase 에서 가장 “tight” 하게 연결된 정점을 차례로 선택 (Prim 과 유사한 maximum adjacency search). 마지막 두 정점 s (마지막에서 두 번째), t (마지막) 가 선택되면, t 의 인접 간선 가중치 합 = phase cut weight.

phase(G):
    A = {initial vertex}
    while A ≠ V:
        v = argmax_{v ∉ A} (total weight to A)
        A = A ∪ {v}
        last_two = [s, t]  # s = 직전, t = 마지막
    cut_weight = sum of weights from t to all vertices
    if cut_weight < global_min: update global_min
    merge(s, t)            # s 와 t 를 하나의 supernode 로 병합

Correctness

• Phase cut δ(t) 는 s 와 t 를 분리하는 어떤 컷보다 작거나 같다 (모든 컷에 대해 w(A) ≤ w(C) 형태로 증명).
• 따라서 phase cut 은 현재 그래프에서 s 와 t 를 분리하는 minimum cut.
• Global min cut 이 s 와 t 를 분리하면 phase cut 이 곧 정답. 분리하지 않으면 s, t 가 같은 쪽에 있으므로 병합해도 global min cut 값이 변하지 않음.

알고리즘

StoerWagner(G):
    global_min = ∞
    original = copy of vertices
    while |V| > 1:
        run phase on G to get s, t, cut_weight
        global_min = min(global_min, cut_weight)
        merge s and t (원래 정점 수는 유지, 간선 재조정)
    return global_min

구현

// Stoer-Wagner O(VE + V^2 log V)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
​
struct Edge { int v; ll w; };
​
ll stoer_wagner(vector<vector<Edge>>& adj) {
  int n = adj.size();
  vector<int> merged(n, 0);
  ll ans = INF;
​
  for (int phase = 0; phase < n - 1; phase++) {
      vector<ll> weight(n, 0);
      vector<bool> added(n, false);
      int s = -1, t = -1;
​
      for (int i = 0; i < n - phase; i++) {
          int u = -1;
          for (int j = 0; j < n; j++) {
              if (merged[j] || added[j]) continue;
              if (u == -1 || weight[j] > weight[u]) u = j;
          }
          added[u] = true;
          s = t; t = u;
          for (auto& e : adj[u]) {
              if (!merged[e.v] && !added[e.v])
                  weight[e.v] += e.w;
          }
      }
​
      ans = min(ans, weight[t]);
      if (ans == 0) break;
​
      // merge s into t (s = -1 on first phase, skip)
      if (s != -1) {
          merged[s] = true;
          for (auto& e : adj[s]) {
              if (!merged[e.v]) {
                  bool found = false;
                  for (auto& e2 : adj[e.v])
                      if (e2.v == t) { e2.w += e.w; found = true; break; }
                  if (!found) adj[e.v].push_back({t, e.w});
              }
          }
          for (auto& e : adj[t])
              if (e.v == s) { e.v = t; break; }
          for (auto& e : adj[t])
              if (e.v == t) { e.w = 0; break; }
      }
  }
  return ans;
}
​
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m; cin >> n >> m;
  vector<vector<Edge>> adj(n + 1);
  for (int i = 0; i < m; i++) {
      int a, b; ll c; cin >> a >> b >> c;
      adj[a].push_back({b, c});
      adj[b].push_back({a, c});
  }
  cout << stoer_wagner(adj) << "\n";
}

# Stoer-Wagner O(VE + V^2 log V)
import sys
input = sys.stdin.readline
INF = 10**18
​
def stoer_wagner(adj):
  n = len(adj)
  merged = [False] * n
  ans = INF
​
  for phase in range(n - 1):
      weight = [0] * n
      added = [False] * n
      s = t = -1
​
      for _ in range(n - phase):
          u = -1
          for v in range(n):
              if merged[v] or added[v]:
                  continue
              if u == -1 or weight[v] > weight[u]:
                  u = v
          added[u] = True
          s, t = t, u
          for v, w in adj[u]:
              if not merged[v] and not added[v]:
                  weight[v] += w
​
      ans = min(ans, weight[t])
      if ans == 0:
          break
​
      if s != -1:
          merged[s] = True
          merged_edges = {}
          for v, w in adj[s]:
              if not merged[v]:
                  merged_edges[v] = merged_edges.get(v, 0) + w
          for v, w in merged_edges.items():
              found = False
              for i, (vv, ww) in enumerate(adj[v]):
                  if vv == t:
                      adj[v][i] = (t, ww + w)
                      found = True
                      break
              if not found:
                  adj[v].append((t, w))
          for i, (v, w) in enumerate(adj[t]):
              if v == s:
                  adj[t][i] = (t, w)
                  break
​
  return ans
​
n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
  a, b, c = map(int, input().split())
  adj[a].append((b, c))
  adj[b].append((a, c))
print(stoer_wagner(adj))

4 5
1 2 1
1 3 2
2 3 3
2 4 4
3 4 5

3

복잡도

변형 / 활용

Minimum Cut in Unweighted Graph

가중치 1 로 두면 minimum edge cut (최소 간선 개수로 그래프 분리). Stoer-Wagner 사용 가능.

2-Way Cut 외 K-Way

Stoer-Wagner 는 2-way cut 전용. K-way cut 은 NP-hard (K ≥ 3).

Image Segmentation / Graph Clustering

전역 최소 컷은 이미지 분할 (GrabCut) 등에서 그래프의 자연스러운 분할점 발견.

함정

1. 방향 그래프

Stoer-Wagner 는 무방향 그래프 전용. 방향 그래프는 s-t cut 정의가 달라 사용 불가.

2. 병합 구현 실수

s 와 t 병합 시 간선 가중치 합산 (w(s, v) + w(t, v)) 을 누락하면 이후 phase 의 가중치가 잘못됨.

3. 0 가중치 조기 종료

weight[t] == 0 이면 이미 분리된 컴포넌트가 존재. 조기 종료 가능 (더 작을 수 없음).

BOJ 연습 문제

참고

• 네트워크 플로우
• 최대 유량 최소 컷 정리
• 최소 컷