Hello Codeforces! Recently, I was learning about Edmonds' Blossom Algorithm for general graph matching, and I've seen implementations like this or this. I failed to prove that they run in $$$O(VE)$$$ or $$$O(V^3)$$$, and suspects that they might just be $$$O(V^2 E)$$$ or $$$O(V^4)$$$ with very low constants.
The main reason is that when they call blossom(v, w, a), v might move through other already-contracted blossoms, and some edges may be used in $$$O(V)$$$ times. However, I failed to construct a case where the number of this kind of edges $$$\in \omega(V)$$$ to disprove the $$$O(V^3)$$$ upper bound. I believe that the implementation here does not suffer this problem, since it v jumps over the already-contracted blossom.
Resulting to problems on Library Checker and UOJ have failed, too, as the two implementation both passed the test cases with similar runtime. As most of the implementations doesn't jump over the already-contracted blossoms, it might be that most people are using a bad implementation, and this worries me. Does anyone know whether the codes mentioned earlier are correct or not?
Wishing you all a favorable weather and thanks in advance!
Note: the problem on Library Checker are mostly randomly generated.
I do have references to O(nmlog(n)) general matching algorithm's pseudo — code , let me know if you are interested?
Ok, so I finally got it.
For each call of
BFS(), at most $$$\frac{n}{2}$$$ blossoms would spawn, since every blossom consume $$$3$$$ vertices/blossoms. Therefore, even ifblossom(v, w, a)may be $$$O(V)$$$, it will only be called $$$O(V)$$$ times perBFS(), thus the total complexity is $$$O(V^3)$$$.Such a straightforward analysis. Why didn't I think of this sooner...