PROBLEM LINK:
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)
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? 