0
$\begingroup$

Given an unweighted bipartite graph which has a perfect matching, is there an algorithm for finding a perfect matching in the graph that is faster than the best known algorithm for finding a maximum cardinality matching (MCM)? For example, is there some way to take advantage of the fact that the graph is known to have some perfect matching to help find one faster?

If yes, could you please help to point out some references? If it is impossible, could you briefly explain the reason? Comments and suggestions are also welcomed.

$\endgroup$
  • $\begingroup$ Wouldn't answering "no" require a proof that Hopcroft-Karp is best possible? I very much doubt that such a proof exists: we're really not good at that kind of very tight lower bound result, especially within P. $\endgroup$ – David Richerby Sep 8 '16 at 14:50
  • $\begingroup$ Thanks for comments. I am wondering if there is any difference for the case that it is known the bipartite graph has perfect matchings. In other words, knowing the matching is perfect, can we find the matching faster? $\endgroup$ – Neil Sep 8 '16 at 15:06
  • 1
    $\begingroup$ Sure. But suppose that you wanted to say, "No, you can't do better than $O(n^{2.5})$ even with the knowledge that the graph has a perfect matching." One way that you could potentially do better is to ignore the promise that a perfect matching exists, and discover an algorithm for finding maximum matchings in, say, time $O(n^2)$. So to say, "No, you can't do better than Hopcroft-Karp", you'd have to prove that this $O(n^2)$ algorithm doesn't exist. $\endgroup$ – David Richerby Sep 8 '16 at 16:10
  • 1
    $\begingroup$ @Neil No, you're missing my point but I can't think of any other way to explain it. To answer this question with "No", you would have to prove that no algorithm finds maximum matchings (with or without with the knowledge that there is a perfect matching in the graph) runs faster than $\Theta(n^{2.5})$. We, as a field, do not know how to prove things like that. $\endgroup$ – David Richerby Sep 9 '16 at 7:43
  • 1
    $\begingroup$ @Neil Because there are two possible types of algorithm: algorithms that use the hint (there exists a PM, the graph is chordal, or whatever other property) to get better performance and algorithms that always get better performance, even without using the hint. If you want to prove that better performance is impossible, you have to rule out both possibilities. $\endgroup$ – David Richerby Sep 9 '16 at 8:53
1
$\begingroup$

Hopcroft-Karp isn't necessarily optimal, and you can already find asymptotically faster algorithms in the relevant Wikipedia pages: https://en.wikipedia.org/wiki/Matching_(graph_theory)#In_unweighted_bipartite_graphs, https://en.wikipedia.org/wiki/Maximum_flow_problem#Solutions. Note that you can use any network flow algorithm to find a perfect matching.

For instance, you can achieve $O(n^{2.373})$ running time using fast matrix multiplication, though this is only a theoretical result; in practice it's slower. However, this is already enough to demonstrate that there's no way we're going to prove that you can't do better than Hopcroft-Karp (because you can). For sparse graphs ($|E|=O(n)$), Madry's algorithm achieves $O(n^{1.43})$ running time. Neither of these use/exploit the fact that the graph already contains a perfect matching.

$\endgroup$
  • $\begingroup$ Thank you very much for the information. I have slightly modify the question and title so that we would focus on the issue concerning the perfect matching condition. $\endgroup$ – Neil Sep 9 '16 at 8:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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