<p>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...</p>
<hr />
<p>If you want to express it as a flow, you could try the standard transformation of replacing every vertex <span class="math-container">$v$</span> with two vertices <span class="math-container">$v_\text{in},v_\text{out}$</span> with an edge <span class="math-container">$v_\text{in} \to v_\text{out}$</span>; edges directed towards <span class="math-container">$v$</span> are replaced with edges to <span class="math-container">$v_\text{in}$</span>, and edges out of <span class="math-container">$v$</span> are replaced with edges out of <span class="math-container">$v_\text{out}$</span>.  I don't know whether that will help in your situation.</p>

CC BY-SA 4.0
2020-12-12T01:40:30.717Z
2020-12-12T01:40:30.717Z
D.W.
<p>I have a directed bipartite graph with vertex sets <span class="math-container">$U$</span> and <span class="math-container">$V$</span>, directed edge sets <span class="math-container">$E(U,V)$</span> and <span class="math-container">$E(V,U)$</span>, and a demand function <span class="math-container">$d \colon U \rightarrow \mathbb{Z}$</span>. I want to find a function <span class="math-container">$f \colon V \rightarrow \mathbb{Z}$</span> that &quot;meets the demand&quot; in the following way. Extend <span class="math-container">$f$</span> to a function on the edges <span class="math-container">$f' \colon E \rightarrow \mathbb{Z}$</span> defined by
<span class="math-container">\begin{equation}
f'(x, y) = \begin{cases}f(x) &amp; (x,y) \in E(V,U)  \\
             -f(v) &amp; (x,y) \in E(U,V)
\end{cases}.
\end{equation}</span>
So, <span class="math-container">$f'(e) = f(u)$</span> when <span class="math-container">$e=(v,u)$</span> is directed from <span class="math-container">$V$</span> to <span class="math-container">$U$</span>, and <span class="math-container">$f'(e) = -f(u)$</span> otherwise. Now I want to <span class="math-container">$f$</span> to satisfy the demand such that for each <span class="math-container">$u \in U$</span> the edges incident to <span class="math-container">$u$</span> sum up to the demand on <span class="math-container">$u$</span>. That is,</p>
<p><span class="math-container">\begin{equation}
\sum_{e \in E(V,U)} f'(e) - \sum_{e \in E(U,V)} f'(e) = d(u).
\end{equation}</span></p>
<p>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.</p>

CC BY-SA 4.0
2020-12-12T01:34:56.153Z
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.
<graph-theory><graph-algorithms>
Has this bipartite graph problem been studied?
Will
# Has this bipartite graph problem been studied?

(Asked by: username_0 on 2020-12-12)

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.

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_1 on 2020-12-12. Score: 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.


---

