헝가리안 알고리즘 시간 복잡도 분석

지난번에 할당 문제와 헝가리안 알고리즘을 주제로 글을 작성하였습니다. 아래 링크를 참조하세요.

2019/08/07 - [조합론적 최적화/Matching] - 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm)

할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm)

저기서는 할당 문제가 무엇인지 알아보고 헝가리안 알고리즘이 어떻게 이 문제를 해결할 수 있는지를 보였습니다. 하지만, 한 가지 빼먹은 부분이 있는데, 그것은 바로 시간 복잡도(time complexity)입니다. 저 글에서는 헝가리안 알고리즘이 언젠간 끝난다는 것은 보였지만, 안타깝게도 입력의 다항 시간(polynomial time)에 동작한다는 것은 증명하지 못하였습니다. 이번에 그 해답을 드리고자 합니다. 아래에서 보일 것은 바로 헝가리안 알고리즘이 \(O(n^4)\)의 시간에 동작한다는 것입니다.(단, \(n\)은 노동자의 수이자 작업의 개수)

 

아래의 글은 다음과 같이 구성되었습니다. 먼저 할당 문제가 무엇인지 다시 한번 짚어보고 헝가리안 알고리즘이 어떻게 동작하는지를 살펴보도록 하겠습니다. 다음에는 쾨니그의 정리(Kőnig's theorem)를 기존에 제가 포스트한 방법과는 다른 방식으로 증명해 보도록 하겠습니다. 새 증명은 다음 절에서 헝가리안 알고리즘이 다항 시간 수행된다는 것을 보일 때 중요하게 사용됩니다.

 

참고로 아래 증명은 수업 시간에 배운 것을 바탕으로 작성되었습니다.

복습

가장 먼저 지난 포스트에서 다루었던 내용을 간략히 살펴보도록 하겠습니다. 할당 문제는 다음과 같이 정의됩니다. 노동자의 집합 \(I\)와 처리할 작업의 집합 \(J\)가 주어집니다.(단, \( n := |I| = |J| \)) 또, 각 노동자 \( i \in I\)를 어떤 작업 \( j \in J\)에 할당할 때 발생하는 비용 \( c(i, j)\)도 함께 주어집니다. 우리의 목표는 각 노동자를 정확히 하나의 작업에 겹치지 않게 모두 할당하는 방법 중 가장 비용이 저렴한 것을 찾는 것입니다.

 

이 문제는 bipartite graph를 통해서 해석할 수도 있다고 알려드렸습니다. \(I\)와 \(J\)를 정점으로 하는 complete bipartite graph를 만들고 간선에는 비용 \( c(i, j)\)를 두는 것이죠. 우리가 찾아야 하는 것은 이 그래프에서 비용이 가장 작은 perfect matching이 됩니다. 위 형식보다는 이 형식이 아래에 나올 내용을 이해하는 데 도움이 돼서 이 글에서는 할당 문제를 그래프 형식으로만 생각하도록 하겠습니다.

 

이전 포스트에서 소개된 헝가리안 알고리즘을 다시 기술하면 다음과 같습니다. 참고로 저번에는 \(i\)행 \(j\)열이 \( c(i,j) \)인 행렬에서 생각했지만 이번에는 그래프의 형식에서 생각할 것이므로 그에 맞게 바꿔서 적었습니다. 지난 글을 통해서도 이 변환은 충분히 이해하시리라 생각합니다.

알고리즘 1. Hungarian algorithm (Graph version)

---

입력: Complete bipartite graph \(G = (I \cup J, I \times J) \) (단, \(n := |I| = |J| \)), 간선 비용 \(c : I \times J \rightarrow \mathbb{Q} \)

출력: Minimum cost perfect matching in \(G\)

 

1. 모든 노동자 정점 \(i \in I\)에 대해, \(i\)에 부속된(incident) 모든 간선의 비용에 그 중 가장 작은 값을 뺀다.
2. 모든 작업 정점 \(j \in J\)에 대해, \(j\)에 부속된 모든 간선의 비용에다 그 중 가장 작은 값을 뺀다.
3. 비용이 0인 간선들의 집합을 \(E^\star\)라고 하자.
4. 모든 정점을 합해서 \( n \) 개보다 적게 뽑아 \(E^\star\)의 모든 간선을 부속시킬 수 있으면 다음을 수행한다.
   1. 그러한 방법 중 가장 크기가 작은 것을 \(I^\prime \subset I\), \(J^\prime \subset J\)라고 하자. 즉, \( I^\prime \cup J^\prime \)은 \((I \cup J, E^\star)\)의 minimum vertex cover이다.
   2. \(E^\star\)에 속하지 않은 간선 중 비용이 가장 작은 값을 \( \epsilon \)이라고 하자.
   3. \(I^\prime\)에 속하지 않은 노동자 정점 \(i\)에 대해서, \(i\)에 부속된 모든 간선의 비용에 \(\epsilon\)을 뺀다.
   4. \(J^\prime\)에 속하는 작업 정점 \(j\)에 대해서, \(j\)에 부속된 모든 간선의 비용에 \(\epsilon\)을 더한다.
   5. \(E^\star\)를 갱신한다.
5. \((I \cup J, E^\star)\)에서 perfect matching을 찾아 출력한다.

 

지난 포스트에서는 비용 \(c\)에다 직접 값을 빼거나 더해서 모든 비용을 0보다 크거나 같은 값으로 만들어 주었습니다만, 사실은 다음과 같이 알고리즘을 표현하는 것이 일반적입니다.

알고리즘 2. Hungarian algorithm (Revised)

---

입력: Complete bipartite graph \(G = (I \cup J, I \times J) \) (단, \(n := |I| = |J| \)), 간선 비용 \(c : I \times J \rightarrow \mathbb{Q} \)

출력: Minimum cost perfect matching in \(G\)

 

1. 모든 노동자 정점 \(i \in I\)에 대해, \( \displaystyle y_i \gets \min_{j : (i, j) \in E} c(i, j) \).
2. 모든 작업 정점 \(j \in J\)에 대해, \( \displaystyle z_j \gets \min_{i : (i, j) \in E} \left[ c(i, j) - y_i \right] \).
3. \(E^\star \gets \{ (i, j) \in I \times J : c(i, j) - y_i - z_j = 0 \}\)
4. 모든 정점을 합해서 \( n \) 개보다 적게 뽑아 \(E^\star\)의 모든 간선을 부속시킬 수 있으면 다음을 수행한다.
   1. 그러한 방법 중 가장 크기가 작은 것을 \(I^\prime \subset I\), \(J^\prime \subset J\)라고 하자. 즉, \( I^\prime \cup J^\prime \)은 \((I \cup J, E^\star)\)의 minimum vertex cover이다.
   2. \( \displaystyle \epsilon \gets \min_{i \notin I^\prime, j \notin J^\prime} \left[ c(i, j) - y_i - z_j \right] \)
   3. \( y_i \gets \left\{ \begin{array}{ll} y_i, & \text{if } i \in I^\prime, \\ y_i + \epsilon, & \text{otherwise.} \end{array} \right. \)
   4. \( z_j \gets \left\{ \begin{array}{ll} z_j - \epsilon, & \text{if } j \in J^\prime, \\ z_j, & \text{otherwise.} \end{array} \right. \)
   5. \(E^\star \gets \{ (i, j) \in I \times J : c(i, j) - y_i - z_j = 0 \}\)
5. \((I \cup J, E^\star)\)에서 perfect matching을 찾아 출력한다.

잘 살펴보시면 알고리즘 1과 알고리즘 2에 차이가 없음을 이해하실 수 있을 것입니다. 앞에서 설명한 대로 비용 \(c(i, j)\)의 값을 바로 변화시키는 대신 \(y_i\)와 \(z_j\)를 두어 \( c(i, j) - y_i - z_j \)를 바뀐 비용으로 생각하고 알고리즘을 기술한 것뿐입니다. 한 가지, 이전 포스트에서 논의한 대로 단계 2를 수행한 이후에는 임의의 \(i \in I, j \in J\)에 대해서 \( c(i, j) - y_i - z_j \geq 0 \)이 유지됩니다.

쾨니그의 정리(Kőnig's theorem) 다시 증명

좋습니다. 여기까지 오셨다면, 이제 알고리즘 2의 어떤 부분이 "멍청"한 지를 생각해 볼 차례입니다. 가장 눈에 띄는 부분 중 하나는 바로 단계 4-i입니다. 저기에 적힌 내용에 따르면 단계 4에 매번 들어갈 때마다 알고리즘은 minimum vertex cover를 찾습니다. 이를 좀 똑똑하게 처리하는 방법은 없을까요? 우리는 일전에 bipartite graph에서의 matching과 vertex cover의 관계를 다룬 쾨니그의 정리를 살펴보았습니다.

정리 1. 쾨니그의 정리(Kőnig's theorem)

---

모든 bipartite graph에서 maximum matching의 크기와 minimum vertex cover의 크기는 동일하다.

지난번에 쾨니그의 정리를 증명할 때는 최대 유량 최소 컷 정리(max-flow min-cut theorem)를 사용했습니다. 때문에 maximum matching과 minimum vertex cover를 직접적으로 비교하지는 않았죠. 하지만 딱 봐도 둘의 연관성은 깊어 보입니다. 게다가 알고리즘 2의 단계 5를 보면 알 수 있듯이 우리의 최종 목표 또한 maximum matching의 끝장판인 perfect matching을 출력하는 것입니다. 따라서, 만약 우리가 어떤 maximum matching에서 크기가 동일한 vertex cover를 빠른 시간에 찾을 수 있다면, 알고리즘 2의 시간 복잡도를 끌어올릴 수 있을 것입니다.

 

시작하기 전에, matching과 관련된 기본적인 명칭을 짚고 넘어가겠습니다. 어떤 matching \(M \subseteq E\)가 주어졌을 때, 어떤 정점이 \(M\)의 어떤 간선의 한 끝점을 이루면 그 정점을 matched 되었다고 부릅니다. 반대로, \(M\)의 어떤 간선의 끝점이 되지 못하는 경우에는 exposed 되었다고 부르죠. 또한, 그래프에서 \(M\)에 들어간 간선과 \(M\)에 들어가지 않은 간선이 교차하는 경로를 \(M\)에 대한 alternating path라고 하며, 그러한 alternating path 중에서 시작점과 끝점이 모두 exposed 인 경우를 특별하게 \(M\)에 대한 augmenting path라고 부릅니다. 더 자세한 내용은 아래 포스트에서도 확인할 수 있습니다.

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

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

 

우리의 목표를 다시 말씀드리도록 하겠습니다. 임의의 bipartite graph \(G = (I \cup J, E) \)와 그 위의 maximum matching \(M \subseteq E\)가 주어졌습니다. 우리가 구해야 하는 것은 다음의 성질을 만족하는 \(I^\prime \subseteq I\)와 \(J^\prime \subseteq J\)입니다.

1. 모든 간선 \( (i, j) \in E\)에 대해, \(i \in I^\prime\)이거나 \(j \in J^\prime\)이다. 즉, \(I^\prime \cup J^\prime\)이 \(G\)의 vertex cover이다.
2. \(|I^\prime| + |J^\prime| = |M|\)이다.

 

이를 만들기 위해서는 약간의 장치가 필요합니다. 바로 \(G\)와 \(M\)을 활용하여 방향 그래프(directed graph) \(D = (I \cup J, A)\)를 만드는 것입니다. 여기서 정점은 \(G\)의 것을 그대로 가지고 오며, 방향 간선(arc) 집합 \(A\)는 다음과 같이 만들어집니다.

1. 만약 \( (i, j) \in M \)이면, \(j\)에서 \(i\)로 가는 \( \langle j, i \rangle \in A \)이다.
2. 반대로 만약 \( (i, j) \in E \setminus M \)이면, \(i\)에서 \(j\)로 가는 \( \langle i, j \rangle \in A \)이다.

위 변환 과정은 다음 그림을 참고하여 주시기 바랍니다.

그림 1. \(D\)의 생성 예시. 왼쪽 그림은 \(I := \{ a, b, c, d \}\)와 \(J := \{1, 2, 3, 4\}\)에 대해 그래프 \(G\)와 maximum matching \(M\)(빨간 실선)을 나타낸 것이고 오른쪽 그림은 이에 맞게 \(D\)를 만든 것을 나타낸 것이다.

하도 유명하여 아실 분들은 잘 아시겠지만, 이런 식으로 방향 그래프 \(D\)를 만든 이유는 이 위의 모든 경로가 본래 그래프 \(G\)에서 \(M\)에 대한 alternating path를 이루기 때문입니다.

그림 2. \(D\)에서의 경로가 \(G\)에서의 \(M\)에 대한 alteranting path를 이루는 것을 보여주는 예시.

자 이제 \(I^\prime\)과 \(J^\prime\)을 뽑아보도록 합시다. \(D\) 위에서 \(I\)의 임의의 exposed vertex로부터 도달할 수 있는(reachable) 모든 정점의 집합을 \( X \subseteq I \cup J \)라고 하겠습니다.(만약 exposed vertex가 없으면 \(I^\prime = I\)가 되므로 \(I^\prime\)이 vertex cover가 됩니다.) 그렇게 하면 놀랍게도, \[ I^\prime := I \setminus X, \quad J^\prime := J \cap X \]가 우리가 찾고 있는 것이 됩니다.

그림 3. \(X\)의 예시. 그림 1의 예시에서 \(I\)에 있는 exposed vertex는 \( a \)이며, 이 정점에서 도달할 수 있는 모든 정점은 \(X = \{ a, b, d, 1, 2\}\)이다. 따라서 이 예시에서는 \(I^\prime := \{c\}\)가, \(J^\prime := \{ 1, 2 \}\)가 된다.

먼저 성질 1, 즉 \(I^\prime \cup J^\prime\)이 vertex cover라는 성질을 증명해 보도록 하겠습니다. 이는 \(D\)의 특성을 이용하면 생각보다 간단히 보일 수 있습니다.

[성질 1 증명] 먼저 \( I \)를 \( I \cap X \)와 \(I \setminus X\)으로, \(J\)를 \(J \cap X\)와 \(J \setminus X\)로 분할하여 생각하겠습니다. 여기서 \(I^\prime := I \setminus X\)이고 \(J^\prime := J \cap X \)이므로 만약 \( I \cap X \)와 \(J \setminus X\) 사이에 간선이 존재하지 않는다는 것을 보이면 증명이 완료됩니다.

 

귀류법을 사용하기 위해 그러한 간선 \( (i, j) \)가 존재한다고 가정해 보겠습니다. 먼저 \( (i, j) \notin M \)이라면, \(D\)에서는 \( \langle i, j \rangle \)가 있었을 것입니다. 이때 \(i \in I \cap X\)이므로 \(I\)의 어떤 exposed vertex로부터 \(i\)에 도달할 수 있습니다. 이를 만족하는 경로에 \( \langle i, j \rangle \)만 덧대면 \(j\)도 해당 exposed vertex에서 도달할 수 있게 됩니다. 하지만 \(j \in J \setminus X\)라고 하였으므로, 모순이 됩니다.

 

반대로 \( (i, j) \in M \)이라면, \(D\)에는 \( \langle j, i \rangle \)가 있었을 것입니다. \(M\)은 matching이기 때문에 \(D\)에서 \(i\)로 들어오는 간선은 오직 저것뿐입니다. 그 말인즉슨, \(i\)가 \(I\)의 어떤 exposed vertex에서 도달이 가능하려면 분명히 \( \langle j, i \rangle \)을 타야만 한다는 뜻입니다. 이는 자연스럽게 \(j\)도 해당 exposed vertex로부터 도달이 가능했다는 뜻이 됩니다. 따라서 위와 똑같은 모순이 발생하게 되지요. ■

 

두 번째 성질을 보이기 위해서 우리가 요긴하게 사용할 특징은 바로 \(M\)이 maximum matching이라는 점입니다. 이전 포스트에서도 언급되었지만, \(M\)이 maximum matching이면 반드시 성립하는 성질이 있습니다.

정리 2. Maximum matching과 augmenting path

---

어떤 matching \(M\)이 maximum matching일 필요충분조건은 \(M\)에 대한 augmenting path가 존재하지 않는다는 것이다.

증명은 위 호프크로프트-카프 알고리즘 관련 포스트를 참조하여 주시기 바랍니다. 이 성질을 이용하면 우리는 당장 성질 2를 증명할 수 있게 됩니다.

[성질 2 증명] 먼저 \(I^\prime\)과 \(J^\prime\)이 모두 \(M\)에 대해 matched 되었다는 것을 보이겠습니다. 먼저 \(I^\prime := I \setminus X\)의 경우, \(X\)에 이미 \(I\)에서 exposed 한 정점들이 포함되므로 자명합니다.

그림 4. \(J^\prime\)은 모두 matched라는 사실을 보여주는 예시. 만약 \(J^\prime\) 중 exposed vertex가 있으면 원래 그래프에 augmenting path가 존재하게 된다.(예컨대, \(\langle a, 1, b, 2 \rangle\) 혹은 \(\langle d, 2 \rangle\) )

반대로 \(J^\prime := I \cap X\)에 exposed vertex가 존재한다는 것은 \(D\) 위에서 시작점과 끝점이 모두 exposed 한 경로가 존재한다는 의미가 됩니다. 앞에서 \(D\)의 모든 경로는 본래 그래프 \(G\)에서의 alternating path에 해당한다고 말씀드렸습니다. 따라서 그 경로는 \(G\)에서 \(M\)에 대한 augmenting path가 됩니다. 이는 정리 2에 의하여 모순이 됩니다.

 

임의의 \(j \in J^\prime\)에 대하여 \(M\)에 의해 matched 된 상대 정점 \(i \in I\)는 \(D\)의 정의에 의해서 \(X\)에 포함되게 됩니다. 따라서 \(i \notin I^\prime\)이 되고, 자연스럽게 \( |I^\prime| + |J^\prime| \leq |M| \)임도 보일 수 있습니다. 임의의 matching의 크기는 항상 어떤 vertex cover의 크기보다 크지 않기 때문에 이 식은 등식이 됩니다. ■

적용 및 분석

이것으로 우리가 원하는 결과를 얻었습니다. 위 절에서 보인 증명은 비단 쾨니그의 정리를 다른 방식으로 보인 것뿐만 아니라, 어떤 maximum matching에서 minimum vertex cover를 얻는 방법을 보여줍니다. 바로 그 matching에 관한 방향 그래프(위에서 \(D\))를 만들고 그 위에서 \(I\)의 모든 exposed vertex로부터 도달 가능한지를 따져보면 되는 것이죠. 따라서 우리는 알고리즘 내부에서 굳이 vertex cover를 별도로 찾을 필요 없이, 원래 우리가 관심을 갖고 있던 matching을 유지하는 것만으로도 충분히 알고리즘을 설계할 수 있게 됩니다.

 

근데 여기서 한 가지 의문점이 생기실 것입니다. 위 증명에서 사용한 matching은 maximum matching이었습니다. 만약 우리 알고리즘이 유지하고 있는 matching이 maximum matching이 아니라면 어떻게 할까요? 이것도 걱정하실 필요가 없습니다. 그렇다면 그 matching에는 분명히 augmenting path가 존재할 것입니다. 이를 어떻게 찾을까요? 고맙게도 이미 방법이 공개되었습니다. 네, 바로 \(I\)의 어떤 exposed vertex로부터 \(J\)의 어떤 exposed vertex가 도달 가능한지만 따져보면 됩니다. 즉, \(I\)의 exposed vertex로부터 도달 가능한 정점들을 아는 것만으로 모두 해결이 됩니다.

 

그렇다면 방향 그래프에서 어떤 정점으로부터 다른 어떤 정점이 도달 가능한지를 어떻게 알 수 있을까요? 이는 분명 학부 자료구조 시간이나 알고리즘 시간에 배우셨을 내용입니다. 바로 깊이 우선 탐색(depth first search, DFS)나 너비 우선 탐색(breadth first search, BFS)로 해결할 수 있습니다. 그것들의 시간 복잡도가 \(O(|V| + |E|)\)이고 이 문제는 complete bipartite graph까지 고려해야 하므로 DFS나 BFS를 한 번 수행하는데 \(O(n^2)\)의 시간이 필요합니다.

 

이 생각들을 정리하면 우리는 알고리즘을 다음과 같이 바꿔 쓸 수 있게 됩니다. 아래에서 \(\oplus\)는 대칭차(symmetric difference)를 의미합니다. 어떤 matching \(M\)과 이에 대한 augmenting path \(P\)가 주어졌을 때 \(M \oplus P\)는 \(P\) 위에서 \(M\)에 들어간 간선은 빼고, 반대로 들어가지 않은 간선은 넣어주는 식으로 만들어집니다. 자세한 내용은 호프크로프트-카프 알고리즘 게시글을 참고하세요.

알고리즘 3. Hungarian algorithm (Final)

---

입력: Complete bipartite graph \(G = (I \cup J, I \times J) \) (단, \(n := |I| = |J| \)), 간선 비용 \(c : I \times J \rightarrow \mathbb{Q} \)

출력: Minimum cost perfect matching in \(G\)

 

1. 모든 노동자 정점 \(i \in I\)에 대해, \( \displaystyle y_i \gets \min_{j : (i, j) \in E} c(i, j) \).
2. 모든 작업 정점 \(j \in J\)에 대해, \( \displaystyle z_j \gets \min_{i : (i, j) \in E} \left[ c(i, j) - y_i \right] \).
3. \(M \gets \emptyset, E^\star \gets \{ (i, j) \in I \times J : c(i, j) - y_i - z_j = 0 \}\)
4. \(M\)이 \(G\)의 perfect matching이 될 때까지 아래를 수행한다.
   1. \( (V, E^\star) \)에서 \(M\)에 대한 augmenting path \(P\)가 존재하면, \( M \gets M \oplus P\)를 한 후 단계 4로 돌아간다.
   2. 그렇지 않다면, 위 절에서 소개한 것처럼 \(I^\prime\)과 \(J^\prime\)을 찾는다.
   3. \( \displaystyle \epsilon \gets \min_{i \notin I^\prime, j \notin J^\prime} \left[ c(i, j) - y_i - z_j \right] \)
   4. \( y_i \gets \left\{ \begin{array}{ll} y_i, & \text{if } i \in I^\prime, \\ y_i + \epsilon, & \text{otherwise.} \end{array} \right. \)
   5. \( z_j \gets \left\{ \begin{array}{ll} z_j - \epsilon, & \text{if } j \in J^\prime, \\ z_j, & \text{otherwise.} \end{array} \right. \)
   6. \(E^\star \gets \{ (i, j) \in I \times J : c(i, j) - y_i - z_j = 0 \}\)
5. \(M\)을 출력한다.

거의 모든 부분이 이전 알고리즘과 비슷하지만 한 가지 짚고 넘어가야 할 점이 있습니다. 바로 단계 4-i에서 실패한 경우인데요. 그러면 이 알고리즘은 적절하게 \(y_i\)와 \(z_j\)를 변경하고 이에 맞춰 \(E^\star\)를 갱신하죠. 문제는 \(M\)은 변하지 않는다는 것입니다. 과연 \(M\)은 갱신된 \(E^\star\)에서도 온전한 채로 유지하게 될까요?

정리 3. \(M\)의 유지 성질

---

만약 알고리즘 3이 단계 4-i에서 그러한 경로를 찾는 데 실패했을 때, \(M\)은 갱신된 \(E^\star\)에 대해서도 여전히 \(M \subseteq E^\star \)이다.

[증명] 알고리즘 3에서 \(c(i, j) - y_i - z_j\)가 증가하여 \(E^\star\)에서 빠지는 경우는 \(i \in I^\prime\)이고 \(j \in J^\prime\)일 때뿐입니다. 위 절에서 본 증명에 따르면 \(i\)는 어떤 \(I\)의 exposed vertex로부터 도달이 불가능하지만, \(j\)는 가능합니다. 만약 \( (i, j) \in M \)이라면 \(D\)에서 \( \langle j, i \rangle \)가 존재했을 것이므로 \(i\)도 \(j\)를 통해 \(I\)의 exposed vertex로부터 도달 가능해지므로 모순이 됩니다. ■

 

이것 말고는 알고리즘 2와 동일하게 동작하므로 이 알고리즘은 정확하게 동작합니다. 이제 시간 복잡도를 분석해 봅시다. 여기서 우리가 집중해야 할 부분은 알고리즘 3에서 \(M\)의 크기가 어떻게 변화하는지입니다. 우리의 목표는 크기가 \(n\)인 \(M\)을 찾는 것입니다. 만약에 단계 4-i에서 \(M\)에 대한 augmenting path를 찾으면 우리는 기존보다 크기가 1만큼 커진 matching을 얻게 됩니다. 따라서 단계 4-i을 총 \(n\) 번 성공하면 알고리즘이 끝납니다.

 

그러므로 언젠간 단계 4-i을 성공했을 때와 그다음 단계 4-i을 성공했을 때 사이에 얼마나 많은 반복을 하는지가 중요합니다. 단계 4-i을 실패하면 \(y\)와 \(z\)의 값을 적절하게 바꾸는 작업을 거치는데, 여기서 문제는 이렇게 변경한 후에도 여전히 \((I \cup J, E^\star)\)에는 \(M\)에 대한 augmenting path가 존재하지 않을 수 있다는 점입니다. 다시 말해, 단계 4-i을 실패한 다음에 또 단계 4-i을 실패할 수도 있다는 것이죠. 이 작업을 다항 횟수로 한정하는 것이 우리의 목표가 됩니다. 이는 다음의 정리를 통해 해결할 수 있습니다.

정리 4. \(J^\prime\)의 단조 성질

---

알고리즘 3에서 언젠간 단계 4-i을 실패하였을 때 단계 4-ii에서 찾은 \(J^\prime\)을 \(J^\prime_\mathsf{prev}\)라고 하자. 만약 바로 다음번에 단계 4-i을 또 실패한 경우, 그때 단계 4-ii에서 찾은 \(J^\prime\)을  \(J^\prime_\mathsf{post}\)라고 하자. 그러면 \( J^\prime_\mathsf{prev} \subsetneq J^\prime_\mathsf{post} \)가 성립한다.

[증명] 이전이나 이후나 고려하고 있는 matching \(M\)은 동일합니다. 정리 3의 증명에서 보았듯이 갱신 후에 \(E^\star\)에서 사라지는 간선은 \( i \in I^\prime_\mathsf{prev}\), \( j \in J^\prime_\mathsf{prev} \)입니다.(단, \( I^\prime_\mathsf{prev} \)는 \(J^\prime_\mathsf{prev}\)를 찾을 때 함께 찾은 \(I^\prime\)) 따라서 이는 \(D\) 위에서 어떤 \(I\)의 exposed vertex로부터 도달할 수 없는 \(i\)로부터 도달할 수 있는 \(j\)로의 방향 간선 \( \langle i, j \rangle \)이 사라지는 것이므로 \(j\)의 도달 가능성에는 영향을 주지 않습니다. 이는 \( J^\prime_\mathsf{prev} \subseteq J^\prime_\mathsf{post} \)라는 점을 보입니다.

 

알고리즘에서 \(\epsilon\)은 \( i \notin I^\prime_\mathsf{prev} \), \( j \notin J^\prime_\mathsf{prev} \)인 간선 중 가장 \( c(i, j) - y_i - z_j \)의 값이 작은 것을 골랐습니다. 해당 최솟값을 이루는 간선을 \( (\hat{i}, \hat{j}) \)이라고 하겠습니다. 그러면 \(y_\hat{i}\)의 값은 \( \epsilon \)만큼 커지지만, \( z_\hat{j} \)는 같은 값을 유지하므로 \( c(\hat{i},\hat{j}) - y_\hat{i} - z_\hat{j} \)의 값이 0이되어 갱신 후에는 \( (\hat{i}, \hat{j}) \)가 \(E^\star\)에 들어오게 됩니다. 갱신 후에도 \(\hat{i}\)은 여전히 어떤 \(I\)의 exposed vertex로부터 도달할 수 있고, 그때의 \(D\)에는 \( \langle \hat{i}, \hat{j}  \rangle \)이 존재하므로 \( \hat{j} \in J^\prime_\mathsf{post} \setminus J^\prime_\mathsf{prev} \)임을 알 수 있습니다. ■

 

이제 우리는 알고리즘 3이 \(O(n^4) \)에 동작한다는 것을 증명할 수 있습니다.

정리 5. 헝가리안 알고리즘의 시간 복잡도

---

알고리즘 3은 \(O(n^4)\) 시간에 동작한다.

[증명] 단계 1, 2, 3은 모두 \( O(n^2) \)에 가능합니다. 앞에서 우리는 단계 4-i을 \(n\) 번 성공하면 알고리즘이 끝난다는 것을 확인하였습니다. 정리 4에 의해서 단계 4-i을 연속으로 실패할 수 있는 횟수는 \(n\)을 넘지 못한다는 점을 알 수 있습니다. 따라서 단계 4는 총 \( O(n^2) \) 번 반복합니다. 단계 4-i과 단계 4-ii는 DFS 혹은 BFS로 가능하다고 위에서 말씀드렸습니다. 단계 4-iii과 단계 4-vi는 \(O(n^2)\)에 가능하며 단계 4-iv와 단계 4-v는 \( O(n) \)에 가능합니다. 따라서 \(O(n^4)\) 시간에 수행이 됩니다. ■

마치며

이것으로 헝가리안 알고리즘이 \(O(n^4)\) 시간에 동작한다는 것을 보였습니다. 이를 위해서 최대 유량 최소 컷 정리가 아닌 maximum matching에서 직접 minimum vertex cover를 추출하는 방식으로 쾨니그의 정리를 다시 증명하였습니다. 따라서 알고리즘이 matching을 직접 유지하면서 동작할 수 있도록 바꿔주었습니다. 마지막으로 0의 비용을 갖는 간선으로 perfect matching이 아닌 maximum matching에 도달한 경우(즉, 알고리즘 3의 단계 4-i에서 실패한 경우) \(y\)와 \(z\) 값을 바꿔주게 되는데 바꾼 이후에도 또 maximum matching일 수 있지만(즉, 단계 4-i을 또 실패) 그 횟수가 그렇게 많지 않다는 것을 통하여 알고리즘의 시간 복잡도를 증명하였습니다.

 

인터넷에 검색해 보니 이 알고리즘을 \( O(n^3) \)으로도 만들 수 있다고 합니다. 근데 이 방향으로는 어떻게 가능한지 저는 잘 모르겠습니다. 어떤 강의 노트 등에서는 연습 문제로 내놓아서 도무지 답을 가르쳐 주지 않고, 또 어떤 분석은 그냥 잘못된 것 같았습니다. 분석이 잘못된 경우는 크게 두 가지로 구분할 수 있는데, 하나는 단계 4-i, 즉 augmenting path를 구하는 작업을 \(O(n)\)에 할 수 있다고 주장하는 것이고, 다른 하나는 단계 4-i을 실패했을 때 \(y\)와 \(z\)를 수정하면 바로 다음번에 단계 4-i을 성공한다고 주장하는 것입니다. 제 머리로는 그것들이 어떻게 가능한지 잘 모르겠습니다. 혹시 아신다면 알려주시기 바랍니다.

 

그렇다고 \( O(n^3) \) 알고리즘이 불가능한 것은 아닙니다. 사실 위 알고리즘이 여전히 멍청한 이유 중 하나는 모든 \(y\)와 \(z\)에 \( \epsilon \)이라는 같은 값을 더하거나 뺀다는 것입니다. 분명 어떤 정점들은 그것보다 더 큰 값을 더하거나 뺄 수 있었을 텐데 말이죠. 이것 때문에 발생하는 문제 중 하나가 바로 단계 4-i을 실패한 다음에 단계 4-i을 또 실패하는 것이죠. 참고로 이는 최단 경로 트리(shortest path tree)를 사용하면 해결할 수 있습니다. 논문 및 교재에 따라서는 이 방법도 헝가리안 알고리즘이라고 부르는 것 같기는 합니다. 나중에 기회가 되면 이것도 다루어 보도록 하겠습니다.

 

지금까지 긴 글 읽어 주셔서 고맙습니다. 이번에 글을 왕창 몰아서 적었는데, 모쪼록 휴식을 취한 후에 다음 포스팅할 거리를 찾아 헤매도록 하죠. 코로나19가 기승인데 모두 건강에 유의하시기 바랍니다.