[Asking for Help] Are Popular Blossom Implementations Correct!

Revision en1, by FHVirus, 2024-03-01 11:41:59

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!

Tags #graph, #complexity, #implementation, #blossom

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English FHVirus 2024-03-01 11:44:21 2
en3 English FHVirus 2024-03-01 11:43:29 0 (published)
en2 English FHVirus 2024-03-01 11:43:04 71
en1 English FHVirus 2024-03-01 11:41:59 1520 Initial revision (saved to drafts)