Ahmad_Elsagheer's blog

By Ahmad_Elsagheer, 5 months ago, In English,

Hello everyone.

A few months ago, I read the proof for the complexity of Edmonds-Karp algorithm O(VE2) in "Introduction to Algorithms" and Dinic's algorithm O(V2E) 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:

  1. consider running a max flow algorithm as a subroutine, so I try to come up with another idea.
  2. 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.

 
 
 
 
  • Vote: I like it  
  • +82
  • Vote: I do not like it  

»
5 months ago, # |
  Vote: I like it +26 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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, 105), (2, 3, 105), (2, 4, 105), (3, 4, 1)}. The algorithm will only push flows of value 1, so it will make at least 105 dfs calls before it terminates. Actually, the algorithm has the output-sensitive complexity, but in a tricky way.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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 105, so first it'll push 2k (so 2k is maximum possible and 2k ≤ 105).

      So for your case it should be around 7 calls to bfs and the same amount to dfs

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 - 4will be constructed so more flows can be detected using the edge 2-3.

  • »
    »
    5 months ago, # ^ |
    Rev. 3   Vote: I like it +18 Vote: I do not like it

    Can you explain the complexity?

    Edit: I found it in this article

»
5 months ago, # |
  Vote: I like it +49 Vote: I do not like it

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

»
5 months ago, # |
Rev. 2   Vote: I like it +38 Vote: I do not like it

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.)

»
5 months ago, # |
  Vote: I like it -64 Vote: I do not like it

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