Should the maximal flow through a parted jungle uniquely prescribe its atomic weight?

27 Views Asked by At

This paper (pages 19-22) offers an algorithm for deciding which player will win Hackenbush when the position is a parted jungle. The key step seems to be very similar to the Ford-Fulkerson algorithm, but only cares about the number of tracks produced, not how many edges they contain, let alone capacities. From there, the maximal flow can be used to compute an enlargement, the enlargement can be used to compute an atomic weight, and the atomic weight can be used to decide a winner. I am not sure if the value of the position can also be derived from the atomic weight.

The problem I see is that the enlargement condition depends on the particular tracks in the maximal flow, which are not unique. For example, the parted jungle...

enter image description here

...has a maximal flow of $1$ track, but this is consistent with pushing flow through the top track or the bottom track, just not both at once. The enlargement, however, could be $0$ or $1$, depending on which track was used in the maximal flow. The paper does not say anything about finding multiple maximal flows.

How does one proceed in the face of this possibility? Must the maximal enlargement attainable among all possible sets of tracks with maximal flow be used? The minimal enlargement among them? Something else? Is there a way to find the correct case algorithmically without computing every possible set of tracks with maximal flow (perhaps somehow encoding the enlargement or atomic weight condition directly as edge capacities so the traditional Ford-Fulkerson algorithm can be used)?

1

There are 1 best solutions below

0
On BEST ANSWER

In your example, red has to chop two green edges to get rid of the blue edges, so the number of paths in the enlargement should be $1$. We can clarify the prescribed algorithm in two equivalent ways to arrive at this result: Either require that the maximal flow that allows for the maximal enlargement be chosen, or clarify what’s meant by “tracks [...] that do not conflict with our existing paths”, namely: that do not use an edge that was already used in the same direction. To see that these are equivalent, apply the approach that’s applied in the previous paragraphs in finding the maximal flow: From an enlargement that uses edges of the maximal flow in the opposite direction, you can obtain a maximal enlargement that doesn’t by deleting any edges that were used in both directions and attaching the disconnected final segments of the enlargement tracks to the initial segments of the maximal flow tracks and vice versa.