디니츠의 알고리즘 (Dinitz' Algorithm)

지금까지 저는 제 블로그에서 최대 흐름 문제(maximum flow problem)를 많은 포스트를 통해서 다루어 왔습니다. 가장 최근에는 최대 흐름 문제를 다항 시간에 해결하는 에드몬즈-카프 알고리즘(Edmonds-Karp algorithm)을 소개해 드렸죠. 이번에는 에드몬즈-카프 알고리즘보다 더 빠른 시간에 최대 흐름 문제를 해결하는 방법 중 하나를 소개하고자 합니다. 바로 우리에게는 디닉의 알고리즘(Dinic's algorithm)으로 더 잘 알려진, 디니츠의 알고리즘(Dinitz' algorithm)입니다.

 

포탈에 검색해 봤더니 디니츠의 알고리즘을 어떻게 구현하는지 우리말로 설명한 게시글은 적잖이 볼 수 있었습니다. 다만 어째서 디니츠의 알고리즘이 에드몬즈-카프 알고리즘보다 효율적으로 동작하는지에 대한 설명은 찾기 어렵더군요. 제가 블로그를 운영하는 가장 큰 이유 중 하나가 바로 이러한 간극을 메우는 것이다 보니, 디니츠의 알고리즘은 언젠가 한번은 꼭 다루어야겠다고 다짐했었습니다. 이번에 이를 정리하게 되어 기쁩니다.

일화(逸話)

Photo by K8 on Unsplash

당시 소련의 학생이던 예핌 디니츠(Yefim Dinitz)는 아델슨-벨스키(George Adel'son-Vel'sky)의 알고리즘 수업을 듣고 있었습니다. AVL 트리의 개발자로 유명한 아델슨-벨스키는 매 수업마다 다음 수업 시간에 배울 주제에 대해 학생들이 한번 생각해 보도록 문제가 무엇인지만 달랑 던져 주었다고 합니다. 언젠가 최대 흐름 문제가 소개되자 포드-풀커슨 방법(Ford-Fulkerson method)을 몰랐던 디니츠는 잘못된 알고리즘을 하나 떠올리게 됩니다. 하지만 놀랍게도 그 잘못된 알고리즘을 조금 수정하면 (비록 약간의 시간 손실은 있을지언정) 효율적으로 최대 흐름 문제를 해결하는 알고리즘을 얻을 수 있었다고 합니다. 그렇게 얻은 결과가 바로 이번에 소개할 디니츠의 알고리즘입니다.

 

이 알고리즘이 개발된 때에는 미국과 소련의 냉전이 한창이었습니다. 따라서 디니츠의 알고리즘이 서구권에는 디니츠의 이름으로 곧바로 소개되지 않았죠. 이스라엘의 컴퓨터과학자 시몬 이븐(Shimon Even)과 (당시 박사 학생이던) 알론 이타이(Alon Itai)는 디니츠의 알고리즘을 알게 되고, 삼일 밤낮을 투자한 끝에 이 알고리즘을 이해한 후 서구권에 이를 소개하게 됩니다. 이때, 디니츠의 이름을 "디닉(Dinic)"으로 잘못 옮겨 적으면서, 우리에게는 디니츠의 알고리즘보다 디닉의 알고리즘이라고 더 잘 알려지게 된 것이라고 합니다.

 

저도 처음에는 이 알고리즘을 지칭할 때 더 잘 알려진 "디닉의 알고리즘"으로 하려고 했습니다만, 아무래도 디니츠의 이름을 밝히는 것이 옳은 것 같아서 "디니츠의 알고리즘"으로 통일하였습니다.

문제 및 기본 개념 소개

최대 흐름 문제가 무엇이고 관련된 개념에 어떤 것들이 있었는지를 가볍게 짚고 넘어가겠습니다. 이 문제는 어떤 흐름 네트워크(flow network) $G=(V,E)$, 용량(capacity) $c:E\to {\mathbb{Z}}_{+}$, 시점(source) $s\in V$, 종점(sink) $t\in V$이 주어졌을 때, 모든 간선 $e\in E$마다 $0\le f(e)\le c(e)$를 만족하고, 시종점을 제외한 모든 정점 $v$마다 $\sum _{e\text{ into }v}f(e)=\sum _{e\text{ out of }v}f(e)$를 만족하는 흐름(flow) $f$ 중 흐름양(flow value) $|f|:=\sum _{e\text{ out of }s}f(e)-\sum _{e\text{ into }s}f(e)$가 가장 큰 것을 찾는 문제입니다. 이때 우리는 일반성을 잃지 않고 다음의 가정을 할 수 있었습니다.

• 모든 용량은 음이 아닌 정수의 값을 갖는다.
• 루프(loop), 평행 간선(parallel edge), 역평행 간선(anti-parallel edge)이 존재하지 않는다.
• $|E|\ge |V|-1$이다.

 

최대 흐름 문제를 해결하는 가장 기본적인 방법은 어떤 흐름 $f$에 대해 얼마큼 더 흘릴 수 있고 얼마큼 뺄 수 있는지를 나타내는 잔여 네트워크(residual network) $G_f=(V,E_f)$, 잔여 용량(residual capacity) $c_f:E_f\to {\mathbb{Q}}_{+}$를 만들고, 여기서 $s$에서 $t$로 가는 임의의 증가 경로(augmenting path) $P$를 찾은 후, $\underset{e\in P}{min}{c}_f(e)$의 흐름양을 갖는 흐름 $f_P$를 따라 기존 흐름 $f$를 $f\uparrow f_P$로 증가시키는 것입니다. 만약 $G_f$에서 더 이상 $s$에서 $t$로 도달이 불가능할 때, 우리는 $f$가 최대 흐름이 된다는 것을 증명하였습니다. 이 방법이 바로 포드-풀커슨 방법이었습니다.

 

혹여 위 내용이 익숙하지 않으신 분들은 이전 포스트를 참조하시기 바랍니다.

에드몬즈-카프 알고리즘 복습

안타깝게도 포드-풀커슨 방법은 증가 경로를 "멍청하게" 선택하면 최악의 경우 지수 시간(exponential time)에 동작하였습니다. 따라서 "똑똑하게" 증가 경로를 선택하는 방법이 필요했죠. 에드몬즈-카프 알고리즘에서는 다음과 같이 가장 간선의 개수가 적은 증가 경로, 다시 말해 최단 증가 경로를 선택했습니다.

알고리즘 1. Edmonds-Karp algorithm

---

입력: 흐름 네트워크 $G,c$, 시종점 $s,t$

출력: 최대 흐름

 

1. $f\leftarrow 0$
2. $G_f$에서 $s$에서 $t$에 도달할 수 없을 때까지 아래를 반복한다.
   1. $G_f$에서 $s$에서 $t$로 가는 경로 중 간선의 개수가 가장 적은 경로 하나를 $P$라고 하자.
   2. $f\leftarrow f\uparrow f_P$
3. $f$를 반환한다.

이전 포스트에서 우리는 에드몬즈-카프 알고리즘이 $O(|V||E{|}^2)$ 시간에 동작한다는 사실을 보였습니다. 이를 증명하기 위한 가장 중요한 사실 중 하나는 매번 최단 증가 경로를 취하면 모든 정점이 잔여 네트워크 위에서 $t$로부터 멀어지기만 한다는 것이었습니다.

 

사실, 위 성질은 더 일반적인 경우에도 성립합니다. 어떤 흐름 $f$가 주어졌을 때, 임의의 두 정점 $u,v\in V$에 대해 $d_f(u,v)$를 $u$에서 $v$로 가는 경로 중 가장 짧은 것의 길이로 하겠습니다. 만약 도달할 수 없으면 $\mathrm{\infty }$의 값을 갖는다고 하죠. 그러면 우리는 다음을 확인할 수 있습니다.

정리 1. 시종점으로부터 멀어지기만 하는 성질

---

어떤 흐름 $f$에 대해, $G_f$ 위에서 최단 증가 경로 $P$를 찾아 $f^{\prime }:=f\uparrow f_P$을 만들었다고 하자. 그러면 임의의 정점 $v\in V$에 대해, $d_f(s,v)\le d_{f^{\prime }}(s,v)$이고, $d_f(v,t)\le d_{f^{\prime }}(v,t)$가 성립한다.

이미 이전 포스트에서 $d_f(v,t)\le d_{f^{\prime }}(v,t)$를 보였으며, 이를 대칭적으로 적용하면 나머지 명제도 쉽게 보일 수 있으므로 자세한 증명은 생략하도록 하겠습니다.

디니츠의 알고리즘 개략적 구조

곧바로 디니츠의 알고리즘이 무엇인지 알려 드리기에 앞서, 개략적인 구조가 어떻게 생겼는지를 따져보면서 어떤 아이디어를 갖고 이 알고리즘이 만들어졌는지를 생각해 보겠습니다. 잠시 에드몬즈-카프 알고리즘으로 다시 돌아와 봅시다. 과연 에드몬즈-카프 알고리즘의 어떤 부분을 우리가 발전시킬 수 있을까요? 정리 1을 통해 우리가 유추할 수 있는 사실은 에드몬즈-카프 알고리즘이 단계 2-a에서 찾는 증가 경로 $P$의 길이는 길어지기만 한다는 것입니다. 다시 말해, $i$ 번째에 단계 2-a에서 찾은 증가 경로를 $P_i$라고 하면, 우리는 $$|P_1|\le |P_2|\le |P_3|\le \cdots$$를 얻게 됩니다.

 

만약 여기서 우리가 같은 길이를 갖는 최단 증가 경로를 "한번에" 찾는 서브루틴(subroutine)이 있다면 어떻게 될까요? 최단 증가 경로의 길이는 분명 $|V|-1$을 넘을 수 없으므로, 이 서브루틴을 $O(|V|)$ 번 수행하면 최대 흐름 문제를 해결할 수 있게 될 것입니다. 수행 시간은 어떻게 될까요? 이 서브루틴이 만약 $r(|V|,|E|)$의 시간 복잡도를 갖는다면, 알고리즘의 총 수행 시간은 $O(|V|\cdot r(|V|,|E|))$가 됩니다. 흥미롭게도 우리는 $r(|V|,|E|)=O(|V||E|)$가 되는 서브루틴을 만들 수 있습니다. 이것이 바로 $O(|V{|}^2|E|)$의 시간 복잡도를 갖는 디니츠의 알고리즘을 이루는 근간이 됩니다.

 

아래에서 우리는 최단 증가 경로를 "한번에" 찾기 위해서 아래를 만족하는 "특별한" 자료 구조를 하나 만들 것입니다.

• 이 자료 구조는 매번 유지하는 흐름에 대한 잔여 네트워크 위의 현재 고려하는 길이의 최단 증가 경로를 계속 포함한다.
• 만약 이 자료 구조 위에서 $s$에서 $t$까지 도달할 수 없으면 현재 고려하는 길이의 최단 증가 경로는 존재하지 않는다.

따라서 이 자료 구조에서 계속 최단 증가 경로를 찾아 흐름을 증가시켜 주면 같은 길이의 최단 증가 경로를 한번에 찾을 수 있게 되는 것이죠. 이를 개략적으로 표현하면 아래와 같습니다.

알고리즘 2. Dinitz' algorithm (sketch)

---

입력: 흐름 네트워크 $G,c$, 시종점 $s,t$

출력: 최대 흐름

 

1. $f\leftarrow 0$
2. $G_f$에서 $s$에서 $t$에 도달할 수 없을 때까지 아래를 반복한다.
   1. 같은 길이의 최단 증가 경로를 한번에 찾을 특별한 자료 구조를 만든다.
   2. 특별한 자료 구조에서 $s$에서 $t$에 도달할 수 없을 때까지 아래를 반복한다.
      1. 특별한 자료 구조에서 $s$에서 $t$로 가는 최단 증가 경로 $P$를 찾는다.
      2. $f:=f\uparrow f_P$
      3. 특별한 자료 구조를 현재의 $f$에 맞게 갱신한다.
3. $f$를 반환한다.

레이어드 네트워크(Layered Network)

Photo by Chor Tsang on Unsplash

이제 특별한 자료 구조를 만나 볼 차례입니다. 앞에서 우리는 이 자료 구조가 매번 현재 유지하는 흐름에 대한 고려하는 길이의 최단 증가 경로를 계속 포함하기를 바랐습니다. 이를 위해서 우리는 어떤 흐름에 대해, 잔여 네트워크 위 $s$에서 $t$로 가는 "모든" 최단 경로들로 이루어진 구조를 만들고자 합니다.

 

좀더 자세히 정의하겠습니다. 어떤 흐름 $f$가 주어졌을 때, $G_f$ 위에서 $s$에서 $t$로 가는 최단 증가 경로의 길이(즉, 거리)를 $\ell$이라고 하겠습니다. 그러면 임의의 최단 증가 경로 $P$는 분명 다음과 같이 $$P=⟨s=v_0,v_1,\cdots ,v_{\ell }=t⟩$$의 꼴을 보일 것입니다. 이때 각 $v_i$는 $s$로부터의 거리는 정확히 $i$이고, $t$까지의 거리는 정확히 $\ell -i$가 됩니다. 역으로 어떤 정점 $v$가 $s$로부터의 거리가 $i$, $t$까지의 거리가 $\ell -i$라면 이 정점이 $i$ 번째 정점이 되는 최단 증가 경로가 하나는 반드시 존재하게 됩니다.

 

따라서, $s$로부터의 거리가 $i$이고 $t$까지의 거리가 $\ell -i$인 정점들을 모으면 이들은 정확히 모든 최단 경로의 $i$ 번째 정점들을 모아 놓은 것과 동일하게 됩니다. 이를 $U_i^f$라고 하겠습니다. 다시 말해, $$U_i^f:=\{v\in V\mid d_f(s,v)=i,d_f(v,t)=\ell -i\}$$ 로 정의하겠습니다. 추가로 $U^f:=U_0^f\cup U_1^f\cup \cdots \cup U_{\ell }^f$로 정의하겠습니다.

 

각 $U_i^f$는 일종의 층(layer)을 이루며, 두 층 사이에는 이전 층에서 다음 층으로 향하는 간선들이 존재할 것입니다. 모든 $i=0,1,\cdots ,\ell -1$에 대해, $U_i^f$의 한 정점에서 $U_{i+1}^f$의 한 정점으로 향하는 간선을 모두 모은 것을 $F_{i\to i+1}^f$이라고 하겠습니다. 다시 쓰면, $$F_{i\to i+1}^f:=\{⟨u,v⟩\in E_f\mid u\in U_i^f,v\in U_{i+1}^f\}$$이 되겠습니다. 참고로 앞의 논의와 비슷하게, $F_{i\to i+1}^f$은 모든 최단 경로의 $i+1$ 번째 간선을 모아 놓은 것과 정확히 일치합니다. 추가로 $F^f:=F_{0\to 1}^f\cup \cdots \cup F_{\ell -1\to \ell }^f$로 정의하겠습니다.

그림 1. (a) 어떤 흐름 $f$의 잔여 네트워크 $G_f$의 예시. (b) 레이어드 네트워크 $L_f$의 예시. 정점 $c$는 $s$에서 $t$로 가는 어떤 최단 증가 경로에도 포함되지 않는다. 회색으로 칠한 간선은 $F^f$에 포함되지 않는 간선들이다.

여기까지 오셨으면, 우리가 찾을 것이 무엇인지 감이 잡히셨을 것입니다. 어떤 흐름 $f$가 주어졌을 때 우리는 $L_f:=(U^f,F^f)$를 만들고자 합니다. 그 구조에서 본따 레이어드 네트워크(layered network)라고 부르겠습니다. 이는 다음과 같이 너비 우선 탐색(breadth-first search, BFS)을 두 번 사용하면 찾을 수 있습니다.

알고리즘 3. Layered network construction

---

입력: 흐름 $f$

출력: 레이어드 네트워크 $L_f=(U^f,F^f)$

 

1. $G_f$ 위에서 정방향으로 $s$에서 BFS를 $t$를 찾을 때까지 수행한다.
2. 이전 단계에서 방문한 정점들과 간선들만 가지고 역방향으로 $t$에서 BFS를 수행한다.

알고리즘 3이 실제로 레이어드 네트워크를 만든다는 증명은 생략하도록 하겠습니다. 

레이어드 네트워크 갱신하기

이전 절에서는 어떤 흐름 $f$에 대해 $L_f$가 $G_f$ 위의 최단 증가 경로를 모두 모아 놓은 것과 동일하다는 것을 확인하였습니다. 따라서 $L_f$ 위에서 $s$에서 $t$로 가는 임의의 경로는 $G_f$ 위의 최단 증가 경로가 되죠. 하지만 이 사실만 가지고는 알고리즘 2에서 써먹을 건더기가 없습니다. 레이어드 네트워크가 빛을 발하려면 증가 후의 흐름에 대해서도 좋은 성질을 갖고 있어야 합니다.

 

어떤 흐름 $f$에 대해, 최단 증가 경로 $P$를 하나 찾고 이를 따라 $f$에서 증가시킨 흐름을 $f^{\prime }:=f\uparrow f_P$이라고 하겠습니다. 동시에 이번에는 레이어드 네트워크 $L_f=(U^f,F^f)$를 고려해 봅시다. $P$를 따라 흐름을 증가시키기 때문에 최소한 하나의 병목 간선은 $E_f$에서 사라지게 됩니다. $L_f$에서도 똑같이 $P$의 병목 간선(들)을 삭제시켜 주도록 합시다. 삭제가 될 간선은 $P$ 위에 있고, $P$는 분명 $L_f$에서도 존재하므로 병목 간선들을 삭제하는 작업은 $O(|P|)=O(|V|)$의 시간이면 충분합니다. 이렇게 갱신된 네트워크를 구분을 위해 $\widehat{L_f}=(\widehat{U^f},\widehat{F^f})$라고 하겠습니다.

 

과연 $\widehat{L_f}$와 $L_{f^{\prime }}$은 어떤 관계를 갖고 있을까요? 흥미롭게도 우리는 다음과 같은 사실을 발견할 수 있습니다.

정리 2. 갱신된 레이어드 네트워크의 성질

---

어떤 흐름 $f$와 $G_f$ 위 최단 증가 경로 $P$, 그리고 $f^{\prime }:=f\uparrow f_P$에 대해, 만약 $G_{f^{\prime }}$ 위 최단 증가 경로의 길이가 $P$와 같다면, $$F^{f^{\prime }}\subseteq \widehat{F^f}\subseteq E_{f^{\prime }}$$를 만족한다.

[증명] 우선 $\widehat{F^f}\subseteq E_{f^{\prime }}$은 $\widehat{L_f}$가 만들어지는 과정을 잘 살펴 보면 어렵지 않게 확인할 수 있습니다. 따라서 나머지 부분인 $F^{f^{\prime }}\subseteq \widehat{F^f}$를 보이는데 집중하겠습니다. 귀류법을 쓰기 위해 $F^{f^{\prime }}⊈\widehat{F^f}$라고 하겠습니다. 그러면 분명 $G_{f^{\prime }}$의 한 최단 경로 $P^{\prime }$에 포함된 $⟨u,v⟩\in F^{f^{\prime }}\setminus \widehat{F^f}$이 하나 존재할 것입니다. 다음 두 가지 경우를 생각해 봅시다.

 

경우 1: $⟨u,v⟩\in E_f$. 일단 정리 1에 의해 $d_f(s,u)\le d_{f^{\prime }}(s,u)$와 $d_f(v,t)\le d_{f^{\prime }}(v,t)$를 만족하므로, $G_f$ 위에서 $u$는 $s$로부터 도달 가능하고, $v$는 $t$로 도달 가능합니다. 그런데 이때 $⟨u,v⟩\notin F^f$이려면 $s$에서 $u$까지 최단 경로를 탄 후 $⟨u,v⟩$를 지나 $v$에서 $t$까지 최단 경로를 타는 방법의 길이가 $\ell :=|P|$보다 길어야 합니다. 그러면 우리는 정리 1에 의해 $$\ell <d_f(s,u)+1+d_f(v,t)\le d_{f^{\prime }}(s,u)+1+d_{f^{\prime }}(v,t)=|P^{\prime }|=\ell$$을 유도할 수 있습니다. 하지만 이는 모순이고, 따라서 $⟨u,v⟩\in F^f$라는 사실을 알 수 있죠. 그럼에도 $⟨u,v⟩\notin \widehat{F^f}$려면 $P$에 $⟨u,v⟩$가 포함되어 있고, 하필 이 간선이 병목 간선이어야 합니다. 하지만 그러면 $E_{f^{\prime }}$에서도 $⟨u,v⟩$가 사라지게 되며 자연스럽게 $F^{f^{\prime }}\subseteq E_{f^{\prime }}$에도 존재할 수 없습니다. 이것도 모순이죠.

 

경우 2: $⟨u,v⟩\notin E_f$. 이 경우는 $⟨v,u⟩$가 $P$ 위에 존재할 때만 가능합니다. 그러므로, $$d_f(s,v)+1+d_f(u,t)=\ell$$을 만족합니다. 동시에 $P^{\prime }$으로부터 $$d_{f^{\prime }}(s,u)+1+d_{f^{\prime }}(v,t)=\ell$$을 유도할 수 있습니다. 두 등식을 더한 후 정리하면 $$\begin{array}{}\text{(1)}& d_{f^{\prime }}(s,u)+d_f(u,t)+d_f(s,v)+d_{f^{\prime }}(v,t)+2=2\ell \end{array}$$을 얻게 됩니다. 이때 정리 1에 의해 $$d_f(s,u)\le d_{f^{\prime }}(s,u),d_f(v,t)\le d_{f^{\prime }}(v,t)$$이고, 또한 $$d_f(s,u)+d_f(u,t)=d_f(s,v)+d_f(v,t)=\ell$$이므로 이를 식 1에 적용하면 $$2\ell +2\le 2\ell$$이 되어 모순을 이끌어 낼 수 있습니다. ■

 

정리 2는 우리에게 도움이 되는 유용한 성질들을 많이 내포하고 있습니다. 특히 다음과 같은 상황을 생각해 봅시다. 어떤 흐름 $f^{(1)}$이 주어졌다고 합시다. 이때의 레이어드 네트워크는 $L_1:=L_{f^{(0)}}$이라고 부르겠습니다. 각 $i=1,2,\cdots$에 대해, $G_{f^{(i)}}$ 의 최단 증가 경로를 $P_i$라고 하고, 이를 따라 증가시킨 흐름을 $f^{(i+1)}:=f^{(i)}\uparrow f_{P_i}$라고 하겠습니다. 이때 $$\ell :=|P_1|=\cdots =|P_k|<|P_{k+1}|$$을 만족한다고 해 보죠. 매번 $f^{(i)}$에서 $f^{(i+1)}$을 만들 때 갱신 후의 레이어드 네트워크를 $L_{i+1}:=\widehat{L_i}$로 정의하겠습니다.

 

첫 번째로 알 수 있는 사실은 $L_{k+1}$에서는 $s$에서 $t$로 가는 경로가 존재하지 않는다는 것입니다. 우리는 이를 알고리즘 2의 단계 2-b를 판단하는데 사용할 수 있습니다. 또한 우리는 $$F^{f^{(1)}}⊋F^{f^{(2)}}⊋\cdots ⊋F^{f^{(k)}}$$를 만족한다는 것을 알 수 있습니다. 이때 등식이 성립하지 않는 이유는 레이어드 네트워크가 갱신될 때마다 최소한 하나의 간선은 병목 간선으로 삭제가 되기 때문입니다. 이는 갱신의 횟수가 $O(|E|)$가 된다는 것을 알려 주죠.

 

마지막으로 각 $L_i$의 간선들이 모두 $E_{f^{(i)}}$의 부분집합이 된다는 사실을 통해, 매 $L_i$에서 찾은 경로가 곧장 $G_{f^{(i)}}$의 최단 증가 경로가 된다는 것을 이끌어낼 수 있습니다. 그러므로 $G_{f^{(i)}}$를 명시적으로 만들 필요 없이 레이어드 네트워크를 갱신하는 것만으로 우리는 충분히 같은 길이의 최단 증가 경로를 찾을 수 있습니다.

레이어드 네트워크에서 최단 증가 경로 찾기

지금까지 레이어드 네트워크는 어떤 흐름의 잔여 네트워크 위 $s$에서 $t$까지의 모든 최단 증가 경로들로 이루어져 있으며, 처음에 한 번만 만들어 놓으면 이후 같은 길이를 갖는 최단 증가 경로는 기존의 레이어드 네트워크를 갱신하여 얻을 수 있다는 것을 살펴 보았습니다. 과연 이것만 가지고 우리가 목표로 하는 수행 시간 $r(|V|,|E|)=O(|V||E|)$를 곧바로 얻을 수 있을까요? 한번 수행 시간을 구해 봅시다.

• 알고리즘 2의 단계 2-a에서 레이어드 네트워크를 하나 만듭니다. 이는 두 번의 BFS면 충분하므로 $O(|E|)$에 수행할 수 있습니다.
• 다음 단계 2-b를 수행합니다. 앞에서 우리는 그 횟수가 $O(|E|)$가 된다는 것을 확인하였습니다. 레이어드 네트워크가 갱신될 때마다 적어도 하나의 간선은 병목 간선이 되어 사라지기 때문이었습니다.
• 먼저 단계 2-b-ii와 2-b-iii을 생각해 봅시다. 만약 최단 증가 경로 $P$를 찾았다면, 그 경로를 따라서 갱신해 주면 됐습니다. 그 길이는 $O(|P|)=O(|V|)$이므로 수행 시간도 그에 비례하여 걸릴 것입니다.

따라서 만약 우리가 단계 2-b-i을 $O(|V|)$의 시간에 할 수 있다면 총 수행 시간은 $O(|E|+|V||E|)$가 될 것입니다. 과연 단계 2-b-i을 그 시간 동안에 끝낼 수 있을까요? 첫 번째 레이어드 네트워크, 막 단계 2-a를 통해 만들어진 네트워크에서는 가능합니다. 그 네트워크가 정확히 $s$에서 $t$로 가는 모든 최단 증가 경로를 묶어 놓은 것과 동일하기 때문에 시점 $s$에서 깊이 우선 탐색(depth-first search, DFS)을 수행하면 매번 다음 층으로 진행할 수 있고 따라서 $O(|V|)$ 시간에 $t$에 도달할 수 있게 됩니다.

 

문제는 갱신한 후에도 가능한지입니다. 정리 2에 따르면 증가한 다음의 흐름 $f^{\prime }$에 대해 $F^{f^{\prime }}\subseteq \widehat{F^f}$를 만족하니까 가능한 것 아니냐고 생각하실 분들이 계실지도 모르겠습니다. 하지만 이는 $F^{f^{\prime }}=\widehat{F^f}$랑 다릅니다. 앞에서 한 논의를 그대로 써먹으려면 둘이 동일해야 하죠.

 

안타깝지만 $\widehat{F^f}$가 $F^{f^{\prime }}$보다 더 많은 간선을 갖고 있을 수 있습니다. 따라서 $\widehat{F^f}$에서 DFS를 돌리면 어쩌면 "막다른 길"에 다다를 수 있고, 그렇게 되면 왔던 길을 되돌아가는 불상사가 발생할 것입니다. 이 모든 상황을 다 고려하면 갱신된 네트워크 위에서 $s$에서 DFS를 수행하여 증가 경로를 찾는 방법의 수행 시간을 $O(|V|)$로 분석하기는 쉽지 않습니다.

그림 2. 막다른 정점이 발생하는 예시. (a) 그림 1-(b)의 최단 증가 경로 $P$. (b) $f^{\prime }:=f\uparrow f_P$로 증가시킨 후 갱신된 레이어드 네트워크 $\widehat{L_f}$의 모습. 정점 $a$, $b$, $d$는 $G_{f^{\prime }}$의 최단 증가 경로에는 나타나지 않지만 $\widehat{L_f}$에는 존재한다.

그렇다면 방법이 없을까요? 앞에서 분석했던 내용을 다시 곰곰이 생각해 봅시다. 갱신된 네트워크에서 $s$에서 출발해 DFS를 수행할 때 언젠가 어느 정점에서 더이상 다음 층으로 진행할 수 없는 "막다른 길"에 도달했다고 가정해 봅시다. 과연 이후에 해당 정점을 다시 방문할 필요가 있을까요?

 

아니요, 없습니다! 레이어드 네트워크의 모든 간선은 이전 층에서 다음 층으로 가는 방향 뿐입니다. 게다가 앞에서 확인했듯이 레이어드 네트워크는 갱신이 될 때마다 간선이 사라지기만 할 뿐입니다. 그러므로 어느 정점이 "막다른 길"로 판단이 된 후에는 과감히 그 정점과, 그 정점으로 들어오는 간선을 무시해 주면 됩니다.

알고리즘 4. Finding an augmenting path in a layered network

---

입력: (갱신된) 레이어드 네트워크 $L=(U,F)$

출력: 증가 경로 혹은 $s$에서 $t$로 도달할 수 없음을 판별

 

1. $s$를 기점으로 다음을 고려하며 DFS를 수행한다.
   1. 만약 어떤 정점를 방문했을 때, 다음 층으로 가는 간선이 존재하지 않으면 해당 정점과 해당 정점으로 들어오는 간선을 $L$에서 지운다.
   2. 만약 $t$에 도달하면, 방문한 경로를 출력한다.
   3. 도달하지 못하면(즉, 네트워크의 모든 개체가 지워졌으면) $s$에서 $t$로 도달할 수 없다고 판별한다.

이제 수행 시간을 분석해 봅시다. 사실 알고리즘 4가 한 번 수행될 때 걸리는 시간은 여전히 $O(|V|)$를 초과할 수 있습니다. 하지만 이전에 막다른 정점을 삭제하지 않는 DFS에 반해 이 알고리즘은 언젠가 막다른 정점에 도달하면 다시는 막다른 정점을 방문하지 않습니다. 따라서 우리는 이 알고리즘의 수행 시간을 거시적인 관점에서 분석해야 이득을 볼 수 있습니다.

정리 3. 최단 증가 경로를 한번에 찾을 때의 총 수행 시간

---

어떤 흐름을 시작으로 레이어드 네트워크를 만든 후, 레이어드 네트워크에서 $s$에서 $t$까지 도달 가능할 동안 알고리즘 4를 사용하여 같은 길이의 최단 증가 경로를 찾고 이를 따라 흐름을 증가시킨 후 레이어드 네트워크를 갱신하면, 이를 모두 수행하는데 들어가는 시간은 $O(|V||E|)$이다.

[증명] 앞에서 레이어드 네트워크를 만드는 작업, 최단 증가 경로를 따라 흐름을 증가시키는 작업, 레이어드 네트워크를 갱신하는 작업은 각각 $O(|E|)$, $O(|V|)$, $O(|V|)$ 시간에 끝낼 수 있다고 하였습니다. 또한 레이어드 네트워크가 한 번 갱신될 때마다 간선이 사라지기만 하므로 알고리즘 4를 제외한 나머지 작업은 총 $O(|V||E|+|E|)$ 시간만 사용합니다.

 

이제 알고리즘 4를 수행하는데 필요한 총 시간을 계산해 보겠습니다. 알고리즘 4가 $s$부터 출발해서 방문한 정점을 시간 순서대로 나열한 것을 생각해 봅시다. 그러면 우리는 이 정점 나열을 다음과 같은 두 부류로 나눌 수 있습니다.

1. 이번 수행 동안 막다른 정점으로 밝혀져 지워진 정점들
2. 그렇지 않은 정점들

여기서 우리는 이 정점 나열에서 막다른 정점으로 판정되지 않은 정점들의 개수가 정확히 층의 개수와 같아진다는 것을 알 수 있습니다. 반면 이번에 막다른 정점으로 판명된 정점들은 이후 다시는 방문되지 않습니다. 따라서 총 수행 시간도 다음의 두 부류에 맞추어 생각해 보겠습니다.

1. 어떤 정점이 막다른 정점으로 밝혀지면 다음에는 전혀 호출되지 않으므로 이에 해당된 정점과 그 정점으로 들어오는 간선을 지우는데 들어가는 총 소요 시간은 $O(|E|)$가 됩니다.
2. 그외의 정점들이 실제 최단 경로를 찾는데 소모한 시간으로 볼 수 있고, 그 길이가 $O(|V|)$이므로 총 $O(|V||E|)$의 시간을 쓰게 됩니다.

따라서 $s$에서 $t$까지 도달할 수 없을 때까지 필요한 총 수행 시간은 $O(|V||E|+|E|)$가 됩니다. ■

 

지금까지 정리한 내용을 종합해 디니츠의 알고리즘을 기술해 보겠습니다.

알고리즘 5. Dinitz' algorithm

---

입력: 흐름 네트워크 $G,c$, 시종점 $s,t$

출력: 최대 흐름

 

1. $f\leftarrow 0$
2. $G_f$에서 $s$에서 $t$에 도달할 수 없을 때까지 아래를 반복한다.
   1. 알고리즘 3을 사용하여 레이어드 네트워크 $L:=L_f$을 만든다.
   2. $L$에서 $s$에서 $t$에 도달할 수 없을 때까지 아래를 반복한다.
      1. $L$에서 알고리즘 4를 통해 $s$에서 $t$로 가는 최단 증가 경로 $P$를 찾는다.
      2. $f:=f\uparrow f_P$
      3. $L$을 갱신한다.
3. $f$를 반환한다.

마치며

이것으로 디니츠의 알고리즘에 대한 정리를 모두 마치겠습니다. 같은 길이의 최단 증가 경로를 한번에 찾아서 적용하는 이 알고리즘은 최대 흐름 문제 및 관련된 분야에 적잖은 파장을 주었습니다. 개인적으로 그중 가장 유명하다고 생각하는 성과는 바로 호프크로프트-카프 알고리즘(Hopcroft-Karp algorithm)입니다. 이는 최대 이분 매칭(maximum bipartite matching)을 $O((|V|+|E|)\cdot \sqrt{|V|})$ 시간에 해결하는 알고리즘으로 유명하죠. 사실 호프크로프트-카프 알고리즘은 디니츠의 알고리즘과 동작 방식이 동일합니다. 다만 이분 그래프(bipartite graph)라는 점과 가중치가 없다는 점 때문에 더 좋은 시간 복잡도를 얻을 수 있었던 것이죠. 호프크로프트-카프 알고리즘에 대해서 궁금하시면 아래 포스트를 참조하시기 바랍니다.

2020/02/22 - [조합론적 최적화/Matching] - 호프크로프트-카프 알고리즘 (Hopcroft-Karp Algorithm)

호프크로프트-카프 알고리즘 (Hopcroft-Karp Algorithm)

어김 없이, 컴퓨터과학의 숙명과도 같은 문제를 가지고 오겠습니다. 과연 더 잘 할 수 있을까요? 놀랍게도 가능합니다. 다만 그 방법들은 매번 잔여 네트워크에서 증가 경로를 찾아 흐름을 증가시키는 포드-풀커슨 방법 기반이 아닙니다. 기회가 되면 이에 대해서 정리하는 시간을 갖도록 하겠습니다.

 

궁금하신 점이 있으시거나, 글의 내용에 잘못된 부분이 있으면 알려 주시기 바랍니다. 고맙습니다.

참조

[1] Yefim Dinitz. "Dinitz’algorithm: The original version and Even’s version." In Theoretical computer science, pp. 218-240. Springer, Berlin, Heidelberg, 2006.