I have an undirected graph $G = (V, E)$ with nodes $V$ and edges $E$. Each node $v$ has an associated number $n_v \in \mathbf{Z}$

Let us define for any two nodes $v, w \in V$ connected by an edge $e \in E$, that to net node $v$ with node $w$ means that we set $n_v = 0$ and set $n_w = n_w + n_v$. We also define that the cost of such a netting operation is $|n_v|f(e) \geq 0$ where $f : E \rightarrow[0,\infty)$ is a function describing unit cost of netting between $v, w$.

As an example:

enter image description here

In the above image, the big numbers in each node $v$ represent $n_v$ and the little numbers along each vertex $e$ represent $f(e)$.

The Question

By only netting nodes, I wish to make node $Z$ (green) the only non-zero node. I also want this done at minimal cost.

Does anyone know of an algorithm that does this at minimal cost?

In the above example, we should net node $A$ with $C$ (with a cost of $|-2|\times1$) and $B$ with $C$ (with a cost of $|-3|\times1$). All nodes apart from $Z$ are then $0$ with a total cost of $5$.


Using an application for motivation, imagine we are a charity distributing medicine across cities in a country with a viral outbreak. The situation is rapidly evolving as the virus spreads or as people get better, and so some cities may find they have a shortage of medicine while others have surplus medicine.

The situation may look like:

enter image description here

We need to move medicine from where there is a surplus to where there is a shortage. The medicine can be transported from one city to another via interconnecting roads. There is a transportation cost involved in transporting each unit of medicine. Equivalently, we can move people from one city's hospital to another (we assume the same cost of transportation as medicine for simplicity, i.e. the undirected graph case).

We wish to ensure that all cities have neither a surplus nor a shortage of medicine. Any surplus must be moved back to the depot. Any shortage must also be moved back to the depot (this represents the scenario when we need to create and distribute new medicine from the medicine depot).

  • $\begingroup$ First observations: if all $n_v$ are non-negative (which you state in the problem, even though your example has negative values as well) and all edge costs are non-negative as well, then you can suffice with a single iteration of Dijkstra's algorithm starting from $Z$. (Let all potential flow towards $Z$ along a shortest path.) Secondly, if there are negative cost cycles, then a minimum may not exist. Finally, if the graph is not connected, then a solution need not even exist. Apart from that, I've had no luck so far solving the general case. $\endgroup$ Jul 6 '15 at 21:44
  • $\begingroup$ Many thanks Josse - to address an immediate point I apologise that I made a confusing typo: it should read $n_v \in \mathbf{Z}$. I will respond to the rest of your comment when I get back home tonight :) $\endgroup$
    – mchen
    Jul 6 '15 at 21:52
  • $\begingroup$ @JossevanDobbendeBruyn as for the existence of a minimum with negative cost cycles, consider the medicine transportation scenario outlined in the Motivation: I cannot see why the minimum cost of transporting medicine to fulfill medicine shortages should not exist. Please could you give an example. $\endgroup$
    – mchen
    Jul 6 '15 at 22:46
  • $\begingroup$ Well, suppose that we have a cycle of length $k \geq 3$ where every edge has cost $-1$. Choose some $v_0 \in V$ and set $n_w = 0$ for all $w \neq v_0$ as well as $n_{v_0} = 1$. Now add a sink $Z$ outside of the cycle which is connected to every vertex along the cycle with edge cost $0$. Now we can move the one unit of potential around in cycles and keep the cost decreasing. Of course, if we require that edge costs are non-negative, then this situation cannot occur, and the general problem may or may not be a lot easier as a result. $\endgroup$ Jul 6 '15 at 22:55
  • $\begingroup$ @JossevanDobbendeBruyn, you are right: I should have also stated that edge costs are non-negative. $\endgroup$
    – mchen
    Jul 6 '15 at 22:58

Seems to be solved immediately by transforming it into a min cost max flow problem (with multiple sources and sinks). First, calculate the sum of all the nodes' values --- this will be node Z's final value (the final value for all other nodes are by definition 0). For a node, consider the difference between their final value and their initial value -- if the initial value is larger, you need to move some of its content around, otherwise it will receive some things from other nodes. Thus, for the former case, it can be treated as one of the multiple sources, and the latter case is treated as one of the multiple sinks.

Each edge shall have infinite capacity and have a cost equal to $f(e)$. The cost of the min-cost max-flow of this graph is exactly the minimum cost required.

Note that this will work even if there are edges with negative value, but negative cycles will result in the algorithm working incorrectly.

EDIT: whoops, didn't read the comments.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.