{"id":"arxiv:2609.37979","kind":"preprint","title":"Can We Break Fine-Grained and NP-Hardness Barriers if We've Seen the Graph Before? The Isomorphic-Priors Model","authors":["Dani Dorfman","Simon Döring","Martin G. Herold","Danupon Nanongkai","Daniel Neuen","Joachim Spoerhase","Zihang Wu"],"author_count":7,"year":2026,"published":"2026-09-29","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2609.37979","nct_id":null,"source_url":"https://arxiv.org/abs/2609.37979","archive_url":"https://space-kitty.com/papers/arxiv:2609.37979","updated":"2026-09-29","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2609.37979","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}