Let's $G=(U, V, E)$ be a balanced bipartite graph which $|U|=|V|=n$ and $|E|=n*(n-1)$; All nodes in $U$ are connected to all nodes in $V$ except $u_i$ to $v_i$ for $1\leq i \leq n$.

Definition1: Cross edges are two edges in $E$, one with two end points $u_i$, $v_j$ and the other with $u_j$, $v_i$.
Definition2: Good-perfect matching is a perfect matching with no cross edges.

What is the complexity of counting the number of Good-perfect matching in $G$?


There is only one instance for each size n. Thus, the problem is clearly in P/poly, and cannot possibly be #P-complete unless the polynomial hierarchy collapses.

In fact, it is polynomial-time computable. You can compute the first few terms of the sequence, and find that it goes 2, 6, 24, 160 ... . You can then look at the online encyclopedia of integer sequences and find it. When you look at the page for this sequence, you find a polynomial-time formula for computing it.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.