zbMATH — the first resource for mathematics

On the complexity of ordinal clustering. (English) Zbl 1243.92043
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.
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
Full Text: DOI