Cograph editing: Merging modules is equivalent to editing P₄s

DOI10.26493/2590-9770.1252.E71MaRDI QIDQ5121555zbMATH OpenOpenAlexFDO

Authors Adrian Fritz, Marc Hellmuth, Peter F. Stadler, Nicolas Wieseke

Publication date 15 September 2020

Published in The Art of Discrete and Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

\(P_{4}\)\textsc{s}cograph editingmodular decompositionmodule mergeprime modules

Mathematics Subject Classification ID

Trees (05C05) Structural characterization of families of graphs (05C75) Analysis of algorithms and problem complexity (68Q25) Taxonomy, cladistics, statistics in mathematical biology (92B10)

Abstract: The modular decomposition of a graph $G=(V,E)$ does not contain prime modules if and only if $G$ is a cograph, that is, if no quadruple of vertices induces a simple connected path $P_4$. The cograph editing problem consists in inserting into and deleting from $G$ a set $F$ of edges so that $H=(V,EDeltaF)$ is a cograph and $|F|$ is minimum. This NP-hard combinatorial optimization problem has recently found applications, e.g., in the context of phylogenetics. Efficient heuristics are hence of practical importance. The simple characterization of cographs in terms of their modular decomposition suggests that instead of editing $G$ one could operate directly on the modular decomposition. We show here that editing the induced $P_4$s is equivalent to resolving prime modules by means of a suitable defined merge operation on the submodules. Moreover, we characterize so-called module-preserving edit sets and demonstrate that optimal pairwise sequences of module-preserving edit sets exist for every non-cograph. This eventually leads to an exact algorithm for the cograph editing problem as well as fixed-parameter tractable (FPT) results when cograph editing is parameterized by the so-called modular-width. In addition, we provide two heuristics with time complexity $O(|V{|}^3)$, resp., $O(|V{|}^2)$.

Recommendations

• Cograph editing: complexity and parameterized algorithms
• Complexity and parameterized algorithms for cograph editing
• Linear-time minimal cograph editing
• Editing to connected f-degree graph
• Editing to Connected F-Degree Graph
• scientific article; zbMATH DE number 1158093
• Simultaneous editing and multilabelling of graphs in system newGRAPH
• On mergings in acyclic directed graphs
• Structured general corecursion and coinductive graphs (extended abstract)
• Co-intersection graph of submodules of a module

Cites work

• A Linear Recognition Algorithm for Cographs
• A Simple Linear Time LexBFS Cograph Recognition Algorithm
• A survey of the algorithmic aspects of modular decomposition
• Algorithm Theory - SWAT 2004
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
• Applying modular decomposition to parameterized cluster editing problems
• Best match graphs
• Cograph editing: complexity and parameterized algorithms
• Complement reducible graphs
• Complexity and parameterized algorithms for cograph editing
• Complexity classification of some edge modification problems
• Correction of weighted orthology and paralogy relations -- complexity and algorithmic results
• Efficient and practical algorithms for sequential modular decomposition
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Graph Classes: A Survey
• 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 1508917 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• scientific article; zbMATH DE number 6472575 (Why is no real title available?)
• scientific article; zbMATH DE number 3414349 (Why is no real title available?)
• Incremental modular decomposition
• Modular decomposition and transitive orientation
• Modular-width: an auxiliary parameter for parameterized parallel complexity
• On a property of the class of n-colorable graphs
• On minimal augmentation of a graph to obtain an interval graph
• On symbolic ultrametrics, cotree representations, and cograph edge decompositions and partitions
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
• On the X-join decomposition for undirected graphs
• On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions
• Orthology relation and gene tree correction: complexity results
• Orthology relations, symbolic ultrametrics, and cographs
• Parameterized Algorithms for Modular-Width
• Partial homology relations -- satisfiability in terms of di-cographs
• Partition refinement techniques: an interesting algorithmic tool kit
• Reciprocal best match graphs
• Reconstructing gene trees from Fitch's xenology relation
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• The cluster deletion problem for cographs
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
• Transitiv orientierbare Graphen

Cited in

(11)

• Indirect identification of horizontal gene transfer
• From modular decomposition trees to rooted median graphs
• Linear-time minimal cograph editing
• From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
• Faster algorithms for cograph edge modification problems
• Complete characterization of incorrect orthology assignments in best match graphs
• Cograph editing: complexity and parameterized algorithms
• A quasi-quadratic vertex-kernel for cograph edge editing
• Trimming forests is hard (unless they are made of stars)
• Complexity and parameterized algorithms for cograph editing
• 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: Cograph editing: Merging modules is equivalent to editing P_4s

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