アブストラクト
| Date | 14:00-15:00 Jan 07, 2026 |
| Speaker | Momoko Hayamizu Department of Applied Mathematics, Waseda University |
| Title | Which Phylogenetic Networks Are Level-k Networks with Additional Arcs? Structure and Algorithms |
| Abstract | Phylogenetic networks, a generalization of phylogenetic trees, are rooted directed acyclic graphs representing reticulate evolutionary history. One natural approach to analyzing such networks is to recognize trees inside a network. Since the paper “Which Phylogenetic Networks are Merely Trees with Additional Arcs?” by Francis and Steel (2015), tree-based networks and their support trees (spanning trees with the same root and leaf set as a given network) have been extensively studied. Subsequently, Hayamizu (2021) established a structure theorem enabling optimal algorithms for various computational problems on support trees of rooted almost-binary networks. However, not all networks are tree-based, and it is meaningful to consider spanning subgraphs beyond trees. In this talk, I present a generalization of the structure theorem that extends the theoretical framework for support trees to support networks. A key result is a direct-product characterization of each of three sets: all, minimal, and minimum support networks, for a given network. These characterizations yield closed-form formulas for their cardinalities, revealing unexpected connections to Fibonacci, Lucas, Padovan, and Perrin numbers, and further lead to optimal algorithms for counting and listing the support networks of each type. Applications include a linear-time algorithm for finding a support network with the fewest reticulations. I also describe exact and heuristic algorithms for finding a support network with the minimum level, both running in exponential time but practical across a reasonably wide range of reticulation numbers. This is joint work with Takatora Suzuki and our paper is available at https://doi.org/10.4230/LIPIcs.WABI.2025.19 |