Efficient algorithm for assigning weights to nodes in graph to create steady state flow

Question

I'm looking for an efficient algorithm (at least polynomial in the size of the graph, preferably linear) for the following problem:

Definitions: Given a graph $(V,E)$, with non-negative weights assigned to it's edges $w_E:E \rightarrow \mathbb{R}^+\cup\{0\}$ and non-negative weights assigned to it's vertices $w_V:V \rightarrow \mathbb{R}^+\cup\{0\}$ we define the flow on the edge $e=(v_1,v_2)\in E$ to be the wight of the vertex where the edge starts times the weight of the edge, $f(e=(v_1,v_2)) \equiv w_V(v_1)\cdot w_E(e)$. The inward flow to vertex $v\in V$ is defined by the sum of the flows on all inward edges $f_{in}(v) = \sum_{e\in E\;s.t.\; e=(u,v)}f(e)$ and the outward flow the sum of flows on all the outward edges $f_{out}(v) = \sum_{e\in E\;s.t.\; e=(v,u)}f(e)$.

The Problem Given a finite directed graph $(V,E)$ and an edge weights assignment $w_E$, find a non-trivial weights assignment to the vertices $w_V$ such that the inward flow and the outward flow are equal for each vertex, $\forall v\in V\; f_{in}(v) = f_{out}(v)$. The trivial solution is $w_V\equiv 0$. Notice that I'm only looking for one non-trivial solution (there could be more than one). If there is no non-trivial solution the algorithm should return some error message.

Any ideas? Thank you for your help

Answer 1

I will assume, that all weights are rational (since there is a problem with representing irrational numbers on computer).

You can solve this problem by using linear programming in similar manner to finding maximal flow.

$\forall_{v \in V} w_V$ is constant.

$\forall_{e \in E} w_e$ is variable.

Firstly, for each node we want to be sure that inward flow is equal to outward flow: $$\forall_{v \in V} \sum_{(v_{i}, v)\in E}w_{v_{i}}w_{(v_{i}, v)} = \sum_{(v, v_o)\in E}w_{v}w_{(v, v_o)}$$

Then we want to be sure, that every edge is non negative: $$\forall_{e \in E} w_e \geq 0$$

You can notice, that if there is any non-trivial solution then there are infinitely many, arbitrary large flows (you can multiply weight of every edge by constant $c$ and it will be still valid). So if there is any non-trivial solution, then there is a solution with sum of weights of edges not smaller then 1: $$\sum_{e \in E} w_e \geq 1$$

Now what's left is to check if there is a solution for this linear programming instance.