Solving a graph game

Question

I've struggled some time with a problem from a programming contest (Andrew Stankevich Contest 21) about a game that goes like follows:

Nick and Peter like to play the following game [...]. They draw an undirected bipartite graph G on a sheet of paper, and put a token to one of its vertices. After that they make moves in turn. Nick moves first.

A move consists of moving the token along the graph edge. After it the vertex where the token was before the move, together with all edges incident to it, are removed from the graph. The player who has no valid moves loses the game.

The graph is given and the task now is to find for a given start node, whether the starting player wins or loses if both players play optimally. To summarize

• Bipartite graph
• We are given the start node (say on the left side)
• We move in turns, a move consists of following an edge, but we can't visit a node that was already visited
• The player who cannot move loses

Since the graph is bipartite, Nick (the first player) will always remove a node from the left side and Peter will always remove a node from the right side.

The graph can have up to 1000 nodes (at most 500 at each side) and 50000 edges, so a good polynomial time algorithm is needed (the time limit here is 2 seconds to solve all starting positions, but I think we can share a lot of information between the different starting positions).

I'm pretty sure that this can be reduced to some kind of vertex covering or packing problem, because the graph is bipartite, but I can't find a strategy that correlates to any of these.

I know the solution for a special case: Let's say the sides have n₁ and n₂ vertices, respectively. If there is a matching of size min(n₁, n₂) and if the player on the smaller side begins, than there exists a winning strategy: He just has to follow the matched edges and automatically wins.

Any ideas?

Answer 1

Proposition. Nick (the first player) wins starting from vertex v iff this vertex belongs to every possible maximum matching of the given graph. We will prove it in two steps.

1. If there is a maximum matching without v, Nick loses.
   Indeed, since the matching is maximum, there is no augmenting path from v. That means every simple odd-length path from v can be prolonged by an edge of the matching. In terms of our problem, it means the game can be continued by Peter after every Nick's move.

2. If there is no maximum matching without v, Nick wins.
   Consider any possible maximum matching. Move along the edge of this matching from v to, say, u. Now, the initial matching minus the edge u-v is a maximum matching of the remaining graph which does not include u. As we know from step 1, the player to move now (which is Peter) is at a loss.

---

As for the implementation, we can first construct a maximum matching in O(VE) utilizing the straightforward algorithm (see here for an example implementation) — turns out the common name is Kuhn's augmenting paths algorithm.

After that, you maintain a maximum matching and look at every vertex. If the vertex, say v, is not currently in the matching, Nick loses. If it is, remove the corresponding edge, say v-u, from the matching, forbid the vertex v temporarily and run a search for an augmenting path from u in O(E). If you don't find such path, Nick wins, and you have to restore the edge you removed. Otherwise, Nick loses again, and the new maximum matching can be left untouched. The total running time is O(VE) again.

Answer 2

Cute problem. I believe that the intended solution is to compute a maximum matching and then determine which left vertices belong to every maximum matching. These are the wins for player one.

The winning strategy is to choose edges that belong to a maximum matching. If the start vertex v belongs to every maximum matching, then the other endpoint w of the edge e chosen by player one does not belong to every maximum matching of the graph minus v (since v belongs to every maximum matching, the cardinality of the maximum matching decreases by one after deletion, so since e belongs to some maximum matching M, we have that M - e is maximum in the new graph and leaves the other endpoint of e unmatched). Conversely, if there exists a maximum matching to which v does not belong, then all of its neighbors w belong to all maximum matchings of the graph minus v (otherwise, find a maximum matching without w and add the edge from v to w, contradicting the assumption that the maximum cardinality of a matching did not decrease when we deleted v).