Parallel Algorithm for Bipartite Graph Perfect Matching

매칭을 바라보는 새로운 시각

그래프 이론에서 이분 그래프 매칭은 두 개의 독립된 정점 집합 사이에서 간선이 겹치지 않게 연결 쌍을 만드는 고전적인 문제입니다. 우리는 보통 이 문제를 접할 때, 정점 하나하나를 거쳐 가며 비어 있는 짝을 찾아가는 Augmenting Path 방식에 익숙해져 있습니다. DFS/BFS 기반의 알고리즘은 $O(VE)$의 시간에 작동하며, 이를 최적화한 Hopcroft-Karp 알고리즘은 $O(E\sqrt{V})$라는 준수한 성능을 보여줍니다.

이번에 소개할 알고리즘은 그래프를 행렬로 변환한 뒤 행렬식을 구함으로써, perfect matching의 존재성을 행렬 곱셈 시간복잡도인 $O(n^\omega)$ ($\omega \approx 2.37$) 만에 판별합니다. 이 접근법은 다항 개수의 프로세서를 투입할 경우 $O(\log^2 n)$시간 안에 문제를 해결할 수 있는 $RNC$ 클래스의 문을 열어줍니다. 이제부터 우리는 어떻게 이분 그래프의 간선들이 행렬의 원소로 변환되는지, 그리고 왜 행렬식이라는 도구가 매칭의 존재를 증명하는지 살펴보겠습니다.

변수 행렬과 행렬식의 조합론적 의미

이분 그래프 $G = (V_1, V_2, E)$에서 완벽 매칭의 존재성을 판별하기 위해, 우리는 먼저 각 정점 사이의 연결 정보를 담은 $n \times n$ 행렬 $A$를 구성합니다. 이때 행렬의 원소 $A_{ij}$는 간선 ${i, j} \in E$가 존재할 경우 서로 독립적인 변수 $x_{ij}$를 할당하고, 존재하지 않을 경우 0을 할당합니다. 이를 통해 그래프의 구조를 하나의 거대한 다항식 행렬로 변환할 수 있습니다. 이렇게 정의된 행렬 $A$의 Determinant를 정의에 따라 전개해 보면 다음과 같은 형태가 됩니다.

$\det(A) = \sum_{\sigma \in S_n} \text{sgn}(\sigma) \prod_{i=1}^n A_{i, \sigma(i)}$

이 수식에서 각 항은 모든 행과 열에서 정확히 하나의 원소씩을 선택하여 곱한 결과입니다. 이분 그래프의 관점에서 볼 때, 특정 항의 값이 0이 아니라는 것은 각 정점 $i$가 서로 다른 정점 $\sigma(i)$와 간선으로 연결되어 있다는 뜻이며, 이는 곧 그래프의 Perfect Matching 하나와 정확히 일대일 대응됩니다.

결과적으로 그래프에 완벽 매칭이 하나라도 존재한다면 $\det(A)$는 0이 아닌 다항식이 됩니다. 반대로 매칭이 존재하지 않는다면 모든 항이 0이 되어 행렬식 자체가 0이 될 것입니다. 즉, 완벽 매칭의 존재 유무는 다항식 $\det(A)$가 Identically Zero인지 확인하는 문제로 귀결됩니다.

다항식 Identity Testing

우리가 정의한 Determinant는 이론적으로 완벽한 도구이지만, 이를 실제로 계산하는 과정에는 커다란 장벽이 존재합니다. 행렬식을 정의대로 전개할 경우 최대 $n!$개의 항이 만들어질 수 있는데, 이 거대한 다항식을 기호적으로 유지하며 모든 항이 0인지 확인하는 작업은 지수적인 시간을 필요로 하기 때문입니다. 현실적으로 컴퓨터가 이 다항식을 직접 펼쳐서 보기에는 무리가 있습니다. 여기서 우리는 발상을 전환하여 다항식 그 자체를 구하는 대신, 특정한 값을 대입했을 때의 결과에 주목합니다. 변수들에 임의의 숫자를 대입하여 얻은 스칼라 행렬의 Determinant를 계산한다면, Gaussian elimination과 같은 기법을 통해 $O(n^\omega)$ 시간 안에 빠르게 처리할 수 있습니다. 다만 우연히 선택하여 대입한 값이 다항식의 Root일 경우, 실제로는 0이 아닌 다항식임에도 불구하고 결과값이 0으로 계산되어 오류를 범할 위험이 있습니다. 이 지점에서 Schwartz-Zippel Lemma가 결정적인 역할을 합니다.

Schwartz-Zippel Lemma의 정의와 증명

우리가 앞서 살펴본 무작위 대입 알고리즘이 정당성을 갖기 위해서는, 0이 아닌 다항식에 임의의 값을 넣었을 때 실수로 0이 나올 확률이 매우 낮다는 수학적 보장이 필요합니다. 이를 완벽하게 설명해 주는 도구가 바로 Schwartz-Zippel Lemma입니다.

Lemma

체 위에서 정의된 $m$개의 변수를 가진 $n$차 다항식 $p$가 Identically Zero가 아닐 때, 유한체의 부분집합 $S$에서 변수값을 무작위로 선택하여 대입했을 때 결과가 0이 될 확률은 다음을 만족합니다.

$\text{Pr}[p(r_1, r_2, \dots, r_m) = 0] \le \frac{n}{

이 식은 다항식의 차수 $n$이 우리가 선택한 샘플 집합의 크기 $

$에 비해 충분히 작다면, 무작위 대입을 통해 다항식의 실체를 거의 확실하게 파악할 수 있음을 의미합니다.

Proof

이 정리는 변수의 개수 $m$에 대한 수학적 귀납법으로 증명할 수 있습니다.

기초 단계 ($m = 1$)

변수가 하나인 $n$차 다항식이 0이 아니라면, 이 다항식은 최대 $n$개의 근을 가집니다. 따라서 전체 집합 $S$에서 무작위로 선택한 값이 이 근 중 하나일 확률은 $n/

$ 이하가 됩니다. 이는 대수학의 기본 원리에서 도출되는 당연한 결과입니다.

귀납 단계 ($m > 1$)

변수가 $m-1$개일 때 정리가 성립한다고 가정합니다. 이제 $m$개의 변수를 가진 다항식 $p$를 첫 번째 변수인 $x_1$에 대해 다음과 같이 내림차순으로 정리합니다.

\[p(x_1, \dots, x_m) = \sum_{i=0}^k x_1^i \cdot p_i(x_2, \dots, x_m)\]

여기서 $k$는 $x_1$의 최대 차수이며, $p_k$는 0이 아닌 $n-k$차 이하의 다항식입니다.

우리는 전체 확률을 두 가지 경우로 나누어 생각할 수 있습니다.

먼저 나머지 변수들을 대입했을 때 $p_k$가 0이 될 확률은 귀납 가정에 의해 $(n-k)/	S	$ 이하입니다.
반대로 $p_k$가 0이 되지 않는다면, $p$는 $x_1$에 대한 1변수 다항식이 되므로 기초 단계에 의해 확률은 $k/	S	$ 이하가 됩니다.
이 두 확률의 합을 구하면 전체 확률은 $n/	S	$ 이하가 됨을 알 수 있습니다. 따라서 귀납법에 의해 임의의 변수 개수에 대해 정리가 성립합니다.

Schwartz-Zippel Lemma를 활용한 알고리즘

수학적 증명을 통해 무작위 대입의 정당성을 확보했으므로, 이제 이를 실제 알고리즘으로 구체화할 수 있습니다. 이 알고리즘은 복잡한 그래프 탐색 대신 선형대수학의 연산을 핵심 동력으로 사용합니다.

완벽 매칭의 존재성을 판별하는 알고리즘은 다음과 같은 단계로 진행됩니다:

유한체의 선택: 그래프의 정점 개수 $n$보다 충분히 큰 소수 $q$를 선택하여 유한체 $GF(q)$를 구성합니다. 일반적으로 오류 확률을 최소화하기 위해 $q \ge 2n$ 이상의 크기를 선택합니다. $2n \le q \le 4n$을 만족하는 $q$의 존재성은 Bertrand’s postulate에 의해 보장됩니다.
무작위 대입: 행렬의 각 변수 $x_{ij}$에 대하여 $GF(q)$의 원소를 무작위로 선택하여 대입합니다. 이 과정을 통해 다항식 행렬은 체의 원소들로 이루어진 스칼라 행렬 $A_R$이 됩니다.
행렬식 계산: 생성된 행렬 $A_R$의 Determinant를 계산합니다.
존재성 판별: 계산된 Determinant 값이 0이 아니라면 완벽 매칭이 존재한다고 판단합니다. 만약 0이라면 매칭이 존재하지 않는 것으로 보고합니다.

시간복잡도 분석

이 알고리즘의 효율성은 행렬 연산의 속도에 전적으로 의존합니다. 순차적 처리: 스칼라 행렬의 Determinant 계산은 Gaussian elimination이나 더 최적화된 기법을 통해 $O(n^\omega)$ 시간 안에 수행됩니다. 여기서 $\omega$는 행렬 곱셈에 필요한 지수로, 현재 약 2.37로 알려져 있습니다. 병렬 처리: Determinant 계산은 $O(\log^2 n)$의 깊이를 가진 회로로 구현될 수 있어, 다항 개수의 프로세서를 활용하면 $O(\log^2 n)$의 시간 안에 계산을 마칠 수 있습니다.

확률적 신뢰도는 아래와 같이 분석됩니다.

매칭이 실제로 없는 경우: 그래프에 완벽 매칭이 없다면 $\det(A)$는 Identically Zero이므로, 어떤 값을 대입해도 결과는 항상 0이 나옵니다. 즉, 매칭이 없는데 있다고 답할 확률은 0입니다.
매칭이 실제로 있는 경우: 그래프에 완벽 매칭이 존재한다면 $\det(A)$는 0이 아닌 다항식입니다. 이때 무작위로 대입한 값이 우연히 이 다항식의 Root일 경우에만 계산 결과가 0이 되어, 매칭이 있음에도 없다고 잘못 판단할 확률이 발생합니다. 이러한 오류 확률은 Schwartz-Zippel Lemma에 의해 $n/q$ 이하로 제한됩니다.

결론

지금까지 이분 그래프에서 완벽 매칭의 존재성을 대수적으로 판별하는 방법을 살펴보았습니다. 이 알고리즘은 행렬식 계산을 통해 존재 여부를 효율적으로 확인습니다.

이분 그래프를 넘어 일반 그래프에서의 완벽 매칭을 구하는 기법은 해당 블로그 글 에 상세히 소개되어 있습니다. 각 간선에 $[1, 2n]$ 사이의 무작위 가중치를 부여하고, Determinant 계산을 통해 Unique Minimum Weighted Perfect Matching을 추출해 내는 흥미로운 과정을 확인할 수 있습니다.

참고문헌

Caltech CS 150 Probability and Algorithms, Fall 2018 Lecture 10