CS Paper Radar

Algorithms for Soft Tree Containment on Tree-Child Networks

Erdem Ugurlu, Louxin Zhang

cs.DS q-bio.PE ·submitted 2026-11-08 08:46 UTC · v1

Abstract

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.

Comment
38 pages, 8 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DM math.CO ·2026-08-20 ·Bálint Kollmann, Yukihiro Murakami, Takatora Suzuki
similarity 0.66
Abstract · 21 pages, 7 figures

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.

0.37

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

cs.DM q-bio.PE ·2026-08-21 ·Takatora Suzuki
similarity 0.66
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

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.63
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

Matroid Parity Meets Vertex Splitting

cs.DS cs.DM ·2026-11-14 ·Hitendra Kumar, Pritesh Kumar, Madhumita Kundu, Saket Saurabh
similarity 0.62
Abstract · 48 pages

A vertex split replaces a vertex by two non-adjacent descendants and partitions its incident edges between them. We study exclusive $\ell$-shallow splitting, where each original vertex has at most $\ell+1$ descendants, with the aim of obtaining a forest, a pseudoforest, or a cluster graph. We consider two natural objectives: minimizing the total number of split operations and minimizing the number of original vertices that are split. Our main conceptual contribution is a connection between vertex splitting and matroid parity. For both forests and pseudoforests, we give a characterization of feasible splitting sequences that leads, via weighted linear matroid parity, to polynomial-time algorithms for minimizing the number of split vertices when $\ell=2$. These algorithms are complemented by NP-hardness for every fixed $\ell\ge3$; for pseudoforests, hardness holds even on graphs of maximum degree four. The total number of split operations behaves differently: for both sparse target classes, this objective is polynomial-time solvable for every $\ell$, using matroid intersection. For cluster graphs, both objectives admit linear-time algorithms when $\ell=1$ and are NP-hard for every fixed $\ell\ge2$. Together, these results identify how the target class, the local splitting bound, and the choice of objective determine the complexity of vertex splitting.

0.33

Parameterized Complexity of Connected Network Microaggregation: The Role of Cluster Size

cs.DS ·2026-08-28 ·Ajinkya Gaikwad, Dušan Knop, Tomáš Valla
theory similarity 0.60
Abstract

Network microaggregation is a fundamental technique in statistical disclosure control, where vertices of a graph are partitioned into clusters satisfying size constraints and admitting a center within bounded distance. We study the parameterized complexity of the \emph{unweighted Connected Network Microaggregation} problem, focusing on structural parameters and natural clustering parameters such as the distance bound $d$ and cluster size gap $u-\ell$. We show that, unlike the weighted variant, the unweighted connected problem is fixed-parameter tractable when parameterized by neighborhood diversity, and hence by vertex cover. In contrast, it remains $\mathrm{W[1]}$-hard for more general structural parameters, including vertex deletion to paths, stars, and cliques. These hardness results hold even for every $d\ge 2$ and any fixed gap $u-\ell$, showing that these clustering parameters do not overcome the structural hardness. We further show that adding the cluster size bound $u$ restores tractability for structural parameters such as treewidth and cluster vertex deletion. Moreover, $u$ is essential: the problem remains $\mathrm{W[1]}$-hard when these structural parameters are considered alone. For kernelization, we prove that the problem has no polynomial kernel parameterized by vertex cover unless $\mathrm{coNP}\subseteq\mathrm{NP/poly}$, even when the distance constraint is vacuous. Adding $u$ yields a polynomial kernel for vertex cover, while kernelization remains unlikely for more general structural parameters even when combined with $u$. Finally, we show that the problem is NP-hard on graphs of bounded clique-width.

0.24

Best Matches in Phylogenetic Networks

cs.DM q-bio.PE ·2026-09-18 ·Patricia A. Ebert, Peter F. Stadler, Marc Hellmuth
similarity 0.58
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

Orientations without transitive arcs for cubic graphs and phylogenetic networks

cs.CC cs.DMmath.COq-bio.PE ·2026-08-20 ·Janosch Döcker, Simone Linz
similarity 0.57
Abstract

An $st$-orientation of an undirected graph $G$ is an acyclic digraph with a single source $s$ and a single sink $t$ that can be obtained from $G$ by assigning a direction to each edge. The classical problem of deciding if an undirected graph $G$ has an $st$-orientation can be solved efficiently. On the other hand, deciding if an $st$-orientation of $G$ exists that does not have any transitive arc is NP-complete, even if each vertex of $G$ has degree at most four. Here we show that this last decision problem remains NP-complete if $G$ is cubic, which settles an open question by Binucci et al. (2025). We obtain NP-completeness for two variants of the problem: (i) $s$ and $t$ are fixed and given as part of the input and (ii) $s$ and $t$ can be chosen freely. We then use these results to investigate the computational complexity of a problem that arises in computational evolution. Specifically, we show that the problem of deciding if an unrooted binary phylogenetic network has an orientation as a rooted binary phylogenetic network without any shortcuts (the analog of a transitive arcs in phylogenetics) is NP-complete. Our results connect the two (mostly) distinct research areas of orienting undirected graphs and orienting unrooted phylogenetic networks.

0.27

Episode Clustering in Phylogenetic Networks

cs.DS q-bio.PE ·2026-08-24 ·Paweł Górecki, Agnieszka Mykowiecka, Jarosław Paszek
published similarity 0.57
Abstract · Preprint version submitted to ECCB 2026 before peer review. A revised version has been accepted for publication in Bioinformatics as part of…

The classical duplication episode clustering (EC) model introduced by Guigó et al. in the 1990s provides a foundational approach for inferring genomic duplication events crucial to understanding genome evolution. This model clusters single gene duplications from a collection of gene trees at locations in the species tree to minimize the total number of such locations, called duplication episodes. Here, we introduce NetEC, a novel extension of this problem to phylogenetic networks. To solve NetEC, we first develop a polynomial-time dynamic programming (DP) algorithm for testing whether a given set of network nodes can serve as episode locations. We then propose a main inference algorithm that utilizes this DP component to optimize the episode count; while the feasibility test runs in polynomial time, the full optimization has exponential worst-case complexity, and an optional heuristic mode is provided for larger instances. We also propose an extended episode analysis procedure that identifies additional genomic duplication candidates below reticulation nodes, complementing the main algorithm by resolving potential upward clustering of duplications induced by reticulation. We evaluate our method on simulated data and on an empirical Pandanales dataset comprising over 29,000 gene trees, demonstrating exact and accurate inference of genomic duplication events even in the presence of multiple reticulations.

0.28