Overlap Analysis of the Shortest Path Problem: Local Search, Landscapes, and Franz-Parisi Potential

Frederic Koehler, Joonhyung Shin
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4050-4228, 2026.

Abstract

Two directions in algorithms and complexity involve: (1) classifying which optimization problems can be solved in polynomial time, and (2) understanding which computational problems are hard to solve \emph{on average} in addition to the worst case. For many average-case problems, there does not currently exist strong evidence via reductions that they are hard. However, we can still attempt to predict their polynomial time tractability by proving lower bounds against restricted classes of algorithms. Geometric approaches to predicting tractability typically study the \emph{optimization landscape}. For optimization problems with random objectives or constraints, ideas originating in statistical physics suggest we should study the \emph{overlap} between approximately-optimal solutions. Formally, properties of \emph{Gibbs measures} and the \emph{Franz–Parisi potential} imply lower bounds against natural local search algorithms, such as Langevin dynamics. A related theory, the \emph{Overlap Gap Property (OGP)}, proves rigorous lower bounds against classes of algorithms which are stable functions of their input. A remarkable recent work of Li and Schramm [COLT 2025] showed that the shortest path problem in random graphs, which is polynomial-time tractable, admits lower bounds against a class of stable algorithms via the OGP. We further investigate and find that: (1) via the OGP and FPP, we can show stable algorithms and natural MCMC chains fail in the optimization landscape of shortest paths, but (2) stable algorithms and local search succeed in the optimization landscape for shortest path \emph{trees}, which agrees with OGP and FPP predictions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-koehler26a, title = {Overlap Analysis of the Shortest Path Problem: Local Search, Landscapes, and Franz-Parisi Potential}, author = {Koehler, Frederic and Shin, Joonhyung}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {4050--4228}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/koehler26a/koehler26a.pdf}, url = {https://proceedings.mlr.press/v336/koehler26a.html}, abstract = {Two directions in algorithms and complexity involve: (1) classifying which optimization problems can be solved in polynomial time, and (2) understanding which computational problems are hard to solve \emph{on average} in addition to the worst case. For many average-case problems, there does not currently exist strong evidence via reductions that they are hard. However, we can still attempt to predict their polynomial time tractability by proving lower bounds against restricted classes of algorithms. Geometric approaches to predicting tractability typically study the \emph{optimization landscape}. For optimization problems with random objectives or constraints, ideas originating in statistical physics suggest we should study the \emph{overlap} between approximately-optimal solutions. Formally, properties of \emph{Gibbs measures} and the \emph{Franz–Parisi potential} imply lower bounds against natural local search algorithms, such as Langevin dynamics. A related theory, the \emph{Overlap Gap Property (OGP)}, proves rigorous lower bounds against classes of algorithms which are stable functions of their input. A remarkable recent work of Li and Schramm [COLT 2025] showed that the shortest path problem in random graphs, which is polynomial-time tractable, admits lower bounds against a class of stable algorithms via the OGP. We further investigate and find that: (1) via the OGP and FPP, we can show stable algorithms and natural MCMC chains fail in the optimization landscape of shortest paths, but (2) stable algorithms and local search succeed in the optimization landscape for shortest path \emph{trees}, which agrees with OGP and FPP predictions.} }
Endnote
%0 Conference Paper %T Overlap Analysis of the Shortest Path Problem: Local Search, Landscapes, and Franz-Parisi Potential %A Frederic Koehler %A Joonhyung Shin %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-koehler26a %I PMLR %P 4050--4228 %U https://proceedings.mlr.press/v336/koehler26a.html %V 336 %X Two directions in algorithms and complexity involve: (1) classifying which optimization problems can be solved in polynomial time, and (2) understanding which computational problems are hard to solve \emph{on average} in addition to the worst case. For many average-case problems, there does not currently exist strong evidence via reductions that they are hard. However, we can still attempt to predict their polynomial time tractability by proving lower bounds against restricted classes of algorithms. Geometric approaches to predicting tractability typically study the \emph{optimization landscape}. For optimization problems with random objectives or constraints, ideas originating in statistical physics suggest we should study the \emph{overlap} between approximately-optimal solutions. Formally, properties of \emph{Gibbs measures} and the \emph{Franz–Parisi potential} imply lower bounds against natural local search algorithms, such as Langevin dynamics. A related theory, the \emph{Overlap Gap Property (OGP)}, proves rigorous lower bounds against classes of algorithms which are stable functions of their input. A remarkable recent work of Li and Schramm [COLT 2025] showed that the shortest path problem in random graphs, which is polynomial-time tractable, admits lower bounds against a class of stable algorithms via the OGP. We further investigate and find that: (1) via the OGP and FPP, we can show stable algorithms and natural MCMC chains fail in the optimization landscape of shortest paths, but (2) stable algorithms and local search succeed in the optimization landscape for shortest path \emph{trees}, which agrees with OGP and FPP predictions.
APA
Koehler, F. & Shin, J.. (2026). Overlap Analysis of the Shortest Path Problem: Local Search, Landscapes, and Franz-Parisi Potential. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:4050-4228 Available from https://proceedings.mlr.press/v336/koehler26a.html.

Related Material