How much does ranking help?

I’ve been thinking about ranked trees in various settings for a few years, and recently we’ve come across this surprise, where adding rank moves to the NNI graph drops the complexity of computing the distance between trees from NP-hard to polynomial. Then G Scholar sent me this paper, where @mathmomike and co-authors show that adding ranks to tree-child networks helps too.

Does anyone have more examples of when ranking ancestral events helps?

2 Likes