A game: When can you merge two directed graphs?

Question

I am trying to consider the conditions under which you can win the following directed graph game:

Graph merging game. Fix an acyclic directed graph $G$; its vertex set is $V$, and its edge set is $E$. In this game, you are given two copies of $G$. For each copy, the vertices have been labeled with non-negative integers.

A move in this game consists of picking an edge $a\rightarrow b$ in one of the two copies. The value at $a$ is decremented by 1; the value of $b$ is incremented by 1. You win if you can make the two copies have the same labels at corresponding vertices, where furthermore all the labels are non-negative.

I have solved the problem for the simple case when $G$ is a tree, but I am struggling to find an efficient algorithm for DAGs—although I feel like one should exist. Any suggestions?

Side note: a solution for trees:

1. For each copy, compute the sum of the values of each subtree.
2. Construct a new labeled tree whose value at each node is the larger of the two subtree sums at that node.
3. In the new tree: subtract from each node's value the sum of its childrens' values.
4. It is straightforward to see if you can make all of the values in this tree nonnegative by passing value from parent to child. If you can, the game is winnable — the resulting tree is a tree that you can make through legal moves starting from either of the initial two trees. If you can't, the game is unwinnable.

Edit: I have an idea for a reduction from this problem to maximal flow, but am not sure if it's correct. Any suggestions?

1. Given a graph $G$ and two labelings $n_1,n_2 : V \rightarrow \mathbb{N}$.
2. Create two copies $G_1$ and $G_2$ of the graph, where the edges of $G_2$ are reversed.
3. Join each vertex in $G_1$ to its counterpart in $G_2$.
4. Add a source connected to every vertex in $G_1$ and target connected from every vertex in $G_2$.
5. Set the channel capacity of each edge $s\rightarrow v$ to the label $n_1(v)$. Set the channel capacity of each edge $v\rightarrow t$ to the label $n_2(v)$.
6. For simplicity, set the channel capacity of each other edge to "maximum"---say, the total $P$ of all the values in a single labeling (for example $P \equiv \sum_{v\in V} n_1(v))$.

I feel like the game is winnable if and only if the maximal flow of this graph is of size $P$. Does that seem correct?

Answer 1

Let's think about the game as moving tokens around in the graph along the edges. We're given two token distributions and asked if they can be made into the same distributions of tokens.

We can play the game on a single copy of the graph, if we have red and blue tokens and a rule that says that a red token and a blue token can annihilate each other when they meet. The question is then whether we can remove all tokens from the board from a given starting position.

This is possible if and only if we can pair up all the tokens in red+blue pairs such that for every pair there is a node in the graph that is reachable from both the red and the blue starting position.

Since it is easy to compute which pairs of nodes have common descendants, this reduces the problem to determining whether a certain bipartite graph has a perfect matching.

If you can have large numbers of tokens starting out at the same node, it will be more useful to recast it as a maximum flow problem instead of a matching problem.