TRIANGULATING VERTEX-COLORED GRAPHS

This paper examines the class of vertex-colored graphs that can be tri angulated without the introduction of edges between vertices of the sa me color. This is related to a fundamental and long-standing problem f or 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 de termine whether a given vertex-colored graph can be so triangulated an d that runs in O((n + m(k - 2))k+1) time, where the graph has n vertic es, 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.