C1: Constructing a perfect matching is RNC

October 30, 2024

• Basic Tools
  • Basic Tool 1
  • Basic Tool 2
• Reference

Random NC: it is used to define a problem that can be solved in polylog time by a randomized parallel algorithm using a polynomial number of processors.

Basic Tools

Basic Tool 1

$\textbf{Lemma}[\textup{Schwartz–Zippel}]$. Let $\mathbb{F}$ denote a field and let $f(x_1,\ldots,x_n) \in \mathbb{F}[x_1,\ldots,x_n]$ be a nonzero multivariate polynomial of degree $d$. Let $S\subseteq \mathbb{F}$ be a finite set. Then, we have

$$\mathbb{P}[f(a_1,\ldots,a_n)=0] \leq \frac{d}{\lvert S \rvert}$$

The degree of a polynomial is the largest degree of its monomials. For example,

$$f(x_1,x_2) = x_1x_2^2 + 1$$

has degree 3.

There, we set $f(x) = x_1^d + x_2+\ldots$. After uniformly at random selecting from the finite set, the probability that they are the root is very small, at most $d/\lvert S \rvert$.

Basic Tool 2

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.

To be continue…

Reference

[1]. Karp, R.M., Upfal, E. and Wigderson, A., 1985, December. Constructing a perfect matching is in random NC. In Proceedings of the seventeenth annual ACM symposium on Theory of computing (pp. 22-32).