pith. sign in

arxiv: 2606.24415 · v1 · pith:VJOLHWDTnew · submitted 2026-06-23 · 💻 cs.DM · q-bio.PE

Novel Triple-Based Problems for the Construction of Phylogenetic Networks via Least Common Ancestors

Patricia A. Ebert , Anna Lindeberg , Marc Hellmuth This is my paper

Pith reviewed 2026-06-25 21:33 UTC · model grok-4.3

classification 💻 cs.DM q-bio.PE
keywords phylogenetic networksrooted triplesanchored triplesleast common ancestorconsistency problemspolynomial timedirected acyclic graphsevolutionary networks
0
0 comments X

The pith

Phylogenetic networks can realize consistent sets of rooted and anchored triples under an LCA interpretation, with the realizing network constructible in polynomial time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that consistency problems for ordinary rooted triples and anchored triples in phylogenetic networks, including versions with forbidden triples, reduce to realization problems for required and forbidden least common ancestor constraints. These problems are all solvable in polynomial time, and a suitable directed acyclic graph together with a phylogenetic network can be built within the same bound whenever a solution exists. A reader would care because such triples encode local information about evolutionary closeness that can be extracted from genomic sequences, so an efficient construction method supports building network models of evolutionary history from incomplete data. The ancestor-based definition handles the fact that networks allow asymmetric ancestral relationships unlike trees.

Core claim

By translating the consistency questions for ordinary and anchored triples into realization problems for required and forbidden LCA-constraints, we show that all resulting problems can be solved in polynomial time. Moreover, whenever a solution exists, a suitable realizing DAG and phylogenetic network can be constructed within the same time bound.

What carries the argument

The reduction of triple consistency questions (with and without forbidden triples) to realization problems for required and forbidden LCA-constraints.

If this is right

  • All variants of the consistency problems for triples and anchored triples are solvable in polynomial time.
  • A realizing directed acyclic graph exists and can be constructed in polynomial time when the constraints are consistent.
  • A phylogenetic network realizing the constraints can be constructed in polynomial time when a solution exists.
  • The same polynomial-time bound holds whether or not forbidden triples are present.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach may extend to consistency problems involving other local constraints on ancestral relationships in networks.
  • It suggests that local LCA information extracted from sequences is often sufficient to determine global network structure under these definitions.
  • Similar reductions might apply to network inference tasks that incorporate additional data types beyond triples.

Load-bearing premise

The ancestor-based interpretation of triples and the anchored relaxation accurately model the biological information inferable from genomic sequences about relative evolutionary proximity.

What would settle it

An input set of triples (ordinary or anchored, with or without forbidden triples) for which the polynomial-time algorithm outputs a DAG or network that fails to display the required LCA relationships as defined in the paper.

Figures

Figures reproduced from arXiv: 2606.24415 by Anna Lindeberg, Marc Hellmuth, Patricia A. Ebert.

Figure 1
Figure 1. Figure 1: Shown are four networks 𝑇, 𝑁1, 𝑁2, and 𝑁3 with leaf set 𝑋 = {𝑎, 𝑏, 𝑐}. The phylogenetic tree 𝑇 displays and topologically-displays the triple 𝑎𝑏|𝑐. All three networks 𝑁1, 𝑁2, and 𝑁3 topologically-display the triple 𝑎𝑏|𝑐 according to (T2) (highlighted by the shaded red arcs) but do not display the triple 𝑎𝑏|𝑐 according to (T1). In 𝑁1, we have lca𝑁1 (𝑏𝑐) ≺𝑁1 lca𝑁1 (𝑎𝑏) = lca𝑁1 (𝑎𝑐). Hence, instead of 𝑎𝑏|𝑐, 𝑁… view at source ↗
Figure 2
Figure 2. Figure 2: Shown are two networks 𝑁1 and 𝑁2 with leaf set {𝑥, 𝑦, 𝑧}. Both ï-display 𝑥𝑦|𝑧 since lca𝑁1 (𝑥𝑦) = 𝑤 ≺𝑁1 𝑢 = lca𝑁1 (𝑥𝑧) and lca𝑁2 (𝑥𝑦) = 𝑢 ≺𝑁2 𝑟 = lca𝑁2 (𝑥𝑧). In 𝑁1, the leaves 𝑦 and 𝑧 have two distinct least common ancestors, namely 𝑢 and 𝑣. In 𝑁2, 𝑣 = lca𝑁2 (𝑦𝑧) is the unique least common ancestor of 𝑦 and 𝑧, but 𝑣 is not an ancestor of 𝑢 = lca𝑁2 (𝑥𝑦). Therefore, neither 𝑁1 nor 𝑁2 ï-displays 𝑦𝑥|𝑧. In parti… view at source ↗
Figure 3
Figure 3. Figure 3: Consider the pair (R, F ) of anchored triple sets with R = {𝑐𝑏|𝑎, 𝑐𝑏|𝑑} and F = {𝑏𝑐|𝑎}. Then 𝑅 = {(𝑏𝑐, 𝑎𝑐), (𝑏𝑐, 𝑐𝑑)} and 𝐹 = {(𝑏𝑐, 𝑎𝑏)} are the relations on P2 (𝑋R,F) with 𝑋R,F = {𝑎, 𝑏, 𝑐, 𝑑} as defined in Theorem 4.2. For 𝑆 ∈ {𝑅, cl𝐹 (𝑅)}, an arc 𝑝 → 𝑞 is drawn precisely if (𝑞, 𝑝) ∈ 𝑆. Then, G𝑅,𝐹 is the canonical DAG of (𝑅, 𝐹) and 𝐺 is the 𝐹|𝑅-extension of G𝑅,𝐹, obtained by applying an 𝑎𝑏-extension for t… view at source ↗
Figure 4
Figure 4. Figure 4: Consider the pair (R, F ) of triple sets with R = {𝑎𝑏|𝑥, 𝑏𝑐|𝑥, 𝑐𝑑|𝑎} and F = {𝑎𝑐|𝑥, 𝑎𝑏|𝑑}. Then F| R = {𝑎𝑐|𝑥} and the DAG 𝐺 agrees with (R, F| R) but does not agree with (R, F ), since 𝑎𝑏|𝑑 is displayed. In accordance with Proposition 5.8, the F| R-extension 𝐺 ′ of 𝐺 agrees with (R, F ). The next result shows that, for the purpose of deciding whether a DAG exists that agrees with (R, F ), it suffices to co… view at source ↗
Figure 5
Figure 5. Figure 5: Consider the pair (R, F ) of triple sets with R = {𝑎𝑏|𝑥, 𝑏𝑐|𝑥, 𝑐𝑑|𝑎} and F = {𝑎𝑐|𝑥, 𝑎𝑏|𝑑}. Let 𝑄0 = cl(𝑅R) whose canonical DAG G𝑄0 is shown in the middle. Here, 𝑄0| ≠ 𝑎𝑐𝑥 = 𝑅 ext 𝑎𝑐| 𝑥 = {(𝑎𝑐, 𝑎𝑥), (𝑎𝑐, 𝑐𝑥), (𝑎𝑥, 𝑐𝑥), (𝑐𝑥, 𝑎𝑥)} and, in particular, G𝑄0 displays the triple 𝑎𝑐|𝑥 ∈ F. In this case, we apply a saturation of 𝑄0 by adding first the elements (𝑎𝑥, 𝑎𝑐) and (𝑐𝑥, 𝑎𝑐) and then computing the closure whi… view at source ↗
Figure 6
Figure 6. Figure 6: Consider the pair (R, F ) of triple sets with R = {𝑎𝑏|𝑥, 𝑏𝑐|𝑥, 𝑐𝑑|𝑎} and F = {𝑎𝑐|𝑥, 𝑎𝑏|𝑑}. Let 𝑄1 be the final relation computed during the unique run of Sat(𝑅R, F), illustrated in [PITH_FULL_IMAGE:figures/full_fig_p020_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Consider the pair (R, F ) of anchored triple sets with R = {𝑐𝑏|𝑎, 𝑐𝑏|𝑑} and F = {𝑏𝑐|𝑎} as in [PITH_FULL_IMAGE:figures/full_fig_p023_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Consider the pair (R, F ) of anchored triple sets with R = {𝑏𝑐|𝑑, 𝑏𝑑|𝑎, 𝑐𝑏|𝑎} and F = {𝑐𝑑|𝑎} and let W = at-suppF = {𝑐𝑑, 𝑎𝑐}. Define 𝑅 = {(𝑏𝑐, 𝑏𝑑), (𝑏𝑑, 𝑎𝑏), (𝑏𝑐, 𝑎𝑐)}, 𝑅 ′ = 𝑅 ∪ {(𝑐𝑑, 𝑐𝑑), (𝑎𝑐, 𝑎𝑐)}, and 𝐹 = {(𝑐𝑑, 𝑎𝑐)} as relations on P2 (𝑋R,F). Shown are the canonical DAG G𝑅,𝐹, its 𝐹|𝑅-extension 𝐺, and the canonical DAG G𝑅′ ,𝐹, where the latter coincides with its 𝐹|𝑅-extension. Here, 𝐺 ï-agrees with (R, … view at source ↗
read the original abstract

Evolutionary histories are often represented by rooted phylogenetic networks, whose leaves correspond to extant taxa and whose internal vertices represent ancestral lineages. Since such histories must usually be inferred from incomplete data, in particular from genomic sequences of present-day taxa, one often obtains only local information about relative evolutionary proximity. For instance, sequence data may suggest that two taxa $x$ and $y$ are more closely related to each other than either is to a third taxon $z$. This information is classically encoded by a rooted triple $xy|z$. In this paper, we study rooted triples in phylogenetic networks under an ancestor-based interpretation: $xy|z$ is displayed if the unique least common ancestor (LCA) of $x$ and $y$ lies strictly below the unique LCA of $x$ and $z$, respectively of $y$ and $z$, and the latter two LCAs coincide. We also introduce anchored triples $\underline{x}y|z$, which retain only the asymmetric comparison that the LCA of $x$ and $y$ lies below the LCA of $x$ and $z$. This relaxation is natural in networks, where different pairwise ancestral relationships need not behave as they do in trees. We consider several variants of consistency problems for ordinary and anchored triples, both with and without forbidden triples. Somewhat surprisingly, these ancestor-based consistency questions for triples in phylogenetic networks do not appear to have been addressed before despite their direct biological interpretation and the fact that such constraints can be inferred naturally from genomic sequence data. By translating these questions into realization problems for required and forbidden LCA-constraints, we show that all resulting problems can be solved in polynomial time. Moreover, whenever a solution exists, a suitable realizing DAG and phylogenetic network can be constructed within the same time bound.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper defines an ancestor-based display condition for rooted triples xy|z (and anchored variants) in phylogenetic networks, requiring unique LCAs with the LCA of x,y strictly below the coinciding LCAs of the other pairs. It studies consistency problems for sets of such triples (with and without forbidden triples) and claims that all variants are solvable in polynomial time by translation to required/forbidden LCA-constraint realization problems on DAGs; moreover, a realizing phylogenetic network can be constructed in the same time bound whenever a solution exists.

Significance. If the reduction is valid, the results supply the first polynomial-time algorithms and constructions for these local, biologically interpretable constraints on networks (as opposed to trees), addressing a previously unstudied class of problems with direct applicability to inference from genomic data.

major comments (1)
  1. [Abstract] Abstract (and the definition of triple display): the ancestor-based condition explicitly requires that LCAs are unique for the relevant leaf pairs. However, the claimed polynomial-time reduction to general LCA-constraint realization on DAGs does not appear to guarantee uniqueness of LCAs in the output networks (especially when reticulations are present). This raises a question about whether the equivalence between triple consistency and constraint satisfaction holds in both directions, which is load-bearing for the polynomial-time claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for highlighting this important point about the uniqueness of LCAs. We address the comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (and the definition of triple display): the ancestor-based condition explicitly requires that LCAs are unique for the relevant leaf pairs. However, the claimed polynomial-time reduction to general LCA-constraint realization on DAGs does not appear to guarantee uniqueness of LCAs in the output networks (especially when reticulations are present). This raises a question about whether the equivalence between triple consistency and constraint satisfaction holds in both directions, which is load-bearing for the polynomial-time claim.

    Authors: The definition in the manuscript does require unique LCAs, as the referee correctly notes. Our reduction translates the ancestor-based (and anchored) triple conditions into a collection of required and forbidden LCA constraints on a DAG; these constraints are formulated so that any realizing DAG must contain, for each constrained triple, a single vertex that serves as the unique LCA satisfying the stated ancestor relations (equality of the two higher LCAs and strict descent of the lower one). The known polynomial-time algorithm for LCA-constraint realization constructs precisely such a minimal DAG, in which the constrained pairs have unique LCAs by construction of the partial order on ancestor vertices. Reticulations are permitted but do not create additional minimal common ancestors for the constrained pairs because the equality and descent constraints force a unique meeting point. We will revise the manuscript to add an explicit paragraph clarifying this direction of the equivalence and confirming that the output networks satisfy the uniqueness requirement in the original definition. revision: yes

Circularity Check

0 steps flagged

No circularity; algorithmic translation and poly-time claims are independent of inputs

full rationale

The paper defines ancestor-based and anchored triple display via unique-LCA predicates, translates consistency questions into LCA-constraint realization problems, and asserts polynomial-time solvability plus explicit DAG/network construction. No fitted parameters, no self-referential definitions (the display predicate is stated directly, not derived from the output networks), and no load-bearing self-citations. The derivation consists of standard reduction to a constraint-realization task whose complexity is established separately; the result does not reduce to its own inputs by construction. The skeptic concern about uniqueness of LCAs in the output networks is a potential soundness issue for the equivalence, not a circularity in the derivation chain itself.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard graph-theoretic properties of least common ancestors in rooted DAGs and existing phylogenetic network definitions; no free parameters or new invented entities are introduced.

axioms (1)
  • standard math Least common ancestors exist and are unique for pairs of leaves in the considered rooted phylogenetic networks.
    The triple definitions and consistency problems are built directly on this property of LCAs in DAGs.

pith-pipeline@v0.9.1-grok · 5864 in / 1254 out tokens · 29002 ms · 2026-06-25T21:33:47.301229+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

38 extracted references · 32 canonical work pages

  1. [1]

    SIAM Journal on Computing 10(3):405–421, DOI 10.1137/0210030 29

    Aho A V, Sagiv Y, Szymanski TG, Ullman JD (1981) Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM Journal on Computing 10(3):405–421, DOI 10.1137/0210030 29

    work page doi:10.1137/0210030 1981

  2. [2]

    Springer Monographs in Mathematics, Springer

    Bang-Jensen J, Gutin GZ (2009) Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer Monographs in Mathematics, Springer

    2009

  3. [3]

    theory and methods in phylogenetic analysis

    Bryant D (1997) Building trees, hunting for trees, and comparing trees. theory and methods in phylogenetic analysis. PhD thesis, University of Canterbury, DOI 10.26021/2479

    work page doi:10.26021/2479 1997

  4. [4]

    Stanley , abstract =

    Bryant D, Steel M (1995) Extension operations on sets of leaf-labeled trees. Adv Appl Math 16(4):425–453, DOI 10.1006/aama.1995.1020

    work page doi:10.1006/aama.1995.1020 1995

  5. [5]

    Discrete Applied Mathematics 127(2):241–269, DOI 10.1016/S0166-218X(02) 00209-3

    Caspard N, Monjardet B (2003) The lattices of closure systems, closure operators, and implicational systems on a finite set: a survey. Discrete Applied Mathematics 127(2):241–269, DOI 10.1016/S0166-218X(02) 00209-3

    work page doi:10.1016/s0166-218x(02 2003

  6. [6]

    MIT press

    Cormen TH, Leiserson CE, Rivest RL, Stein C (2022) Introduction to Algorithms. MIT press

    2022

  7. [7]

    URLhttps://arxiv.org/abs/2605.03827,2605.03827

    Ebert PA, Hellmuth M (2026) Inferring phylogenetic networks from required and forbidden LCA- constraints. URLhttps://arxiv.org/abs/2605.03827,2605.03827

    Pith/arXiv arXiv 2026

  8. [8]

    Journal of Mathematical Biology 74(7):1729–1751, DOI 10.1007/s00285-016-1068-3

    Gambette P, Huber KT, Kelk S (2017) On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters. Journal of Mathematical Biology 74(7):1729–1751, DOI 10.1007/s00285-016-1068-3

    work page doi:10.1007/s00285-016-1068-3 2017

  9. [9]

    Journal of Mathematical Biology 78(7):2015– 2057, DOI 10.1007/s00285-019-01332-9

    Geiß M, Ch ´avez E, Gonz ´alez Laffitte M, L ´opez S ´anchez A, Stadler BMR, Valdivia DI, Hellmuth M, Hern´andez Rosales M, Stadler PF (2019) Best match graphs. Journal of Mathematical Biology 78(7):2015– 2057, DOI 10.1007/s00285-019-01332-9

    work page doi:10.1007/s00285-019-01332-9 2019

  10. [10]

    Journal of Mathematical Biology 80(3):865–953, DOI 10.1007/s00285-019-01444-2

    Geiß M, Stadler PF, Hellmuth M (2020) Reciprocal best match graphs. Journal of Mathematical Biology 80(3):865–953, DOI 10.1007/s00285-019-01444-2

    work page doi:10.1007/s00285-019-01444-2 2020

  11. [11]

    IEEE/ACM Transactions on Computational Biology and Bioinformatics 10(1):151– 160, DOI 10.1109/TCBB.2013.8

    Gr¨ unewald S, Spillner A, Bastkowski S, Bogershausen A, Moulton V (2013) Superq: Computing supernet- works from quartets. IEEE/ACM Transactions on Computational Biology and Bioinformatics 10(1):151– 160, DOI 10.1109/TCBB.2013.8

    work page doi:10.1109/tcbb.2013.8 2013

  12. [12]

    Journal of Bioinformatics and Computational Biology 04(01):59–74, DOI 10.1142/S0219720006001709

    He YJ, Huynh TND, Jansson J, Sung WK (2006) Inferring phylogenetic relationships avoiding for- bidden rooted triplets. Journal of Bioinformatics and Computational Biology 04(01):59–74, DOI 10.1142/S0219720006001709

    work page doi:10.1142/s0219720006001709 2006

  13. [13]

    URLhttps://arxiv.org/abs/2606.16963,2606.16963

    Hellmuth M, Lindeberg A, Moulton V (2026) Encoding phylogenetic networks with least common ancestor constraints. URLhttps://arxiv.org/abs/2606.16963,2606.16963

    arXiv 2026

  14. [14]

    Algorithmica 66(3):714–738, DOI 10.1007/s00453-012-9659-x

    Huber KT, Moulton V (2013) Encoding and constructing 1-nested phylogenetic networks with trinets. Algorithmica 66(3):714–738, DOI 10.1007/s00453-012-9659-x

    work page doi:10.1007/s00453-012-9659-x 2013

  15. [15]

    IEEE/ACM Transactions on Computational Biology and Bioinformatics 8(3):635– 649, DOI 10.1109/TCBB.2010.17

    Huber KT, van Iersel L, Kelk S, Suchecki R (2011) A practical algorithm for reconstructing level-1 phylogenetic networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics 8(3):635– 649, DOI 10.1109/TCBB.2010.17

    work page doi:10.1109/tcbb.2010.17 2011

  16. [16]

    Algorithmica 77(1):173–200, DOI 10.1007/s00453-015-0069-8

    Huber KT, van Iersel L, Moulton V, Scornavacca C, Wu T (2017) Reconstructing phylogenetic level-1 net- works from nondense binet and trinet sets. Algorithmica 77(1):173–200, DOI 10.1007/s00453-015-0069-8

    work page doi:10.1007/s00453-015-0069-8 2017

  17. [17]

    IEEE/ACM Transactions on Computational Biology and Bioinformatics 1(4):151–158, DOI 10.1109/TCBB.2004.44

    Huson D, Dezulian T, Klopper T, Steel M (2004) Phylogenetic super-networks from partial trees. IEEE/ACM Transactions on Computational Biology and Bioinformatics 1(4):151–158, DOI 10.1109/TCBB.2004.44

    work page doi:10.1109/tcbb.2004.44 2004

  18. [18]

    Genome Biol Evol 3:23–35, DOI 10.1093/gbe/evq077

    Huson DH, Scornavacca C (2011) A survey of combinatorial methods for phylogenetic networks. Genome Biol Evol 3:23–35, DOI 10.1093/gbe/evq077

    work page doi:10.1093/gbe/evq077 2011

  19. [19]

    In: Jonassen I, Kim J (eds) Algorithms in Bioinformatics, Springer Berlin Heidelberg, Berlin, Heidelberg, pp 388–399, DOI 10.1007/978-3-540-30219-3 33

    Huson DH, Dezulian T, Kl ¨opper T, Steel MA (2004) Phylogenetic super-networks from partial trees. In: Jonassen I, Kim J (eds) Algorithms in Bioinformatics, Springer Berlin Heidelberg, Berlin, Heidelberg, pp 388–399, DOI 10.1007/978-3-540-30219-3 33

    work page doi:10.1007/978-3-540-30219-3 2004

  20. [20]

    Cambridge University Press

    Huson DH, Rupp R, Scornavacca C (2011) Phylogenetic Networks: Concepts, Algorithms and Applications. Cambridge University Press

    2011

  21. [21]

    Algo- rithmica 60(2):207–235, DOI 10.1007/s00453-009-9333-0 30

    van Iersel L, Kelk S (2011) Constructing the simplest possible phylogenetic network from triplets. Algo- rithmica 60(2):207–235, DOI 10.1007/s00453-009-9333-0 30

    work page doi:10.1007/s00453-009-9333-0 2011

  22. [22]

    Journal of Mathematical Biology 68(7):1707–1729, DOI 10.1007/s00285-013-0683-5

    van Iersel L, Moulton V (2014) Trinets encode tree-child and level-2 phylogenetic networks. Journal of Mathematical Biology 68(7):1707–1729, DOI 10.1007/s00285-013-0683-5

    work page doi:10.1007/s00285-013-0683-5 2014

  23. [23]

    IEEE/ACM Transactions on Computational Biology and Bioinformatics 6(4):667– 681, DOI 10.1109/TCBB.2009.22

    van Iersel L, Keijsper J, Kelk S, Stougie L, Hagen F, Boekhout T (2009) Constructing level-2 phylogenetic networks from triplets. IEEE/ACM Transactions on Computational Biology and Bioinformatics 6(4):667– 681, DOI 10.1109/TCBB.2009.22

    work page doi:10.1109/tcbb.2009.22 2009

  24. [24]

    Journal of Bioinformatics and Computational Biology 07(04):597–623, DOI 10.1142/S0219720009004308

    van Iersel L, Kelk S, Mnich M (2009) Uniqueness, intractability and exact algorithms: Reflections on level-k phylogenetic networks. Journal of Bioinformatics and Computational Biology 07(04):597–623, DOI 10.1142/S0219720009004308

    work page doi:10.1142/s0219720009004308 2009

  25. [25]

    Information Processing Letters 178:106300, DOI 10.1016/j.ipl.2022.106300

    van Iersel L, Kole S, Moulton V, Nipius L (2022) An algorithm for reconstructing level-2 phylogenetic networks from trinets. Information Processing Letters 178:106300, DOI 10.1016/j.ipl.2022.106300

    work page doi:10.1016/j.ipl.2022.106300 2022

  26. [26]

    Theoretical Computer Science 363(1):60–68, DOI 10.1016/j.tcs.2006.06.022, computing and Combina- torics

    Jansson J, Sung WK (2006) Inferring a level-1 phylogenetic network from a dense set of rooted triplets. Theoretical Computer Science 363(1):60–68, DOI 10.1016/j.tcs.2006.06.022, computing and Combina- torics

    work page doi:10.1016/j.tcs.2006.06.022 2006

  27. [27]

    SIAM Journal on Computing 35(5):1098–1121, DOI 10.1137/S0097539704446529

    Jansson J, Nguyen NB, Sung WK (2006) Algorithms for combining rooted triplets into a galled phylogenetic network. SIAM Journal on Computing 35(5):1098–1121, DOI 10.1137/S0097539704446529

    work page doi:10.1137/s0097539704446529 2006

  28. [28]

    In: Arge L, Hoffmann M, Welzl E (eds) Algorithms – ESA 2007, Springer Berlin Heidelberg, pp 265–274, DOI 10.1007/978-3-540-75520-3 25

    Kowaluk M, Lingas A (2007) Unique lowest common ancestors in dags are almost as easy as matrix multiplication. In: Arge L, Hoffmann M, Welzl E (eds) Algorithms – ESA 2007, Springer Berlin Heidelberg, pp 265–274, DOI 10.1007/978-3-540-75520-3 25

    work page doi:10.1007/978-3-540-75520-3 2007

  29. [29]

    Bull Math Biol 87(3):44, DOI 10.1007/s11538-025-01419-z

    Lindeberg A, Hellmuth M (2025) Simplifying and characterizing DAGs and phylogenetic networks via least common ancestor constraints. Bull Math Biol 87(3):44, DOI 10.1007/s11538-025-01419-z

    work page doi:10.1007/s11538-025-01419-z 2025

  30. [30]

    Displaying trees across two phylogenetic networks

    Lindeberg A, Alfonsson A, Moulton V, Scholz GE, Hellmuth M (2026) Inferring DAGs and phylogenetic networks from least common ancestors. Theoretical Computer Science 1082:116114, DOI 10.1016/j.tcs. 2026.116114

    work page doi:10.1016/j.tcs 2026

  31. [31]

    Oxford University Press

    Matou ˇsek J, Neˇsetˇril J (2009) Invitation to discrete mathematics. Oxford University Press

    2009

  32. [32]

    Discrete Applied Mathematics 98(3):227–235, DOI 10.1016/S0166-218X(99)00160-2

    Ng MP, Steel M, Wormald NC (2000) The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees. Discrete Applied Mathematics 98(3):227–235, DOI 10.1016/S0166-218X(99)00160-2

    work page doi:10.1016/s0166-218x(99)00160-2 2000

  33. [33]

    PLOS ONE 9(9):1–1, DOI 10.1371/journal.pone.0106531

    Poormohammadi H, Eslahchi C, Tusserkani R (2014) Tripnet: A method for constructing rooted phyloge- netic networks from rooted triplets. PLOS ONE 9(9):1–1, DOI 10.1371/journal.pone.0106531

    work page doi:10.1371/journal.pone.0106531 2014

  34. [34]

    Theoretical Computer Science 865:63–84, DOI 10.1016/j.tcs.2021.02.037

    Schaller D, Stadler PF, Hellmuth M (2021) Complexity of modification problems for best match graphs. Theoretical Computer Science 865:63–84, DOI 10.1016/j.tcs.2021.02.037

    work page doi:10.1016/j.tcs.2021.02.037 2021

  35. [35]

    Birkh¨auser Boston, DOI 10.1007/978-1-4612-0053-6

    Schr ¨oder BSW (2003) Ordered Sets. Birkh¨auser Boston, DOI 10.1007/978-1-4612-0053-6

    work page doi:10.1007/978-1-4612-0053-6 2003

  36. [36]

    European Journal of Combinatorics 70:384–407, DOI 10.1016/j.ejc.2018.02.013

    Seemann CR, Hellmuth M (2018) The matroid structure of representative triple sets and triple-closure computation. European Journal of Combinatorics 70:384–407, DOI 10.1016/j.ejc.2018.02.013

    work page doi:10.1016/j.ejc.2018.02.013 2018

  37. [37]

    Journal of Mathematical Biology 83(3):28, DOI 10.1007/s00285-021-01654-7

    Semple C, Toft G (2021) Trinets encode orchard phylogenetic networks. Journal of Mathematical Biology 83(3):28, DOI 10.1007/s00285-021-01654-7

    work page doi:10.1007/s00285-021-01654-7 2021

  38. [38]

    IEEE/ACM Transactions on Computational Biology and Bioinformatics 8(3):785–796, DOI 10.1109/TCBB.2010.69 31

    Willson SJ (2011) Regular networks can be uniquely constructed from their trees. IEEE/ACM Transactions on Computational Biology and Bioinformatics 8(3):785–796, DOI 10.1109/TCBB.2010.69 31

    work page doi:10.1109/tcbb.2010.69 2011