Reduction from MAX-CNF-SAT to Maximum Local Edge Connectivity

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

Implications

assume: SETH
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