Further parameterized algorithms for the [formula omitted]-free edge deletion problem.

Given a graph G = (V , E) and a set F of forbidden subgraphs, we study the F -Free Edge Deletion problem, where the goal is to remove a minimum number of edges such that the resulting graph does not contain any F ∈ F as a (not necessarily induced) subgraph. Enright and Meeks (Algorithmica, 2018) gave an algorithm to solve F -Free Edge Deletion whose running time on an n -vertex graph G of treewidth tw (G) is bounded by 2 O (| F | tw (G) r) n , if every graph in F has at most r vertices. We complement this result by showing that F -Free Edge Deletion is W[1]-hard when parameterized by tw (G) + | F |. We also show that F -Free Edge Deletion is W[2]-hard when parameterized by the combined parameters solution size, the feedback vertex set number and pathwidth of the input graph. A special case of particular interest is the situation in which F is the set T h + 1 of all trees on h + 1 vertices, so that we delete edges in order to obtain a graph in which every component contains at most h vertices. This is desirable from the point of view of restricting the spread of a disease in transmission networks [5]. We prove that T h + 1 -Free Edge Deletion is fixed-parameter tractable (FPT) when parameterized by the vertex cover number of the input graph. We also prove that it admits a kernel with 2 k h vertices and 2 k h 2 + k edges, when parameterized by k + h. [ABSTRACT FROM AUTHOR]