Algorithms speed up solving graph problems seen before
Can We Break Fine-Grained and NP-Hardness Barriers if We've Seen the Graph Before? The Isomorphic-Priors Model
Data Structures and Algorithms
Summary
The paper asks whether doing a lot of work analyzing some graphs first can help solve similar new graphs much faster. The authors created a framework where after studying a few graphs and their exact answers, a quick step can either solve new graphs that look like the old ones or say they are different. They show this works well for several hard problems, while others remain tough unless a famous problem (graph isomorphism) becomes easy. Their approach also speeds up some challenging problems and games that are usually slow to solve.
What this means in practice
- •For network schedulers: Improve routing and pathfinding by reusing previous computations on similar network topologies for faster solutions.
- •For game ai developers: Speed up solving certain complex infinite-duration games by quickly recognizing previously analyzed game graphs.
Authors
Dani Dorfmann, Simon Döring, Martin G. Herold, Danupon Nanongkai, Daniel Neuen, Joachim Spoerhase, Zihang Wu
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.