On the complexity of ordinal clustering

Rahul Shah, Martin Farach-Colton

    Research output: Contribution to journalArticlepeer-review


    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.

    Original languageEnglish (US)
    Pages (from-to)79-102
    Number of pages24
    JournalJournal of Classification
    Issue number1
    StatePublished - Jun 2006


    • Ordinal embeddings
    • Phylogenetics
    • Tree metrics

    ASJC Scopus subject areas

    • Mathematics (miscellaneous)
    • Psychology (miscellaneous)
    • Statistics, Probability and Uncertainty
    • Library and Information Sciences


    Dive into the research topics of 'On the complexity of ordinal clustering'. Together they form a unique fingerprint.

    Cite this