Bipartite Nim-Geography

Question

Two players are playing a game on a bipartite graph where all of the edges are nim-heaps of various sizes. A token starts on one of the vertices, and on your turn you must move the token over an edge and pick up some of the matchsticks in the nim heap corresponding to that edge. If all of the edges meeting the vertex containing the vertex are empty when you start your turn, you lose.

Is there a polynomial time algorithm to decide this game?

Motivation:

I am interested in a multiplayer combinatorial game played as follows: between every pair of people sits a combinatorial game. One player starts with a "hot potato" token. Whoever has the token must make a move on one of the games incident to him to pass the token to the other player playing that game. If he can't make a move in any of the games adjacent to him, he loses and everybody else wins.

Since multiplayer games are hard to analyze, we can simplify the problem by splitting the players into two teams, where each team wants the potato to end up in the hands of the other team. To simplify the game further, we might also assume that no two players on the same team have a game between them. Even then, if all of the games are numbers then this problem is directed bipartite geography which I'm pretty sure is PSPACE-complete, so I'm assuming all of the games are impartial as well.

If all of the nim-heaps have size one or zero, though, then this problem becomes undirected bipartite geography, which can be solved in polynomial time, so I strongly suspect that bipartite nim-geography should have a polynomial time solution as well.

Answer 1

I guess you already know this, but I just stumbled on this paper that studies the exact same game you described:

M. Fukuyama, A Nim game played on graphs, Theoret. Comput. Sci. 304 (2003), 387–399.

$\text{Section 3}$ of this paper studies the Nim game on a simple bipartite graph in which all vertices on one side are of degree (at most) $2$. At the start of the game, the token is assumed to be on a vertex on the side without the degree condition. I put the term "at most" in parentheses because this is proved to be irrelevant in the paper so that you can safely assume that all vertices on the restricted side are of degree $2$. The author gives necessary and sufficient conditions for the first player to have a winning strategy.

To decide if the first player can win by using the necessary and sufficient conditions given in this paper, if my understanding through skimming the paper is correct, you check if the following three conditions hold for each vertex $u$ on the side with the degree restriction:

1. The number $h$ of matchsticks in the nim heap on one edge with $u$ as its endpoint is different from that of the other edge with $u$ as its endpoint, (In the following, $h$ is assumed to be smaller.)

2. Split the vertex $u$ into $u_1$ and $u_2$ and w.l.o.g. assume that the unique edge of which $u_1$ is an endpoint after splitting is of weight $h$. The minimum capacity of $u_1$-$u_2$ cuts is equal to $h$.

3. For any minimum $u_1$-$u_2$ cut, the vertex the token is currently at is connected to $u_2$ (i.e., the one with more matchsticks on its edge).

Checking the first condition is trivial. The second one only needs to compute the minimum capacity, which can be done in polynomial time. For the third condition, while checking if two vertices are connected in a graph can be done quickly, we may have to list all minimum $u_1$-$u_2$ cuts. Google got me this paper that mentions an algorithm for listing all minimum $s$-$t$ cuts for fixed $s$ and $t$, where the run time depends on the total number of minimum $s$-$t$ cuts for all pair $s, t$ in the vertex set, which can be exponential... The details are relegated to another technical report by the same authors (Ref. [GN1] in the linked PDF), and there seems to be an improvement on this in said technical report. But I couldn't find it online.

I looked for a similar paper that doesn't impose the degree condition, but my google-fu failed me.