[Asking for Help] Are Popular Blossom Implementations Correct!

Правка en3, от FHVirus, 2024-03-01 11:43:29

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.

Теги #graph, #complexity, #implementation, #blossom

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский FHVirus 2024-03-01 11:44:21 2
en3 Английский FHVirus 2024-03-01 11:43:29 0 (published)
en2 Английский FHVirus 2024-03-01 11:43:04 71
en1 Английский FHVirus 2024-03-01 11:41:59 1520 Initial revision (saved to drafts)