On a conjecture of compatibility of multi-states characters

Original · EN

Perfect phylogeny consisting of determining the compatibility of a set of characters is known to be NP-complete. We propose in this article a conjecture on the necessary and sufficient conditions of compatibility: Given a set C of r-states full characters, there exists a function f(r) such that C is compatible iff every set of f(r) characters of C is compatible. Some previous work showed that f(2)=2, f(3)=3 and f(r) ≥ r-1. Gusfield et al. 09 conjectured that f(r) = r for any r ≥ 2. In this paper, we present an example showing that f(4) ≥ 5 and then a closure operation for chordal sandwich graphs. The later problem is a common approach of perfect phylogeny. This operation can be the first step to simplify the problem before solving some particular cases f(4), f(5),..., and determining the function f(r).