Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Characterizing and transforming DAGs within the ℐ-lca framework
Stockholm University, Faculty of Science, Department of Mathematics.ORCID iD: 0000-0002-1620-5508
Stockholm University, Faculty of Science, Department of Mathematics.ORCID iD: 0000-0001-9664-1918
Number of Authors: 22026 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 378, p. 584-593Article in journal (Refereed) Published
Abstract [en]

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=GW 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.

Place, publisher, year, edition, pages
2026. Vol. 378, p. 584-593
Keywords [en]
Cluster, Galled-tree, Hasse diagram, Hierarchy, I-ary set systems, Phylogenetic network, Regular DAGs
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:su:diva-246610DOI: 10.1016/j.dam.2025.08.037ISI: 001565640600001Scopus ID: 2-s2.0-105014613207OAI: oai:DiVA.org:su-246610DiVA, id: diva2:1997908
Available from: 2025-09-15 Created: 2025-09-15 Last updated: 2025-09-15Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Hellmuth, MarcLindeberg, Anna

Search in DiVA

By author/editor
Hellmuth, MarcLindeberg, Anna
By organisation
Department of Mathematics
In the same journal
Discrete Applied Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 16 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf