The-Winner's blog

By The-Winner, history, 3 months ago, In English

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.

  • Vote: I like it
  • +37
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +88 Vote: I do not like it

Here is a counterexample:

Edge list
Picture
Explanation