PROBLEM LINK:Author: Jakub Safin 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 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. QUICK EXPLANATION:================ 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.
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 matchingIf 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 matchingIf $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 VERTICESThere 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 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 winningness 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 alternatewalk from this vertex):
AUTHOR'S, TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 13 Jul '15, 04:45

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

@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. answered 13 Jul '15, 17:27
For first part of problem: "two players choose new vertex" in Google gives me solution with the very first link :) 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 emaxx in a way which allows us to handle blossom compression properly :) Well, I also learned a lot  but in my case same holds for problem from June, and I don't see much difference.
(13 Jul '15, 17:55)
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.
(13 Jul '15, 18:28)
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 :D On another note, this also explains why there are so many partial scorers for this problem as I found it nontrivial.
(13 Jul '15, 18:42)

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. answered 14 Jul '15, 19:43

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? answered 13 Jul '15, 17:08
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... https://ideone.com/envPZl.
(13 Jul '15, 17:32)
