# Determining if we can balance these graph weights

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?

• I think something is missing in your condition. Apr 16 '20 at 12:13
• ah yes, my mistake, fixed Apr 16 '20 at 17:35

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'$$).

• Ok, so that's how I would set up the problem. Can you give name of an algorithm to compute maximum flow $f^*$? Sorry, I have not yet learned much about network flow. Apr 20 '20 at 17:11
• Also, could you explain why this follows the restrictions that flow must be along a tree? Apr 20 '20 at 17:16
• Uh oh, I'm sorry but I didn't notice the constraint that the flow must move along a spanning tree. For flow algorithms look at Ford-Fulkerson, Edmonds-Karp, and Push-Relabel. Apr 20 '20 at 20:02