BST Rotation Distance Computational Complexity
Complexity of Rotation Distance Between Binary Search Trees · arXiv:2311.00779
Status solved high confidence
The question of the computational complexity of rotation distance between binary search trees (equivalently, flip distance between triangulations of a convex polygon) has been resolved. Joseph Dorfer (arXiv:2602.22874, February 2026) proves that both problems are NP-complete, settling a question open since at least the 1980s. This rules out the possibility of a polynomial-time exact algorithm (unless P=NP), despite the known polynomial-time 2-approximation and several FPT algorithms.
Cited literature (1)
-
proof Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete (2026)
Proves that computing the flip distance between triangulations of a convex polygon—equivalently, the rotation distance between binary search trees—is NP-complete, resolving a decades-long open problem.
Reviewer notes. The NP-completeness result (arXiv:2602.22874) was submitted February 26, 2026, about 27 months after the source paper. The proof extends techniques for flip sequences in non-crossing spanning trees. The problem is in NP since a flip sequence of length k can be verified in polynomial time, so NP-hardness implies NP-completeness.
Context
The paper identifies the rotation distance problem as a central motivation for studying shortest paths on polymatroids. Despite a known polynomial-time 2-approximation and several FPT algorithms, the problem is neither known to be NP-hard nor known to admit a polynomial-time exact algorithm, making it a widely open question.
Notes. Stated in prose as 'another widely open question'; not a newly posed problem but an existing open question highlighted as a primary motivation. PDF source — math notation appears clean for this item.
Source paper
Shortest paths on polymatroids and hypergraphic polytopes
Jean Cardinal, Raphael Steiner · 2023-11-06
https://arxiv.org/abs/2311.00779
PDF source