On a conjecture of compatibility of multi-states characters

Abstract

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 $\mathcal{C}$ of $r$-states full characters, there exists a function $f(r)$ such that $\mathcal{C}$ is compatible iff every set of $f(r)$ characters of $\mathcal{C}$ is compatible. Some previous work showed that $f(2)=2$, $f(3)=3$ and $f(r)\ge r-1$. Gusfield et al. 09 conjectured that $f(r)=r$ for any $r\ge 2$. In this paper, we present an example showing that $f(4)\ge 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)$.

Cited by in corpus (2)

• A Simple Characterization of the Minimal Obstruction Sets for Three-State Perfect Phylogenies
• Improved Lower Bounds on the Compatibility of Multi-State Characters