Grocery on Distributed Algorithms

C1: Constructing a perfect matching is RNC

Reminder: This post contains 1360 words · 4 min read · by Xianbin

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