Bipartite perfect matching $\in\mathsf{RNC}$ (randomized), but whether it $\in\mathsf{NC}$ remains open.

Bipartite graph can be represented by an $n\times n$ adjacency matrix $A$. If there is an edge between $i$ on the left and $j$ on the right, the $A_{i,j}$ is $1$.

Existence of Perfect Matching

Permutation, Permanent, and Determinant

Trivial idea: try all permutation ($O(n!)$ in total, very bad).

Observation: the permanent is defined: $$ \mathsf{perm}(A)=\sum_{\sigma}\prod_{i\in[n]}A_{i,\sigma(i)} $$ If there exists a perfect matching $\sigma$, $\prod_{i\in[n]}A_{i,\sigma(i)}=1$. Thus, $\exist$ perfect matching $\Leftrightarrow\mathsf{perm}(A)>0$.

However, computing permanent of a matrix needs iterating through all permutation ($n!$, not feasible). We consider a similar notion, determinant $\det(A)$. $$ \det(A)=\sum_{\sigma}\mathsf{sign}(\sigma)\prod_{i\in[n]}A_{i,\sigma(i)} $$ The sign of $\sigma$ depends on odd/even number of switches from $1,2,\cdots,n$. It is known that determinant can be computed in polynomial time (by Gaussian Elimination, etc.)

So $\det(A)\neq0\Rightarrow\exists$ a perfect matching. Reverse implication is not true. But there are cases where $det(A)=0$ but a perfect matching exists.

Randomization

Plan: define $A'$ as a function of $A$ (randomized) s.t., if $\exists$ perfect matching in $A$, $\det(A')\neq0$ with probability $\geq\frac{1}{2}$, so that by $O(\log n)$ trials, the probability of success (if there exists a perfect matching) is amplified to $\geq(1-\frac{1}{n})$.

Isolation Lemma

Given a set of elements $S=\{1,2,\cdots,n\}$, each element has a weight $w_i$.

Given a set of subsets $F=\{S_1,\cdots,S_k\},S_j\subseteq S\forall j\in[k]$. The weight of $S_j$ is $W_j=\sum_{i\in S_j}w_i$

If the weights is from $\{1,2,\cdots,2n\}$, there exists an unique minimum weight of subset with probability $\geq\frac{1}{2}$.

We apply isolation lemma to the randomized algorithm.

$A'$ add weights on edge. If each element $i$ gets a random weights from $2^0,2^1,\cdots,2^{2n^2}$, then there is a perfect matching with unique smallest weights with probability $\geq\frac{1}{2}$.

Pseudocode

Repeat $\log n$ times:

Start from $A$, construct $A'$ by assigning each edge with the value $2^k,k\in[2n^2]$ (here directly upper bounded)
Compute $\det(A')$, if $\det(A')\neq0$ return TRUE, else continue

return FALSE

The algorithm runs in $O(\log^2n)$ time with $O(n^{5.5}\log n)$ processors.

Find a Perfect Matching

Given an $n\times n$ adjacency matrix $A$, compute $A'$

$D_{i,j}$ is the $\det$ of $A'$ removing $i$-th row and $j$-th column. In the original bipartite graph, removing node $i$ on the left and $j$ on the right.

Compute all $D_{i,j}$, the edge $(i,j)$ is in a perfect matching if $$ D_{i,j}\cdot\frac{2^{w_{i,j}}}{2w}\text{ is odd.} $$ Here $D_{i,j}\cdot2^{w_{i,j}}$ represents all the matchings that has edge $(i,j)$.