arXiv · Sep 29, 2026
Can We Break Fine-Grained and NP-Hardness Barriers if We've Seen the Graph Before? The Isomorphic-Priors Model
By Dani Dorfman, Simon Döring, Martin G. Herold et al.
If we run a heavy-duty computation on prior data, can we avoid repeated computation for similar future inputs? Inspired by this question, we introduce a new computational model for graph problems called algorithms with isomorphic priors. Solving a graph problem Π in this model involves two phases: (i) The preprocessing phase quickly analyzes prior graphs G₁, ..., G_k along with the (previously computed) exact optimal values OPT(G_i). (ii) Subsequently, given a new graph H, a fast query phase must either (a) output the exact solution OPT(H), or (b) correctly report that H is not isomorphic to any G_i. Can we avoid computing OPT(H) from scratch when H is isomorphic to some G_i? We show that this is the case for a number of problems; for many others, we establish conditional lower bounds. (1) Some NP-hard problems, including Constrained Shortest Path and ℓ_p-Shortest Path and Constrained Spanning Tree, admit polynomial preprocessing and query times in our model. In contrast, almost all of Karp's 21 NP-complete problems and (2-ε)-approximate k-Center, for every fixed ε>0, admit no such algorithms unless Graph Isomorphism (GI) is in P, even with O(1) priors. (2) In contrast to conditional n^(3-o(1)) fine-grained lower bounds, our framework achieves an O(n^ω) query time for Negative Triangle and a near-linear query time for Replacement Path. It also achieves near-linear query time for Maximum Flow. (3) While it remains a major open problem whether infinite-duration games (Paritiy Game, Mean Payoff Game, Energy Game, and Stochastic Game) admit polynomial-time algorithms, they can be easily solved in near-linear time within our model. Our proofs rely on a simple combination of existing tools and are accessible to readers without specialized background.