조합론 및 알고리즘 여름학교 Part 1. Flows and Cuts
2024년 7월 22~26일에 기초과학원 이산수학그룹에서 진행한 조합론 및 알고리듬 여름학교에 참가하여 수업을 들었습니다. 정리를 하다가 대입 시즌이 겹쳐서 정리하는 데 너무 오랜 시간을 사용해서, 드디어 내용정리를 시작했습니다.
이 글은 여름학교에서 진행한 두 강의 중 Chien-Chung Huang 교수님의 <Combinatorial Optimizations> 강의 중 유량(포드-풀커슨, 푸시-리라벨) 부분에 대해 다룹니다.
경기과학고 동아리 나는코더다에서 강의 참고자료로 사용함을 알립니다.
그럼 시작해봅시다. 우선 flow와 cut에 대해 정의합시다.
Definition: Flow
유향 그래프 $G=(V, E)$에 대해,
- 모든 간선에 대한 용량 $c : E \rightarrow \mathbb{R}^+$와,
- 소스와 싱크를 나타내는 두 정점 $s, t \in V$를 정의해 둡시다. $f: E \rightarrow \mathbb{R}^+$가 (즉 모든 간선에 어떤 실수를 대응했을 때)
- $0 \le f(e) \le c(e)\,\,\, \forall e \in E$ 이고 (각 간선의 용량보다는 대응한 실수가 작고)
- $\sum_{\text{incoming}} f(e) = \sum_{\text{outgoing}} f(e)$ 이라면 (각 정점으로 들어오는 양과 나가는 양이 같다면) $f$를 flow라 합니다.
$\delta^+(v)$를 정점 $v$에서 나가는 모든 간선, $\delta^-(v)$를 $v$로 들어오는 간선이라 두면, $|f| = \sum_{e \in \delta^+(s)} f(e) - \sum_{e \in \delta^-(s)} f(e)$ 를 flow value라 합니다. (즉 소스에서 싱크로 흐르는 용량을 유량이라 합니다.)
Definition: Max-Flow Prob.
$G$가 주어질 때, $|f|$가 최대가 되는 flow $f$를 찾는 문제를 최대 유량 문제라 합니다.
Definition: Cut
마찬가지로 유향 그래프 $G=(V, E)$에 대해서 용량, 소스, 싱크를 정의해 두면,
- $C \subset V$, $C \neq V$, $s \in C$, $t \notin C$ (즉 전체집합이 아닌 정점 부분집합이 $s$는 포함하지만 $v$는 포함하지 않는 경우) 인 정점 부분집합 $C$를 $s-t$ cut이라 합니다. 이때
- $|C| = \sum_{e \in \delta^+(C)} c(e)$ 를 cut value라 합니다. (즉 소스 포함 부분집합에서 싱크 포함 여집합으로 들어가는 유량의 총합입니다.)
Definition: Min-Cut Prob.
$G$가 주어질 때, $|C|$가 최소가 되는 cut $C$를 찾는 문제를 최소 컷 문제라 합니다.
Maximum Flow vs. Min Cut - Weak Duality
이 둘은 서로 완전히 다른 문제같아 보이지만, 서로 쌍대성(Duality)을 가집니다. 재미있는 성질을 하나 끄집어 봅시다:
Proposition 1. $s \in X, t \notin X$를 만족하는 임의의 $X \subset V$에 대해, $|f| = \sum_{e \in \delta^+(X)} f(e) - \sum_{e \in \delta^-(X)}f(e)$이다.
증명은 간단합니다. 플로우의 정의에서 $|f| = \sum_{u \in X}\left [ \sum_{e \in \delta^+(u)} f(e) - \sum_{e \in \delta^-(u)} f(e) \right ]$같이 식을 둘 수 있습니다(simple double-counting).
여기서 식의 우항은 항상 cut value $|C|$보다 작습니다, 왜냐면 $\sum_{e \in \delta^+(X)} f(e)$는 용량보다 클 수 없고 $\sum_{e \in \delta^-(X)}f(e)$는 0보다 작을 수 없으니까요. 그러니까 예쁜 따름정리 하나를 같이 끌고 올 수 있습니다:
Corollary 1(Weak Duality of Max Flow Min Cut). 어떤 그래프의 임의의 flow $f$와 cut $C$에 대해, $|f| \leq |C|$.
참고로, 아실 분들은 아시겠지만, Strong Duality에 의해 재미있게도 $\max|f|=\min|C|$랍니다. 알고리즘을 만드는 과정에서 증명될 예정입니다.
Definition: Residual Network
용량이 $c$인 그래프 $G$의 어떤 유량 $f$에 대해 새로운 그래프 $G(f) = (V, F)$를 정의합시다. 이때 $F$는, $\forall e=(u,v) \in E$,
- $c(e)-f(e)>0$이면, 용량이 $c(e)-f(e)$인 유향간선 $(u,v)$를 포함합니다.
- $f(e)>0$이면, 용량이 $f(e)$인 유향간선 $(v,u)$를 포함합니다.
$G(f)$의 용량함수는 $u$라 둡시다.
직관적으로 말하기 뭔가 이상하긴 한데, 만약 $G(f)$에 어떤 간선이 있다면 그 간선에 그만큼의 ‘용량이 더 남아있다’는 느낌으로 해석할 수 있습니다. 아래에서 조금 더 얘기합시다.
Definition: Augmenting Path
여기서, $G(f)$의 어떤 path $f$가 simple $s-t$ path이면 $f$를 augmenting path라 합시다. 원래 그래프 $G$에는 $f$가 없을 수도 있다는 점을 기억합시다.
그렇다면 직관적으로, $G(f)$에서 $f$의 용량만큼 $f$의 경로의 모든 간선이 ‘비어 있으니’ 그만큼 유량을 ‘더 넣어줄 수’ 있겠죠? 이렇게 했을 때 원래 그래프 $G$에서 flow의 조건이 깨지지 않기 때문에 유효합니다. 이런 동작을 augment라고 부르겠습니다.
Proposition 2. 어떤 flow $f$를 augmenting path $p$로 $min_{e \in P} u(e)$만큼 augment하면 $|f|$가 $min_{e \in P} u(e)$만큼 커집니다.
당연하죠? 이걸 하는 알고리즘을 만들어봅시다.
Algorithm 1
- 초기화: $f := \emptyset$
- while $\exists p \text{ an augmenting path } (s,t)$
- $p$를 augment
여기서 개쩌는 정리가 하나 나옵니다.
Theorem: Ford-Fulkerson 1965.
Algorithm 1이 종료하면 이때의 $f$가 Max flow이다.
참이라면, augm path를 찾아서 계속 augment해주기만 하면 최대 유량을 찾을 수 있다는 거겠죠? 그럼 증명해봅시다.
Proof. 그럼 Augm (s,t) Path가 없는 상태에 도달하면 최대 유량임을 보이면 됩니다.
$G(f)$에서 $s$에서 출발해 도달할 수 있는 정점 집합 $X$를 잡으면 $t \notin X$입니다. 즉 $X$는 cut입니다. 위에서 $|f| = \sum_{e \in \delta^+(X)} f(e) - \sum_{e \in \delta^-(X)} f(e)$였는데,
- $e \in \delta^+(X)$에 대해 $f(e) < c(e)$인 것이 없고
- $e \in \delta^-(X)$에 대해 $f(e) > 0$인 것이 없습니다.
- 있다면 도달 가능한 정점 집합이 보다 크니까요.
그러면 $|f| = \sum_{e \in \delta^+(X)} c(e) - \sum_{e \in \delta^-(X)} 0 = |X|$입니다. 즉 $|f|=|X|$입니다. 앞에서 증명한 최대 유량-최소 컷의 weak duality에 의해 이런 $f$가 최대 유량이고 동시에 $X$가 최소 컷입니다.
엄청 대단한 게 맞긴 한데, 솔직히 그렇게 빠르게 작동하는 효율적 알고리즘은 아니긴 합니다. 말 그대로 augm path를 ‘아무거나’ 뽑아도 알고리즘이 작동하기 때문에, 비효율적인 방법으로 뽑으면 정말 오래 걸릴 수도 있습니다. 시간복잡도를 계산하자면, 모든 용량이 정수인 경우 $O(nm\max(c))$가 되고, 실수인 경우 최악의 경우에서 시복이 bound되지 않습니다.
1972년에 발표된 Edmond-Karp에 의하면, Algorithm 1에서 가장 짧은 augm path를 골라 augment해주는 방향을 택한다면 $O(nm^2)$ 정도로 시복을 줄일 수 있긴 합니다. 그러나, 이미 1년 전에 좀 더 쩌는 알고리즘이 나온 뒤였습니다.
Reflow-Push Alg. (aka Push-Relabel)
푸시리라벨로 더 잘 알려진 바로 그 알고리즘입니다. 우선 Preflow를 정의합시다.
그래프 $G=(V, E)$, 용량 $c: E \rightarrow \mathbb{R}_{>0}$, 소스와 싱크 $s, t \in V$에 대해서 $f: E \rightarrow \mathbb{R}_{\ge 0}$가
- $0 \le f(e) \le c(e) \;\; \forall e \in E$이고 (플로우의 조건이죠?)
- $e(v) = \sum_{e \in \delta^-(V)} f(e) - \sum_{e \in \delta^+(V)} f(e) \ge 0 \;\; \forall v \in V/{s,t}$이면 (그러니까 $e(v)$는 $v$에서 나가야 하는 추가 유량(excess)입니다.)
그러한 $f$를 preflow라 합니다. 이런 $f$에 대해서도 residual network를 똑같이 정의할 수 있다는 점을 기억해 둡시다. 이제 label을 정의합시다.
$d: V \rightarrow \mathbb{Z}_{\ge 0}$이
- $\forall e=(u, v) \in G(f), \;d(u) \le d(v) + 1$ (즉, 모든 정점에 $d$라는 값이 붙어 있는데 residual 간선이 있는 경우 시점이 종점보다 1 이상 작은 값을 가진다는 소리입니다.) 를 만족한다면 그 $d$를 label이라 합니다. 이때
- 간선 $e=(u, v) \in G(f)$이 정당하려면 $d(u) = d(v) + 1$입니다.
- 이때 정점 $v \in V \setminus {s,t}$이 $e(v) > 0$이면 그 정점이 ‘active’하다고 하겠습니다. (대충 유량이 넘치고 있어서 처리해주어야 한다는 얘깁니다. active 정점이 없어지면 그때의 preflow는 flow가 되겠죠?)
Algorithm 2
초기화:
- $\forall e = (s, u) \in E$, $f(e) = c(e)$
- $d(s) = n$, $d(t) = 0$, $\forall v \in V\setminus{s,t}$ $d(v) = 0$ while $\exists u$ an active node:
- Push: if $\forall (u, v)$ legitimate in $G(f)$, then
- push flow on (u, v) with the amount $\min(U(u, v), e(u))$ (residual에서 active node가 있을때 legitimate한 간선이 있으면, 그 간선을 최대한 push합니다.)
- Relabel: else, $d(u) = (\min_{(u, v) \in G(f)} {d(v)}) + 1$ (그런 거 없으면, $d$의 label을 바꿉니다.)
이때 다음 두 가지는 쉽게 볼 수 있습니다. Proposition:
- 알고리즘의 while을 돌릴 때 preflow와 label의 조건이 그대로 만족
- 알고리즘이 멈추면 $f$는 flow 1은 자명합니다. 2도 알고리즘이 멈추면 더 이상 active한 정점이 없기 때문에 자명하죠.
이제 알고리즘이 정말로 포드-풀커슨보다 괜찮다는 사실을 증명해봅시다.
Lemma: $G(f)$에서 $u \rightarrow v$의 최단 경로는 $d(u)-d(v)$보다 크거나 같다.
증명은 간단합니다. 최단 경로가 $p$라 하고 $p=(u=i_0),i_1, \cdots (i_k=v)$로 둡시다. 이때 $d_{i_k} \le d_{i_{k+1}} + 1 \;\rightarrow\; d_{i_k} - d_{i_{k+1}} \le 1$입니다. 다 더하면 $d_{i_0} - d_{i_k} \le k$니까 증명이 되죠?
Lemma. 어떤 active한 정점 $u$에 대해, $G(f)$에 $u$에서 $s$로 갈 수 있는 경로가 존재한다.
이걸 증명하면 Algorithm 2가 중간에 막히지 않고 active node가 없어질 때까지 계속 작동할 수 있음이 보여지기 때문에 증명이 완료된다고 생각할 수 있습니다.
증명은 이렇게 할 수 있습니다. 일단 $s$로 갈 수 없는 정점만 모아둬서 그 집합을 $Y$라 둡시다. 그리고 어떤 active node $u \in Y$를 잡으면, $\sum_{v \in Y} e(v) = \sum_{v \in Y} \left (\sum_{e \in \delta^-(v)} f(e) - \sum_{e \in \delta^+(v)} f(e)\right )= \sum_{e \in \delta^-(Y)} f(e) - \sum_{e \in \delta^+(Y)} f(e) > 0$이니까 $\delta^-(Y)$의 간선 중 양수 유량을 가진 것이 적어도 하나는 있습니다. (왜냐면 모든 excess는 0보다 크고 excess인 정점이 적어도 하나는 있으니까요.)
그렇다면, $Y$에서 $V \setminus Y$로 갈 수 있는 간선이 존재하게 됩니다. 그러면 $Y$에서 $V \setminus Y$를 거쳐 $s$로도 갈 수 있으니까 ($Y$에는 $s$로 못 가는 모든 점이 있기 때문에, $V \setminus Y$의 모든 점에서는 $s$로 갈 수 있습니다) 모순입니다. 따라서 증명이 됩니다.
Corollary. 임의의 정점 $u \notin {s, t}$에 대해 $d(u) \le 2n-1$다.
$u$가 active해야 $d(u)$가 늘어날 수 있기 때문에, $d(u)$가 늘어난다는 것은 $u$애서 $s$로 갈 수 있다는 얘깁니다. 그런 경로의 길이는 최대 $n-1$이니까 $d(u)-d(s) \le n-1$이고, 초기에 $d(s)=n$이므로 $d(u) \leq 2n-1$ 역시 참입니다.
이제 이 알고리즘의 시간복잡도를 증명하면 이야기를 마칠 수 있습니다. 이를 위해 알고리즘의 Push 연산의 ‘포화도’를 이야기합시다. Push 연산에서 추가되는 유량이 $u(e)$면 이를 포화(saturating) Push, 아니면 불포화(non-saturating) Push라 부르겠습니다.
Lemma. Relabel 연산의 횟수는 $O(n^2)$이다.
위 Corollary를 가져다 쓰면 자명합니다. 정점이 $n$개고 $d(u)$는 $2n-1$ 이하이므로, Relabel 연산은 $n(2n-1)$번보다 많아질 수는 없겠죠.
Lemma. 포화 Push 연산의 횟수는 $O(nm)$이다.
간선 $(u,v)$에 push가 일어나는 상황을 생각합시다. $d(u)=d(v)+1$이 성립합니다. 이 간선에 push를 한 번 더 하려면 $d(v)=d(u)+1$이어야겠죠, 즉 $d(v)$가 2 이상 늘어나야 합니다. 따라서 이 간선에 생길 수 있는 포화 push는 $O(n)$번입니다(Corollary에 의해 $d$는 $2n$ 안쪽이니까요). 간선 개수 $m$을 곱하면 포화 push의 횟수는 $O(nm)$이 됩니다.
Lemma. 불포화 push 연산의 횟수는 $O(n^2m)$이다.
‘포텐셜’이라는 이름으로 $\Phi(f, d) := \sum_{u \text{ is active}} d(u)$를 정의합시다. 최초 및 최종 값은 0이겠죠?
- 포텐셜이 늘어난다는 것은 relabel 혹은 포화 push 연산이 가해진다는 뜻이고요,
- 줄어든다는 것은 불포화 push 연산이 가해진다는 겁니다.
여기서 relabel 연산은 포텐셜을 1 늘리며, 그 횟수는 $O(n^2)$입니다. 포화 push는 포텐셜을 최대 $O(n(2n-1)m)$ 늘립니다. 즉 포텐셜이 $O(n^2m)$만큼 늘어나는 것이고, 불포화 push는 포텐셜을 1 이상 줄이므로 당연히 줄어드는 횟수도 $O(n^2m)$번 입니다. 따라서 불포화 push 연산 횟수는 $O(n^2m)$입니다.
Lemma. 알고리즘이 종료하면 그게 최대 유량이다.
지금까지 보인 lemma들에 의해 자명하죠. 최대 유량이 아니라면 $G(f)$에 $s$에서 $t$로 가는 경로가 있을 텐데, 그 길이가 적어도 $d(s)-d(t)=n$보다 작지는 않을 것입니다. 모순이죠?
따라서 Reflow-Push의 시간복잡도는 $O(n^2m)$입니다.
Minor Adjustments
- 여기서 조금만 변형하면 $O(n^3)$도 어렵지 않게 가능하다고 합니다.
- 매 while iteration에서, active 정점을 label이 증가하는 순서대로 모두 나열해 둡시다.
- 그리고 push 혹은 relabel 연산을 그 순서에 따라서 돌립시다.
- 만약 한 개의 iteration에서 relabel이 한 번도 없다면 알고리즘을 종료합니다.
- 이렇게 하면, non-saturating push의 개수가 $O(n^3)$으로 줄어들기 때문에 $m$이 $n$으로 줄어든다고 하네요. 정확한 증명은 저도 모르겠습니다.
- 이게 연습문제로 나왔는데, 제가 못 풀었거든요. ㅋㅋ~
- 현존하는 것중 가장 시복이 빠른 것은 $O(m^{1+O(1)})$이라고 합니다. 위키피디아에도 있으니 궁금하면 한번 들여다 보시고요.
- 푸시리라벨, 이름만 들어보고 실제로 배우지는 않았던 알고리즘인데 드디어 공부했습니다. 생각보다 매우 개쩌는 알고리즘이었네요.