- cc.complexity-theory graph-theory graph-algorithms np matching
- Updated Sat, 21 May 2022 18:17:32 GMT

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.

Yes, cause the problem lies in P. Look at paper Fukuda, Matsui ''Finding All The Perfect Matchings in Bipartite Graphs''

- +3 – 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. — May 03, 2015 at 17:03
- +0 – I prefer 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! — Jan 07, 2019 at 08:51

External links referenced by this document: