에드몬즈-카프 알고리즘 (Edmonds-Karp Algorithm)

Photo by Victor Garcia on Unsplash

최대 흐름 문제(maximum flow problem)는 어떤 흐름 네트워크(flow network)가 주어졌을 때 시점(source)에서 종점(sink)까지 최대로 많은 양의 흐름을 찾는 문제입니다. 이때 흐름은 각 간선에서 용량(capacity)을 넘을 수 없고, 시점과 종점을 제외한 나머지 정점에서는 들어오는 양과 나가는 양이 동일해야 하죠.

 

지난 포스트에서는 이 문제를 풀기 위하여 잔여 네트워크(residual network)와 증가 경로(augmenting path)가 무엇인지에 대해서 살펴보았으며, 최종적으로는 매번 현재 흐름으로 정의되는 잔여 네트워크 위에서 시점에서 종점으로 향하는 임의의 증가 경로를 찾아 현재 흐름을 증가시켜 주면 (모든 간선의 용량이 유리수일 때) 언젠간 최대 흐름을 찾게 된다는 것을 증명하였습니다. 이를 포드-풀커슨 방법(Ford-Fulkerson method)라고 불렀습니다.

 

포드-풀커슨 방법의 가장 큰 문제점은 효율적으로 동작한다는 보장을 하지 못한다는 것이었습니다. 이는 분석이 허술했던 게 아니었습니다. 증가 경로를 "멍청하게" 선택하면 포드-풀커슨 방법이 실제로 지수 시간(exponential time)에 동작하는 경우가 존재했습니다. 따라서 우리에게는 다음과 같은 의문이 자연스럽게 따라오게 됩니다.

만약 증가 경로를 "똑똑하게" 선택한다면 포드-풀커슨 방법이 효율적으로 동작할 수 있을까?

흥미롭게도 가능합니다. 매번 잔여 네트워크 위에서 시점에서 종점으로 가는 최단 경로(shortest path)를 하나 찾아 적용한다면, 이러한 포드-풀커슨 방법은 효율적으로, 즉 다항 시간(polynomial time)에 동작한다는 것을 보일 수 있습니다. 이 알고리즘이 바로 에드몬즈-카프 알고리즘(Edmonds-Karp algorithm)입니다.

 

이번 포스트에서는 에드몬즈-카프 알고리즘이 무엇인지 알아보고, 어째서 효율적으로 동작하는지에 대해서도 살펴보겠습니다. 이 글은 흐름 네트워크, 잔여 네트워크, 증가 경로, 포드-풀커슨 방법 등 최대 흐름 문제를 이해하는 데 필요한 기본적인 개념들을 잘 알고 있다는 가정 하에 작성되었습니다. 이에 대한 내용은 이전 포스트에서 소개하였으니 익숙하지 않으시면 이를 참조하시기 바랍니다.

포드-풀커슨 방법과 에드몬즈-카프 알고리즘

지난 포스트에서 다루었던 포드-풀커슨 방법을 다시 적어 보겠습니다. 사용된 기호는 모두 아래 포스트와 동일함을 알려 드립니다.

2020/08/30 - [조합론적 최적화/Flow & Circulation] - 포드-풀커슨 방법 (Ford-Fulkerson Method)

포드-풀커슨 방법 (Ford-Fulkerson Method)

Ford-Fulkerson method

---

입력: 흐름 네트워크 $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$를 반환한다.

이 방법은 $P$에 대한 조건이 $s$에서 $t$로 가는 단순 경로라는 것 말고는 존재하지 않기 때문에 매우 비효율적으로 동작하는 경우가 발생합니다. 에드몬즈-카프 알고리즘은 위에서 단 한 곳, 어떤 $P$를 찾을지에 대해 특정합니다. 바로 간선의 개수가 가장 적은 경로, 즉 최단 경로입니다.

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$를 반환한다.

이 알고리즘은 포드-풀커슨 방법의 한 가지 구현(implementation)에 해당합니다. 이전 포스트에서 우리는 용량이 모두 정수로 주어진다면 포드-풀커슨 방법이 최종적으로 최대 정수 흐름(maximum integral flow)을 반환한다는 것을 살펴보았습니다. 따라서 에드몬즈-카프 알고리즘도 최대 정수 흐름을 반환한다는 것을 알 수 있습니다. 이제 남은 것은 이 알고리즘이 다항 시간에 동작한다는 것을 보이는 것입니다.

다항 시간 알고리즘 증명

증명은 생각보다 어렵지는 않습니다. 이를 위해서는 각 정점이 잔여 네트워크 위에서 종점 $t$까지의 거리(distance)를 추적할 필요가 있습니다. 어떤 흐름 $f$에 대해, 한 정점 $v\in V$가 주어졌을 때, $d_f(v)$를 $G_f$ 위에서 $v$에서 종점 $t$까지 최단 경로의 간선의 개수라고 하겠습니다. 만약 도달할 수 없으면 $\mathrm{\infty }$를 갖습니다. 그러면 우리는 다음 정리를 보일 수 있습니다. 이 정리가 의미하는 바는 매번 $s$에서 $t$로 가는 최단 경로를 따라 흐름을 증가시키면 잔여 네트워크 상에서 각 정점은 종점 $t$로부터 계속 멀어지기만 한다는 것입니다.

정리 1. 잔여 네트워크 위에서의 거리의 증가성

---

언젠가 에드몬즈-카프 알고리즘이 $f$를 유지하고 있고, 단계 2-b를 통해 $f^{\prime }:=f\uparrow f_P$를 얻었다고 하자. 그러면 임의의 정점 $v\in V$에 대해 항상 $d_{f^{\prime }}(v)\ge d_f(v)$가 성립한다.

[증명] 증가시킨 후의 흐름 $f^{\prime }$에 대해 $V$의 모든 정점을 $d_{f^{\prime }}(v)$의 오름차순으로 정렬해 보겠습니다. 각 정점을 이 순서대로 살펴보면서 귀납적으로 증명하도록 하겠습니다. 첫 번째 정점은 분명 $t$가 되며, $d_{f^{\prime }}(t)=d_f(t)=0$이므로 정리의 명제가 자명하게 성립합니다. 이제 임의의 정점 $v$에 대해 귀납 가정(induction hypothesis)으로 이전에 나오는 정점들이 모두 정리의 명제가 성립한다고 가정하겠습니다. 만약 $d_{f^{\prime }}(v)=\mathrm{\infty }$인 경우에는 $d_f(v)\le \mathrm{\infty }$는 자명하므로 더 증명할 것이 없습니다.

 

따라서 $d_{f^{\prime }}(v)<\mathrm{\infty }$라고 가정하겠습니다. $G_{f^{\prime }}$ 위에서 $v$에서 $t$로 가는 최단 경로에서 $v$ 바로 다음 정점을 $u$라고 하겠습니다. 이때 만약 $⟨v,u⟩$가 증가시키기 전의 흐름 $f$의 잔여 네트워크 $G_f$ 위에 있었다면, $$d_{f^{\prime }}(v)=d_{f^{\prime }}(u)+1\ge d_f(u)+1\ge d_f(v)$$가 성립합니다. 여기서 첫 번째 부등식은 $u$가 정렬된 후에 $v$보다 이전에 위치하기 때문에 귀납 가정에 의해 성립하며, 두 번째 부등식은 $⟨v,u⟩\in E_f$이므로 $v$에서 $u$로 간 후 $u$에서 $t$까지 최단 경로를 타는 것이 $v$에서 $t$로 가는 경로 중 하나이기 때문에 만족합니다.

 

마지막으로 남은 경우는 $⟨v,u⟩\notin E_f$인 경우입니다. 이 상황은 분명 $⟨u,v⟩$가 이번에 취한 증가 경로 $P$ 위에 있다는 의미입니다. 그래야 $P$를 따라 흐름을 증가시켜 줘서 $G_{f^{\prime }}$에 $⟨v,u⟩$가 생기기 때문이죠. $P$가 $s$에서 $t$로 가는 최단 경로라는 사실을 통해 우리는 $d_f(u)=d_f(v)+1$이라는 것을 알 수 있고, 따라서 귀납 가정과 함께 $$d_{f^{\prime }}(v)=d_{f^{\prime }}(u)+1\ge d_f(u)+1=d_f(v)+2\ge d_f(v)$$임을 이끌어 낼 수 있습니다. ■

 

이 정리를 어떻게 활용해야 알고리즘이 다항 시간에 동작한다는 것을 보일 수 있을까요? 만약 매번 증가 경로를 적용시킬 때마다 $d_{f^{\prime }}(v)>d_f(v)$가 되는 정점 $v$가 하나라도 존재한다면 우리는 에드몬즈-카프 알고리즘의 단계 2가 총 $O(|V{|}^2)$ 동작한다는 것을 알 수 있습니다. 왜냐하면 어떤 그래프 위에서 어느 두 정점의 최단 경로의 간선 개수는 (도달할 수 있다면) $|V|-1$을 넘지 못하기 때문입니다. 만약 그렇게 된다면, 최단 경로는 BFS로 $O(|E|)$의 시간에 찾을 수 있으므로 총 $O(|V{|}^2|E|)$의 수행 시간을 갖게 될 것입니다. 하지만 안타깝게도 증가 경로를 적용시킨 후에도 모든 정점의 $d_f(v)$가 변화하지 않는 경우가 존재합니다. (그림 1)

그림 1. 증가 경로를 적용시킨 후에도 모든 정점의 $d_f(v)$가 변화하지 않는 경우. (i) 초기 $G,c$와 $f=0$의 모습. (ii) (i)의 $f$에 대한 $G_f$와 $P$의 모습. 파란색 기울임꼴 글씨는 각 정점 $v$의 $d_f(v)$를 나타낸다. (iii) (i)의 $P$를 적용시킨 다음 $f$의 모습. (iv) (iii)의 $f$에 대한 $G_f$의 모습. 모든 정점의 $d_f(v)$가 변화하지 않음을 확인할 수 있다.

따라서 이 방향으로는 분석할 수 없고, 다른 방법을 강구해야 합니다. 여기서 우리의 시야를 정점에서 간선으로 돌려 보겠습니다. 언젠가 알고리즘이 찾은 증가 경로 $P$ 위에서 가장 작은 잔여 용량을 갖는 간선을 $P$의 병목 간선이라고 부르겠습니다. 모든 증가 경로에는 최소한 하나의 병목 간선이 존재하므로, 만약 우리가 각 간선이 어떤 증가 경로의 병목 간선이 되는 횟수가 그리 커질 수 없다는 것을 보인다면 알고리즘이 단계 2를 수행하는 횟수도 그리 크지 않다는 것을 보일 수 있을 것입니다. 이 아이디어를 정형화한 것이 다음 정리입니다.

정리 2. 증가 경로를 찾는 횟수의 상한

---

에드몬즈-카프 알고리즘이 동작하면서 잔여 네트워크에 등장할 수 있는 임의의 간선 $⟨u,v⟩$에 대해 이 방향 간선이 어떤 증가 경로의 병목 간선이 될 횟수는 $|V|/2$를 넘지 않는다. 따라서 알고리즘이 단계 2를 수행하는 총 횟수는 $O(|V||E|)$이다.

[증명] 언젠가 알고리즘이 흐름 $f_1$을 유지하고 있을 때 $G_{f_1}$에서 찾은 증가 경로의 병목 간선이 $⟨u,v⟩$라고 하겠습니다. 그 후에 $⟨u,v⟩$가 어떤 증가 경로의 병목 간선으로 참여할 때 알고리즘이 유지하고 있는 흐름을 $f_3$라고 하겠습니다.

 

알고리즘이 $f_1$을 유지하고 있을 때 $⟨u,v⟩$가 병목 간선이었으므로 다음 흐름의 잔여 네트워크에는 $⟨u,v⟩$는 없고, 대신 그 반대 방향인 $⟨v,u⟩$만 있었을 것입니다. 그런데 그 이후에 $G_{f_3}$에서 $⟨u,v⟩$를 증가 경로에 포함시켰으려면 알고리즘이 $f_1$을 유지할 때와 $f_3$를 유지할 때 사이에 $G_{f_2}$에서 $⟨v,u⟩$가 포함된 증가 경로를 선택하는 흐름 $f_2$가 반드시 있어야 합니다.

 

이를 통해 우리는 $$d_{f_3}(u)=d_{f_3}(v)+1\ge d_{f_2}(v)+1=d_{f_2}(u)+2\ge d_{f_1}(u)+2$$를 이끌어 낼 수 있습니다. 여기서 모든 부등식은 정리 1을 통해 얻을 수 있으며, 모든 등식은 알고리즘이 매번 최단 경로를 찾기 때문에 성립합니다. 이로써 간선 $⟨u,v⟩$가 한 번 병목 간선으로 참여한 후에 다시 병목 간선이 되려면 $u$가 $t$로부터 2 이상 멀어져야 합니다. 앞에서 $u$가 $t$에 도달할 수 있을 때 $d_f(u)$의 값은 $|V|-1$을 넘을 수 없으므로 이 간선이 어느 흐름의 증가 경로의 병목 간선이 되는 횟수는 $|V|/2$를 넘지 못합니다.

 

에드몬즈-카프 알고리즘이 계속 수행되면서 잔여 네트워크에 등장할 수 있는 간선은 원래 네트워크의 간선의 전진 간선(forward edge)이나 후진 간선(backward edge) 뿐이며, 따라서 그 수는 $2|E|$를 넘지 못합니다. 매번 증가 경로를 찾을 때마다 적어도 하나는 병목 간선이 되므로, 알고리즘이 단계 2를 수행하는 횟수는 $O(|V||E|)$가 됩니다. ■

 

앞에서 최단 경로는 BFS를 사용하여 얻을 수 있다고 말씀 드렸습니다. 따라서 단계 2가 한 번 수행되는 데 필요한 시간은 $O(|E|)$입니다. 이 사실과 정리 2를 통해 에드몬즈-카프 알고리즘이 $O(|V||E{|}^2)$에 동작함을 알 수 있습니다.

마치며

여기까지 포드-풀커슨 방법의 다항 시간 구현 방법 중 하나인 에드몬즈-카프 알고리즘을 모두 살펴보았습니다. 포드-풀커슨 방법에서 단 하나, 어떤 증가 경로를 찾을지에 대해 특정한 것으로 지수 시간 알고리즘을 다항 시간 알고리즘으로 발전시킬 수 있었죠. 참으로 흥미로운 발견이 아닐 수 없습니다.

 

그럼에도 컴퓨터 과학의 숙명과도 같은 질문은 여전히 이어집니다. 과연 에드몬즈-카프 알고리즘을 발전시켜서 더 잘할 수 있을까요? 이는 최대 흐름 문제와 깊은 연관성이 있는 최대 이분 매칭 문제(maximum bipartite matching problem)에서 실마리를 찾을 수 있습니다. 최대 이분 매칭 문제를 해결하는 가장 간단한 방법은 매번 현재 매칭에 대한 증가 경로(augmenting path)를 하나 찾아서 적용하는 것입니다. 이때, 매번 가능한 짧은 증가 경로를 적용하면 흥미로운 성질을 하나 발견할 수 있는데, 바로 같은 길이의 증가 경로들이 서로 정점을 공유하지 않는다는 것입니다. 따라서 같은 길이의 증가 경로를 한번에 찾는다면 수행 시간을 단축시킬 수 있을 것입니다. 이 아이디어를 통해 얻은 방법이 바로 호프크로프트-카프 알고리즘(Hopcroft-Karp algorithm)입니다.

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

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

과연 비슷한 방법을 통해 에드몬즈-카프 알고리즘을 발전시킬 수 있을까요? 네, 그렇습니다. 그리고 그 알고리즘이 바로 디니츠의 알고리즘(Dinitz' algorithm)입니다. 우리에게는 디닉의 알고리즘(Dinic's algorithm)으로 더 잘 알려져 있죠. 다음 시간에는 이 알고리즘에 대해서 좀더 자세히 알아보도록 하겠습니다.

 

궁금한 점이 있으시거나, 내용에 오류가 있는 경우에는 알려 주시기 바랍니다. 고맙습니다. :)

참조

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, 3rd Edition. MIT Press 2009.