Provably Good Prim-Dijkstra Revisited: New Theory and a Practical Algorithm for a Classical VLSI Routing Problem with LLMs
Hardware ArchitectureData Structures and Algorithms
Summary
The authors show how large language models can help revisit old but tricky problems in computer science, using a specific routing problem in chip design as an example. They prove the problem's difficulty level, explore a new balance between cost and distance, and create a new solver called HP-RCRST. Their solver outperforms existing methods on many test cases, demonstrating how combining theory and experiments can revive interest in longstanding challenges. They also provide their code for others to use and verify their work.
Authors
Keren Zhu
Abstract
Large language models may make precise but dormant algorithmic problems practical to revisit, and may expose new paths toward fundamental ones. We demonstrate this possibility through Prim-Dijkstra routing, a classic VLSI problem whose terminal-only Manhattan complexity remained open despite decades of practical work. We prove weak NP-completeness, derive a continuous cost-radius tradeoff with a balanced (2,2) guarantee, and build HP-RCRST, a height-partition-based multi-mode solver. On 28 development instances, its stronger modes Pareto-dominate the published-method union on 23 and tie on five. The case shows how conflicting conjectures, counterexamples, formal checks, and implementation can reopen neglected questions. Code and reproducibility materials are available at https://github.com/CODA-Team/hp-rcrst.