Some easy optimization problems have the overlap-gap property

Shuangping Li, Tselil Schramm

We show that the shortest $s$-$t$ path problem has the overlap-gap property in (i) sparse $\mathbf{G}(n,p)$ graphs and (ii) complete graphs with i.i.d. Exponential edge weights. Fu…