imeimi / Algorithm DB

Push-Relabel

1사전유량

방향 그래프 G = (V, E), 소스 s, 싱크 t, 용량 함수 c: V × V → ℝ≥0 (E 밖의 쌍은 0)이 주어진다.

사전유량(preflow) f: V × V → ℝ은 다음 세 조건을 만족한다.

  • 반대칭: f(u,v) = −f(v,u)
  • 용량 제약: f(u,v) ≤ c(u,v)
  • 음이 아닌 초과량: ∀v ∈ V\{s}: e(v) = ∑u∈V f(u,v) ≥ 0

e(v)를 v의 초과량(excess)이라 한다. 사전유량은 s와 t를 제외한 정점에서 흐름 보존을 요구하지 않는다. e(v) > 0이고 v ∉ {s, t}인 정점을 활성 정점(active vertex)이라 한다.

잔여 용량 r(u,v) = c(u,v) − f(u,v).

잔여 그래프 Gf = (V, Ef), Ef = {(u,v) : r(u,v) > 0}.

2높이 함수

n = |V|. 유효 높이 함수(valid height function) h: V → ℤ≥0는 다음 조건을 만족한다.

  • h(s) = n, h(t) = 0
  • ∀(u,v) ∈ Ef: h(u) ≤ h(v) + 1

높이 조건을 경로에 반복 적용하면, Gf에서 v에서 t까지의 최단 거리 d(v)에 대해 h(v) ≤ d(v)가 성립한다.

3연산

3.1Push(u, v)

e(u) > 0, (u,v) ∈ Ef, h(u) = h(v) + 1인 경우.

δ = min(e(u), r(u,v))만큼 u에서 v로 유량을 보낸다: f(u,v) ← f(u,v) + δ.

δ = r(u,v)이면 포화 푸시(saturating push), δ < r(u,v)이면 비포화 푸시(non-saturating push)다. 비포화 푸시 후 e(u) = 0이어서 u는 비활성화된다.

3.2Relabel(u)

e(u) > 0이고 ∀(u,v) ∈ Ef: h(u) ≤ h(v)인 경우.

h(u) ← 1 + min{h(v) : (u,v) ∈ Ef}.

Relabel 직전에는 모든 (u,v) ∈ Ef에 대해 h(u) ≤ h(v)이므로 min{h(v)} ≥ h(u)이고, 따라서 새 h(u) ≥ h(u) + 1이다. Relabel은 h(u)를 증가시킨다.

4알고리즘

다음과 같이 초기화한다.

  • h(s) = n, ∀v ≠ s: h(v) = 0
  • ∀(s,v) ∈ E: f(s,v) = c(s,v) (s에서 나가는 모든 간선 포화)
  • ∀(u,v) ∈ E, u ≠ s: f(u,v) = 0

활성 정점이 없을 때까지, 임의의 활성 정점 u를 고른 후 Push 가능한 (u,v) ∈ Ef가 있으면 Push(u,v), 없으면 Relabel(u)를 수행하는 것을 반복한다.

5증명

5.1보조 정리 1 (높이 불변식)

h는 항상 유효 높이 함수이다.

Push(u,v) 후: 새로 생길 수 있는 잔여 간선은 (v,u)뿐이다. h(v) = h(u) − 1이므로 h(v) ≤ h(u) + 1.

Relabel(u) 후: 새 h(u) = 1 + min{h(v) : (u,v) ∈ Ef}이므로 나가는 모든 잔여 간선 (u,v)에 대해 h(u) ≤ h(v) + 1. 들어오는 잔여 간선 (w,u)에 대해서는 h(u)가 증가했으므로 h가 유효하다. ■

5.2보조 정리 2

모든 활성 정점 v에 대해 Gf 안에 v → s 경로가 존재한다.

정점이 활성화되는 순서에 대한 귀납법을 사용한다.

기저 (초기화 직후 활성화): 초과량을 가지는 정점은 s에 인접한 정점뿐이다. 이때 역방향 잔여 간선 (v,s) ∈ Ef가 생성되어 v → s 경로가 존재한다.

귀납 (Push로 활성화): Push(u,v)로 v가 새로 활성화되면 (v,u) ∈ Ef가 생기고, 귀납 가설에 의해 Gf 안에 u → s 경로가 존재한다. 따라서 v → u → ⋯ → s 경로가 존재한다. ■

따름 정리: Relabel(u) 호출 시 Ef에 u의 나가는 간선이 반드시 존재한다.

알고리즘이 종료할 때, 즉 활성 정점이 없는 경우 f가 최대 유량임을 증명한다. s와 t를 제외한 모든 v에서 e(v) = 0이므로 흐름 보존이 성립하고 f는 s-t 유량이다.

Gf에 s → t 경로 s = u0 → u1 → ⋯ → uk = t가 존재한다고 가정한다. 유효 높이 조건을 반복 적용하면 h(s) ≤ h(t) + k, 즉 n ≤ k이다. 단순 경로의 길이는 최대 n−1이므로 모순이다. 따라서 Gf에 s → t 경로가 없고, Max-Flow Min-Cut Theorem에 의해 f는 최대 유량이다. ■

6시간 복잡도

6.1보조 정리 3 (높이 상한)

∀v ∈ V에 대해 h(v) ≤ 2n − 1.

v가 활성 정점이면 보조 정리 2에 의해 Gf에 경로 v = u0 → u1 → ⋯ → uk = s (k ≤ n−1)가 존재한다. 유효 높이 조건을 반복 적용하면 h(v) ≤ h(s) + k ≤ n + (n−1) = 2n−1.

v가 비활성 정점이면 v의 높이는 마지막 Relabel 시점 이후 변하지 않고, 그 시점에서 v는 활성이었으므로 동일한 상한이 성립한다. h(s) = n과 h(t) = 0은 2n − 1 이하이다. ■

6.2보조 정리 4 (Relabel 횟수)

Relabel은 O(n2)번 수행된다.

각 Relabel(u)는 h(u)를 최소 1 증가시킨다. h(u)는 단조 증가하고 보조 정리 3에 의해 2n−1이 상한이므로, 각 정점에 대해 Relabel은 최대 2n−1번이다. n개의 정점 전체에 걸쳐 합산하면 O(n2). ■

6.3보조 정리 5 (포화 푸시 횟수)

포화 푸시는 O(nm)번이다.

간선 (u,v)에 포화 푸시가 발생하면 r(u,v) = 0이 된다. 이후 같은 간선에 다시 포화 푸시가 발생하려면, 먼저 Push(v,u)를 통해 r(u,v) > 0이 회복되어야 한다. Push(v,u)의 조건은 h(v) = h(u) + 1이다. 포화 푸시 시점에서 h(u) = h(v) + 1이었으므로, Push(v,u)가 가능해지려면 h(v)가 최소 2 증가해야 한다. h(v)는 단조 증가하고 2n−1이 상한이므로 간선 (u,v)당 포화 푸시는 최대 n번이고, 전체는 O(nm). ■

6.4보조 정리 6 (비포화 푸시 횟수)

비포화 푸시는 O(n2 m)번이다.

포텐셜 Φ = ∑v : 활성 h(v)를 정의한다.

  • 초기: s에 인접한 정점만 활성이고 초기 높이는 0이므로 Φ = 0.
  • Relabel(u): h(u)가 최대 2n−1만큼 증가하므로 ΔΦ ≤ 2n−1. Relabel은 O(n2)번이므로 ΔΦ = O(n3).
  • 포화 Push(u,v): v가 새로 활성화되면 ΔΦ ≤ h(v) ≤ 2n−1. 포화 푸시는 O(nm)번이므로 ΔΦ = O(n2m).
  • 비포화 Push(u,v): u가 비활성화된다. v는 이미 활성이거나 새로 활성화된다. h(u) = h(v) + 1이므로 ΔΦ ≤ h(v) − h(u) = −1.

Φ ≥ 0이고 ΔΦ ≤ O(n3) + O(n2m)이므로, 비포화 푸시 횟수는 O(n3) + O(n2m) = O(n2m). ■

보조 정리 4, 5, 6에 의해 시간 복잡도는 O(n2m)이다.

7참고 문헌

  • Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum-flow problem. Journal of the ACM, 35(4), 921–940.
  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.