A ternary permutation constraint satisfaction problem (CSP) is specified by a subset of the symmetric group S3. An instance of such a problem consists of a set of variables Vand a set of constraints C, where each constraint is an ordered triple of distinct elements from V. The goal is to construct a linear ordering αon Vsuch that, for each constraint (a, b, c) ∈C, the ordering of a,b,cinduced by αis in . Excluding symmetries and trivial cases there are eleven such problems, and their complexity is well known. Here we consider the variant of the problem, denoted 2-, where we are allowed to construct two linear orders αand βand each constraint needs to be satisfied by at least one of the two. We give a full complexity classification of all eleven 2-problems, observing that in the switch from one to two linear orders the complexity landscape changes quite abruptly and that hardness proofs become rather intricate. To establish the proofs, we use several computer-aided searches. Each such search returns a small instance with a unique solution for a given problem. We then focus on one of the eleven problems in particular, which is closely related to the 2-Caterpillar Compatibilityproblem in the phylogenetics literature. We show that this particular CSP remains hard on three linear orders, and also in the biologically relevant case when we swap three linear orders for three phylogenetic trees, yielding the 3-Tree Compatibilityproblem. Lastly, we give extremal results concerning the minimum number of trees required, in the worst case, to satisfy a set of rooted triplet constraints on nleaf labels.@en

Phylogenetic networks are leaf-labeled directed acyclic graphs that are used to describe nontreelike evolutionary histories and are thus a generalization of phylogenetic trees. The hybridization number of a phylogenetic network is the sum of all in-degrees minus the number of nodes plus one. The hybridization number problem takes as input a collection of rooted binary phylogenetic trees and asks to construct a phylogenetic network that contains an embedding of each of the input trees and has the smallest possible hybridization number. We present an algorithm for the hybridization number problem on three binary phylogenetic trees on n leaves that runs in time O(ckpoly(n)) with k the hybridization number of an optimal network and c some (astronomical) constant. For the case of two trees, an algorithm with running time O(3.18kn) was proposed before, whereas an algorithm with running time O(ckpoly(n)), also called an EPT algorithm, had prior to this article remained elusive for more than two trees. The algorithm for two trees uses the close connection to acyclic agreement forests to achieve a linear exponent in the running time, while previous algorithms for more than two trees (explicitly or implicitly) relied on a brute force search through all possible underlying network topologies, leading to running times that are not O(ckpoly(n)) for any c. The connection to acyclic agreement forests is much weaker for more than two trees, so even given the right agreement forest, the reconstruction of the network poses major challenges. We prove novel structural results that allow us to reconstruct a network without having to guess the underlying topology. Our techniques generalize to more than three input trees with the exception of one key lemma that maps nodes in the network to tree nodes in order to minimize the amount of guessing involved in constructing the network. The main open problem therefore is to prove results that establish such a mapping for more than three trees.@en

Background Reticulate events play an important role in determining evolutionary relationships. The problem of computing the minimum number of such events to explain discordance between two phylogenetic trees is a hard computational problem. Even for binary trees, exact solvers struggle to solve instances with reticulation number larger than 40-50. Results Here we present CycleKiller and NonbinaryCycleKiller, the first methods to produce solutions verifiably close to optimality for instances with hundreds or even thousands of reticulations. Conclusions Using simulations, we demonstrate that these algorithms run quickly for large and difficult instances, producing solutions that are very close to optimality. As a spin-off from our simulations we also present TerminusEst, which is the fastest exact method currently available that can handle nonbinary trees: this is used to measure the accuracy of the NonbinaryCycleKiller algorithm. All three methods are based on extensions of previous theoretical work (SIDMA 26(4):1635-1656, TCBB 10(1):18-25, SIDMA 28(1):49-66) and are publicly available. We also apply our methods to real data. @en