AbstractIn this paper, we examine two related problems of inferring the evolutionary history ofnobjects, either from present characters of the objects or from several partial estimates of their evolutionary history. The first problem is called thePhylogenyproblem, and second is theTree Compatibilityproblem. Both of these problems are central in algorithmic approaches to the study of evolution and in other problems of historical reconstruction. In this paper, we show that both of these problems can be solved by graph theoretic methods in linear time, which is time optimal, and which is a significant improvement over existing methods.