Structural properties of distance-bounded phylogenetic reconciliation

Phylogenetic reconciliation seeks to explain host-symbiont co-evolution by mapping parasite trees onto host trees through events such as cospeciation, duplication, host switching, and loss. Finding an optimal reconciliation that ensures time-consistency is computationally hard when timing information is incomplete, and the complexity remains open when host switches are restricted by a fixed maximum distance $d$. While the case $d = 2$ is known to be polynomial, larger values are unresolved. In this paper, we study the cases $d = 3$ and $d = 4$. We show that although arbitrarily large cycles may occur, it suffices to check only bounded-size cycles (we provide a complete list), provided the reconciliation satisfies acyclicity (i.e., time-consistency) in a stronger sense, which we call strong acyclicity. Strong acyclicity is associated with incorporating discrete time slices into the model.