Applications

For number theory applications, see number theory ref.

Perfect matchings

Bipartite graph

G = (U, V, E); $|U|=|V|=n$. Matching: $\left\{e\right\}\in E$ not sharing endpoints. Perfect matching (pm) has size n. Naive alg takes $O((n!)n)$ time.

Make symbolic matrix with $A_{i,j}=x_{i,j}$ if $(u_i,v_j)\in E$, else 0. Let Q(x) = det(A) : $n^2$-nomial, ‘symbolic determinant’. G has pm iff $\mathrm{\exists }r:Q(r)\ne 0$. $deg(Q)\le n$. Take prime $p>2n$, pick r from $Z_p$; by Schwartz Zippel Thm, $Pr(Q(r)=0|\mathrm{\exists }{r}^{\prime }|Q(r^{\prime })\ne 0)<2^{-1}$.

If pm unique, find pm in polytime: Repeat: $E=E-\left\{e\right\}$; see if G still has pm. (Parallelizable.)

If pm not unique

Take uniformly random weight fn $w:[1,m]\to [1,2m]$; let $W(S)=\sum _{d\in S}w(d)$.

Isolation lemma

Let $S_i\in [1,m]$; take k $S_i$. $Pr(\mathrm{\exists }minWt{S}_i,S_j|e\in S_i,e\notin S_j)\le (2m{)}^{-1}$: by principle of deferred decisions: Pick W(e) last to $W(S_j)-W(S_i-\left\{e\right\})$. So, $\cup$ bound: Pr($\mathrm{\exists }$ unique $S_i$ with $W(S_i)$ min) $\le 2^{-1}$.

Get w(e) $\mathrm{\forall }e=(u_i,v_j)\in E$. Get matrix $B_{i,j}=2^{w((u_i,v_j))}$. Then $det(B)=\sum _{pmM}(\pm 2^{W(M)})$. So find pm by finding highest power of 2 dividign det(B).

General graph

(Tutte): G = (V, E); Make Tutte matrix: $\mathrm{\forall }i<j$ if $(u_i,v_j)\in E$, $A_{i,j}=x_{i,j}$ and $A_{j,i}=-x_{i,j}$, else 0. Let $|A|=Q(x)$ multinomial; G has pm iff $\mathrm{\exists }xQ(x)\ne 0$: $det(A)=\sum _{\pi }sgn(\pi )\prod A_{i,\pi (i)}$; if some $\mathrm{\forall }\pi :\prod A_{i,\pi (i)}=0$, no pm. Else, Take prime $p>2n$, pick r from $Z_p$, take Q over $Z_p$; by Schwartz Zippel, $\mathrm{\exists }x$ where $Q(x)\ne 0$.