Fixed-Parameter Algorithms for the Tree Containment Problem on Multifurcating Phylogenetic Network

In recent years, phylogenetic trees have proved insufficient for representing certain evolutionary phenomena, particularly reticulation events commonly observed in nature. To overcome this limitation, phylogenetic networks were introduced as a richer model capable of capturing such events. The interplay between phylogenetic trees and networks naturally gives rise to the Tree Containment Problem, a fundamental computational challenge. This problem is NP-hard even for binary networks and has therefore attracted substantial research interest. Earlier work has mainly focused on exponential-time algorithms for the binary setting or on algorithms tailored to specific biologically motivated classes of networks. Prior to this paper, the best-known runtime for fixed-parameter algorithms in the binary case was $O(1.618^k n^2)$, where $k$ and $n$ represent the reticulation number and the number of vertices in the phylogenetic network, respectively. In this paper, we focus on the Tree Containment Problem on rooted multifurcating phylogenetic networks. Firstly, we study the problem parameterized by the reticulation number $k$ of the network and propose a parameterized algorithm with a runtime of $O(1.618^k m^3)$, where $m$ is the number of arcs in the phylogenetic network. Afterwards, we adapt the algorithm to solve the problem parameterized by the level number $l$, with a runtime of $O(1.618^l m^3)$. Since $l \le k$ for any phylogenetic network, the level-parameterized algorithm is asymptotically more efficient when $l$ is significantly smaller than $k$.