On the existence of a cherry-picking sequence
Recently, the minimum number of reticulation events that is required to simultaneously embed a collection P of rooted binary phylogenetic trees into a so-called temporal network has been characterized in terms of cherry-picking sequences. Such a sequence is a particular ordering on the leaves of the trees in P. However, it is well-known that not all collections of phylogenetic trees have a cherry-picking sequence. In this paper, we show that the problem of deciding whether or not P has a cherry-picking sequence is NP-complete for when P contains at least eight rooted binary phylogenetic trees. Moreover, we use automata theory to show that the problem can be solved in polynomial time if the number of trees in P and the number of cherries in each such tree are bounded by a constant.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Deciding the existence of a cherry-picking sequence is hard on two trees
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 earli…
On Context-aware Detection of Cherry-picking in News Reporting
Cherry-picking refers to the deliberate selection of evidence or facts that favor a particular viewpoint while ignoring or distorting evidence that supports an opposing perspective. Manually identifying cherry-picked sta…
Cherry on the Cake: Fairness is NOT an Optimization Problem
In Fair AI literature, the practice of maliciously creating unfair models that nevertheless satisfy fairness constraints is known as "cherry-picking". A cherry-picking model is a model that makes mistakes on purpose, sel…
FairnessMulti-Label ClassificationMUlTI-LABEL-ClASSIFICATIONBreaking the Trend: How to Avoid Cherry-Picked Signals
Our empirical results, illustrated in Fig.5, show an impressive fit with the pretty complex theoritical Sharpe formula of a Trend following strategy depending on the parameter of the signal, which was derived by Grebenko…
On the Definition and Detection of Cherry-Picking in Counterfactual Explanations
Counterfactual explanations are widely used to communicate how inputs must change for a model to alter its prediction. For a single instance, many valid counterfactuals can exist, which leaves open the possibility for an…