Deciding the existence of a cherry-picking sequence is hard on two trees

Journal article (2019)

Authors

Janosch Döcker Universität Tübingen
L.J.J. van Iersel Discrete Mathematics and Optimization - EEMCS
Steven Kelk Universiteit Maastricht
Simone Linz The University of Auckland
Research Group
Discrete Mathematics and Optimization (EEMCS) (TU Delft)
Copyright: © 2019 Janosch Döcker, L.J.J. van Iersel, Steven Kelk, Simone Linz
DOI: https://doi.org/10.1016/j.dam.2019.01.031
Phylogenetic networks Phylogenetics Satisfiability NP-hardness Elimination orders Temporal networks
More Info
expand_more

Published Date

2019

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

Abstract

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.