I need to find out if you can have a perfect matching in a given graph, with $n$ vertices and $m$ edges and $1\leq n,m\leq 100$. I want a complexity of $O(n)$ if possible. I only need to know if there is such a perfect matching, not its composition.
$\endgroup$ 22 Answers
$\begingroup$Check out the bounds on the wiki page. An existence algorithm is given here, but I don't know how much that buys you.
$\endgroup$ 3 $\begingroup$Edmonds matching algorithm runs in $O(n^4)$. It is relatively easy to understand (I think). The Wikipedia page says that the paper 'An $O(V^{1/2}E)$ algorithm for finding maximum matching in general graphs' can do it in $O(\sqrt VE)$, but since (usually) $E=O(V^2)$, it is about $O(V^{\frac 52})$. I can't find that article on google right now. When I find it, I'll post a link. Here is a paid one.
EDIT: And this seems to be a free version.
To know whether or not a perfect matching exists is usually just as hard as finding one. If you know your graph is $K_n$ or some other strong fact about it, it may be easy to prove. Otherwise, you will have to search for one.
$\endgroup$
