Generating Random Matchings (GRM)

Input

A bipartite graph $G = (V_1, V_2, E)$ with $|V_1| = |V_2| = n$ and a designated edge $uv$.

Problem

(1) Is $uv$ in the matching generated by Broder’s algorithm?

(2) Is $uv$ in the matching generated by Jerrum and Sinclair’s algorithm?

Definitions

Let $M_n(G)$ denote the set of perfect matchings in $G$ and $M_{n-1}(G)$ denote the set of near perfect matchings, that is, matchings of size $n-1$. Broder [1] and Jerrum and Sinclair [2] give probabilistic algorithms for generating elements in $M_n(G) \cup M_{n-1}(G)$. We call these algorithms Broder’s algorithm and Jerrum and Sinclair’s algorithm.

Status

$\P$-complete (Teng [3]).

Remarks

The reductions for both these problems are from LFMIS.

These algorithms are important for approximating the permanent. Also, see MM and PME for some related open problems.