C1: Where does the Isolating Lemma come from?

November 03, 2024

• Problem
• Tools
  • Basic Tool 1: Determinant
  • Basic Tool 2: Tutte’s Perfect Matching Theorem
• The Algorithm
• Reference

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).

Tools

Basic Tool 1: Determinant

See basics about determinant

Basic Tool 2: Tutte’s Perfect Matching Theorem

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.

To be continued…

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).