ON THE TREE AND CLUSTER CONTAINMENT PROBLEMS FOR PHYLOGENETIC NETWORKS

Abstract

The tree containment problem (TCP) and cluster containment problem (CCP) are two fundamental problems arising from verification of network model for evolution. These problems are NP-hard for arbitrary networks. A lot of effort has been devoted to find network classes where these problems can be solved quickly. A bottleneck 7-years conjecture asks whether the TCP is solvable in polynomial time if the network input is reticulation-visible. In this paper, we present a positive answer to the conjecture and present a quadratic-time TCP algorithm for arbitrary reticulation-visible networks. While studying the problem, we discover a novel network decomposition that is useful in dealing with TCP and CCP. We then study the applications of this decomposition, and construct several TCP and CCP algorithms for some network classes. We also established a linear-time transformation from CCP instance to SAT instance, which opens up a possibility for creating faster CCP algorithms in the future.