Flows with Negative Values?

Question

Define a "non-standard" flow to be a flow where the quantity flowing through an edge may be negative.

Formally, given a directed graph $G$, and two designated and distinct vertices $s$ and $t$ (such that no edges are leaving $t$, and no edges are entering $s$), a non-standard flow $f : G_E \to \mathbb{R}$ is a valuation on the edges such that

For each $v \in G_V\setminus \{s, t\}$, the sum of the values of $f$ on the edges entering $v$ is equal to the sum of the values of $f$ on the edges leaving $v$.

Assuming all the capacities are positive, does the Max-Flow Min-Cut theorem still hold for non-standard flows?

Furthermore, is there a network with positive edge capacities, such that the maximum non-standard flow through the network is larger than the maximum (standard) flow through the network?

The standard proof for Max-Flow Min-Cut theorem uses the non-negativity of the flow to claim that each flow is smaller than each cut. I would guess that this tells us that the counterexample (if any) would have a cut that has negative flow into its incoming edges.

Answer 1

The maximum flow calculated using only positive flow values on each edge can indeed be smaller than the maximum if flow can also be negative. You can easily see why in a trivial graph with only two nodes and two edges:

  ---- capacity 1 --->
A                      B
  <--- capacity 1 ----

If A is the source node and B is the sink, you can obviously see that if only positive flows are allowed, you get a max flow of 1 but if negative flows are allowed you'd get 2 (with the bottom edge flowing "backwards").

As I commented, the way to figure out the capacity of a graph that allows negative flows as well as positive ones is to restate the problem. Instead of allowing negative flows, add an additional reversed edge everywhere there's a normal edge in the original graph. Then solve the problem with only positive flows. In the trivial example above, you'd have two edges running each direction, and when you found the maximum using only positive flows, you'd get the right answer, 2.