# Can We Break Fine-Grained and NP-Hardness Barriers if We've Seen the Graph Before? The Isomorphic-Priors Model

Preprint · Dani Dorfman, Simon Döring, Martin G. Herold, Danupon Nanongkai, Daniel Neuen, Joachim Spoerhase, Zihang Wu

- Archive id: arxiv:2609.37979
- Published: 2026-09-29
- arXiv: https://arxiv.org/abs/2609.37979
- Source URL: https://arxiv.org/abs/2609.37979
- PDF: https://arxiv.org/pdf/2609.37979
- Provenance: arxiv

## Abstract

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\_1, ..., 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. $\\textbf{(1)}$ Some NP-hard problems, including Constrained Shortest Path and $\\ell\_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-\\varepsilon)$-approximate $k$-Center, for every fixed $\\varepsilon\>0$, admit no such algorithms unless Graph Isomorphism (GI) is in P, even with O(1) priors. $\\textbf{(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. $\\textbf{(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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.