Computing quartet distance is equivalent to counting 4-cycles

The quartet distance is a measure of similarity used to compare two unrooted phylogenetic trees on the same set of n leaves, defined as the number of subsets of four leaves related by a different topology in both trees. After a series of previous results, Brodal et al. [SODA 2013] presented an algorithm that computes this number in O ( nd log n ) time, where d is the maximum degree of a node. For the related triplet distance between rooted phylogenetic trees, the same authors were able to design an O ( n log n ) time algorithm, that is, with running time independent of d . This raises the question of achieving such complexity for computing the quartet distance, or at least improving the dependency on d .

Authors

• Bartlomiej Dudek 0001
• Pawel Gawrychowski

Keywords

• counting 4-cycles
• fine-grained complexity
• quartet distance