Interest in phylogenetic trees for histories of species and DNA has spawned many problems, one of which is TreeContainment; a problem that asks whether a tree is contained within a network. The TreeContainment problem is proven to be NP-hard for general trees and networks, however it is solvable in polynomial time for networks that meet the tree-child restriction. An algorithm to solve TreeContainment for binary tree-child networks has been created previously with quadratic running time (van Iersel, Semple, Steel, 2010). Janssen and Murakami have recently created a new algorithm that solves a larger problem NetworkContainment, for semi-binary tree-child networks (Janssen, Murakami, 2019). This new algorithm uses tree-child sequences introduced by Linz and Semple, but there has not been an implementation of it until now. In this paper I show an implementation (using Python) of this algorithm, in which I have made a modification that increases its speed on networks with large indegrees. Furthermore I have proven in this paper that the output of this algorithm remains correct under this modification, and that the running time of the modified algorithm is now linear without requiring a constant maximum indegree at all.

TreeContainment is a well-known problem within phylogenetics, which asks whether a binary phylogenetic tree is embedded in a binary phylogenetic network. For this problem, Jones, Weller and van Iersel (2022) have created an algorithm that uses dynamic programming on tree-decompositions to achieve a running time that is exponential in the tree-width parameter instead of in the number of reticulations. However, due to the implicit formulations of two crucial steps in this algorithm, this running time cannot be achieved in practice without finding ways to generate the required structures explicitly. This paper provides two new sub-algorithms that can do that. To further improve the performance of the algorithm, I introduce a number of criteria and other methods that can be used to reduce the number of structures generated. Additionally, I describe a way to manipulate the nice tree-decompositions to create a more favorable order of bags for the dynamic programming. These sub-algorithms and improvements are used by two new algorithms TWITCH and PITCH, whose implementations are compared to a brute force algorithm and a new branching cherry-picking algorithm named BOTCH. The latter has an FPT running time that is exponential in the number of vertices that have only reticulations as children. The comparisons show that the implementations of the dynamic programming algorithms TWITCH and PITCH are slower in practice than the brute force algorithm, despite their numerous improvements. Of the four new implementations, BOTCH has the best test results and it is shown to be fast in practice.