0

I am wondering if the celebrated duality between max-flow and min-cut actually tolerates infinite valued capacities. Here is a simple example where it seems not:

source s, sink t, five other nodes a, b, c, d, e

s -> a: capacity 3

s -> b: 3

a -> c: $\infty$

a -> d: $\infty$

b -> d: $\infty$

b -> e: $\infty$

c -> t: 1

d -> t: 1

e -> t: 4

The max flow is 5. However, there is no cut whose capacity is 5. This is because the infinite edge capacities force all a, b, c, d, e to belong to the same set of a cut (otherwise there would be an $\infty$ weight in the cut-set).

Janathan
  • 3

1 Answers1

1

You can always replace $\infty$ by a very large finite value, so infinite capacity edges cannot cause problems with the max-flow min-cut theorem.

In your particular example, a min-cut is $\{s,a,c,d\}$ on the source side and $\{b,e,t\}$ on the sink side. The cut edges are (s,b), (c,t), (d,t) which have total capacity 3+1+1=5.

Your argument about infinite capacity edges in the cut is not correct because the edges of the flow network (and the cut) are directed. Even though $d$ and $b$ are on opposite sides of the cut, there is no infinite capacity in the cut because $d$ is on the source side and $b$ is on the sink side, whereas in the flow network, the edge is going from $b$ to $d$.

Ted
  • 33,788