Faster algorithms for cograph edge modification problems

2019/08/03 by Dekel Tsur, Tsur, Dekel
Computer Science · Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #cs.DS #math.CO

paper · pdf · doi:10.48550/arxiv.1908.01223

arxiv created 2019/12/30 · arxiv updated 2020/01/01

Abstract

In the Cograph Deletion (resp., Cograph Editing) problem the input is a graph G and an integer k, and the goal is to decide whether there is a set of edges of size at most k whose removal from G (resp., removal and addition to G) results in a graph that does not contain an induced path with four vertices. In this paper we give algorithms for Cograph Deletion and Cograph Editing whose running times are O^*(2.303^k) and O^*(4.329^k), respectively.

Related

• Exact and heuristic algorithms for Cograph Editing
• Techniques for the Cograph Editing Problem: Module Merge is equivalent to Editing P4s
• Cograph Editing: Merging Modules is equivalent to Editing P4's
• Cluster Editing on Cographs and Related Classes
• A quasi-quadratic vertex Kernel for Cograph edge editing