Parameterized Algorithms for the Tree Containment Problem on Multifurcating Phylogenetic Network
摘要
Recent studies have shown that phylogenetic trees fail to capture certain evolutionary processes, such as reticulation events. To address this, phylogenetic networks were introduced as a more expressive model. This led to the fundamental Tree Containment Problem, which is NP-hard even in the binary case and has been extensively studied, primarily through exponential-time algorithms for binary networks and biologically relevant subclasses. Prior to this work, the best-known fixed-parameter algorithm for binary networks ran in \( O(1.618^k n^2) \) , where \( k \) is the reticulation number and \( n \) is the number of vertices. In this paper, we study the Tree Containment Problem on rooted multifurcating phylogenetic networks, proposing a parameterized algorithm with a runtime of \( O(1.618^k m^3) \) , where \( m \) is the number of arcs. We then adapt this algorithm for parameterization by the level number \( l \) , achieving a runtime of \( O(1.618^l m^3) \) . Since \( l \le k \) , this provides a more efficient solution when \( l \) is significantly smaller.