Reduction from MAX-CNF-SAT to st-Maximum Flow

FROM: MAX-CNF-SAT TO: st-Maximum Flow

Implications

assume: SETH
then: for any fixed $\epsilon > {0}$, in graphs with $n$ nodes, $m=O(n)$ edges, and capacities in $\{1,\cdots,n\}$ target cannot be solved in time $O((n^{2}m)^{1-\epsilon})$

Year

2018

Reference

Krauthgamer, R., & Trabelsi, O. (2018). Conditional lower bounds for all-pairs max-flow. ACM Transactions on Algorithms (TALG), 14(4), 1-15.

https://dl.acm.org/doi/abs/10.1145/3212510