TRIANGULATING VERTEX-COLORED GRAPHS

This paper examines the class of vertex-colored graphs that can be triangulated without the introduction of edges between vertices of the same color. This is related to a fundamental and long-standing problem for numerical taxonomists, called the Perfect Phylogeny Problem. These problems are known to be polynomially equivalent and NP-complete. This paper presents a dynamic programming algorithm that can be used to determine whether a given vertex-colored graph can be so triangulated and that runs in O((n + m(k - 2))k+1) time, where the graph has n vertices, m edges, and k colors. The corresponding algorithm for the Perfect Phylogeny Problem runs in O(r(k+1)k(k+1) + sk2) time, where s species are defined by k r-state characters.