Recognizing Level- k k -Based Phylogenetic Networks is NP-Complete
Takatora Suzuki · 2026
Read Recognizing Level- k k -Based Phylogenetic Networks is NP-Complete by Takatora Suzuki (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-26852.txt.
Introduction
Suzuki proves a conjecture of Suzuki and Hayamizu about how far a phylogenetic network sits from being tree-based. For every fixed level k at least one, he shows it is NP-complete to decide whether the network's minimum support level is at most k. The proof settles the conjectured hardness and closes the gap left by earlier exponential-time algorithms for the problem.
Catalog record
| CREATOR | Takatora Suzuki |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52455 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.26852
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Recognizing Level- k k -Based Phylogenetic Networks is NP-Complete Takatora Suzuki Abstract Phylogenetic networks generalize phylogenetic trees by representing reticulate evolution. Tree-based networks and their support trees have been extensively studied, but not all networks are tree-based. To measure how far such networks are from being tree-based, Suzuki and Hayamizu (2025) formulated the problem of finding the support network with minimum level of a given rooted almost-binary phylogenetic network. They conjectured that this problem is NP-hard and provided exponential-time algorithms. In this paper, we prove this conjecture by showing that, for every fixed integer k ≥ 1 k\geq 1 , it is NP-complete to decide whether the minimum level is at most k k . 1 Introduction Phylogenetic networks are graph-theoretical models for representing reticulate evolution of species, such as horizontal gene transfer [ 2 , 27 ] and hybridization [ 14 ] . Compared with phylogenetic trees, which describe only branching evolution, they can represent a wider range of evolutionary histories, but this also makes them more difficult to interpret. To address this issue, various subclasses of phylogenetic networks have been proposed, each capturing a biologically meaningful scenario while retaining mathematical tractability (see [ 22 ] for a comprehensive review). Among these, two classes have attracted particular attention. The first is the class of level- k networks [ 5 ] , which were introduced to make various computational problems on phylogenetic networks tractable by restricting the local density of reticulations. Specifically, a network is called level- k if each of its biconnected components contains at most k reticulations. Level- 1 networks, originally defined as galled trees in [ 15 ] , have been extensively studied [ 12 , 23 , 4 ] , and level- k networks in general have also attracted considerable attention [ 11 , 28 ] . The second is the class of tree-based networks (e.g., [ 10 , 29 , 1 , 7 , 17 , 16 , 24 , 21 , 20 ] ), which captures the perspective where evolution is tree-like with some reticulate events. More precisely, a network is called tree-based if it has at least one support tree , defined as a spanning tree sharing the root and leaf set. Tree-based networks and their support trees have been the subject of active research since their introduction by Francis and Steel [ 10 ] . Several studies have shown that whether a given network is tree-based can be decided in linear time [ 10 , 29 , 20 , 17 ] . A particularly influential development is Hayamizu’s structure theorem for rooted binary phylogenetic networks (or more generally, for almost-binary networks) [ 17 ] . This theorem provides a direct-product characterization of the family of support trees in a given network by canonically decomposing the network into a unique set of subgraphs called maximal zig-zag trails. This characterization yields optimal algorithms for various computational problems on support trees in a unified manner, such as counting, enumeration, listing, and optimization. On the other hand, it has also been shown that it is NP-hard to decide whether a given tree-based network has a support tree that is a subdivision of a given tree [ 1 ] (see, e.g., [ 21 ] for other hardness result on tree-based networks). However, not all phylogenetic networks are tree-based. Several approaches have been proposed to solve computational problems on such networks [ 7 , 17 , 25 , 9 , 6 , 26 ] . One natural approach is to consider substructures that generalize support trees and to optimize how “close to a support tree” such a substructure is. Along this line, Suzuki and Hayamizu [ 26 ] introduced the notion of support networks for rooted almost-binary phylogenetic networks N , defined as spanning subgraphs of N sharing the root and the leaf set. They then formulated two optimization problems: for a given rooted almost-binary phylogenetic network N , Reticulation Minimization asks for a support network of N with the minimum number of reticulations, and Level Minimization asks for a support network of N with the minimum level. The minimum level among all support networks of N is called the base level of N . For the former problem, they provided a linear-time algorithm. For the latter problem, they conjectured its NP-hardness and developed two exponential-time algorithms: an exact algorithm and a faster heuristic. These algorithms for the two problems are based on their extension of the structure theorem [ 17 ] from support trees to support networks, which also serves as the theoretical foundation of this paper. In this paper, we prove that Level Minimization is NP-hard. We introduce its decision version, which we call Level Decision : given a rooted almost-binary phylogenetic network N and an integer k\geq 0 , decide whether the base level of N is at most k . We note that the case k=0 coincides with the problem of deciding whether N is tree-based, which is known to be linear-time solvable. We prove that Level Decision is NP-complete for every fixed k\geq 1 ; in particular, the NP-hardness of Level Minimization is a direct corollary of this result. The remainder of this paper is organized as follows. Section 2 introduces preliminaries, and Section 3 formulates Level Minimization and its decision version Level Decision . Section 4 recalls two key results from [ 17 ] and [ 26 ] and extends them to the multiple-rooted setting, since our reduction uses multiple-rooted networks as gadgets. Section 5 then establishes the NP-completeness of Level Decision for k=1 via a polynomial-time reduction from 3SAT, which immediately implies the NP-hardness of Level Minimization . Section 6 extends this reduction to establish the NP-completeness of Level Decision for every fixed k\geq 2 . Section 7 concludes with a discussion of open problems and directions for future work. 2 Preliminaries 2.1 Graph theoretical terminology The graphs in this paper are finite, simple (i.e., having neither loops nor multiple edges), acyclic directed graphs, unless otherwise stated. For a graph G , V(G) and E(G) denote the sets of vertices and edges of G , respectively. For two graphs G and H , G is a subgraph of H if both V(G)\subseteq V(H) and E(G)\subseteq E(H) hold, in which case we write G\subseteq H . Two graphs G and H are isomorphic , denoted by G=H , if there exists a bijection \varphi:V(G)\to V(H) such that (u,v)\in E(G) if and only if (\varphi(u),\varphi(v))\in E(H) for all u,v\in V(G) . A subgraph G of H is proper if G\neq H . A subgraph G of H is a spanning subgraph of H if V(G)=V(H) . Given a graph G and a non-empty subset S\subseteq E(G) , the edge-set S is said to induce the subgraph G[S] of G , that is, the one whose edge-set is S and whose vertex-set is the set of the ends of all edges in S . For a graph G with |E(G)|\geq 1 and a partition \{E_{1},\dots,E_{d}\} of E(G) , the collection \{G[E_{1}],\dots,G[E_{d}]\} is a decomposition of G , and G is said to be decomposed into \{G[E_{1}],\dots,G[E_{d}]\} . Here we recall that a partition of a set is a collection of pairwise disjoint non-empty subsets