Faster algorithm for Cograph Deletion

08/03/2019

∙

by   Dekel Tsur, et al.

∙

0

∙

share

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