# Has this bipartite graph problem been studied?

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 $$$$f'(x, y) = \begin{cases}f(x) & (x,y) \in E(V,U) \\ -f(v) & (x,y) \in E(U,V) \end{cases}.$$$$ 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,

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

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.

• I don't think you mean $f'(e)=f(e)$, since $f$ is a function on vertices. Also your sum is over $(v,u)$ but then you use $e$, and $e$ isn't defined.
– D.W.
Dec 12, 2020 at 1:34

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.