Triangulating Vertex-Colored Graphs
Fred R. McMorris, Tandy J. Warnow, Thomas Wimer · SIAM Journal on Discrete Mathematics · 1994
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} + sk^2 )$ time, where s species are defined by kr-state characters.