We explore the connections between clusters and least common ancestors (LCAs) in directed acyclic graphs (DAGs), focusing on the interplay between so-called ℐ-lca-relevant DAGs and DAGs with the ℐ-lca-property. Here, ℐ denotes a set of integers. In ℐ-lca-relevant DAGs, each vertex is the unique LCA for some subset A of leaves of size |A|∈ℐ, whereas in a DAG with the ℐ-lca-property there exists a unique LCA for every subset A of leaves satisfying |A|∈ℐ. We elaborate on the difference between these two properties and establish their close relationship to pre-ℐ-ary and ℐ-ary set systems. This, in turn, generalizes results established for (pre-) binary and k-ary set systems. Moreover, we build upon recently established results that use a simple operator ⊖, enabling the transformation of arbitrary DAGs into ℐ-lca-relevant DAGs. This process reduces unnecessary complexity while preserving key structural properties of the original DAG. The set ℭ_G consists of all clusters in a DAG G, where clusters correspond to the descendant leaves of vertices. While in some cases ℭ_H=ℭ_G when transforming G into an ℐ-lca-relevant DAG H, it often happens that certain clusters in ℭ_G do not appear as clusters in H. To understand this phenomenon in detail, we characterize the subset of clusters in ℭ_G that remain in H for DAGs G with the ℐ-lca-property. Furthermore, we show that the set W of vertices required to transform G into H=G⊖W is uniquely determined for such DAGs. This, in turn, allows us to show that the “shortcut-free” version of the transformed DAG H is always a tree or a galled-tree whenever ℭ_G represents the clustering system of a tree or galled-tree and G has the ℐ-lca-property. In the latter case ℭ_H=ℭ_G always holds.

In phylogenetics, reconstructing rooted trees from distances between taxa is a common task. Böcker and Dress generalized this concept by introducing symbolic dating maps δ, where distances are replaced by symbols, and showed that there is a one-to-one correspondence between symbolic ultrametrics and labeled rooted phylogenetic trees. Many combinatorial structures fall under the umbrella of symbolic dating maps, such as 2-dissimilarities, symmetric labeled 2-structures, or edge-colored complete graphs, and are here referred to as strudigrams. Strudigrams have a unique decomposition into non-overlapping modules, which can be represented by a modular decomposition tree (MDT). In the absence of prime modules, strudigrams are equivalent to symbolic ultrametrics, and the MDT fully captures the relationships between pairs of vertices through the label of their least common ancestor in the MDT. However, in the presence of prime modules, appearing as prime vertices in the MDT, this information is generally hidden. To provide this missing structural information, we aim to locally replace the prime vertices in the MDT to obtain networks that capture full information about the strudigrams. While starting with the general framework of prime-vertex replacement networks, we then focus on a specific type of such networks obtained by replacing prime vertices with so-called galls, resulting in labeled galled-trees. We introduce the concept of galled-tree explainable (GaTEx) strudigrams, provide their characterization, and demonstrate that recognizing these structures and reconstructing the labeled networks that explain them can be achieved in polynomial time.

Median graphs are connected graphs in which for all three vertices there is a unique vertex that belongs to shortest paths between each pair of these three vertices. To be more formal, a graph G is a median graph if, for all μ, u, v ∈ V(G), it holds that |I(μ, u) ∩ I(μ, v) ∩ I(u, v)| = 1 where I(x, y) denotes the set of all vertices that lie on shortest paths connecting x and y.

In this paper we are interested in a natural generalization of median graphs, called k-median graphs. A graph G is a k-median graph, if there are k vertices μ₁, …, μ_k ∈ V(G) such that, for all u, v ∈ V(G), it holds that |I(μ_i, u) ∩ I(μ_i, v) ∩ I(u, v)| = 1, 1 ≤ i ≤ k. By definition, every median graph with n vertices is an n-median graph. We provide several characterizations of k-median graphs that, in turn, are used to provide many novel characterizations of median graphs.

Orthologous genes, which arise through speciation, play a key role in comparative genomics and functional inference. In particular, graph-based methods allow for the inference of orthology estimates without prior knowledge of the underlying gene or species trees. This results in orthology graphs, where each vertex represents a gene, and an edge exists between two vertices if the corresponding genes are estimated to be orthologs. Orthology graphs inferred under a tree-like evolutionary model must be cographs. However, real-world data often deviate from this property, either due to noise in the data, errors in inference methods or, simply, because evolution follows a network-like rather than a tree-like process. The latter, in particular, raises the question of whether and how orthology graphs can be derived from or, equivalently, are explained by phylogenetic networks. In this work, we study the constraints imposed on orthology graphs when the underlying evolutionary history follows a phylogenetic network instead of a tree. We show that any orthology graph can be represented by a sufficiently complex level-k network. However, such networks lack biologically meaningful constraints. In contrast, level-1 networks provide a simpler explanation, and we establish characterizations for level-1 explainable orthology graphs, i.e., those derived from level-1 evolutionary histories. To this end, we employ modular decomposition, a classical technique for studying graph structures. Specifically, an arbitrary graph is level-1 explainable if and only if each primitive subgraph is a near-cograph (a graph in which the removal of a single vertex results in a cograph). Additionally, we present a linear-time algorithm to recognize level-1 explainable orthology graphs and to construct a level-1 network that explains them, if such a network exists. Finally, we demonstrate the close relationship of level-1 explainable orthology graphs to the substitution operation, weakly chordal and perfect graphs, as well as graphs with twin-width at most 2.

Rooted phylogenetic networks, or more generally, directed acyclic graphs (DAGs), are widely used to model species or gene relationships that traditional rooted trees cannot fully capture, especially in the presence of reticulate processes or horizontal gene transfers. Such networks or DAGs are typically inferred from observable data (e.g., genomic sequences of extant species), providing only an estimate of the true evolutionary history. However, these inferred DAGs are often complex and difficult to interpret. In particular, many contain vertices that do not serve as least common ancestors (LCAs) for any subset of the underlying genes or species, thus may lack direct support from the observable data. In contrast, LCA vertices are witnessed by historical traces justifying their existence and thus represent ancestral states substantiated by the data. To reduce unnecessary complexity and eliminate unsupported vertices, we aim to simplify a DAG to retain only LCA vertices while preserving essential evolutionary information. In this paper, we characterize LCA -relevant and lca -relevant DAGs, defined as those in which every vertex serves as an LCA (or unique LCA) for some subset of taxa. We introduce methods to identify LCAs in DAGs and efficiently transform any DAG into an LCA -relevant or lca -relevant one while preserving key structural properties of the original DAG or network. This transformation is achieved using a simple operator "⊖" that mimics vertex suppression. 

The class of GAlled-Tree EXplainable (GATEX) graphs has recently been discovered as a natural generalization of cographs. Cographs are precisely those graphs that can be uniquely represented by a rooted tree where the leaves correspond to the vertices of the graph. As a generalization, GATEX graphs are precisely those that can be uniquely represented by a particular rooted acyclic network, called a galled-tree. This paper explores the use of galled-trees to solve combinatorial problems on GATEX graphs that are, in general, NP-hard. We demonstrate that finding a maximum clique, an optimal vertex coloring, a perfect order, as well as a maximum independent set in GATEX graphs can be efficiently done in linear time. The key idea behind the linear-time algorithms is to utilize the galled-trees that explain the GATEX graphs as a guide for computing the respective cliques, colorings, perfect orders, or independent sets.

The Djoković-Winkler relation Θ is a binary relation defined on the edge set of a given graph that is based on the distances of certain vertices and which plays a prominent role in graph theory. In this paper, we explore the relatively uncharted “reflexive complement” Θ‾ of Θ, where (e,f)∈Θ‾ if and only if e=f or (e,f)∉Θ for edges e and f. We establish the relationship between Θ‾ and the set Δef, comprising the distances between the vertices of e and f and shed some light on the intricacies of its transitive closure ⁎Θ‾⁎. Notably, we demonstrate that ⁎Θ‾⁎ exhibits multiple equivalence classes only within a restricted subclass of complete multipartite graphs. In addition, we characterize non-trivial relations R that coincide with Θ‾ as those where the graph representation is disconnected, with each connected component being the (join of) Cartesian product of complete graphs. The latter results imply, somewhat surprisingly, that knowledge about the distances between vertices is not required to determine ⁎Θ‾⁎. Moreover, ⁎Θ‾⁎ has either exactly one or three equivalence classes.

The modular decomposition of a graph G is a natural construction to capture key features of G in terms of a labeled tree (T,t) whose vertices are labeled as “series” (1), “parallel” (0) or “prime”. However, full information of G is provided by its modular decomposition tree (T,t) only, if G is a cograph, i.e., G does not contain prime modules. In this case, (T,t) explains G, i.e., {x,y}∈E(G) if and only if the lowest common ancestor lcaT(x,y) of x and y has label “1”. Pseudo-cographs, or, more generally, GaTEx graphs G are graphs that can be explained by labeled galled-trees, i.e., labeled networks (N,t) that are obtained from the modular decomposition tree (T,t) of G by replacing the prime vertices in T by simple labeled cycles. GaTEx graphs can be recognized and labeled galled-trees that explain these graphs can be constructed in linear time.

In this contribution, we provide a novel characterization of GaTEx graphs in terms of a set FGT of 25 forbidden induced subgraphs. This characterization, in turn, allows us to show that GATEX graphs are closely related to many other well-known graph classes such as P4-sparse and P4-reducible graphs, weakly-chordal graphs, perfect graphs with perfect order, comparability and permutation graphs, murky graphs as well as interval graphs, Meyniel graphs or very strongly-perfect and brittle graphs. Moreover, we show that every GATEX graph as twin-width at most 1.

Orthology detection from sequence similarity remains a difficult and computationally expensive problem for gene families with large numbers of gene duplications and losses. REvolutionH-tl implements a new graph-based approach to identify orthogroups, orthology, and paralogy relationships first, and it uses this information in a second step to infer event-labeled gene trees and their reconciliation with an inferred species tree. It avoids using gene trees and species trees upon input and settles for a maximal subtree reconciliation in cases where noise or horizontal gene transfer precludes a global reconciliation. The accuracy of the tool is comparable to competing tools at substantially reduced computational cost. 

Most genes are part of larger families of evolutionary-related genes. The history of gene families typically involves duplications and losses of genes as well as horizontal transfers into other organisms. The reconstruction of detailed gene family histories, i.e., the precise dating of evolutionary events relative to phylogenetic tree of the underlying species has remained a challenging topic despite their importance as a basis for detailed investigations into adaptation and functional evolution of individual members of the gene family. The identification of orthologs, moreover, is a particularly important subproblem of the more general setting considered here. In the last few years, an extensive body of mathematical results has appeared that tightly links orthology, a formal notion of best matches among genes, and horizontal gene transfer. The purpose of this chapter is to broadly outline some of the key mathematical insights and to discuss their implication for practical applications. In particular, we focus on tree-free methods, i.e., methods to infer orthology or horizontal gene transfer as well as gene trees, species trees, and reconciliations between them without using a priori knowledge of the underlying trees or statistical models for the inference of phylogenetic trees. Instead, the initial step aims to extract binary relations among genes.