pith. sign in

arxiv: 2605.19962 · v1 · pith:6O3KGEPKnew · submitted 2026-05-19 · 🧬 q-bio.PE · cs.DM

Computing the Arc-Deletion Distance to Orchard Networks is NP-hard

Peng Li , Zhiwei Liu , Yangjing Long This is my paper

Pith reviewed 2026-05-20 03:38 UTC · model grok-4.3

classification 🧬 q-bio.PE cs.DM
keywords phylogenetic networksorchard networksarc-deletion distanceNP-hardnessDegree-3 Vertex Coverreticulate arcscomputational complexityphylogenetic transformations
0
0 comments X

The pith

Computing the arc-deletion distance to orchard networks is NP-hard.

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

The paper establishes that finding the smallest number of reticulate arcs to delete from a phylogenetic network in order to produce an orchard network is NP-hard. It reaches this conclusion by constructing a polynomial-time reduction from the Degree-3 Vertex Cover problem that exactly preserves the minimum cover size as the deletion distance. A reader would care because orchard networks possess useful structural properties that simplify many downstream analyses of evolutionary histories involving hybridization or gene transfer. Demonstrating intractability for this particular proximity measure adds to the broader picture of which network transformations admit efficient algorithms.

Core claim

We prove that computing the arc-deletion distance to orchard networks is NP-hard via a polynomial-time reduction from the Degree-3 Vertex Cover problem. Our result establishes the computational intractability of this proximity measure and contributes to the complexity theory of phylogenetic network transformations.

What carries the argument

A polynomial-time reduction from Degree-3 Vertex Cover instances to phylogenetic networks that maps minimum vertex-cover size exactly to the minimum number of reticulate arcs whose deletion yields an orchard network.

If this is right

  • No polynomial-time algorithm exists for the arc-deletion distance unless P equals NP.
  • The computational intractability of this proximity measure follows directly from the reduction.
  • The result adds to the known hardness landscape for transformations among subclasses of phylogenetic networks.

Where Pith is reading between the lines

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

  • Heuristic or approximation methods will likely be required in any practical software that measures closeness to orchard networks.
  • Analogous hardness proofs may apply to deletion distances toward other restricted network classes such as tree-child or galled networks.
  • Parameterized algorithms with respect to the number of reticulations or the target distance value remain worth exploring even if the general problem is hard.

Load-bearing premise

The constructed reduction preserves the exact numerical correspondence between vertex-cover size and arc-deletion distance while running in polynomial time and correctly identifying all reticulate arcs.

What would settle it

Discovery of a polynomial-time algorithm that computes the exact arc-deletion distance for arbitrary phylogenetic networks, or an explicit counterexample instance where the reduction maps a vertex cover of size k to a network whose true orchard distance differs from k.

Figures

Figures reproduced from arXiv: 2605.19962 by Peng Li, Yangjing Long, Zhiwei Liu.

Figure 1
Figure 1. Figure 1: (a) Phylogenetic network N1 with leaf set {x1, x2, . . . , x5}. {x1, x2} forms a cherry, while {x4, x5} forms a reticulated cherry; (b) Phylogenetic tree T1 with leaf set {x1, x2, . . . , x5}. Round and triangle vertices denote tree vertices and reticulations, respectively. As illustrated in [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (N2)S is a phylogenetic network containing only a leaf. S = {(x1, x2),(x4, x5),(x3, x4),(x3, x5),(x1, x3),(x1, x5)}. In addition to the reduction-based definition above, orchard networks can also be characterized using arc decompositions. Let N be a network. A cherry shape is a subgraph of N consisting of ver￾tex set {x, y, p} and arc set {px, py}, where x and y are called the endpoints, and p is the inter… view at source ↗
Figure 3
Figure 3. Figure 3: (a) Phylogenetic network N3, with its cherry cover P1 = {C1, C2, C3, R1}, represented by distinct dashed styles; (b) The cherry cover auxiliary graph of P1, which is acyclic; (c) Phylogenetic network, with its cherry cover P2 = {C1, C2, C3, R1}; (d) The cherry cover auxiliary graph of P2, which is cyclic. Orchard networks can also be characterized by a special type of vertex labeling, called HGT-consistent… view at source ↗
Figure 4
Figure 4. Figure 4: (a) Tree-based Phylogenetic network N4; (b) A subdivision tree T˜ 4 of N4; (c) A base tree T4 of N4. To characterize the structural features of tree-based networks, a method based on arc decomposition—called the maximal zig-zag trail decomposi￾tion—was proposed in [11]. Specifically, a sequence of arcs (a1, a2, . . . , ak) with k > 1 is called a zig￾zag trail if for every i ∈ [1, k − 1], it holds that eith… view at source ↗
Figure 5
Figure 5. Figure 5: The two gadgets corresponding to an edge [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The effect of deleting the arc w v 4 r v 4 in a selected gadget. Panels (a) and (c) show the relevant parts of NG and N E G , respectively. Panels (b) and (d) show the corresponding parts of the cherry-cover auxiliary graphs; the directed cycle present in (b) is destroyed in (d). 14 [PITH_FULL_IMAGE:figures/full_fig_p014_6.png] view at source ↗
read the original abstract

Phylogenetic networks generalize phylogenetic trees by allowing reticulate evolutionary events such as horizontal gene transfer and hybridization. Among the many subclasses of phylogenetic networks, orchard networks have attracted increasing attention due to their structural and algorithmic properties. In this paper, we study the arc-deletion distance to orchard networks, defined as the minimum number of reticulate arcs whose deletion transforms a phylogenetic network into an orchard network. We prove that computing this distance is NP-hard via a polynomial-time reduction from the Degree-3 Vertex Cover problem. Our result establishes the computational intractability of this proximity measure and contributes to the complexity theory of phylogenetic network transformations.

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 / 1 minor

Summary. The paper claims to prove that computing the arc-deletion distance to orchard networks (the minimum number of reticulate arcs to delete to obtain an orchard network) is NP-hard, via a polynomial-time reduction from the Degree-3 Vertex Cover problem.

Significance. If the reduction is correct, the result establishes intractability for this proximity measure and adds to the complexity landscape of phylogenetic network problems. The reduction approach from an established NP-hard problem is a standard and potentially strong way to obtain such a result.

major comments (1)
  1. [Main reduction section / Theorem 1] The central reduction from Degree-3 Vertex Cover is asserted in the abstract and introduction, but the manuscript does not supply the explicit network construction (how vertices/edges are mapped to tree arcs versus reticulate arcs) or the full argument showing that every minimum arc-deletion set corresponds exactly to a minimum vertex cover with no smaller deletion sets possible via other reticulations. This equivalence is load-bearing for the NP-hardness claim.
minor comments (1)
  1. [Preliminaries] Notation for reticulate arcs and orchard networks could be introduced with a small example figure in the preliminaries to aid readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful review and for highlighting the need for greater clarity in the presentation of our main result. We address the major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Main reduction section / Theorem 1] The central reduction from Degree-3 Vertex Cover is asserted in the abstract and introduction, but the manuscript does not supply the explicit network construction (how vertices/edges are mapped to tree arcs versus reticulate arcs) or the full argument showing that every minimum arc-deletion set corresponds exactly to a minimum vertex cover with no smaller deletion sets possible via other reticulations. This equivalence is load-bearing for the NP-hardness claim.

    Authors: We agree that the reduction requires a more explicit and self-contained exposition to make the equivalence fully transparent. In the revised manuscript we will expand the relevant section to include: (i) the precise polynomial-time construction that maps each vertex and edge of a Degree-3 Vertex Cover instance to a combination of tree arcs and reticulate arcs in the target phylogenetic network; (ii) a detailed proof that every minimum-size arc-deletion set in the constructed network corresponds to a minimum vertex cover and, conversely, that every minimum vertex cover yields a minimum arc-deletion set; and (iii) an explicit argument ruling out the possibility that a smaller deletion set could be obtained by deleting reticulate arcs that do not correspond to the chosen vertices. These additions will be placed immediately after the statement of Theorem 1 so that the NP-hardness claim rests on a complete, verifiable argument. revision: yes

Circularity Check

0 steps flagged

Standard reduction from independently known NP-hard problem

full rationale

The paper establishes NP-hardness of computing arc-deletion distance to orchard networks by exhibiting a polynomial-time reduction from the Degree-3 Vertex Cover problem, which is a classically known NP-complete problem independent of this work. The abstract explicitly states the reduction approach without invoking self-citations, fitted parameters, or redefinitions of the target quantity in terms of itself. Because the source problem and its hardness are external, the derivation chain does not collapse to any of the enumerated circular patterns; the result is a conventional complexity-theoretic argument whose validity rests on the correctness of the (external) reduction construction rather than on internal self-reference.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result depends on standard definitions of phylogenetic networks, orchard networks, and NP-hardness via reduction; no free parameters or invented entities are introduced.

axioms (2)
  • standard math Degree-3 Vertex Cover is NP-hard
    Invoked as the source problem for the polynomial-time reduction in the abstract.
  • domain assumption Orchard networks are a well-defined subclass of phylogenetic networks with the stated structural properties
    Used to define the target class for the arc-deletion distance.

pith-pipeline@v0.9.0 · 5629 in / 1161 out tokens · 26383 ms · 2026-05-20T03:38:41.662346+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    M. C. Fontaine, J. B. Pease, A. Steele, R. M. Waterhouse, D. E. Neafsey, I. V. Sharakhov, X. Jiang, A. B. Hall, F. Catteruccia, E. Kakani, et al. Extensive introgression in a malaria vector species complex revealed by phylogenomics.Science, 347(6217):1258524, 2015

    work page 2015

  2. [2]

    R. Cui, M. Schumer, K. Kruesi, R. Walter, P. Andolfatto, and G. G. Rosenthal. Phylogenomics reveals extensive reticulate evolution in Xiphophorus fishes.Evolution, 67(8):2166–2179, 2013

    work page 2013

  3. [3]

    Cardona, F

    G. Cardona, F. Rosselló, and G. Valiente. Comparison of tree-child phy- logenetic networks.IEEE/ACM Transactions on Computational Biology and Bioinformatics, 6(4):552–569, 2008

    work page 2008

  4. [4]

    A. R. Francis and M. Steel. Which phylogenetic networks are merely trees with additional arcs?Systematic Biology, 64(5):768–777, 2015

    work page 2015

  5. [5]

    P.L.Erdős, C.Semple, andM.Steel.Aclassofphylogeneticnetworksre- constructable from ancestral profiles.Mathematical Biosciences, 313:33– 40, 2019

    work page 2019

  6. [6]

    van Iersel, M

    L. van Iersel, M. Jones, E. Julien, and Y. Murakami. Making orchard by adding leaves.arXiv preprint arXiv:2305.03106, 2023

    work page arXiv 2023

  7. [7]

    Fischer, T

    M. Fischer, T. N. Hamann, and K. Wicke. How far is my network from being edge-based? Proximity measures for edge-basedness of un- rooted phylogenetic networks.Discrete Applied Mathematics, 337:303– 320, 2023

    work page 2023

  8. [8]

    M. Susanna. Making phylogenetic networks orchard: Algorithms to de- termine if a phylogenetic network is orchard and to transform non- orchard to orchard networks. Master’s thesis, Delft University of Tech- nology, Delft, The Netherlands, 2022

    work page 2022

  9. [9]

    van Iersel, R

    L. van Iersel, R. Janssen, M. Jones, Y. Murakami, and N. Zeh. A unify- ing characterization of tree-based networks and orchard networks using cherry covers.Advances in Applied Mathematics, 129:102222, 2021

    work page 2021

  10. [10]

    van Iersel, R

    L. van Iersel, R. Janssen, M. Jones, and Y. Murakami. Orchard networks are trees with additional horizontal arcs.Bulletin of Mathematical Biol- ogy, 84(8):76, 2022. 19

    work page 2022

  11. [11]

    Hayamizu

    M. Hayamizu. A structure theorem for rooted binary phylogenetic net- works and its implications for tree-based networks.SIAM Journal on Discrete Mathematics, 35(4):2490–2516, 2021

    work page 2021

  12. [12]

    Janssen and Y

    R. Janssen and Y. Murakami. On cherry-picking and network contain- ment.Theoretical Computer Science, 856:121–150, 2021. 20

    work page 2021