Complexity of terminal-only Manhattan cost-radius spanning trees
Follow the latest progress by email.
What is the computational complexity of finding a rooted spanning tree using only prescribed terminals in the Manhattan metric, subject to both total-cost and root-radius bounds?
Why it matters and what counts as progress
Why it matters: Terminal-only constraints distinguish the decision problem from routing variants that allow extra Steiner points.
What counts as progress: A polynomial algorithm or NP-completeness proof for the exact cost-radius model; a weak Partition reduction does not establish strong NP-completeness.
How the problem developed
- 1992 · Open problem [1]
Cong and coauthors Formulated bounded-radius routing trees and left open the minimum-cost complexity question for terminal-only Manhattan routing.
- 1995 · Algorithm [1]
Alpert and coauthors Introduced the parameterized Prim–Dijkstra family to navigate the wirelength–delay tradeoff.
- 18 Jul 2026 · Reported claim [1]
Keren Zhu The preprint proves weak NP-completeness for the terminal-only Manhattan cost–radius problem and gives a separate balanced approximation result.
AI contribution
Provably Good Prim-Dijkstra Revisited: New Theory and a Practical Algorithm for a Classical VLSI Routing Problem with LLMs
The rooted terminal-only Manhattan cost-radius spanning-tree decision problem is NP-complete under polynomial-time many-one reductions through a weak reduction from positive-integer Partition.
Sources
Website timeline
Publication dates and editorial changes.
GPT-assisted proof reports weak NP-completeness for terminal-only Manhattan routing