Hopcroft–Karp bipartite matching algorithm

Hopcroft–Karp 알고리즘은 이분 그래프에서 최대 매칭을 $O((V+E)\sqrt{V})$에 구하는 알고리즘이다.

 

아이디어는 다음과 같다. 정점의 집합 $X$, $Y$가 있고, 이분그래프 $G = (X \cup Y, E)$의 어떤 매칭 $M$이 있다고 하자. (매칭은 간선의 집합이라고 보고, 자명히 $M \subset E$ 다.) 이때 $X$에 속하면서 아직 매칭되지 않은 정점에서 출발해, $E-M$에 속한 간선과 $M$에 속한 간선을 번갈아 가면서 $Y$에 속하면서 아직 매칭되지 않은 정점으로 도착하는 단순 경로를 확장 경로(augmenting path)라고 한다. 이때 어떤 매칭인지 언급해야 할 필요가 있을 경우 M-확장 경로(augmenting path with respect to M)라고 한다. 확장 경로를 찾으면 매칭의 크기를 1 늘릴 수 있다.

 

 

위의 그림을 보자. 첫 번째 그림에서 점선은 매칭에 속하지 않은 간선, 실선은 매칭에 속한 간선이다. 이때 두 번째 그림에서 주황색으로 표시한 확장 경로에서 매칭에 속한 간선은 매칭에서 제외하고, 매칭에 속하지 않은 간선은 매칭에 포함시킨다. 확장 경로에 속한 간선의 상태를 뒤집는다고 생각하면 된다. 이러면 세 번째 그림처럼 매칭의 크기가 1 늘어나게 된다. 이를 좀 더 엄밀하게 증명해보자. 확장 경로를 $P$라고 하면 확장 경로에 속한 간선의 상태를 뒤집는 과정은 $M$ 대신 $M \triangle P$를 매칭으로 택한다고 볼 수 있다. ($\triangle$은 대칭차집합 기호로, $M \triangle P = (M-P)\cup(P-M)$이다.)

 

• $M \triangle P$가 $M$보다 크기가 1 큰 매칭임을 증명하자.

먼저 $M \triangle P$가 매칭임을 증명하자. $M \triangle P$가 매칭이 아니라면 $M \triangle P$에 속한 두 간선이 공유하는 점인 $v$가 있을 것이다. 이 간선들을 $e_1$, $e_2$라고 하면 $M-P$와 $P-M$은 서로소이므로 각 간선은 두 집합 중 한 곳에만 속해야 한다. $e_1, e_2 \in M-P \subset M$이라면 $M$이 매칭이 아니므로 모순이고, $e_1, e_2 \in P-M$이라면 매칭에 속하지 않은 간선을 두 번 지나서 $P$가 확장 경로가 아니므로 모순이다. 따라서 일반성을 잃지 않고 $e_1 \in M-P$, $e_2 \in P-M$이다. 그런데 $e_1$에 의해 $v$는 매칭된 정점이므로 확장 경로의 양 끝점이 될 수 없다. 따라서 $e_2$로 들어온/나가는 확장경로는 $v$에서 멈추지 않고 $M$에 속한 유일한 간선인($M$은 매칭이므로 해당되는 간선은 유일하다) $e_1$으로 나가야/들어와야 한다. 이때 $e_1 \in M-P, e_1 \in P$이므로 모순이 된다. 따라서 귀류법에 의해 $M \triangle P$은 매칭이다.

이제 $M \triangle P$가 $M$보다 크기가 1 크다는 사실을 증명하자. $P$의 양 끝점은 매칭되지 않은 정점이므로, $P$의 양 끝 간선은 $M$에 속하지 않는다. $P$는 $E-M$에 속한 간선과 $M$에 속한 간선을 번갈아 가므로, $P$는 $E-M$에 속한 $k+1$개의 간선과 $M$에 속한 $k$개의 간선을 지나게 된다. 따라서 $\ABS{M \triangle P} = \ABS{M} + \ABS{P} - 2\ABS{M \cap P} = \ABS{M} + (2k+1) - 2(k) = \ABS{M}+1$이다. ■

 

따라서 확장 경로를 찾으면 매칭의 크기를 1 늘릴 수 있다. 이제 확장 경로가 없을 때 최대 매칭이 되는 것을 증명하자.

 

• 어떤 그래프 $G = (V, E)$의 매칭 $M$, $M'$가 $\ABS{M'}\geq\ABS{M}$을 만족한다면, $M \triangle M'$은 적어도 $\ABS{M'}-\ABS{M}$개의 정점이 겹치지 않는(vertex disjoint) M-확장 경로를 포함한다.
  

그래프 $G' = (V, M \triangle M')$를 생각하자. 이 그래프의 모든 정점은 차수가 2 이하다. (그래프의 모든 간선은 $M-M' \subset M$이나 $M'-M \subset M'$에 속한다. 만약 차수가 3 이상인 정점이 존재한다면 비둘기집의 원리에 의해 $M$이나 $M'$중 어느 한 쪽에 간선이 2개 이상 있어야 하므로 모순이다.) 따라서 $G'$는 단순 경로와 사이클로 이루어져 있다. 이때 매칭은 한 정점을 공유하는 2개 이상의 간선을 가질 수 없으므로 $G'$의 모든 경로는 $M-M'$에 속한 간선과 $M'-M$에 속한 간선을 번갈아 가야 한다.

이분그래프의 사이클의 길이는 짝수이므로 $M-M'$과 $M'-M$에서 지나간 간선 수가 같다. 따라서 $M-M'$과 $M'-M$에서 지나간 간선 수가 다르려면 단순 경로여야 하며, $M-M'$에 속한 간선이 1개 더 많거나 $M'-M$에 속한 간선이 1개 더 많아야 한다. 이때 $M'-M$에 속한 간선이 1개 더 많으려면 양 끝 간선이 $M'-M$에 속해야 하므로 이 단순 경로는 M-확장 경로가 된다. 따라서 그래프 $G'$는 적어도 $\ABS{M'-M}-\ABS{M-M'} = \ABS{M'}-\ABS{M}$개의 정점이 겹치지 않는(vertex disjoint) M-확장 경로를 포함한다.■

 

최대 매칭이 아닌 경우 확장 경로가 존재하므로, 확장 경로가 없을 경우 최대 매칭이 된다. 따라서 더 이상 확장 경로를 찾을 수 없을 때까지 확장 경로를 찾아서 확장 경로에 속한 간선의 상태를 뒤집으면 최대 매칭을 구할 수 있다. Hopcroft–Karp 알고리즘은 여기서 길이가 제일 짧은 확장 경로들부터 찾는 알고리즘이다.

1. $M\gets\varnothing$
2. $\mathcal{P}\gets\{ P_1, P_2, \ldots, P_k \}$는 최단 M-확장 경로들을 정점이 안 겹치게 최대한 고른 집합
3. $\mathcal{P}=\varnothing$이면 $M$이 최대 매칭이므로 알고리즘을 종료한다.
4. $\mathcal{P}\neq\varnothing$이면 $M \gets M\triangle(P_1 \cup P_2 \cup \ldots \cup P_k)$ 후 과정 2로 돌아간다.

추후에 보겠지만, 최단 M-확장 경로들을 찾고 간선의 상태를 뒤집는 과정을 BFS 한 번, DFS 한 번으로 구할 수 있어서 $O(V+E)$의 시간이 걸린다. 또한 알고리즘의 반복문은(과정 2~4) 최대 $O(\sqrt{V})$번 돌아간다. 따라서 Hopcroft-Karp 알고리즘의 시간복잡도는 $O((V+E)\sqrt{V})$다.

반복문이 최대 $O(\sqrt{V})$번 돌아가는 것을 증명하기 위해 몇 가지를 정의하고 들어가자. 매칭 $M$이 있을 때 $\{ P_1, P_2, \ldots, P_k \}$를 최단 M-확장 경로들을 정점이 안 겹치게 최대한 고른 집합으로 정의하고 최단 M-확장 경로의 길이를 $l$이라고 한다. 또한, 매칭 $M'=M\triangle(P_1 \cup P_2 \cup \ldots \cup P_k)$에서 $P$를 임의의 최단 M'-확장 경로라고 하자.

 

• $P$가 $P_1, P_2, \ldots, P_k$와 정점이 안 겹친다면 $P$의 길이는 $l$보다 길다.

간선이 겹치면 정점이 겹치므로 정점이 겹치지 않으면 간선이 겹치지 않는다. 따라서 $P$에 속한 임의의 간선 $e$에 대해 $e \in M'$이라면 $e \in M - (P_1 \cup P_2 \cup \ldots \cup P_k) \subset M$이고, $e \in E-M'$이라면 $e \in E - (M \cup (P_1 \cup P_2 \cup \ldots \cup P_k)) \subset E-M$이므로, $P$는 M-확장 경로다. $\ABS{P} < l$이라면 최단 M-확장 경로의 길이가 $l$이라는 조건과 모순이고, $\ABS{P} = l$이라면 $P_i$들이 최대한 고른 집합이라는 조건과 모순이므로 $\ABS{P} > l$이다.■

 

• $P$가 $P_1, P_2, \ldots, P_k$와 정점이 겹친다면 간선도 겹친다.

겹친 정점을 $v$라고 하고 $P_1, P_2, \ldots, P_k$중 $v$를 포함하는 M-확장 경로를 $P_i$라고 하자. 이때 $v$가 $M$에서 매칭된 정점이라면 $P_i$의 양 끝점이 될 수 없으므로 $M$에 속하지 않은 간선으로 들어오면/나가면 $P_i$는 $v$에서 멈추지 않고 $M$에 속한 간선으로 나가야/들어와야 한다. 또한 $v$가 $M$에서 매칭되지 않은 정점이라면 $M$에 속한 간선이 없으므로 $M$에 속하지 않은 간선으로 나가야/들어와야 한다. 따라서 $P_i$는 $M$에 속하지 않고 끝점이 $v$인 간선이 존재하며, 이 간선은 $M'$의 정의에 의해 $M'$에서 $v$가 매칭된 간선이 된다.

이제 $v$는 $M'$에서 매칭된 정점이므로 $P$의 양 끝점이 될 수 없고, $M'$에 속하지 않은 간선으로 들어오면/나가면 $P$는 $v$에서 멈추지 않고 $M'$에 속한 유일한 간선으로 나가야/들어와야 한다. 이 간선은 $P$와 $P_i$에 동시에 속해있으므로, $P$와 $P_i$는 겹치는 간선이 존재한다.■

 

• $P$가 $P_1, P_2, \ldots, P_k$와 정점이 겹친다면 $P$의 길이는 $l$보다 길다.

$A=M \triangle M' \triangle P$라고 하자. $M' \triangle P$는 매칭이고, $M$에서 확장 경로 $k+1$개를 찾은 후의 매칭이므로, $\ABS{M' \triangle P} - \ABS{M} = k+1$이다. 따라서 위에서 증명한대로 $A$는 적어도 $k+1$개의 정점이 겹치지 않는 M-확장 경로를 포함한다. 최단 M-확장 경로의 길이는 $l$이고, 정점이 겹치지 않으면 간선이 겹치지 않으므로, $\ABS{A} \geq (k+1)l$이다.

대칭차는 교환 법칙과 결합 법칙이 성립하므로 $M'$의 정의에 의해 $A=(P_1 \cup P_2 \cup \ldots \cup P_k) \triangle P$다. 정점이 겹치지 않으면 간선이 겹치지 않으므로 $\ABS{(P_1 \cup P_2 \cup \ldots \cup P_k)}=kl$이다. 따라서 $\ABS{P-(P_1 \cup P_2 \cup \ldots \cup P_k)}\geq l$이다. 이때 위에서 증명한대로 $P$와 $(P_1 \cup P_2 \cup \ldots \cup P_k)$에 모두 포함된 간선이 있으므로 $\ABS{P} \geq l+1 > l$이다.■

 

• Hopcroft-Karp 알고리즘의 반복문은 최대 $2\sqrt{V}$번 돌아간다.

$P$의 길이는 $l$보다 길으므로, 반복문을 돌 때마다 최단 확장 경로의 길이는 길어진다. 따라서 만약 반복문을 $\sqrt{V}$번 돌았다면, 최단 확장 경로의 길이가 $\sqrt{V}$ 이상이므로 정점이 겹치지 않는 확장 경로는 최대 $\sqrt{V}$개 이하다. $M'$를 임의의 최대 매칭이라고 하면 위에서 증명한 정리의 대우로 인해 $\ABS{M'} - \ABS{M} \leq \sqrt{V}$다. 확장 경로를 $\ABS{M'} - \ABS{M}$개 찾아야 하고, 반복문을 돌 때마다 확장 경로를 1개 이상 찾으므로 반복문은 앞으로 최대 $\sqrt{V}$번 돌 수 있다. 따라서 반복문은 최대 $2\sqrt{V}$번 돌아간다.■

 

이제 남은 것은 Hopcroft-Karp 알고리즘을 실제로 코드로 구현하는 것이다. C++로 구현한 코드가 아래에 있다.

class Hopcroft_Karp {
private:
	int n;
	vector<int> X, Y, dist;
	vector<vector<int>> graph;
	// n = X그룹의 원소 수, 원소들은 1부터 시작해야 함 (1base)
	// X, Y = X, Y그룹의 i번 원소와 매칭된 상대편 원소 번호
	// dist = 매칭되지 않은 X그룹의 원소로부터 X그룹의 i번 원소까지의 거리
	// graph = X그룹의 i번 원소와 연결된 Y그룹의 원소 번호들

	// 확장 경로가 존재하는지를 리턴함
	bool bfs(){
		queue<int> q;
		dist[0] = INT_MAX;
		for (int i = 1; i <= n; i++) {
			if (!X[i]){
				dist[i] = 0;
				q.push(i);
			}
			else dist[i] = INT_MAX;
		}
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			for (int y : graph[x]) {
				if (dist[Y[y]] == INT_MAX) {
					dist[Y[y]] = dist[x] + 1;
					q.push(Y[y]);
				}
			}
		}

		return dist[0] != INT_MAX;
	}

	// x를 지나가는 확장 경로가 있는지를 리턴함
	bool dfs(int x){
		for (auto y : graph[x]) {
			if (dist[Y[y]] == dist[x] + 1 && (!Y[y] || dfs(Y[y]))){
				X[x] = y; Y[y] = x;
				return true;
			}
		}

		dist[x] = INT_MAX;
		return false;
	}

public:
	Hopcroft_Karp(int x_count, int y_count)
		: n(x_count), X(x_count + 1), Y(y_count + 1), dist(x_count + 1), graph(x_count + 1) {}

	void addEdge(int x_node, int y_node) {
		// 1 <= x_node <= x_count, 1 <= y_node <= y_count를 만족해야 함
		graph[x_node].push_back(y_node);
	}

	// 최대 매칭의 크기를 리턴함
	int solve(){
		int match = 0;
		while (bfs()) {
			for (int i = 1; i <= n; i++) {
				if (!X[i] && dfs(i)) {
					match++;
				}
			}
		}

		return match;
	}

	const vector<int>& getX() const {
		return X;
	}
	const vector<int>& getY() const {
		return Y;
	}
};

생성자로 $\ABS{X}$, $\ABS{Y}$를 넘겨주고, addEdge로 간선들을 추가한 다음 solve를 돌리면 최대 매칭의 크기를 리턴한다. 어떤 정점이 매칭됐는지 알아야 한다면 getX, getY로 $X$나 $Y$의 정점과 매칭된 정점을 확인할 수 있다.

제일 중요한 solve를 보자. 먼저 BFS로 최단 확장 경로를 구한다. BFS로 최단거리를 구하는 원리와 똑같다. 이때 시간과 메모리를 줄이기 위해 $X$의 정점만 계산하며, $Y$의 정점은 즉시 $Y$와 매칭된 정점으로(Y[y]) 이동한다고 생각한다. BFS는 확장 경로를 따라서 이동하면서 매칭되지 않은 $X$의 정점으로부터 최단거리를 dist에 저장한다. 확장 경로 마지막에는 매칭되지 않은 정점에 도착하므로 Y[y]는 0이 된다. 따라서 확장 경로가 있다면 제일 짧은 확장 경로의 길이가 (정확히는 $X$의 정점만 셌을 때 길이가) dist[0]에 저장되고, 확장 경로가 없다면 dist[0]은 바뀌지 않아서 INT_MAX 상태로 남아있게 된다. 이를 이용해 확장 경로가 존재하는지 확인할 수 있고, 이후에 DFS를 통해 이동할 때 모든 확장 경로가 아니라 최단 확장 경로를 통해서만 이동할 수 있게 만든다.

이제 DFS를 통해 최단 확장 경로들을 찾고 매칭에 포함시켜야 한다. 확장 경로는 매칭되지 않은 정점부터 시작해야 하므로 X[i] == 0인 정점에서 DFS를 시작한다. 이때 BFS에서 구한 최단거리를 따라서 이동하면 DFS에서도 확장 경로를 따라서 이동할 수 있다. 만약 Y[y] == 0이거나, 이후 DFS로 확장 경로를 찾았다면 X[x] = y; Y[y] = x;로 간선의 상태를 뒤집고 true를 리턴한다. 이 정점에서 갈 수 있는 모든 정점을 봤지만 가능한 확장 경로가 없다면 false를 리턴한다.

보통 여기서 DFS에서 같은 정점을 두 번 이상 지나가지 않기 위해 visit 배열 등을 사용하지만, 이 코드에서는 그럴 필요가 없다. 먼저 매칭되지 않은 정점, 즉 X[i] == 0인 정점은 DFS 안에서 방문할 방법이 없으므로 solve의 for문에서만 방문할 수 있는데, for문은 자명하게 정점을 최대 1번씩만 방문한다. 다음으로 이미 매칭된 정점인 경우에는 Y[y] = x나 dist[x] = INT_MAX 때문에 dist[Y[y]] == dist[x] + 1를 더 이상 만족하지 않아서 두 번 이상 지나가지 않는다. 따라서 visit 배열 등의 추가적인 조치가 필요없다.

 

BOJ 11375 열혈강호를 위 코드로 풀어봤다. 대놓고 이분매칭을 하라는 단순한 문제다. 88ms로, 굉장히 빠른 것을 알 수 있다.