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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.