Lesson 8

Now, we are ready to present the final algorithm for detecting a perfect matching in a graph. The algorithm proceeds as follows:

• Given a graph \(G\), construct the Tutte matrix \(T\).


• Choose values \(v_{ij}\) for each variable \(x_{ij}\) uniformly at random from \([p]\), where \(p = \Theta(n^{2})\) is a prime number.


• Substitute the values \(v_{ij}\) into the matrix \(T\) and compute its determinant over \(\mathbb{F}_{p}\) in time \(O(n^{\omega}\cdot \log^{O(1)}n)\). Here, \(\omega\) denotes the matrix multiplication exponent, with the best known bound being \(\omega < 2.38\).


• If the determinant is non-zero, output that a perfect matching exists. Otherwise, output that no perfect matching exists.

From the Schwartz–Zippel lemma, we know that the probability of error is at most \(1 - \frac{1}{n}\), since the degree of the determinant polynomial is at most \(n\).