Subroutines Sample Clauses

Subroutines. 4.1 Enumerating the set of reticulation-trimmed subnetworks We now show how to enumerate the set of all reticulation-trimmed subnetworks of a network N in time O(3|R(N)||V (N )|). The reticulation-trimmed subnetworks are characterized by having no more reductions than what sufficiently removes the desired reticulation edges. Luckily, we will see that at most one such network can exist; we must only remove the complete subnetwork under both endpoints of the reduced reticulation edge. This is guaranteed possible by cherry reduc- tions, assuming all reticulations below these endpoints have also been specified for removal. Algorithm 2 shows how to enumerate the relevant edges, and uses Algorithm 3 as a subroutine, which finds the reticulation-trimmed subnetwork with respect to a given edge set. We show that the reticulation-trimmed subnet- work of N with respect to F ⊆ R(N ) is uniquely defined in Lemma 4. We say that a set of edges F is disjoint if, for any two distinct edges (u, v), (x, y) ∈ F , {u, v} ∩ {x, y} = ∅. Algorithm 2 REDUCED-SET-FINDER Input A network U Output The set of all reticulation-trimmed subnetworks of U 1: for each F ∈ {P(ER(U )) : (a, b), (c, b) ∈/ F for any a, b, c} do 2: N → N ∪ RT-SUBNET-MAKER(U , F ) 3: end for 4: return N Lemma 2. Let N be a network, F ⊆ ER(N ) be a set, and N ′ be a network that is a reticulation-trimmed subnetwork of N with respect to F. Then F is disjoint. For proof of Lemma 2, see Appendix. Next, for F ⊆ ER(N ), a topological sort of F is an ordering of its element such that for distinct edges e1, e2 ∈ F , if there is a path from a vertex of e1 to a vertex of e2 in N , then e1 comes later than e2 in this ordering. Lemma 3. Let N be a network and F ⊆ ER(N ) be a set such that there exists a reticulation-trimmed subnetwork of N with respect to F. Then there exists a topological sort of F. For proof of Lemma 3, see Appendix. The next lemma is crucial, as it shows that reticulation-trimmed subnetworks with respect to a given F are either unique, or do not exist. This allows us to enumerate in reasonable time. Lemma 4. Let N be a network and let F ⊆ ER(N ). Then there does not exist two non-strongly isomorphic reticulation-trimmed subnetworks of N with respect to F. For proof of Lemma 4, see Appendix. For an example, given a network N , of an F ⊆ ER(N ) that does not admit a reticulation-trimmed subnetwork of N , consider N with 2 reticulations, r1, r2 such that r1 ∈ reach−(r2). Choosing F = {(p1, r1)}, for p1 chosen...