Is Ford-Fulkerson(DFS) + blocking flow + randomization hackable?

Revision en1, by PeruvianCartel, 2023-12-07 14:39:24

Hi guys. When I was doing a problem that basically requires a reasonably fast maximum flow template, one thought came across my mind: Is it possible to hack Ford-Fulkerson(DFS) + blocking flow + randomization? I know that using BFS to run Ford-Fulkerson is much safer, as there is a test generator (It's for MCMF, which is literally DFS Ford-Fulkerson) that make the basic DFS Ford-Fulkerson runs in $$$F$$$ iterations, resulting in the complexity of $$$O(EF)$$$ ($$$E$$$ is number of edges, $$$F$$$ is the maximum flow of the network).

However, I just really want to use DFS Ford-Fulkerson, since you can do blocking flow on it, which grants some pretty bullsh*t performance boost on average (and it's trivial to implement). So... is there any close upper-bound on the complexity of DFS Ford-Fulkerson given these optimization? And if my optimization sucked, is there a test generator to blow it up? (Obviously I can get godlike luck and find the maximum flow on the first iteration. Conversely, RNGesus could just walked my algorithm right into the worst case, so we are only counting the average case here)


  Rev. Lang. By When Δ Comment
en1 English PeruvianCartel 2023-12-07 14:39:24 1263 Initial revision (published)