arxiv: 2605.03827 · v2 · submitted 2026-05-05 · 💻 cs.DM · q-bio.PE

Recognition: no theorem link

Inferring Phylogenetic Networks from Required and Forbidden LCA-Constraints

Patricia A. Ebert , Marc Hellmuth

Authors on Pith no claims yet

Pith reviewed 2026-05-12 03:06 UTC · model grok-4.3

classification 💻 cs.DM q-bio.PE

keywords phylogenetic networksLCA constraintsrequired constraintsforbidden constraintsrealization problempolynomial-time algorithmsnetwork inferenceevolutionary reticulation

0 comments

The pith

Exact characterizations determine when phylogenetic networks realize required LCA constraints while avoiding forbidden ones under three avoidance variants, and these yield polynomial-time decision and construction algorithms.

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

The paper determines the precise conditions under which a phylogenetic network can satisfy a given collection of required least common ancestor relations between taxa while also respecting a collection of forbidden relations. It examines three natural interpretations of what avoidance of a forbidden constraint means. For each interpretation the authors supply a complete characterization of the compatible pairs of required and forbidden constraint sets. These characterizations immediately produce polynomial-time procedures that decide existence and construct a suitable network when one is possible. The extension matters because it incorporates negative prior knowledge about non-ancestral pairs into network reconstruction for histories that include reticulation events such as hybridization.

Core claim

For each of three formalizations of avoiding a forbidden LCA constraint, there exists an exact characterization of the sets R of required constraints and F of forbidden constraints such that a phylogenetic network realizing all of R while avoiding all of F exists. These characterizations immediately yield polynomial-time algorithms that decide the existence of such a network and output one whenever it does.

What carries the argument

The three variants of avoidance for forbidden LCA-constraints together with the exact realizability characterizations for pairs (R, F) of required and forbidden constraints.

If this is right

Polynomial-time decision procedures exist for each of the three avoidance variants.
Whenever a suitable network exists, it can be constructed in polynomial time.
The framework extends the earlier realization problem that considered required constraints alone.
Researchers can now test consistency of a candidate network with both positive and negative ancestral information in a single procedure.

Where Pith is reading between the lines

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

The decision procedures could be combined with other forms of phylogenetic data such as gene-tree topologies to produce more constrained network reconstructions.
Biologists could apply the algorithms to validate or reject proposed networks against accumulated prior knowledge about forbidden ancestral relationships.
The characterizations may expose structural features of networks that are forced specifically by the interplay between required and forbidden constraints.

Load-bearing premise

The three chosen formalizations of avoiding a forbidden LCA constraint are the natural and complete ways to interpret avoidance, and the characterizations rest on standard definitions of phylogenetic networks and LCA relations on a fixed set of taxa.

What would settle it

A concrete instance consisting of sets R and F for which the polynomial-time algorithm returns a network that fails to realize some member of R or fails to avoid some member of F, or returns no network when at least one valid network actually exists.

Figures

Figures reproduced from arXiv: 2605.03827 by Marc Hellmuth, Patricia A. Ebert.

**Figure 1.** Figure 1: On the left, we give a graphical representation of the relations R = {(xy,xz),(xx,yz)} and F = {(xz,xy)} on P2(X) with X = {x,y,z}. Here we draw a solid (resp. dashed) arc p → q precisely if (q, p) ∈ R (resp. (q, p) ∈ F). In addition, the graphical representation of clF (R) is provided where arcs (p, p) are omitted for all p ∈ suppclF (R) . Furthermore, the canonical DAG GR,F which AF-realizes (R,F) is sho… view at source ↗

**Figure 2.** Figure 2: Shown is the graphical representation of cl/0(R) and clF (R) for the relations R = {(xy,xz),(yy, yz)} and F = {(yz,xz)}. Here we draw an arc p → q precisely if (q, p) ∈ cl but omitted arcs of the form (p, p), cl ∈ {cl/0(R), clF (R)}. In addition, the canonical DAGs GR,/0 and GR,F are shown. Here, GR,/0 AF-realizes (R, /0) but not (R,F). Moreover, GR,F AF-realizes (R,F), see Example 2 for further details. E… view at source ↗

**Figure 2.** Figure 2: On the left, we give a graphical representation of the relations R = {(xy,xz),(xx,yz)} and F = {(xz,xy)} on P2(X) with X = {x,y,z}. Here we draw a solid (resp. dashed) arc p → q precisely if (q, p) ∈ R (resp. (q, p) ∈ F). In addition, the graphical representation of clF(R) is provided where arcs (p, p) are omitted for all p ∈ suppclF (R) . Furthermore, the canonical DAG GR,F which RF-realizes (R,F) is show… view at source ↗

**Figure 3.** Figure 3: Shown is the canonical DAG GR,F of the two relations R = {(xy,ab)} and F = {(xy,ay)} on P2(X) with X = {a,b,x,y} and its F|R-extension G. While GR,F AF-realizes (R,F|R) = (R, /0) it does not AF-realize (R,F) which, in turn, is AF-realized by G, see Example 3 for more details. In addition, the network N obtained from G is shown. Algorithm 1 [STRICT] AF-REALIZABILITY Input: A pair (R,F) of relations on P2(X)… view at source ↗

**Figure 4.** Figure 4: Shown are clF (R), clF (R lca), and the F|R-extension G of GR,F for the relations R = {(xy,ab)} and F = {(xy,ay),(ay,ab)} on P2(X) with X = {a,b,x, y}. Here we draw an arc p → q precisely if (q, p) ∈ clF but omitted arcs of the form (p, p), clF ∈ {clF (R),clF (R lca)}. While G AF-realizes (R,F), the pair (R,F) is not AFlca-realizable, see Example 4 for more details. Additionally, it is easy to verify that … view at source ↗

**Figure 4.** Figure 4: Shown is the closure clF(R) as constructed in [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗

**Figure 5.** Figure 5: Shown is the canonical DAG GR,F of the two relations R = {(xy,ab)} and F = {(xy,ay)} on P2(X) with X = {a,b,x, y} and its F|R-extension G. While GR,F RF-realizes (R,F|R) = (R, /0), it does not RF-realize (R,F) which, in turn, is RF-realized by G, see Example 4 for more details. In addition, the network N obtained from G is shown. Algorithm 1 [STRICT] RF-REALIZABILITY Input: A pair (R,F) of relations on P2(… view at source ↗

**Figure 6.** Figure 6: Shown are clF(R), clF(R lca), and the F|R-extension G of GR,F for the relations R = {(xy,ab)}, R lca = {(xy,ab),(ay,ay)} and F = {(xy,ay),(ay,ab)} on P2(X) with X = {a,b,x,y}. Here we draw an arc p → q precisely if (q, p) ∈ clF but omitted arcs of the form (p, p), clF ∈ {clF(R),clF(R lca)}. While G RFrealizes (R,F), the pair (R,F) is not RFlca-realizable, see Example 5 for more details. of those constrain… view at source ↗

read the original abstract

Phylogenetic networks provide a framework for representing evolutionary histories involving reticulate events such as hybridization or horizontal gene transfer. A central problem is to infer such networks from local structural information. In this paper, we study network inference from least common ancestor (LCA) constraints, which specify relative ancestral relationships between pairs of taxa. While previous work has characterized when a set of required LCA constraints can be realized by a phylogenetic network, practical applications may also involve constraints that must be explicitly avoided, for example due to biological prior knowledge. We therefore consider the realization problem for pairs $(R,F)$, where $R$ is a set of required LCA-constraints and $F$ is a set of forbidden ones. Since there are several natural ways to formalize what it means for a network to avoid a forbidden LCA-constraint, we study three such variants. For each of them, we characterize exactly when there exists a phylogenetic network that realizes all constraints in $R$ while avoiding all constraints in $F$ in the respective sense. Based on these characterizations, we derive polynomial-time algorithms that decide the existence of such networks and construct one whenever it exists.

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.

Desk Editor's Note private letter to a colleague

This extends required LCA constraint realization to forbidden ones via three avoidance variants plus claimed poly-time decision and construction algorithms.

read the letter

The core advance is taking the prior characterizations of networks that realize a set of required LCA constraints and adding forbidden constraints, formalized in three distinct ways. For each variant the paper states exact conditions under which a network exists that satisfies all required constraints while avoiding the forbidden ones, then gives polynomial-time algorithms to decide existence and output a network when one exists. That combination of negative constraints and efficient algorithms is the practical step beyond the earlier required-only results. It directly addresses cases where biologists have prior knowledge that certain ancestral relations must not hold. The three avoidance interpretations look like a reasonable way to cover different possible meanings of “forbidden,” and the claim that the algorithms run in polynomial time would be useful if the characterizations are tight. Because only the abstract is available, the actual proofs and algorithm details cannot be inspected, so it is impossible to confirm that the characterizations are complete or that no hidden exponential steps slipped into the construction routines. The motivation for choosing exactly these three variants also remains unshown; one or two might turn out to be redundant or biologically less relevant once examples are examined. The work sits squarely in algorithmic phylogenetics. Readers who already know the required-LCA literature will see the extension immediately and can judge whether the new conditions are usable in their own pipelines. A specialist referee would be able to verify the combinatorial arguments and runtime claims in a few hours, so the paper is worth sending out for review rather than desk-rejecting. I would ask the authors to include at least one small worked example for each variant and a brief comparison of the three avoidance notions before final acceptance.

Referee Report

1 major / 0 minor

Summary. The paper studies the inference of phylogenetic networks from pairs of required LCA-constraints R and forbidden LCA-constraints F. It considers three natural formalizations of what it means for a network to avoid a forbidden constraint, claims exact characterizations of the pairs (R,F) that are realizable under each formalization, and derives polynomial-time algorithms that decide realizability and construct a realizing network when one exists.

Significance. If the characterizations and algorithms are correct, the work would extend prior results on required LCA-constraints to the practically relevant setting that also incorporates forbidden constraints arising from biological prior knowledge. Polynomial-time decision and construction procedures would provide efficient tools for network inference in computational phylogenetics.

major comments (1)

[Abstract] Abstract: the central claims assert exact characterizations of realizability together with polynomial-time algorithms, yet the manuscript consists solely of the abstract and supplies neither the definitions of the three avoidance variants, the statements of the characterizations, nor any proof sketches or algorithm descriptions. This prevents verification that the claimed results hold.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review and for highlighting the issue with the submitted manuscript. We address the major comment below and commit to a revision that supplies the missing content.

read point-by-point responses

Referee: [Abstract] Abstract: the central claims assert exact characterizations of realizability together with polynomial-time algorithms, yet the manuscript consists solely of the abstract and supplies neither the definitions of the three avoidance variants, the statements of the characterizations, nor any proof sketches or algorithm descriptions. This prevents verification that the claimed results hold.

Authors: We agree that the version provided for review contains only the abstract and therefore does not include the required definitions, formal statements of the three avoidance variants, characterizations, or algorithm descriptions. This prevents independent verification of the claims. The complete manuscript with all technical details is available on arXiv:2605.03827. We will submit the full paper as a revision so that the characterizations and polynomial-time algorithms can be properly evaluated. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The abstract presents a purely combinatorial characterization of realizability for pairs (R, F) of required and forbidden LCA constraints under three avoidance variants, together with polynomial-time decision and construction algorithms. No equations, fitted parameters, self-referential definitions, or load-bearing self-citations appear in the provided text. The claimed characterizations and algorithms are described as extensions of prior work on required constraints alone, but the abstract supplies no internal reduction of any new result to its own inputs by construction. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard domain assumptions from phylogenetic network theory and introduces no free parameters, new entities, or ad-hoc axioms beyond the problem formalization.

axioms (2)

domain assumption Phylogenetic networks are rooted directed acyclic graphs with leaves corresponding to the taxa and satisfying the usual degree and labeling conditions.
Invoked implicitly when defining realization of LCA constraints.
domain assumption LCA relations between pairs of taxa can be meaningfully required or forbidden and admit three distinct formal interpretations of avoidance.
Central to the problem statement and the three variants studied.

pith-pipeline@v0.9.0 · 5472 in / 1217 out tokens · 64979 ms · 2026-05-12T03:06:58.160629+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages · 1 internal anchor

[1]

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

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

work page doi:10.1137/0210030 1981
[2]

Springer Monographs in Mathematics, Springer

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

work page 2009
[3]

theory and methods in phyloge- netic analysis

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

work page doi:10.26021/2479 1997
[4]

Adv Appl Math 16(4):425– 453

Bryant D, Steel M (1995) Extension operations on sets of leaf-labelled trees. Adv Appl Math 16(4):425– 453

work page 1995
[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 implica- tional systems on a finite set: a survey. Discrete Applied Mathematics 127(2):241–269, DOI 10.1016/ S0166-218X(02)00209-3

work page 2003
[6]

MIT press

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

work page 2022
[7]

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 net- works from triplets and clusters. Journal of Mathematical Biology 74(7):1729–1751, DOI 10.1007/ s00285-016-1068-3

work page 2017
[8]

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
[9]

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
[10]

In: CSB ’03: Proceedings of the IEEE Computer Society Conference on Bioin- formatics, IEEE Computer Society, Washington DC, US, pp 363–374, DOI 10.1109/CSB.2003.1227337

Gusfield D, Eddhu S, Langley C (2003) Efficient reconstruction of phylogenetic networks with con- strained recombination. In: CSB ’03: Proceedings of the IEEE Computer Society Conference on Bioin- formatics, IEEE Computer Society, Washington DC, US, pp 363–374, DOI 10.1109/CSB.2003.1227337

work page doi:10.1109/csb.2003.1227337 2003
[11]

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
[12]

Journal of Mathematical Biology 66(1):399–420, DOI 10.1007/s00285-012-0525-x

Hellmuth M, Hernandez-Rosales M, Huber KT, Moulton V , Stadler PF, Wieseke N (2013) Orthology relations, symbolic ultrametrics, and cographs. Journal of Mathematical Biology 66(1):399–420, DOI 10.1007/s00285-012-0525-x

work page doi:10.1007/s00285-012-0525-x 2013
[13]

Proceedings of the National Academy of Sciences120(33) (2023) https://doi.org/10.1073/pnas

Hellmuth M, Wieseke N, Lechner M, Lenhof HP, Middendorf M, Stadler PF (2015) Phylogenomics with paralogs. Proceedings of the National Academy of Sciences 112(7):2058–2063, DOI 10.1073/pnas. 1412770112 20

work page doi:10.1073/pnas 2015
[14]

Theory in Biosciences 142(4):301–358, DOI 10.1007/s12064-023-00398-w

Hellmuth M, Schaller D, Stadler PF (2023) Clustering systems of phylogenetic networks. Theory in Biosciences 142(4):301–358, DOI 10.1007/s12064-023-00398-w

work page doi:10.1007/s12064-023-00398-w 2023
[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 phylo- genetic 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]

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

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

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

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
[18]

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 phylo- genetic 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
[19]

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
[20]

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
[21]

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 phyloge- netic network. SIAM Journal on Computing 35(5):1098–1121, DOI 10.1137/S0097539704446529

work page doi:10.1137/s0097539704446529 2006
[22]

Master’s thesis, University of Canterbury, DOI 10.26021/15536

Levy M (2024) Triplet matroids and closure in phylogenetics. Master’s thesis, University of Canterbury, DOI 10.26021/15536

work page doi:10.26021/15536 2024
[23]

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
[24]

Inferring DAGs and Phylogenetic Networks from Least Common Ancestors

Lindeberg A, Alfonsson A, Moulton V , Scholz GE, Hellmuth M (2025) Inferring dags and phy- logenetic networks from least common ancestors. URLhttps://arxiv.org/abs/2511.07965v2, 2511.07965v2

work page internal anchor Pith review Pith/arXiv arXiv 2025
[25]

Algorithms for Molecular Biology 20(1):19, DOI 10.1186/s13015-025-00285-7

Lindeberg A, Scholz GE, Wieseke N, Hellmuth M (2025) Orthology and near-cographs in the context of phylogenetic networks. Algorithms for Molecular Biology 20(1):19, DOI 10.1186/s13015-025-00285-7

work page doi:10.1186/s13015-025-00285-7 2025
[26]

Journal of Mathematical Biology 81(4):961–980, DOI 10.1007/s00285-020-01533-7

Linz S, Semple C (2020) Caterpillars on three and four leaves are sufficient to reconstruct binary normal networks. Journal of Mathematical Biology 81(4):961–980, DOI 10.1007/s00285-020-01533-7

work page doi:10.1007/s00285-020-01533-7 2020
[27]

Oxford University Press

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

work page 2009
[28]

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 phylo- genetic 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
[29]

Journal of Mathematical Biology 82(20), DOI 10.1007/ s00285-021-01564-8

Schaller D, Geiß M, Stadler PF, Hellmuth M (2021) Complete characterization of incorrect or- thology assignments in best match graphs. Journal of Mathematical Biology 82(20), DOI 10.1007/ s00285-021-01564-8

work page 2021
[30]

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
[31]

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
[32]

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
[33]

Bull Math Biol 72:340–358, DOI 10

Willson SJ (2010) Properties of normal phylogenetic networks. Bull Math Biol 72:340–358, DOI 10. 1007/s11538-009-9449-z 21

work page 2010