Flip Distance Complexity for Rectangulations

Complexity of Flip Distance Between Rectangulations · arXiv:2311.00779

arXiv Informal medium confidence— first stated 2023-11-06

Authors: Jean Cardinal, Raphael Steiner

Status open high confidence

The computational complexity of computing the flip distance between two rectangulations of a unit square remains open as of May 2026. The source paper (Cardinal–Steiner 2023) proves NP-hardness for shortest paths on polymatroids in general — a framework that subsumes rectangulations as a special case — but this general hardness result does not resolve the specific complexity of the rectangulations instance. A wide search of the 2024–2026 literature found no follow-up paper settling this question; Cardinal’s June 2025 invited talk at CNRS still presents the rectangulations case within the same open context.

Reviewer notes. No follow-up paper specifically resolving the complexity of flip distance between rectangulations was found. Closely related work in the same area: (1) Ito et al. proved NP-hardness of computing combinatorial shortest paths on graph associahedra (SIAM J. Discrete Math., 2024, DOI:10.1137/24M1720317), and an FPT algorithm for the same graph-associahedra problem appeared at ICALP 2025 (DOI:10.4230/LIPIcs.ICALP.2025.63); both concern elimination-tree flip graphs, not rectangulations. (2) The Rectangulotopes paper (arXiv:2404.17349, 2024) constructs polytopes whose skeleta are flip graphs on rectangulations but does not address computational complexity. The rectangulations case remains a specific open sub-problem within the broader polymatroid shortest-path framework of 2311.00779.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. What is the computational complexity of computing the flip distance between two rectangulations of a unit square?

Context

Rectangulations are tessellations of the unit square by axis-aligned rectangles, whose flip graphs are skeletons of polytopes that are polymatroids (and special cases of quotientopes). Since they fall under Problem 2 (shortest paths on a polymatroid), the authors note explicitly that the complexity of the flip distance problems between rectangulations remains open.

Notes. Stated in prose as 'The complexity of these problems is open.' 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