Greedy maximum matching?

Revision en2, by The-Winner, 2023-12-07 22:54:36

Hello, Codeforces!

(Disclaimer: I know very little about flows and matchings)

An interesting idea that I heard at the University recently was a greedy algorithm to find the maximum matching in a bipartite graph. The idea is simple, at each step take the node with the smallest number of unmatched neighbours (I will call it active degree) and match this node with one of its neighbours. Specifficaly match it with the neighbour whose active degree is the smallest. Update the active degree for all neighbours of the 2 nodes. Repeat until you can't match anything.

Noone in class was able to find a counter example, but we also couldn't prove that it is correct (which it likely isn't).

If anyone would be kind enough to provide a counter example / proof / link to some paper / article I would be very thankful.

Tags matching, maximum flow


  Rev. Lang. By When Δ Comment
en2 English The-Winner 2023-12-07 22:54:36 0 (published)
en1 English The-Winner 2023-12-07 22:53:18 846 Initial revision (saved to drafts)