doreshnikov's blog

Non-bipartite matchings, (in)correct algorithm
By doreshnikov, 13 months ago, translation, In English

Hello everyone!

I thought that maybe someone on Codeforces can help me find an error or build a counterexample. If you remember matchings in non-bipartite graphs, then the problem with Kuhn's algorithm is as follows: we need to find an augmenting path, but we can arrive at the desired vertex via an edge of the wrong type, mark it as visited, and leave.

  1. First attempt to solve the problem: do a dfs on vertices of the form (v, flag), where flag is the type of edge we arrived by. Obviously, this doesn't work: we can go through both (v, false) and (v, true) because they are different vertices, but then our augmenting path in the original graph is not simple, and we haven't actually found an augmenting path.

  2. Second attempt to solve the problem: do the same thing as before, but explicitly forbid dfs to go to vertices that have already been visited (are on the path from the start to the current vertex), even if they were visited with a different flag. Something like this:

vis[v, flag] <- false for each v, flag
path = []

dfs(v, flag):
    vis[v, flag] = true
    path.add(v)

    for u : g[v], such that (status[vu] != flag) && (u not in path) && (not vis[u, !flag]):
        dfs(u, !flag)

    path.pop()

Since people write Blossom algorithm, and I'm probably not smarter than Edmonds, who came up with it, there is either a counterexample to my “solution” or it just takes a long time, but I haven't yet realized why. I hope that there are smart people out there who will somehow see this post and explain to me where I'm wrong :)

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

»
13 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I think it should be quite simple to find a counter-example to your implementation with just a stress test, but I don't remember any such test right away.

The very similar algorithm, but a bit more powerful, was discussed here, code. The important difference is that in linked code we jump over and don't mark as visited odd vertices on a path, while you explicitly mark all vertices visited (path.add(v) and u not in path).

If you shuffle graph edges and do multiple attempts to find an augmenting path, this algorithm works very well, and I got AC in multiple tasks about general matchings this way (and even once in PTZ camp something much more complicated, on skew-symmetric flows). E.g. Timus 1099, which aggregated tests for decades (I hope), can be solved with this approach quite easily. It's claimed above that there is a test family where it's hard to find matchings heuristically, but I haven't seen such a test family.

→ Reply