# Is finding whether k different perfect matchings exist in a bipartite graph co-NP?

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.

• The problem "given a n x n bipartite graph, find k different perfect matchings, $\hspace{1.14 in}$ where k= polynomial(n)" is not a co-NP problem, since it's not a decision problem. $\hspace{.89 in}$ What would it mean for "finding k different perfect matchings in a bipartite graph" to be co-NP? $\hspace{.17 in}$ (I can't think of any generalization of co-NP to search problems that's not equal to $\hspace{.98 in}$ the corresponding generalization of NP.) $\;$ – user6973 May 2 '15 at 20:13
• It is indeed a decision problem, but I typed incorrectly. Apologies. I fixed it now. – Traveling Salesman May 2 '15 at 21:10
• Look at the literature on the alldifferent constraint in constraint programming. Propagation for alldifferent is equivalent to this problem. – Jules May 3 '15 at 19:06

• The linked paper 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 May 3 '15 at 17:03