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( rk + 1 kk + 1 + sk² ) time, where s species are defined by kr-state characters.