Reduction from MAX-CNF-SAT to All-Pairs Maximum Flow: Difference between revisions
Jump to navigation
Jump to search
No edit summary Tags: Manual revert Reverted |
No edit summary Tag: Manual revert |
||
| Line 7: | Line 7: | ||
== Implications == | == Implications == | ||
assume: SETH<br/>then: for any fixed $\epsilon > {0}$, in graphs with $n$ nodes, $m=O(n)$ edges, and | 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 == | == Year == | ||
Latest revision as of 09:59, 10 April 2023
FROM: MAX-CNF-SAT TO: All-Pairs Maximum Flow
Description
Implications
assume: SETH
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 for all-pairs max-flow. ACM Transactions on Algorithms (TALG), 14(4), 1-15.