0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think you could transform your negative-flow graph into a normal flow graph by simply adding reversed copies of all the edges. Move the negative flows to the new edges (with negated values) and you're set. In a more specific (non-abstract) problem, you might need to consider if the capacities of the reversed edges should be always identical to the capacities of the corresponding original edges, but I suspect if that wasn't the case you wouldn't have been able to have negative flow values in the first place. $\endgroup$ – Blckknght Nov 21 '17 at 1:21
  • $\begingroup$ @Blckknght But that is not the answer I am looking for. I want to know if there is a graph where the usual max flow is smaller than the nonstandard max flow on the same graph. $\endgroup$ – Agnishom Chattopadhyay Nov 21 '17 at 3:10
3
$\begingroup$

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.

$\endgroup$

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.