CS Paper Radar

How many cherry-picking sequences are needed to reduce all subtrees of a phylogenetic tree?

Bálint Kollmann, Yukihiro Murakami, Takatora Suzuki

cs.DM math.CO ·submitted 2026-08-20 11:32 UTC · v1

Abstract

Phylogenetic networks are graphs that represent the evolutionary history of species. Recently, the class of orchard phylogenetic networks, which can be reduced by so-called cherry-picking sequences, has gained attention for its computational and biological aspects. In this paper, we study a fundamental question on orchards and their cherry-picking sequences by considering the CoveringNumber problem: given an orchard network $N$, how many cherry-picking sequences are needed to reduce all subnetworks of $N$? We initiate this study by considering the problem for trees. We then show that the covering number can be computed for binary trees recursively using a similar but more fine-grained notion of survival covering number. We also give a recursive formula for the survival covering number of non-binary trees. However, computing the covering number for non-binary trees appears to be considerably more challenging. For this case, we show that the covering number of star trees (whose root is adjacent to all leaves) is equivalent to the so-called SubsetConnectivity problem, which we introduce in this paper. Finally, we show that if there is no restriction on the sequence length, a single sequence of minimum length $\binom{n}{2}$ suffices to reduce all subtrees of a tree on $n$ leaves.

Comment
21 pages, 7 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Algorithms for Soft Tree Containment on Tree-Child Networks

cs.DS q-bio.PE ·2026-11-08 ·Erdem Ugurlu, Louxin Zhang
similarity 0.66
Abstract · 38 pages, 8 figures

Phylogenetic networks generalize evolutionary trees by allowing lineages to merge. The Tree Containment problem asks whether a network $N$ displays a tree $T$ on the same taxa. When the polytomies of $T$ reflect uncertainty rather than simultaneous divergence, the relevant notion is soft display, in which $N$ may refine the polytomies of $T$. We take it in its asymmetric reading. Soft Tree Containment is NP-hard on reticulation-visible networks even at reticulation indegree three, and it was open for a non-binary tree and a tree-child network with multifurcating tree nodes or reticulations of indegree above two. We solve this case. A cluster characterization reduces soft display to realizing all clusters of $T$ by one switching, and in a tree-child network the vertices that can realize a cluster lie on a single chain. The per-cluster requirements then form a constraint network of width one, which arc consistency decides without search, and a $2$-SAT instance when $N$ is binary. This yields, to our knowledge, the first polynomial-time algorithm for soft Tree Containment on single-labelled tree-child networks of arbitrary reticulation indegree, and a linear-time algorithm when $T$ is binary. The same method decides the symmetric variant of the problem, in which the polytomies of $N$ may be resolved as well.

0.21

Finding Tree-Like Substructures in Phylogenetic Networks: ILP Approaches and Their Application

cs.DM q-bio.PE ·2026-08-21 ·Takatora Suzuki
similarity 0.65
Abstract · 12 pages, 6 figures

Phylogenetic networks model evolutionary histories that involve reticulate events, but their structural complexity makes them difficult to interpret. Extracting their simple substructures both clarifies the evolutionary pathways and quantifies the complexity of the networks themselves. For a given rooted almost-binary phylogenetic network, the Level Minimization problem asks for a spanning subgraph that has the same root and leaf-set and whose level is minimum, i.e., which is as close to a tree as possible. Networks for which the minimum level is zero are known as tree-based networks and can be recognized in linear time. However, Level Minimization is NP-hard in general. State-of-the-art algorithms rely on exhaustive searches of the solution spaces and hence apply only to networks of limited size. In this paper, we propose two methods for Level Minimization using integer linear programming: an exact formulation for finding such a subgraph of level at most one, and a heuristic formulation for the general case. Computational experiments confirmed the practicality of both formulations. An application to ancestral recombination graphs suggests that the minimum level provides an alternative measure of the topological complexity of an inferred network.

0.24

Counting Paths and Trees via Exterior Algebra

cs.DS ·2026-09-13 ·Fahad Panolan, Saket Saurabh, Meirav Zehavi, Jie Xue
similarity 0.59
Abstract · Counting k-paths, Counting k-trees, Exterior Algebra

We give randomized approximation algorithms for counting k-paths and k-forests in a host graph. Here k denotes the number of pattern vertices, n and m denote the numbers of host vertices and edges or arcs, ε is the relative error, and δ is the failure probability. Our main results are: 1. Paths: We approximate the number of directed paths on $k$ vertices in $2^k k^{O(1)}(n+m)\varepsilon^{-2}\log(2/δ)$ arithmetic operations. 2. Trees and forests: For every fixed $η>0$, we approximate the number of non-induced copies of a given forest on $k$ vertices in $(2+η)^k n^{O_η(1)}\varepsilon^{-2}\log(2/δ)$ arithmetic operations. Our path algorithm resolves a conjecture of Koutis and Williams~[CACM 2016] and answers an open question of Lokshtanov, Saurabh, and Zehavi~[SODA 2021] by giving a $2^k poly(n,\varepsilon^{-1})$-time approximation scheme. Our algorithms combine exterior algebra with random matrix estimators, using the tensor-train moment bound of Rakhshan and Rabusseau~[AISTATS 2020]. For forests, we use a small-component separator to evaluate the estimator efficiently.

0.04

NOC NOC, who's there? Clustering systems of tree-child and normal networks

cs.DS cs.DMmath.COq-bio.PE ·2026-09-11 ·Anna Lindeberg, Marc Hellmuth
theory similarity 0.59
Abstract

Clustering systems provide a natural way to encode structural information contained in phylogenetic networks. In this note, we study the clustering systems of normal and tree-child networks through an overlap-based property of set systems, called not-overlap-covered (NOC). We show that the NOC property is equivalent to inclusion-visibility, a memberwise formulation of the strict-compatibility condition previously used for tree-child clustering systems. We characterize normal networks as precisely the semi-regular networks whose clustering systems satisfy NOC. Consequently, a clustering system is realized by a normal network if and only if it satisfies NOC, or equivalently, if every one of its clusters is inclusion-visible. In this case, the Hasse diagram provides a canonical normal realization. These are exactly the clustering systems realized by tree-child networks. The NOC formulation yields a sharp quadratic upper bound on the number of distinct clusters of tree-child and normal networks and a direct polynomial-time recognition algorithm. Finally, we explore several consequences of the NOC perspective beyond the phylogenetic setting. These include connections to the enumeration of normal networks, an order-theoretic interpretation of inclusion-visibility, structural properties of NOC set systems, and a tractable special case of Minimum Set Cover, which is NP-hard in general.

0.21

Report the tolerance, not the count: exact phylogenetic distance deconvolution with incomplete references

cs.DS q-bio.PE ·2026-10-22 ·Haotian Tang
code/data similarity 0.59
Abstract · 13 pages, 3 figures. Supplementary appendices (37 pages) are included as an ancillary file. Code, exact input fixtures and saved run records…

Phylogenetic distance deconvolution represents mixture-to-reference distances by weighted sources placed on a reference tree. We study the minimum number of strictly interior sources that explains a distance profile, and what incomplete references cost. On a positive-rational reduced tree we give an exact algorithm with 2^O(K) poly(B) bit complexity for a free positive mean pendant and any nonempty set of observed leaves; the single-exponential dependence on K is tight under ETH, already with every leaf observed. With arbitrary missing references and a prescribed pendant the problem is W[1]-hard in the source budget K, even on positive binary trees supplied with a strict explanation using at most K+1 sources. We then use the algorithm as an instrument. Removing references can only lower the minimum source count, never raise it, at every error tolerance. Which references are missing then matters far more than how many. Under nearest-to-source deletion a median of two references can be erased before the generating support stops being the unique smallest explanation, and that budget stays nearly flat as the panel grows (Spearman 0.10 over 20 to 361 references, against 0.82 for random loss). Discarding 7,931 of 10,575 references from a real 16S panel at random costs 1.8% of the tolerance at which one source suffices. Discarding comparably many as whole clades costs 90%. That tolerance needs neither ground truth nor an error model, which makes the model measurable on real data. The generating configuration's worst-leaf residual exceeds the one-source optimum in all 296 real ANI cases, and in 248 after refitting the common pendant. The phenomenon is not unobservable in practice. A point estimate of the count alone does not quantify it. Methods for this problem should report the tolerance at which an explanation of a given size exists.

0.43

Best Matches in Phylogenetic Networks

cs.DM q-bio.PE ·2026-09-18 ·Patricia A. Ebert, Peter F. Stadler, Marc Hellmuth
similarity 0.57
Abstract

Best match graphs (BMGs) were introduced in mathematical phylogenetics to describe the concept of closest relatives for related genes (leaves of rooted tree) in different organisms (defining leaf colors). We generalize this concept here to leaf-colored rooted networks, where least common ancestors are in general neither unique nor comparable. We characterize BMGs of rooted networks as those vertex-colored digraphs that are properly colored and satisfy an easy-to-check condition that we call the sicor-in-hub property. BMGs can be recognized in linear time and an explaining network can be constructed in quadratic time. Analogous results are obtained for reciprocal best match graphs (RBMGs), where an edge $\{x,y\}$ corresponds to pairs of vertices with different color that are mutually closest relatives.

0.15

On Kernels and Leaves: Searching for Bare and Lush Trees

cs.DS cs.CCcs.DM ·2026-09-24 ·Jesse Beisegel, Ekkehard Köhler, Robert Scheffler, Martin Strehler
similarity 0.57
Abstract · Full version of an extended abstract accepted for IPEC 2026

We study a variation of the classical Maximum (Minimum) Leaf Spanning Tree problem. In many applications, Depth-First Search (DFS) is used to compute a spanning tree of a graph. Such a search tree is constructed by connecting each vertex $v$ with the last vertex the search has visited before $v$ and we call this a last-in tree. By restricting the Maximum (Minimum) Leaf Spanning Tree problem to last-in trees of a graph search, we ask for a search ordering that leads to the largest (smallest) number of leaves in its search tree. Recently, Bergougnoux et al. [Journal of Computer and System Sciences 154 (2025)] have studied the parameterized complexity of these problems for DFS. They showed that the minimization problem is para-$\mathsf{NP}$-hard and the maximization problem is $\mathsf{W}[1]$-hard when parameterized by the number of leaves. When parameterized by the number of internal vertices, both problems have polynomial kernels. Here, we examine whether these results also hold for the variant Lexicographic DFS (LDFS). We show that the hardness results of DFS can be transferred to LDFS. We also present exponential kernels for the number of internal vertices as the parameter. We complement this by showing that polynomial kernels do not exist, unless $\mathsf{NP} \subseteq \mathsf{coNP} / \mathsf{poly}$. We also consider last-in trees of searches that do not follow the DFS scheme. In contrast to (L)DFS, minimizing the number of internal vertices is para-$\mathsf{NP}$-hard for several searches including Breadth-First Search.

0.31

A Polynomial-Time Algorithm for $k$-Path Vertex Cover Reconfiguration on Trees under Token Sliding

cs.DS cs.DM ·2026-10-22 ·Duc A. Hoang
similarity 0.57
Abstract

A $k$-path vertex cover ($k$-PVC) of a graph is a set of vertices meeting every path on $k$ vertices. In Token Sliding, one token occupies each vertex of a cover; a move slides one token along an edge to an unoccupied vertex, preserving the cover property. We study whether two covers of a tree are joined by such moves. The case $k=2$ admits a linear-time decision algorithm. For every integer $k\geq2$, we give an $O(kn^2)$-time decision algorithm on trees of order $n$, with $k$ part of the input. Two covers are reachable precisely when their rigid tokens, which never move, occupy the same set and every component remaining after their deletion has the same token count. The proof transforms configurations of equal size without rigid tokens into a canonical configuration built on properly rooted subtrees, whose paths on $k$ vertices pass through their roots. A rooted-subtree recurrence identifies movable candidate tokens. We also give a direct recursive construction between the supplied endpoints, returning at most $8n^2\,3^{\lceil n/2\rceil}$ slides in $O(n^{10}3^{n/2})$ time. ChatGPT 6 Pro and Claude Fable 5.1 were used to assist with developing and reviewing mathematical arguments and drafting and revising the paper. The author takes full responsibility for the correctness and content of the paper.

0.20