View source for Reduction from MAX-CNF-SAT to Maximum Local Edge Connectivity

FROM: [[MAX-CNF-SAT]] TO: [[Maximum Local Edge Connectivity]]

== Description == 



== Implications == 

assume: SETH<br/>then: for any $\epsilon > {0}$, in graphs with $n$ nodes and $\tilde{O}(n)$ edges, target cannot be solved in time $O(n^{2-\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