# Counting modified perfect matchings

Consider a bipartite graph with vertex set partitioned into $X=\{u_1,u_2,u_3\}$ and $Y=\{v_1,v_2,v_3\}$. Consider the graph has the following edges: $\{u_1,v_1\}$, $\{u_2,v_2\}$, $\{u_2,v_3\}$, $\{u_3,v_2\}$ and $\{u_3,v_3\}$. The perfect matchings are $\{\{u_1,v_1\}$, $\{u_2,v_2\}$, $\{u_3,v_3\}\}$ and $\{\{u_1,v_1\}$, $\{u_2,v_3\}$, $\{u_3,v_2\}\}$. The total number of such matchings is $2$.

However I do not want the same edge to occur in two different sets. Here edge $\{u_1,v_1\}$ occurs in both the sets. So I can pick one of the two possible matchings for a total of $1$.

Is there any counting strategy for the new matching problem? Note that permanent counts perfect matchings in the base case.

Is there an approximation algorithm?

• Can you explain what is the quantity you are trying to compute? Are you looking for the maximal number of disjoint perfect matchings? – Yuval Filmus Sep 23 '13 at 6:36
• @Yuval Exactly that is correct. Is that a known result? I could get an upper bound in terms of lowest degree. – T.... Sep 23 '13 at 11:24
• There is a slightly related question on mathoverflow. – NicoDean Mar 12 '18 at 1:26