Attempting to recognize a tree inside a phylogenetic network is a fundamental undertaking in evolutionary analysis. Therefore, the concept of " tree-based " phylogenetic networks, which was introduced by Francis and Steel, has attracted much attention of theoretical biologists in the last few years. In this context, spanning trees of a certain kind called "subdivision trees" play an essential role and there are many important computational problems about them, whose time complexity is still unclear. Against this backdrop, the present paperaims to provide a graph theoretical framework for solving different problems on subdivision trees in a simple and unified manner. To this end, we focus on a structure called the maximal zig-zag trail decomposition that is inherent in any rooted binary phylogenetic network N and prove a structure theorem that characterizes the collection of all subdivision trees of N . Our theorem does not only imply and unify various results in the literature but also yield linear time (for enumeration, linear delay) algorithms for the following problems: given a rooted binary phylogenetic network N, 1) determine whether or not N has a subdivision tree and find one if there exists any (decision/search problem) ; 2)  compute the number of subdivision trees of N (counting problem); 3 ) list all subdivision trees of N (enumeration problem); and 4 ) find a subdivision tree to maximize or minimize a prescribed objective function (optimization problem). Importantly, the results and algorithms in this paper still hold true for some non-binary phylogenetic networks and this generalization gives a partial answer to an open question from Pons, Semple, and Steel. We also mention some statistical applications and further research directions .
Attempting to recognize a tree inside a phylogenetic network is a fundamental undertaking in evolutionary analysis. In the last few years, therefore, tree-based phylogenetic networks, which are defined by a spanning tree called a subdivision tree, have attracted attention of theoretical biologists . However, the application of such networks is still not easy, due to many problems whose time complexities are not clearly understood. In this paper, we provide a general framework for solving those various old or new problems from a coherent perspective, rather than analyzing the complexity of each individual problem or developing an algorithm one by one. More precisely, we establish a structure theorem that gives a way to canonically decompose any rooted binary phylogenetic network N into maximal zig-zag trails that are uniquely determined, and use it to characterize the set of subdivision trees of N in the form of a direct product, in a way reminiscent of the structure theorem for finitely generated Abelian groups. From the main results, we derive a series of linear time and linear time delay algorithms for the following problems: given a rooted binary phylogenetic network N, 1) determine whether or not N has a subdivision tree and find one if there exists any ; 2) measure the deviation of N from being tree-based; 3) compute the number of subdivision trees of N ; 4 ) list all subdivision trees of N ; and 5 ) find a subdivision tree to maximize or minimize a prescribed objective function . All algorithms proposed here are optimal in terms of time complexity. Our results do not only imply and unify various known results, but also answer many open questions and moreover enable novel applications, such as the estimation of a maximum likelihood tree underlying a tree-based network. The results and algorithms in this paper still hold true for a special class of rooted non-binary phylogenetic networks .
R
Therefore, the concept of "
In the last few years, therefore,
D
"
R
was introduced by Francis and Steel, has attracted much
are defined by a spanning tree called a subdivision tree, have attracted
R
in the last few years. In this context, spanning trees of a certain kind called "subdivision trees" play an essential role and there are many important computational problems about them, whose time complexity is still unclear. Against this backdrop, the present paperaims to provide a graph theoretical
. However, the application of such networks is still not easy, due to many problems whose time complexities are not clearly understood. In this paper, we provide a general
R
different problems on subdivision trees in a simple and unified manner. To this end, we focus on a structure called the maximal zig-zag trail decomposition that is inherent in
those various old or new problems from a coherent perspective, rather than analyzing the complexity of each individual problem or developing an algorithm one by one. More precisely, we establish a structure theorem that gives a way to canonically decompose
R
and prove a structure theorem that characterizes the collection of all
into maximal zig-zag trails that are uniquely determined, and use it to characterize the set of
R
. Our theorem does not only imply and unify various results in the literature but also yield linear time (for enumeration, linear delay)
in the form of a direct product, in a way reminiscent of the structure theorem for finitely generated Abelian groups. From the main results, we derive a series of linear time and linear time delay
D
(decision/search problem)
A
measure the deviation of N from being tree-based; 3)
R
(counting problem); 3
; 4
R
(enumeration problem); and 4
; and 5
R
(optimization problem). Importantly, the
. All algorithms proposed here are optimal in terms of time complexity. Our results do not only imply and unify various known results, but also answer many open questions and moreover enable novel applications, such as the estimation of a maximum likelihood tree underlying a tree-based network. The
R
some
a special class of rooted
D
and this generalization gives a partial answer to an open question from Pons, Semple, and Steel. We also mention some statistical applications and further research directions