Perfect matching detection

We consider the following problem: Given a bipartite graph $G=(V,E)$ where $V = X \cup Y$ is a bi-partition and $|X|=|Y|=n$, our goal is to decide whether $G$ has a perfect matching.

Digression: Matching

Let us try to understand a bit the structure of the problem through a set of exercises. A matching in $G$ is a set of edges $M \subseteq E(G)$ that are vertex-disjoint (i.e., for all distinct $e, f \in M$, we have $e \cap f = \emptyset$). A matching is perfect if the union of edges in $M$ (vertices incident to $M$) is $V(G)$.

The problem of finding a matching of maximum cardinality (a.k.a. maximum matching) is among the most fundamental problems in algorithms (the "big threes" in algorithms = matching, cuts, flows).

Exercise 126

For all $n$, present a connected graph with $n$ nodes, in which every maximum matching has only one edge.

Exercise 127

Consider the following Heuristic A: Starting from $M = \emptyset$, keep adding arbitrary edges into $M$ while possible until we cannot add anymore.

• Present a graph where this heuristic returns one edge and the optimal has two edges.
• Prove that this heuristic returns at a matching of size at least half of the optimal.

Exercise 128

Let us further improve the heuristic (say, Heuristic A+). Starting from $M$ returned by Heuristic A, while it is possible to find $e \in M$ and $f, f' \in E(G) \setminus M, f\neq f'$ so that $(M - \{e\}) \cup \{f,f'\}$ is a matching, update $M \gets (M-\{e\}) \cup \{f,f'\}$.

• Present a graph where this heuristic returns two edges and the optimal has three edges.
• Prove that this heuristic returns a matching of size at least two thirds of the optimal.

Exercise 129

Define Heuristic A++ that strengthens A+ and achieves at least three fourths of the optimal. Prove that your heuristic returns a matching of size at least three fourths of the optimal.

Back to polynomials

Currently, there is a near linear-time algorithm for solving perfect matching in bipartite graphs. We will look at a much simpler, randomized algorithm that is highly parallelizable. In particular, we will show a randomized reduction from perfect matching to computing the determinant of a matrix - a task that admits a high degree of parallelism.

Determinants: Denote by $S_n$ the set of all permutations $\sigma: [n] \rightarrow [n]$.¹ For each permutation $\sigma \in S_n$, the sign of $\sigma$, denoted by ${\sf sign}(\sigma)$ is a number which is either $-1$ or $1$ (depending on $\sigma$). We use the following definition of the determinant of matrix $M$.

$\det(M) = \sum_{\sigma \in S_n} {\sf sign}(\sigma) \prod_{i=1}^n M_{i,\sigma(i)}$

The precise definition of ${\sf sign}$ is quite irrelevant here, so we omit this definition.

Reduction from matching to determinant: Given a bipartite graph $G$, we denote $X= \{x_1,\ldots, x_n\}$ and $Y= \{y_1,\ldots, y_n\}$. Each entry $M_{ij}$ is defined to be a variable $z_{i,j}$ if $\{x_i, y_j\} \in E(G)$ and $0$ if there is no edge $\{x_i, y_j\}$ in $G$. Notice that we have at most $n^2$ variables in the matrix $M$, so $p(\textbf{z}) = \det(M)$ is a polynomial on at most $n^2$ variables. The degree of $p$ is at most $n$ (each term $\prod_{i \in [n]}M_{i,\sigma(i)}$ is a product of at most $n$ distinct variables).

Observation 3

Polynomial $p$ is a non-zero polynomial if and only if graph $G$ has a perfect matching.

Proof (Sketch):

To prove the $\Longleftarrow$ direction, let $M$ be a perfect matching, we use the permutation defined by $M$. More formally, we define $\sigma_M$ where $\sigma_M(i) = j$ whenever $\{x_i,y_j\} \in M$. This implies that the term ${\sf sign}(\sigma_M) \prod_{i \in [n]} M_{i,\sigma_M(i)} = {\sf sign}(\sigma_M) \prod_{i \in [n]} z_{i,\sigma_M(i)}$ is non-zero, hence $p$ is non-zero (one also needs to formally justify this, i.e. do you see why the term does not cancel out?). The other direction can be proved similarly.

Since $p$ is a polynomial of degree at most $n$, we can test whether $p$ is identically zero by picking a random $\textbf{a} \in \{1,\ldots, 10n\}^{n^2}$ and check whether $p(\textbf{a}) =0$. In practice, this can be done by defining matrix $A$ where $A_{i,j} \in \{1,\ldots, 10n\}$ is chosen randomly and uniformly. Afterwards, compute the determinant $\det(A)$. We argue that the probability of failure is small.

• If $G$ does not have a perfect matching, then $\det(M)$ is a zero polynomial and so is $\det(A)$.
• If $G$ has a perfect matching, then $p(\textbf{z}) = \det(M)$ is a non-zero polynomial of degree at most $n$. Therefore, the probability that $p(\textbf{a}) = \det(A) = 0$ is at most $n/10n = 1/10$ by Theorem 48.

Footnotes

1. For instance, $S_3 = \{(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)\}$. ↩