On the complexity of ordinal clustering. (English) Zbl 1243.92043

Shah, Rahul; Farach-Colton, Martin

J. Classif. 23, No. 1, 79-102 (2006).

Summary: Given a set of pairwise distances on a set of n points, constructing an edgeweighted tree whose leaves are these n points such that the tree distances would mimic the original distances under some criteria is a fundamental problem. One such criterion is to preserve the ordinal relation between the pairwise distances. The ordinal relation can be of the form of total order on the distances or it can be some partial order specified on the pairwise distances. We show that the problem of finding a weighted tree, if it exists, which would preserve the total order on pairwise distances is NP-hard. We also show the NP-hardness of the problem of finding a weighted tree which would preserve a particular kind of partial order called a triangle order, one of the most fundamental partial orders considered in computational biology.

MSC:

92D15	Problems related to evolution
62H30	Classification and discrimination; cluster analysis (statistical aspects)
65Y20	Complexity and performance of numerical algorithms
05C90	Applications of graph theory
65C20	Probabilistic models, generic numerical methods in probability and statistics

Keywords:

phylogenetics; tree metrics; ordinal embeddings