Reminder: This post contains 1259 words
· 4 min read
· by Xianbin
The Isolating Lemma comes from the study of matching.
Problem
Given a bipartite graph \(G=(L\cup R, E)\) with a perfect matching, the goal is to find a perfect matching (in parallel).
See basics about determinant
Given an undirected graph \(G=(V, E)\), its Tutte matrix \(T\) is the \(n\times n\) symbolic matrix as follows.
Let \((i,j)\in E\) denote the edge in \(G\).
\[M_{i,j} : =
\begin{cases}
x_{i,j}, && i<j \\
-x_{i,j}, && i>j \\
0, && \text{Otherwise}
\end{cases}\]
We can show that \(M\) is skew-symmetric, i.e.,
\[M^T = - M\]
\(\textbf{Lemma}\)[Tutte’s Perfect Matching Lemma] Let \(M\) be the Tutte matrix of an undirected graph \(G=(V, E)\). We have
\[\text{det}(M) \not = 0\]
if and only if \(G\) has a perfect matching.
The Algorithm
From Tutte’s perfect matching theorem, we almost know how to find a perfect matching. The question is how to be fast. As the post the perfec matching is RNC shown, one idea is to use Tutte’s theorem to prune out the edges not in the prefect matching which can be done in \(O(\log^2 n)\) time. By each iteration, there is a constant rate of progress, so there is \(O(\log n)\) iterations. Then, it gives a \(\text{RNC}^3\) algorithm.
Reference
[1]. Mulmuley, K., Vazirani, U.V. and Vazirani, V.V., 1987, January. Matching is as easy as matrix inversion. In Proceedings of the nineteenth annual ACM symposium on Theory of computing (pp. 345-354).