combinatorial game theory - Bipartite Nim-Geography

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.

• Next ac.commutative algebra - Intersection of finitely generated subalgebras also finitely generated?
• Previous at.algebraic topology - Extending a property of commutative algebras to C infinity algebras