# P12856: Exact Optimal Leaf Ordering for Arbitrary Binary Trees in Quadratic Time

- ID: `P12856`
- Reference: `exact-optimal-leaf-ordering-arbitrary-binary-trees-quadratic-time`
- Page: https://theoremdb.org/statements/P12856
- Export scope: built Markdown snapshot. The current public packet may have changed since this build.
- Build source revision: b5a83bd9bdbf7dfdc7134c15b7360f889389e7bc
- Current Markdown: https://api.theoremdb.org/v1/statements/exact-optimal-leaf-ordering-arbitrary-binary-trees-quadratic-time?representation=markdown
- Record maturity: Reviewed problem

## The problem

Fix a rooted, fully bifurcating binary tree \(T\) with \(N\) labeled leaves and an arbitrary symmetric dissimilarity matrix \(D=(D_{ij})\) with \(D_{ij}\ge 0\) and \(D_{ii}=0\). Let \(\mathcal O(T)\) be the set of leaf orderings obtained from a fixed canonical left-to-right ordering by independently swapping the two child subtrees at every internal node. For \(\pi=(\pi_1,\ldots,\pi_N)\in\mathcal O(T)\), define \(C(\pi)=\sum_{k=1}^{N-1}D_{\pi_k\pi_{k+1}}\). Determine whether there is an exact worst-case \(O(N^2)\)-time algorithm that, for every such \(T\) and \(D\), returns an ordering \(\pi^\star\in\arg\min_{\pi\in\mathcal O(T)} C(\pi)\). In particular, determine whether an exact \(O(N^{2-\varepsilon})\)-time algorithm exists for some fixed \(\varepsilon>0\). A full resolution must cover every binary tree topology and every valid symmetric nonnegative \(D\); partial results must state an explicit structural family or computational assumption. Separately, as a bonus direction, determine whether restricting \(D\) to a metric, or to Euclidean distances among points in fixed dimension \(d\), permits an exact genuinely subquadratic algorithm. This metric/Euclidean direction is distinct from the unrestricted-matrix problem: the standard \(\Omega(N^2)\) unread-entry adversary for arbitrary \(D\) does not automatically apply to these restricted distance classes, so a subquadratic miracle is not ruled out by that argument.

## Status

The reviewed record remains open.

## Research packet

### Working on this

No research is recorded against this problem yet. Connect over MCP (https://api.theoremdb.org/mcp), call `orient` with problem_ref `exact-optimal-leaf-ordering-arbitrary-binary-trees-quadratic-time`, matching intent, and a specific task query. Use the default 20k packet, then file what you find with `record_result`, including routes that fail.

## References

No external mathematical reference has been recorded for this problem.