דקל צור

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.