<p>Yes, cause the problem lies in P. Look at paper <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.469&amp;rank=2" rel="noreferrer">Fukuda, Matsui ''Finding All The Perfect Matchings in Bipartite Graphs''</a></p>

CC BY-SA 3.0
2015-05-03T17:03:00.157Z
The linked paper http://dx.doi.org/10.1016/0893-9659(94)90045-0 gives an algorithm that runs in time that depends on the number of perfect matchings.  The idea is to create a perfect matching different from a given one.  This is applied recursively whenever a new matching is found, splitting on the presence or absence of an edge that is present in one of the matchings but not the other.  This is polynomial in $n$ (I'm assuming the OP meant the polynomial is fixed).  Therefore so is the overall runtime: the algorithm can stop once it has found the required number of matchings.
András Salamon
CC BY-SA 4.0
2019-01-07T08:51:38.467Z
I prefer https://core.ac.uk/download/pdf/82129717.pdf that is simpler to understand, gives the same theoretical result and solves a more general problem is slightly more time!
Labo
CC BY-SA 3.0
2015-05-03T14:59:22.960Z
2015-05-03T14:59:22.960Z
Vsevolod Oparin
<p>Few definitions first. The co-NP problem is a decision problem where the answer "NO" can be verified in polynomial time. The perfect matching in a bipartite graph is a set of pairs of nodes (a pair is an edge in the graph) and where every node occurs in this set exactly once.</p>

<p>I am given an n x n bipartite graph, and I am trying to find out if the problem of finding whether k different perfect matchings exist in the graph, where k= polynomial(n), is a co-NP problem.</p>

<p><strong>Work done so far</strong></p>

<p>To initially simplify the problem, I believe that if k=2, then this is a co-NP problem. I think this is true, because the bipartite graph does not have 2 different perfect matchings, if there does not exist an exchange of neighbors between 2 nodes. I define the exchange of neighbors as the following. Let G1 be the first set in the graph, and G2 be the second set in the graph. The exchange occurs when we have a subset of G1, S1={A,B}, and a second subset of G2, S2={X,Y}, where {(A,X),(A,Y),(B,X),(B,Y)} belongs to the set of edges E. I call it exchange because if A was initially matched with X, and B with Y, then when A gets paired with Y, and B with X, A and B have exchanged their neighbors. I believe that the only way to have 2 different perfect matchings is to have at least one such exchange.</p>

<p>Now, we can verify that no such exchange exist, in polynomial time. This is true since getting all the possible subsets S1 and S2 has O(n^4) time complexity. This because we need (n choose 2) from G1 multiplied by (n choose 2) from G2, and this gives us an upper bound of n^4.</p>

CC BY-SA 3.0
2015-05-02T21:10:04.147Z
It is indeed a decision problem, but I typed incorrectly. Apologies. I fixed it now.
Traveling Salesman
CC BY-SA 3.0
2015-05-03T19:06:58.700Z
Look at the literature on the alldifferent constraint in constraint programming. Propagation for alldifferent is equivalent to this problem.
Jules
<cc.complexity-theory><graph-theory><graph-algorithms><np><matching>
Is finding whether k different perfect matchings exist in a bipartite graph co-NP?
Traveling Salesman
# Is finding whether k different perfect matchings exist in a bipartite graph co-NP?

(Asked by: username_0 on 2015-05-02)

Few definitions first. The co-NP problem is a decision problem where the answer "NO" can be verified in polynomial time. The perfect matching in a bipartite graph is a set of pairs of nodes (a pair is an edge in the graph) and where every node occurs in this set exactly once.

I am given an n x n bipartite graph, and I am trying to find out if the problem of finding whether k different perfect matchings exist in the graph, where k= polynomial(n), is a co-NP problem.

**Work done so far**

To initially simplify the problem, I believe that if k=2, then this is a co-NP problem. I think this is true, because the bipartite graph does not have 2 different perfect matchings, if there does not exist an exchange of neighbors between 2 nodes. I define the exchange of neighbors as the following. Let G1 be the first set in the graph, and G2 be the second set in the graph. The exchange occurs when we have a subset of G1, S1={A,B}, and a second subset of G2, S2={X,Y}, where {(A,X),(A,Y),(B,X),(B,Y)} belongs to the set of edges E. I call it exchange because if A was initially matched with X, and B with Y, then when A gets paired with Y, and B with X, A and B have exchanged their neighbors. I believe that the only way to have 2 different perfect matchings is to have at least one such exchange.

Now, we can verify that no such exchange exist, in polynomial time. This is true since getting all the possible subsets S1 and S2 has O(n^4) time complexity. This because we need (n choose 2) from G1 multiplied by (n choose 2) from G2, and this gives us an upper bound of n^4.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, np, matching
> **Comments:**
> **username_0**: It is indeed a decision problem, but I typed incorrectly. Apologies. I fixed it now.  
> **username_1**: Look at the literature on the alldifferent constraint in constraint programming. Propagation for alldifferent is equivalent to this problem.  

---

## 1 answers

### Answer by username_2 on 2015-05-03. Score: 5 | Accepted answer

Yes, cause the problem lies in P. Look at paper [Fukuda, Matsui ''Finding All The Perfect Matchings in Bipartite Graphs''](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.469&rank=2)

> **Comments:**
> **username_3**: The linked paper http://dx.doi.org/10.1016/0893-9659(94)90045-0 gives an algorithm that runs in time that depends on the number of perfect matchings.  The idea is to create a perfect matching different from a given one.  This is applied recursively whenever a new matching is found, splitting on the presence or absence of an edge that is present in one of the matchings but not the other.  This is polynomial in $n$ (I'm assuming the OP meant the polynomial is fixed).  Therefore so is the overall runtime: the algorithm can stop once it has found the required number of matchings.  
> **username_4**: I prefer https://core.ac.uk/download/pdf/82129717.pdf that is simpler to understand, gives the same theoretical result and solves a more general problem is slightly more time!  

---

