As far as I know, all existing strongly polynomial algorithms for flows and assignment problem have $\Omega(V^3)$ complexity in the arithmetic model (assuming the graph is dense). I'm interested in the arithmetic model of computation, where each arithmetic operation on two numbers takes $O(1)$ time regardless of the size of the numbers, not the RAM model.

Is there any theoretical result or conjecture that explains this? I know that there are conjectured complexity lower bounds for problems in P based on 3SUM/APSP/some other problems, but I've never seen them applied to flow-related problems.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.