Determining if we can balance these graph weights

Question

Let $G$ be a complete directed graph with $n$ vertices. Each vertex $v$ has a weight $w(v)>0$, such that the sum of all vertex weights is $n$. We have that the edge $e$ from $u$ to $v$ has a weight $0 \leq w(e) \leq w(u)$.

We say that these weights can be balanced, if there exists a directed spanning tree, $T$, and function on the edges of $T$, $f$, where $0 \leq f(e)\leq w(e)$, such that for every vertex $v$, we have that $$w(v) + \sum_{e \in I_v} f(e) - \sum_{e \in O_v} f(e)=1$$ where $I_v$ is the set of all edges in $T$ going into $v$, and $O_v$ is the set of edges in $T$ going out from $v$.

Is determining whether the weights can be balanced a known problem? It sounds like a network flow problem, but I'm not too familiar. What's an algorithm which could solve this?

Answer 1

This solves the problem if the function $f$ is not constrained to the edges of a spanning tree.

You can think of your problem as a flow problem where each vertex $u\in V$ "generates" $w(u)$ units of flow and "sinks" 1 unit of flow.

To reduce this problem to a standard flow formulation you can create a new directed graph $G' = (V', E')$ in which each edge $e \in E'$ has a capacity $c(e)$:

• $V' = V \cup \{s,t\}$, where $s$ is a new "source" vertex and $t$ is a new "sink" vertex.
• For each $v \in V$, add to $E'$ the edge $(s,v)$ with capacity $w(u)$.
• For each edge $e \in E$, add $e$ to $E'$ with capacity $c(e) = w(e)$.
• For each $v \in V$ add to $E'$ the edge $(v,t)$ with capacity $1$.

Compute the value $f^*$ maximum flow from $s$ to $t$ in $G'$. If $f^* = |V|$ then your all units of flow can be generated and sunk (one unit from each vertex $u \in V$), therefore your problem problem admits a solution. If $f^* < |V|$ your problem admits no solution (to see this you can show that you can convert any feasible solution to your original problem to a flow of $|V|$ in $G'$).