Max-flow problem

[tbonald]

Here is a suggestion by @hcars :

This is a feature request. I would be interested in adding this to the library if the other contributors like it. The single commodity flow problem centers on finding the maximum flow from a set of source node to a set of target nodes with edge capacity constraints. We could implement a maximum flow method by wrapping https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.maximum_flow.html

[tbonald]

The algorithms available in scipy are not suitable as too computationally expensive.
We might consider more efficient algorithms like the following:
Chen, L.; Kyng, R.; Liu, Y.P.; Gutenberg, M.P.; Sachdeva, S. (2022). "Maximum Flow and Minimum-Cost Flow in Almost-Linear Time". https://arxiv.org/abs/2203.00671

[hcars]

@tbonald sorry, I've been busy for a bit. That could be a good direction. The paper that you linked is a 2022 paper with 4 citations. I haven't read it yet, but should we consider something more tried and true? Also, if we are implementing algorithms ourselves, do we have a guide for making efficient use of Cython, numpy, and other faster alternative to pure Python?

[hcars]

Improvement on King, Rao, and Tarjan for m = O(n^(1.06))
https://dl.acm.org/doi/10.1145/2488608.2488705

[tbonald]

Interesting.
Note that the algorithm by Chen et. al. (2022) seems to be a major breakthrough:
https://www.quantamagazine.org/researchers-achieve-absurdly-fast-algorithm-for-network-flow-20220608/

Implementing it (or a simple version of it) would be a major contribution.

[hcars]

Ok, I will start working through the details of implementing it! Sorry, I've been a bit busy with work.

[hcars]

Interesting. Note that the algorithm by Chen et. al. (2022) seems to be a major breakthrough: https://www.quantamagazine.org/researchers-achieve-absurdly-fast-algorithm-for-network-flow-20220608/

Implementing it (or a simple version of it) would be a major contribution.

I've been trying to get an outline of their algorithm, but the paper contains a lot of concepts that I don't quite understand. What I've gotten so far is they reduce the max-flow problem to min-ratio cycles. I'm not sure how they perform this reduction. Then, they solve the m^(o(1)) min-ratio cycles subproblems using a sparsifier. I'm not sure how the details of this works out.

I might attempt to implement the algorithm by Orlin first since I can understand it better, and it seems to be the largest improvement before Chen et al.

[tbonald]

Sounds good, thanks for the notice.

[hcars]

@tbonald Here is what I have found:

For _Chen, L.; Kyng, R.; Liu, Y.P.; Gutenberg, M.P.; Sachdeva, S. (2022). "Maximum Flow and Minimum-Cost Flow in Almost-Linear Time". https://arxiv.org/abs/2203.00671, they have a near linear-time running time. However, they don't seem to have been as widely cited as the second best algorithm that I could find for max-flow. The second best run-time guarantee that I could find was Orlin's Excess Scaling. Before Excess Scaling, there were are several other deterministic max flow algorithms that improved over Ford-Fulkerson. One that stood out to me is King, Rao, and Tarjan's.

I am going to narrow things down to the Chen paper and Orlin's Excess Scaling and look through the details of their implementation.

Does this approach sound good to you?