1
$\begingroup$

Prove or disprove: Given a maximum flow f returned by Dinic's algorithm, there does not exist a cycle in the network such that every edge on the cycle has a strictly positive flow (f(e) > 0).

My intuition tells me this statement is true and should be proven, but I am struggling to formulate a formal proof - I tried approaching the proof by looking at the distance labels (d(v)) from the BFS layered graph. I thought about splitting the cycle into two parts (the part where flow was already pushed, and the part being pushed in the current phase) and trying to show a contradiction with the property that distance labels never decrease (d_{new}(v)<= d_{old}(v)), but I got tangled up in the inequalities.

Any help, hints, or directions for a formal proof would be greatly appreciated. Thanks!

Improve this question
New contributor
CS student is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

Here's a hint for you: it's not true.

Consider a short path (all is unit capacity): s-a-b-c-t and a long path s-x-y-z-u-v-c and an edge c-a and another long path a-p-q-r-t (all are directed in the order written).

This will send flow in two passes:

  • sabct
  • sxyzuvcapqrt

Notice the cycle abca with flow 1.

In Pictures

The flow network:

dinic-1-flow-network

There is a unique shortest path:

dinic-2-short

After shortest path is saturated:

dinic-3-path-1-saturated

There is a unique $s$-$t$-path remaining:

dinic-4-second-path

We saturate the second path:

dinic-5-second-path-saturated

Behold! A cycle.

dinic-6-cycle

A cycle can be cancelled:

dinic-7-cycle-cancelling

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.