Towards a Characterisation of the Generalised Cladistic Character Compatibility Problem for Non-branching Character Trees

摘要

In [3,2], the authors introduced the Generalised Cladistic Character Compatibility (GCCC) Problem which generalises a variant of the Perfect Phylogeny Problem in order to model better experiments in molecular biology showing that genes contain information for currently unexpressed traits, e.g., having teeth. In [3], the authors show that this problem is NP-complete and give some special cases which are polynomial. The authors also pose an open case of this problem where each character has only one generalised state, and each character tree is non-branching, a case that models these experiments particularly closely, which we call the Benham-Kannan- Warnow (BKW) Case. In [18], the authors study the complexity of a set of cases of the GCCC Problem for non-branching character trees when the phylogeny tree that is a solution to this compatibility problem is restricted to be either a tree, path or single-branch tree. In particular, they show that if the phylogeny tree must have only one branch, the BKW Case is polynomial-time solvable, by giving a novel algorithm based on PQ-trees used for the consecutive-ones property of binary matrices. In this work, we characterise the complexity of the remainder of the cases considered in [18] for the single-branch tree and the path. We show that some of the open cases are polynomial-time solvable, one by using an algorithm based on directed paths in the character trees similar to the algorithm in [2], and the second by showing that this case can be reduced to a polynomial-time solvable case of [18]. On the other hand, we will show that other open cases are NP-complete using an interesting variation of the ordering problems we study here. In particular, we show that the BKW Case for the path is NP-complete.