Has this bipartite graph problem been studied?

Question

I have a directed bipartite graph with vertex sets $U$ and $V$, directed edge sets $E(U,V)$ and $E(V,U)$, and a demand function $d \colon U \rightarrow \mathbb{Z}$. I want to find a function $f \colon V \rightarrow \mathbb{Z}$ that "meets the demand" in the following way. Extend $f$ to a function on the edges $f' \colon E \rightarrow \mathbb{Z}$ defined by \begin{equation} f'(x, y) = \begin{cases}f(x) & (x,y) \in E(V,U) \\ -f(v) & (x,y) \in E(U,V) \end{cases}. \end{equation} So, $f'(e) = f(u)$ when $e=(v,u)$ is directed from $V$ to $U$, and $f'(e) = -f(u)$ otherwise. Now I want to $f$ to satisfy the demand such that for each $u \in U$ the edges incident to $u$ sum up to the demand on $u$. That is,

\begin{equation} \sum_{e \in E(V,U)} f'(e) - \sum_{e \in E(U,V)} f'(e) = d(u). \end{equation}

My initial thought was that this could be reduced to some kind of flow problem, but I don't know how to deal with the fact that for each vertex the amount of flow on each edge incident to that vertex must be equal.

Answer 1

This can be solved in polynomial time: it is a system of linear equations over the integers, so you can solve it in polynomial time by forming the Hermite normal form. This might not be the most efficient way to solve it...

---

If you want to express it as a flow, you could try the standard transformation of replacing every vertex $v$ with two vertices $v_\text{in},v_\text{out}$ with an edge $v_\text{in} \to v_\text{out}$; edges directed towards $v$ are replaced with edges to $v_\text{in}$, and edges out of $v$ are replaced with edges out of $v_\text{out}$. I don't know whether that will help in your situation.