Simplifying Evolutionary Networks: An ILP Puzzle to Reveal Hidden Tree Structures

Imagine a network that shows how different species are related, but sometimes they cross like rivers that join together. These phylogenetic networks are useful, but hard to read. Researchers want to extract simpler, almost tree‑like parts to better understand evolution. The problem is called Level Minimization: find a spanning subgraph that keeps the same root and leaf set but has as few levels as possible, i.e., is as close to a tree as possible. For some networks the minimum level is zero, meaning they are already tree‑based. In general, however, the problem is NP‑hard. This paper proposes two integer linear programming methods. The first is exact and finds a subgraph with level at most one. The second is a heuristic for the general case. Computational experiments compared the approaches with existing algorithms, showing improved speed and accuracy. Using ILP allows systematic exploration of optimal solutions, something exhaustive searches cannot do on larger networks. Applying the method to ancestral recombination graphs also uncovered new clues about population genetic history. In short, the work merges algorithmic theory with evolutionary biology, providing a practical tool to reveal hidden structure in phylogenetic networks.

The Level Minimization problem aims to delete as few arcs as possible from a rooted almost‑binary phylogenetic network while preserving the original leaf set and root, seeking a subgraph with the smallest possible level. The level of a network is the maximum number of directed arcs in a series from the root to a leaf. A level‑zero network is already a tree; a level‑one network contains exactly one 2‑cycle. The exact formulation for level ≤1 introduces binary variables x_e for each arc and, besides standard flow conservation constraints, adds constraints that forbid 2‑cycles. The objective minimizes the total cost of selected arcs, where costs can reflect biological importance. For the general case, a heuristic based on LP relaxations and iterative cutting provides a good approximation in reasonable time. Computational tests covered synthetic networks up to several thousand nodes and real ancestral recombination graphs. The exact model solved small instances instantly, while the heuristic handled larger networks with solution quality close to the global optimum. When applied to ancestral recombination graphs, the minimum level emerged as an alternative measure of topological complexity, complementing traditional recombination counts. Future work will extend the model to non‑almost‑binary networks, incorporate phenotypic data, and explore cutting‑plane techniques to accelerate solving.