Here we show that deciding whether two rooted binary phylogenetic trees on the same set of taxa permit a cherry-picking sequence, a special type of elimination order on the taxa, is NP-complete. This improves on an earlier result which proved hardness for eight or more trees. Via a known equivalence between cherry-picking sequences and temporal phylogenetic networks, our result proves that it is NP-complete to determine the existence of a temporal phylogenetic network that contains topological embeddings of both trees. The hardness result also greatly strengthens previous inapproximability results for the minimum temporal-hybridization number problem. This is the optimization version of the problem where we wish to construct a temporal phylogenetic network that topologically embeds two given rooted binary phylogenetic trees and that has a minimum number of indegree-2 nodes, which represent events such as hybridization and horizontal gene transfer. We end on a positive note, pointing out that fixed parameter tractability results in this area are likely to ensure the continued relevance of the temporal phylogenetic network model.

@en

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

It has recently been shown that the NP-hard problem of calculating the minimum number of hybridization events that is needed to explain a set of rooted binary phylogenetic trees by means of a hybridization network is fixed-parameter tractable if an instance of the problem consists of precisely two such trees. In this paper, we show that this problem remains fixed-parameter tractable for an arbitrarily large set of rooted binary phylogenetic trees. In particular, we present a quadratic kernel.@en

We show that the problem of computing the hybridization number of two rooted binary phylogenetic trees on the same set of taxa $X$ has a constant factor polynomial-time approximation if and only if the problem of computing a minimum-size feedback vertex set in a directed graph (DFVS) has a constant factor polynomial-time approximation. The latter problem, which asks for a minimum number of vertices to be removed from a directed graph to transform it into a directed acyclic graph, is one of the problems in Karp's seminal 1972 list of 21 NP-complete problems. Despite considerable attention from the combinatorial optimization community, it remains to this day unknown whether a constant factor polynomial-time approximation exists for DFVS. Our result thus places the (in)approximability of hybridization number in a much broader complexity context, and as a consequence we obtain that it inherits inapproximability results from the problem Vertex Cover. On the positive side, we use results from the DFVS literature to give an $\text{O}( \log r \log \log r)$ approximation for the hybridization number where $r$ is the correct value.@en