<p>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.</p>

<p>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 <a href="http://oeis.org/A038205">find it</a>. When you look at the page for this sequence, you find a polynomial-time formula for computing it. </p>

CC BY-SA 2.5
2011-01-06T15:28:49.953Z
2011-01-06T15:28:49.953Z
Peter Shor 
<p>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$.  </p>

<p>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$.<br>
Definition2: Good-perfect matching is a perfect matching with no cross edges.  </p>

<p>What is the complexity of counting the number of Good-perfect matching in $G$?</p>

CC BY-SA 2.5
2011-01-05T15:12:05.010Z
This question suffers the *exact same* problem as your previous qeustion: http://cstheory.stackexchange.com/questions/4086/coumputing-the-permanent-of-a-0-1-matrix-which-only-the-entries-on-the-main-diago
Kristoffer Arnsfelt Hansen
CC BY-SA 2.5
2011-01-06T18:38:33.153Z
Cross posted to math.se: http://math.stackexchange.com/questions/16419/complexity-of-counting-the-number-of-good-perfect-matching-in-bipartite-graph
Aryabhata
<cc.complexity-theory><co.combinatorics><counting-complexity><permanent>
Complexity of counting the number of Good-perfect matching in the bipartite graph
marjoonjan
# Complexity of counting the number of Good-perfect matching in the bipartite graph

(Asked by: username_0 on 2011-01-05)

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$?

**Tags:** cc.complexity-theory, co.combinatorics, counting-complexity, permanent
> **Comments:**
> **username_1**: This question suffers the *exact same* problem as your previous qeustion: http://cstheory.stackexchange.com/questions/4086/coumputing-the-permanent-of-a-0-1-matrix-which-only-the-entries-on-the-main-diago  
> **username_2**: Cross posted to math.se: http://math.stackexchange.com/questions/16419/complexity-of-counting-the-number-of-good-perfect-matching-in-bipartite-graph  

---

## 1 answers

### Answer by username_3 on 2011-01-06. Score: 6 | Accepted answer

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](http://oeis.org/A038205). When you look at the page for this sequence, you find a polynomial-time formula for computing it.


---

