Dinic

[kth-competitive-programming]

Dinic

[ludopulles]

Link is dead, consider https://github.com/TimonKnigge/TCR/blob/master/snippets/flowalgorithms/dinic.cpp

[simonlindholm]

I guess we can remove Hopcroft-Karp when we add Dinic, to win back space.

[ludopulles]

Do you also still need EdmondsKarp in this case? Otherwise, it would give PushRelabel, Dinic and EdmondsKarp as flow options. While the last two have the same complexity.

[simonlindholm]

Possibly worth keeping if it's shorter? (Surely Dinic's must be faster than EdmondsKarp.) On the other hand, maybe we should just unify on a single flow algorithm, to avoid being able to pick the wrong thing. This part of KACTL has always been a mess...

[Chillee]

EdmondsKarp is VE^2, while Dinic is EV^2. Dinic's also has a lot of nice properties on things like unit graphs or bipartite matching graphs too (VE^(1/2) for bipartite matching graphs, and min(V^(1/2), E^(2/3))E on unit graphs). So using Dinic's can also obsolete Hopcroft Karp too.

[Chillee]

I think this issue, at least, is resolved. There's another discussion to be had about the "Flow algorithm" situation.

[simonlindholm]

Yep.