Reduction from MAX-CNF-SAT to st-Maximum Flow: Revision history

15 February 2023

• curprev 11:1911:19, 15 February 2023‎ Admin talk contribs‎ 503 bytes −92‎ No edit summary Tag: Manual revert
• curprev 11:1911:19, 15 February 2023‎ Admin talk contribs‎ 595 bytes +92‎ No edit summary Tags: Manual revert Reverted
• curprev 10:5510:55, 15 February 2023‎ Admin talk contribs‎ 503 bytes −92‎ No edit summary Tag: Reverted

• curprev 10:5510:55, 15 February 2023‎ Admin talk contribs‎ 595 bytes +595‎ Created page with "FROM: MAX-CNF-SAT TO: st-Maximum Flow == Description == == Implications == assume: SETH<br/>then: for any fixed constants $\epsilon > {0}$, $c_1,c_2 \in ({0},{1})$, on graphs with $n$ nodes $|S|=\tilde{\Theta}(n^{c_1})$, $|T|=\tilde{\Theta(n^{c_2})}$, $m=O(n)$ edges, and capacaties in $\{1,\cdots,n\}$, target cannot be solved in $O((|S|T|m)^{1-\epsilon})$ == Year == 2018 == Reference == Krauthgamer, R., & Trabelsi, O. (2018). Conditional lower bounds..."