T1: Algebraic Matching Algorithms (1)

July 12, 2024

• Definitions
  • Leibniz Formula to Compute a Determinant
• Lovász’s Algorithm
• Karp, UPpfal, Wigderson Algorithm
• Rabin and Vazirani Algorithm
• Reference

This post will show how to detect and find a matching using matrix.

Definitions

Given a bipartite graph $G=(L, R, E)$ with $\lvert L\rvert = \lvert R \rvert = n$, the Edmonds Matrix $E(G)$ is defined as $n\times n$ matrix of variables in the following.

$$\mathrm{E}_{i,j} = \begin{cases} 0, & (i,j) \not \in E \text{ and } {i\in L, j\in R}\\ 1, & (i,j)\in E \text{ and } {i\in L, j\in R} \end{cases}$$

We know that the basics are always important.

Leibniz Formula to Compute a Determinant

For more about determinant, please read the post What is determinant.

$$\textup{Det}(\textbf{a}_1, \textbf{a}_2,\ldots, \textbf{a}_n) = \sum_{(j_1,\ldots,j_n)\in \pi_n}\text{sgn}(j_1,\ldots,j_n) \prod_{i=1}^n v_{j_n i}$$

where $\pi_n$ is a permutation.

Lovász’s Algorithm

$\textbf{Theorem}$[35] Let $\textup{E}(G)$ be the Edmonds matrix of a bipartite graph $G$. Then, $\textup{E}(G)$ is non-zero iff $G$ contains a perfect matching.

Wow! Cool! What a beautiful theory!

Karp, UPpfal, Wigderson Algorithm

Rabin and Vazirani Algorithm

Reference

[1] Tutte, William T. “The factorization of linear graphs.” Journal of the London Mathematical Society 1.2 (1947): 107-111.