vkgainz's blog

Max-Flow in almost linear time
By vkgainz, history, 3 years ago, In English

A friend shared this paper with me. It was published today, and seems to suggest that max-flow/min-cut can be exactly computed in almost linear time in the number of edges for general graphs.

I haven't gotten much time to read through it, but I thought it would be interesting to post it here for discussion.

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

»
3 years ago, # |
  Vote: I like it +62 Vote: I do not like it

Am I correct if I rephrase that as follows? For any $$$\alpha > 1$$$, this algorithm is strictly faster asymptotically than $$$O(m^\alpha)$$$.

It's not something that can be just done from scratch during a contest so I expect an optimised library code. I looked through the paper for performance comparisons of this implementation to standard algorithms but didn't find any. That prompts a question: how fast is it in practice? It's like matrix multiplication: nobody uses weird-ass asymptotically best matmul because it's super complex and not that fast on normally sized matrices and modern computers.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +61 Vote: I do not like it

    Re matmat: it's possible to ask multiplications of 10^4 sized matrices in ways that require Strassen... although you do need hardware dependent optimizations / parallelization to truely compare.

    For max-flow, existing codes are all really fast (about 10^6 edges a second). Looking at the code of HiPr (hierarchical push-relabel, anyone got link?) was actually a major motivation for this type of approach (lots of trees, no linear systems)

    For experimental comparisons, the 'right' problem is probably min-cost flow. My understanding is that current codes get quite slow around 2 * 10^4 edges already. However, I have not systematically investigated benchmarks there, does anyone know what's the latest on that?

    ilyaraz, xyz2606, Saurabh, Yihe, and I did look a bit at the performance of optimal transport a while back: OPOT. If you are interested in reviving that it would be awesome.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Elaborating a bit on what rpeng is saying. First, Strassen's

    $$$O(n^{\log_{2}7})$$$

    time matrix multiplication algorithm is (to my understanding) used in practice. This is because it's still pretty explicit.

    And yes, maxflow has great heuristic algorithms in practice, just as various forms of push-relabel, possibly with tree-based heuristics. On the other hand, this seems to work worse with min-cost flow.

    An amazing part of this numerical / linear-algebraic approach to designing outer loops for flow algorithms is that we never see the difference between max-flow and min-cost flow in our analysis at all! In fact, our algorithm works for all flow problems: you can put your favorite convex function on each edge, we can still give a working algorithm (i.e. mincost flow is a linear cost function on each edge, but you can put any cost function you want and our algorithm still works in linear time).

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Correct me if I'm wrong, but I think the matrix multiplication algorithms Xellos is talking about are ones like this which runs in $$$O(n^{2.37})$$$, so it's asymptotically faster than Strassen, but the constant is so large it's unusable in the real world. Quoting the authors, "We nevertheless stress that such improvements are only of theoretical interest, since the huge constants involved in the complexity of fast matrix multiplication usually make these algorithms impractical."

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, the ones beyond Strassen are purely theoretical (the algorithms are much less explicit than Strassen).

        → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Yes, that's the type I'm talking about. It's really the point at which theoretical complexity is irrelevant in practice but we instead focus on things like cache misses, pipeline stalls and (sometimes) parallelisation costs incurred by our code on modern HW.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +19 Vote: I do not like it

          The practical picture with flow algorithms is quite complex. Even for the somewhat less-studied min-cost flow problem, the competing methods are:

          • network simplex: nm time, just like Dinic, but probably also lots of room for optimization.
          • linear systems / central path following methods, which theoretically take m^{1.49}, but except highly tailored data, is about 80 Laplacian solves for 10^7 edges (this is one of my main motivations for banning all linear algebra from OI...)
          • sparsification based things tailored toward dense instances. The OPOT git repo did this hack where it numerically modified the Hungarian code to produce sparser feasible graphs, which apparently helps a lot on benchmarks.

          My suspicion is for most real world data, you'd want to try one of the three above first. Such data are far far from worst case: for max-flow, variants of Dinic do great in practice.

          Then there is this tree based OI meme build. I can imagine some kind of low-stretch tree based network simplex doing well, but one probably need to get a benchmark/data repo for mincost flow going first.

          → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +102 Vote: I do not like it

While most of us CPers are still using Dinitz’s $$$\mathcal O(n^2 m)$$$ max-flow algorithm and $$$\mathcal O(n m f)$$$ min-cost max-flow algorithm, it’s stunning that the academia has made such great progress from $$$\tilde{\mathcal O}(m^{1.5 - \frac{1}{328}})$$$ (gg I misspelled it) to $$$\mathcal O(m^{1 + o(1)})$$$!

rpeng, can you show us the technical details of the algorithm?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +86 Vote: I do not like it

    Lol I was wondering how 328 and 58 (=(3+2)8) were going to get misspelled...

    The build is basically dynamic trees adapted to tree-based graph approximators. Brief guide to technical details from an OI data structures perspective:

    • Write flows in linear algebraic notation, bash some inequalities, turn the problem into supporting about m approximate minimum-ratio cycles on a dynamically changing graph. (Section 4 & 9)
    • Observe that routing along low stretch trees give such approximate solutions to the min-ratio cycle problem. (Dijkstra running in mlogn time is OP) (Section 2.2. for static, dynamic version in Section 7)
    • Start with one such tree embedding, throw HLD/separators/contractions at it to maintain partial routings to end points of vertices involved in updates. (Section 6)
    • Problem on these vertices involved in updates becomes maintaining spanners under vertex splits. In static cases, this can be done by expanders, which are structureless graphs. Maintain such graphs with another round (or two) of segtrees... (Section 5)
    • Things can still break because the costs of the partial routing significantly decreased. Do some coordinated rebuild of the k layers of recursion (Section 8).
    • Carefully analyze the interactions of the randomness against the future updates, using stability of the optimal update step. (start of Sections 6, then Section 9)
    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +29 Vote: I do not like it

    Elaborating a bit on what rpeng said. To me, the main unintuitive parts of this algorithm to CPers is that the problems we solve during each iteration are undirected mostly. This contrasts with more classical approaches to maxflow where we store directed graphs all the time.

    The subproblems to solve are: given an undirected graph G with edge gradients (these are signed gradients, directed along an edge), and edge lengths (these are positive lengths), find a cycle with approximately maximized ratio. Here, the ratio of a cycle is its total gradient divided by its total length. When calculating the total gradient, if the cycle goes opposite to the direction of the edge, we count it as negative the gradient, and if it goes in the same direction, we count it as positive gradient.

    The other possibly unintuitive part is that if the ratio of the cycle returned is a polylog(n) multiplicative off the maximum that's still fine. Now, there is (a nontrivial but) standard algorithm for doing this in linear time. Now... using a lot of data structures / trees / etc. (as rpeng described) we show how to do this dynamically where the gradients and lengths change slowly over the course of the algorithm.

    → Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Is it useful in the competition?

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +65 Vote: I do not like it

Tagging akaiNeko and desert97.

Please note that this is a preliminary version, and has not been thoroughly verified yet. Any questions/thoughts about it will be greatly appreciated though.

In the meantime, maybe we (the authors with CF ids) should go do some team contests and get rekt by flows / trees ... (in my experience, one is surprisingly bad at topics that one has written papers on...)

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    But I haven't written any papers...

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Why write papers when you can print them :p?

      On a more serious note, if you'd like to try some research, now might actually be a good time to get into these graph algorithms, especially in the overlap with ML / network science.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Uhoh this blog is now on Twitter...

    → Reply
»
3 years ago, # |
  Vote: I like it -48 Vote: I do not like it

Why is there no open source implementation with benchmarks?

https://paperswithcode.com should really be a requirement for all CS research.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +71 Vote: I do not like it

    Welcome to the world of theoretical computer science. No code necessary. So TCS research does not always have an experiment part..the important part is the math is correct

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Nah, not sure how much are you into research, but for majority of algorithmic papers it doesn't really make sense to implement things. For some it does though.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      As long as they are theoretically sound, you probably don't need. However in AI/Data science field there are tons of experiments reported in papers and not reproducible in any universe lol

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Yes, that's true. For ML you definitely need experimental results

        → Reply
»
3 years ago, # |
  Vote: I like it +82 Vote: I do not like it

Great paper! Waiting for someone to implement it so the rest of us mortals can use it in competitions.

→ Reply
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

May I ask what level is qualified for scientific research work? It must be cool to be like the author!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    As long as you know the material you can do research, it's not like a degree is required for the material, since nowadays everything is available on the internet. Same applies for every field.

    → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +38 Vote: I do not like it

Tangentially related: According to Donald Knuth (see the TAoCP fascicle and some slides from one of his talks), it is an open problem to determine whether Hopcroft-Karp (or Dinic) is an $$$O(m)$$$ algorithm for bipartite matching. This was really surprising to me!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    Doesn't the example described here require about $$$\sqrt N$$$ rounds for the standard Hopcroft Karp? https://cs.stackexchange.com/questions/116476/an-example-where-the-algorithm-of-hopcroft-and-karp-performs-poorly

    The example graph basically has many connected componentes, each connected component being "a path of length $$$i$$$" for $$$i$$$ from $$$1$$$ to $$$k$$$.

    At least, I am pretty sure that the standard version of Dinitz / Hopcroft-Karp I've seen in various team notebooks could be fooled by such a test cases with adversarial ordering of the vertices. Such a test cases is trivially sped up by almost any extra pruning (like separating in connected components first), but I don't think that many team notebook implementations take such a special extra care.

    I have just skimmed it, but this text claims to actually construct worst-case graphs for the Hopcroft Karp bound (and for other standard algorithms as well): https://people.mpi-inf.mpg.de/~mehlhorn/AlgEng/bipartite_card_matching_ext.ps

    The test case seems to be similar to the previous one since it incorporates many chains of length $$$i$$$ for all $$$i$$$, but made more robust by adding extra nodes to the graph connecting everything.

    → Reply
»
3 years ago, # |
  Vote: I like it +57 Vote: I do not like it

Wow, this is amazing, congratulations to the authors. I'll have to try to implement this, seems like the kind of data structure bash I like :P

I haven't read that far yet, but it seems that a part from the end of "Informal theorem 1.4" on page 3 is missing. It might be just my pdf reader, but it randomly ends with ", and", which seems unintended.

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it -66 Vote: I do not like it

Hi, Is there any open-source implementation for this paper?

→ Reply