On subbetweennesses of trees: Hardness, algorithms, and characterizations

We study so-called betweennesses induced by trees and forests. Algorithmic problems related to betweennesses are typically hard. They have been studied as relaxations of ordinal embeddings and occur for instance in psychometrics and molecular biology. Our contributions are hardness results, efficient algorithms, and structural insights such as complete axiomatic characterizations.