Hierarchically Compatible k-Means on the Line: Exact Is Easy, Near-Exact Is Hard

A hierarchy is α-compatible at a level k if its k-cluster partition costs at most α times the optimal flat k-clustering. We study compatibility for weighted k-means on the line, where every flat problem is polynomial-time solvable. Exact compatibility is polynomial for a fixed number of prescribed levels, for all levels, and for arbitrary non-degenerate levels. In contrast, for every fixed rational 1<α<α₀ ≈ 1.674297, compatibility is NP-complete at the two levels 3n/4,n/2, and when all levels are prescribed. The hardness holds for both interval and unrestricted hierarchies. For a fixed number of levels, the best worst-level ratio over interval hierarchies admits an FPTAS. We explain the contrast through nested segmentation. Exactness can be enforced by tight arcs; one remaining additive budget is tractable, while a strictly exposed local tradeoff yields hardness for two budgets normalized by flat optima. The reduction must control all local cardinalities and realize its budget equality exactly. For two separate interval costs without prescribed counts, we strengthen this sufficient condition to a dichotomy: in any effectively scaling- and separated-sum-closed class with positive stand-alone optima, either every instance admits nested stand-alone optima, or compatibility is NP-complete for some fixed rational pair of factors greater than one. A paired-radix construction handles arbitrarily many profiles on an exposed face. This count-free result does not give a dichotomy for fixed-count k-means. Applications include nested lot sizing and an explicit unweighted, strictly increasing quantile-segmentation instance family. A four-point counterexample shows why nonideality alone does not imply the strict conflict required by the fixed-count transfer theorem. Further results distinguish Monge, median and bottleneck costs and the role of degenerate checkpoints. Research preprint; not peer reviewed. This release distributes the 17 October 2026 manuscript, with the author affiliation updated to Independent Researcher, Israel, together with source files and exact finite verification programs. Package version: 2026.10.18.