2015/09/23 by Marc Hellmuth, Hellmuth, Marc, Adrian Fritz +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Genome Rearrangement Algorithms #cs.DM #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1509.06983
openalex publication_date 2015/09/23 · arxiv created 2015/09/24 · arxiv updated 2015/09/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Cographs are graphs in which no four vertices induce a simple connected path P4. Cograph editing is to find for a given graph G = (V,E) a set of at most k edge additions and deletions that transform G into a cograph. This combinatorial optimization problem is NP-hard. It has, recently found applications in the context of phylogenetics, hence good heuristics are of practical importance. It is well-known that the cograph editing problem can be solved independently on the so-called strong prime modules of the modular decomposition of G. We show here that editing the induced P4's of a given graph is equivalent to resolving strong prime modules by means of a newly defined merge operation on the submodules. This observation leads to a new exact algorithm for the cograph editing problem that can be used as a starting point for the construction of novel heuristics.