The complexity of some edge deletion problems

The edge deletion problem (EDP) corresponding to a given class H of graphs is to find the minimum number of edges the deletion of which from a given graph G results in a subgraph G´, G ´∈H. Previous complexity results are extended by showing that the EDP corresponding to any class H of graphs in each of the following cases is NP-hard. (1) H is defined by a set of forbidden homeomorphs or minors in which every member is a 2-connected graph with minimum degree three; (2) BH is defined by K₄-e as a forbidden homeomorph or minor; and (3) H is defined by P_l , l⩾3, the simple path on l nodes, as a forbidden induced subgraph