Given a network flow, are there bounds on the change in weight on nodes?

Here's my precise situation: I have a graph with nodes $V$ and edges $E$, and the nodes have some non-negative integer weights $w_i$. In one step of the protocol, I am now allowed to move weight around among nodes. This is expressed through a flow $f$ defined on the edges: $f(i,j)$ tells me how much weight I transfer from $i$ to $j$.

• The flow cannot create new weight.
• The flow must be integer.
• $f(i,j)$ is allowed to be larger than $w_i$, but after the entire flow has been applied all the $w_i$ must be non-negative again.

Let $\Delta_i$ be the total change in the weight on node $i$, with the sign convention such that $\Delta_i$ is positive if more tasks leave node $i$ than arrive at $i$. An upper bound on $\Delta_i$ is $w_i$, by virtue of the third condition on the flow. My question now is: Is there also a lower bound?

A naive lower bound for each $\Delta_i$ would be given by the sum of the $\Delta_j$ for all neighbors of $i$, but I wonder if some network- and graph-theory can find better bounds?

If a good lower bound on the $\Delta_i$ is not possible, maybe there is a good \emph{upper} bound on the quantity $$\sum_{i \in V} \Delta_i^2$$?

• It looks interesting. Is there any motivation/application for this problem. Apr 2, 2011 at 19:28
• Yes, I'm studying a random protocol for load balancing: The weights are the number of (unit-size) tasks per node. Each tasks migrates to another node with a certain probability, leading to an expected flow. I want to compare the expected flow with the optimal flow. This is the flow that leads to the largest drop in the potential function $\sum_i w_i(w_i+1)/s_i$, where the $s_i$ are (integer) speeds of the node. Apr 2, 2011 at 19:34

1 Answer

I think you're using a confusing sign convention, but I'll stick with it. It's pretty easy to see that for any connected graph you can have all weight flowing into a single vertex (unless I'm misunderstanding something), so the lower bound you'll get is $$\Delta_i\geq -\sum_{i\in V}w_i.$$

Things won't really be better for bounding the square. For example, if your graph is a star in which every leaf has $w_i=1$, then $$\sum_{i\in V}\Delta_i^2 = (|V|-1)+(|V|-1)^2.$$

You can't get a neighbourhood restriction, either, because you can take the example of a $k$-ary tree in which every leaf has weight 1 and all the weight goes to the root.

What you can get, however, is the possibly useful bound $$\sum_{i\in V}{|\Delta_i|} \leq 2\sum_{i\in V}w_i.$$

To see this, just note that when charge leaves a vertex you'll count it twice.

• Thank you. Okay... I guess I then have to work out some bounds that take into account more properties of the specific flow I'll get. Since explaining these properties here would take too long, and the value for anyone but myself would be close to zero, I'll just leave it at that. Apr 3, 2011 at 15:46