Hello everyone.

A few months ago, I read the proof for the complexity of Edmonds-Karp algorithm *O*(*VE*^{2}) in *"Introduction to Algorithms"* and Dinic's algorithm *O*(*V*^{2}*E*) on Maximal. Both proofs are convincing in the sense that they provide a correct upper bound. Also, the output-sensitive complexity *O*(*flow*·*E*) helps in some problems.

However, due to the graph constraints, some problems I encounter make me feel reluctant to:

- consider running a max flow algorithm as a subroutine, so I try to come up with another idea.
- select the algorithm that will pass the time limit (coding time vs. running time).

Here is an example of such problems: ASC 4 — A. Unique Attack. With the given graph constraints (1 ≤ *V* ≤ 800, 1 ≤ *E* ≤ 10000), it seems that max flow algorithms will not pass in 1 second. However, they do! (even Edmonds-Karp).

I was wondering if someone can provide a (quite large generated) test case that is close to the upper bound or maybe share intuitions/approximations/estimates for a tighter bound.

Dinic with scaling works in where is the maxflow. And it's also very easy to write.

I didn't hear before about

"Dinic with scaling", so thanks for mentioning it.I found a code for it here. If this is the correct/meant implementation for it, then

this complexity is not correct.Consider the following undirected weighted graph:

V= {1 -source, 2, 3, 4 -sink},E= {(1, 2, 1), (1, 3, 10^{5}), (2, 3, 10^{5}), (2, 4, 10^{5}), (3, 4, 1)}. The algorithm will only push flows of value 1, so it will make at least 10^{5}dfscalls before it terminates. Actually, the algorithm has the output-sensitive complexity, but in a tricky way.I'm not sure, can you elaborate why do you think it will push only

`flow=1`

?There's a path

`1->3->2->4`

with capacity 10^{5}, so first it'll push 2^{k}(so 2^{k}is maximum possible and 2^{k}≤ 10^{5}).So for your case it should be around 7 calls to

`bfs`

and the same amount to`dfs`

Because the algorithm builds a level graph based on distances from source using edges with flow < capacity. It will look like

`1 - [2, 3] - 4`

(levels are from left to right). So, the edge between nodes 2 and 3 will not be considered because they are at the same level.When we reach

`flow = 1`

, two pushes are possible`1->2->4`

and`1->3->4`

. After these pushes, flows in edges`1-2`

and`3-4`

will reach the capacity, and a new level graph`1 - 3 - 2 - 4`

will be constructed so more flows can be detected using the edge`2-3`

.It builds level graph based on edges

capacity-flow≥lim: https://github.com/ADJA/algos/blob/master/Graphs/Dinic.cpp#L72So the first time it'll build a graph with the only one path

`1->3->2->4`

when`lim = 2^16`

True. You are right. Thanks!

Can you explain the complexity?

Edit: I found it in this article

But still, can someone please provide a "worst-case" for MaxFlow? I have no idea how to go about constructing one of these.

I was always under impression it's not easy.

There is this paper I found: http://rain.ifmo.ru/~buzdalov/papers/cec15-flows.pdf

There is even some code on github so you can try to generate testcases yourself: https://github.com/mbuzdalov/papers/tree/master/2015-cec-flows

So yeah, this seems like relatively elaborate method. I played with it some time ago, and the cases are not that close to upper bound as you would like. (I didn't try particularly hard though.)

Why to learn MaxFlow when you have a president like me!!!