  This paper categorizes the parameterized complexity of the algorithmic
problems Perfect Phylogeny and Triangulating Colored Graphs when parameterized
by the number of genes and colors, respectively. We show that they are complete
for the parameterized complexity class XALP using a reduction from Tree-chained
Multicolor Independent Set and a proof of membership. We introduce the problem
Triangulating Multicolored Graphs as a stepping stone and prove
XALP-completeness for this problem as well. We also show that, assuming the
Exponential Time Hypothesis, there exists no algorithm that solves any of these
problems in time $f(k) n^{o(k)}$, where $n$ is the input size, $k$ the
parameter, and $f$ any computable function.
