HAMILG - Editorial

PROBLEM LINK:

Practice
Contest

Author: Jakub Safin
Tester: Mugurel Ionut Andreica
Editorialist: Lalit Kundu

DIFFICULTY:

Hard

PREREQUISITES:

game theory, graphs, maximum matching, Edmonds’ blossom algorithm

PROBLEM:

Two players, A and B, play a game with a token on an undirected graph G. The game goes as follows:

  • A chooses a starting vertex and places the token on this vertex.
  • The players now alternate turns; B moves first.
  • In his turn, each player has to move the token along exactly one edge to another vertex.
  • It’s not allowed to move the token to some vertex if it was on that vertex earlier during the game (including the starting vertex).
  • The player who can’t make a move loses.

A vertex v is called a winning vertex if A is able to win after choosing this v as the starting vertex. Assume that both players play optimally.
Given the graph G, determine how many winning vertices exist.

QUICK EXPLANATION:

================
Any vertex that is unmatched in one of the maximum matchings of the graph is a winning vertex. Using a maximum matching algorithm (for example Edmonds’ Blossom) build one maximum matching of the graph.

Now, find all alternating paths on it which start on unmatched vertices (once again using Edmonds’ blossom algorithm). All vertices at the end of some alternating path of even length are winning.

EXPLANATION:

================

DEFINITIONS:

First let us see a few definitions.

  • Given a general graph G = (V, E), a maximum matching M is defined as a set of edges such that each vertex in V is incident with at most one edge in M and |M| is maximized.

  • Given G = (V, E) and a matching M of G, a vertex v is “exposed” if no edge of M is incident with v.

  • A path in G is an alternating path, if its edges are alternately not in M and in M (or in M and not in M).

  • An augmenting path P is an alternating path that starts and ends at two distinct exposed vertices. A matching augmentation along an augmenting path P is the operation of replacing M with a new matching as shown in the following image.

  • According to Berge’s lemma, a matching being maximum is equivalent to non-existence of an augmenting path in the graph.

  • A perfect matching is a matching of a graph containing \frac {n}{2} edges(where n is number of vertices), the largest possible, meaning perfect matchings are only possible on graphs with an even number of vertices.

WINNING CONDITION:

First, let’s investigate the winning condition of the players.
There are two cases to be considered here depending on whether graph has a perfect matching or not.

Graph has perfect matching

If graph G has a perfect matching, all vertices v of G are matched, that means, no matter where A puts the token, B can always move this token along the matched edges in this matching. This guarantees that player B will always have a valid move and since the game is finite, he has to win.

Graph doesn’t have perfect matching

If G does not have a perfect matching, player A can choose a maximum matching and place the token in an unmatched vertex, which will result in the player B moving it to a matched one. The player A can now repeat the same strategy of moving along matched edges to win. Notice that there’s no way for the player B to move the token to an unmatched vertex, as that would construct an augmenting path(remember the definition?), but there are no augmenting paths in a maximum matching.

Now, we clearly know what we want. We want to count how many vertices don’t belong to all the maximum matchings of the graph G. Or in other words, we know what the winning vertices are: they’re vertices unmatched in some maximum matching.

Proof to above statement:
If a vertex belongs to all maximum matchings, then player B will win by simply always moving along matched edges; in this arrangement player A can never move to an unmatched vertex, as that’d construct an alternating path that starts in a matched and ends in an unmatched vertex and flipping that path creates a new maximum matching where the starting vertex is unmatched, which is not possible since vertex belongs to all maximum matchings.

HOW TO COUNT WINNING VERTICES

There are too many distinct maximum matchings and even counting them is hard. We can see some of the methods below to count such vertices.

What we can do is find number of edges in maximum matching(for example using Edmonds’ blossom algorithm) of G. Say this value is C. Now for each vertex v we try to decide if it belongs to all maximum matchings or not. If we remove v from G and calculate maximum matching again, and if the new matching value c is \lt C, then we can say that it was part of all maximum matchings of G. An easy way to intuitively realise this is to consider that there exists a matching M of G which doesn’t have v matched, then removing G shouldn’t change the matching and maximum matching in G - {v} should still remain C.

Solution 1(slow)

Now, for calculating the maximum matching in the graph G by excluding some vertex v, we can compute the maximum matching with v excluded from scratch. This option clearly has complexity O(V \cdot \textrm{max_matching}) where O(\textrm{max_matching}) is the complexity of maximum matching algorithm. It can pass subtasks 1, 2 and 3 if you use fairly fast maximum matching algorithm like Edmonds’ Blossom modification which works in O(E \sqrt{V}).

Solution 2(fast)

For every vertex i which is part of the initial maximum matching, try to remove it and check if the matching can be increased. If not, then i occurs in all maximum matchings of the graph. For testing if the matching can be increased after removing the vertex i, it is enough to try to find an augmenting path starting from the vertex j, which is the vertex to which i is matched in the initial maximum matching.

Solution 3(faster)

We don’t want to calculate maximum matching again and again. For that we need to analyse our matchings in some more detail. Let’s say we have calculate a random maximum matching on the graph G initially. I hereby propose a statement:

All vertices at the end of some alternating path of even length beginning at an unmatched vertex are winning.
If there is such an alternating path, we can flip the edges in it to produce another maximum matching, where the vertex at the end of this alternating path will now become unmatched. Now, we can say that this vertex is a winning vertex, because it’s unmatched in one of the maximum matching.

If some vertex is winning, take the symmetric difference of our chosen (and computed) matching and the one where it’s unmatched. There’s a path starting on that vertex (it corresponds to an alternating path) and it has an even length (both matchings are maximum), so it has to end at an unmatched vertex in our chosen matching. Now, we’ve proven both sides of the equivalence between alternating paths and winning-ness of vertices.

The above part of finding vertices at the end of some alternating path of even length beginning at an unmatched vertex can be done in similar way to finding the augmenting paths in Edmonds’ Blossom algorithm. For each unmatched vertex, try to augment from that vertex. There are 3 types of vertices in that augmenting DFS path(i.e. the path you take when you root the DFS tree at the unmatched vertex and go to all the vertices you see when you alternate-walk from this vertex):

  • vertices in at least one blossom; add all of them to the answer.
  • matched vertex whose spouse is behind it in the path; add to answer(since then path is of even length)
  • matched vertex whose spouse is after it in the path; do not add to answer(odd length)

AUTHOR’S, TESTER’S SOLUTIONS:

setter
tester

1 Like

Last month you said that problem CONPOIN is bad because it is about googling the paper, now you created similar task by yourself? :slight_smile: In this case you first need to google original problem and transition to matching problem; then google new task to get the idea about Edmonds-Gallai decomposition. The only difference - two papers instead of one; are you serious? :slight_smile:

11 Likes

I don’t have an access to Setter’s implementation. Could you fix it?
Why did you require so fast version of Edmonds’ algorithm? Was it about googling a paper with O(E*sqrt(V)) algo? Wouldn’t O(n^3) passing be better?

@lebron: (not as a comment because of charlimit)

I didn’t base this problem on any paper (it’s partly a problem from a local math contest and partly my own ideas); also, I tried to google the solution, back when this problem was in that local math contest, and now again. I was unable to find a single one of the ideas found in this solution. (I found out during testing that it can be googled.)

The original math problem was just the winning condition and just for odd number of vertices (lol). I knew about matchings back then, and one of my guesses was that it has something to do with matchings, but I didn’t know about them well enough to prove anything. In the end, I found a proof for trees based on stealing strategies, but anyway… when a lot failed, and then when all else failed, I tried googling. Seriously, I had a month for that contest, and I put a LOT of effort into it. Believe me, I tried. Yet, I was unable to find anything.

Compare it to that problem I complained about: one abstraction, first search result, paper with (simple) implementation. In my mind, these situations are vastly different.

Maybe one of us (or both, seeing the number of solution each time) just had a lot of luck googling in our situations.

Also, I received two PMs during the contest; both were along the lines of “I learned a lot while trying to solve this”. I’m satisfied.

2 Likes

After I read this problem, I immediately connect it to this problem. But I’m busy on playing some game and have no time to study how to change bipartite case to general graph case lol.

2 Likes

My solution is something like O(EV), I think. Matching can be sped up a lot using heuristics, like finding a maximal matching first and then running Edmonds.

Solutions are always inaccessible in editorials… envPZl - Online C++0x Compiler & Debugging Tool - Ideone.com.

For first part of problem: “two players choose new vertex” in Google gives me solution with the very first link :slight_smile: For second part - something like “vertex all maximal matchings” already gives you stackexchange link with question and correct answer (some other person was also solving Long contest :D), and you may find it in some other way also.
But I was lazy to figure out how to rewrite blossom algorithm from e-maxx in a way which allows us to handle blossom compression properly :slight_smile:
Well, I also learned a lot - but in my case same holds for problem from June, and I don’t see much difference.

Stackexchange… so someone was cheating.

I didn’t actually learn much in the problem from June - the paper reaffirmed my (only) guess at how it could be solved, and the implementation was easy to reproduce after I read it.

Wow, looks like I could have also googled the same thing and saved myself a couple of hours.

Just kidding, it was fun to figure out that matching, of all things, was involved :smiley:

On another note, this also explains why there are so many partial scorers for this problem as I found it nontrivial.