From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats

DOI10.1016/J.DAM.2022.06.042MaRDI QIDQ2172401zbMATH OpenOpenAlexWikidataFDO

Authors Marc Hellmuth, G. E. Scholz

Publication date 15 September 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2112.05537

zbMATH Keywords

cographsgalled treemodular decompositionphylogenetic networksprime modulesprime vertex replacementrecognition algorithms

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Problems related to evolution (92D15)

Abstract: 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$ does not contain prime modules. In this case, $(T,t)$ explains $G$, i.e., $x,yinE(G)$ if and only if the lowest common ancestor $mathrm{lca}_T(x,y)$ of $x$ and $y$ has label "$1$". This information, however, gets lost whenever $(T,t)$ contains vertices with label "prime". In this contribution, we aim at replacing "prime" vertices in $(T,t)$ by simple 0/1-labeled cycles, which leads to the concept of rooted labeled level-1 networks $(N,t)$. We characterize graphs that can be explained by such level-1 networks $(N,t)$, which generalizes the concept of graphs that can be explained by labeled trees, that is, cographs. We provide three novel graph classes: emph{polar-cats} are a proper subclass of emph{pseudo-cographs} which forms a proper subclass of emph{prime polar-cats}. In particular, every cograph is a pseudo-cograph and prime polar-cats are precisely those graphs that can be explained by a labeled level-1 network. The class of prime polar-cats is defined in terms of the modular decomposition of graphs and the property that all prime modules "induce" polar-cats. We provide a plethora of structural results and characterizations for graphs of these new classes. In addition, we show under which conditions there is a unique least-resolved labeled level-1 network that explains a given graph and provide linear-time algorithms to recognize all these types of graphs and to construct level-1 networks to explain them.

Recommendations

• From modular decomposition trees to rooted median graphs
• \(P_ 4\)-trees and substitution decomposition
• scientific article; zbMATH DE number 1456953
• Capturing polynomial time using modular decomposition
• An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures

Cites work

• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A canonical decomposition theory for metrics on a finite set
• A Linear Recognition Algorithm for Cographs
• A lower bound on the tree-width of graphs with irrelevant vertices
• A short note on undirected Fitch graphs
• A simple linear time algorithm for cograph recognition
• A Simple Linear Time LexBFS Cograph Recognition Algorithm
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• A survey of the algorithmic aspects of modular decomposition
• Algorithm Theory - SWAT 2004
• Alternative characterizations of Fitch's xenology relation
• An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
• Beyond representing orthology relations by trees
• Cograph editing: Merging modules is equivalent to editing P₄s
• Complement reducible graphs
• Computing the maximum agreement of phylogenetic networks
• Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
• Dacey Graphs
• Efficient and practical algorithms for sequential modular decomposition
• Encoding and constructing 1-nested phylogenetic networks with trinets
• From modular decomposition trees to rooted median graphs
• Graph Classes: A Survey
• Graphs indecomposable with respect to the X-join
• Graphs with unique maximal clumpings
• scientific article; zbMATH DE number 1003286 (Why is no real title available?)
• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• scientific article; zbMATH DE number 1375569 (Why is no real title available?)
• scientific article; zbMATH DE number 1508917 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• scientific article; zbMATH DE number 3414349 (Why is no real title available?)
• Incremental modular decomposition
• Indecomposable graphs
• Indirect identification of horizontal gene transfer
• Linear time algorithms for graph search and connectivity determination on complement graphs.
• Minimal indecomposable graphs
• Modular decomposition and transitive orientation
• On a property of the class of n-colorable graphs
• On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters
• On the minimum sum coloring of P₄-sparse graphs
• On the number of vertices and edges of the Buneman graph
• On the X-join decomposition for undirected graphs
• On variations of \(P_{4}\)-sparse graphs
• Orthology relation and gene tree correction: complexity results
• Orthology relations, symbolic ultrametrics, and cographs
• Partition refinement techniques: an interesting algorithmic tool kit
• Phylogeny. Discrete and random processes in evolution
• Primitivity is hereditary for 2-structures
• Recognizing P₄ -Sparse Graphs in Linear Time
• Reconstructing gene trees from Fitch's xenology relation
• Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets
• Reconstructing unrooted phylogenetic trees from symbolic ternary metrics
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• The cluster deletion problem for cographs
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
• The Pathwidth and Treewidth of Cographs
• The relation graph
• The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
• Theory of 2-structures. I: Clans, basic subclasses, and morphisms
• Theory of 2-structures. II: Representation through labeled tree families
• Three-way symbolic tree-maps and ultrametrics
• Transitiv orientierbare Graphen
• Upper bounds to the clique width of graphs

Cited in

(7)

• From modular decomposition trees to rooted median graphs
• Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
• Linear time algorithms for NP-hard problems restricted to \textsc{GaTEx} graphs
• Shared ancestry graphs and symbolic arboreal maps
• The weighted total cophenetic index: a novel balance index for phylogenetic networks
• Representing distance-hereditary graphs with multi-rooted trees
• Solving NP-hard problems on \textsc{GaTEx} graphs: linear-time algorithms for perfect orderings, cliques, colorings, and independent sets

This page was built for publication: From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2172401)