2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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.) $\;$ $\endgroup$
    – user6973
    Commented May 2, 2015 at 20:13
  • $\begingroup$ It is indeed a decision problem, but I typed incorrectly. Apologies. I fixed it now. $\endgroup$
    – Traveling Salesman
    Commented May 2, 2015 at 21:10
  • $\begingroup$ Look at the literature on the alldifferent constraint in constraint programming. Propagation for alldifferent is equivalent to this problem. $\endgroup$
    – Jules
    Commented May 3, 2015 at 19:06

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – András Salamon
    Commented May 3, 2015 at 17:03
  • $\begingroup$ 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! $\endgroup$
    – Labo
    Commented Jan 7, 2019 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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