Further parameterized algorithms for the -free edge deletion problem

Abstract

Given a graph �=(�,�) and a set � of forbidden subgraphs, we study the �-FREE EDGE DELETION problem, where the goal is to remove a minimum number of edges such that the resulting graph does not contain any �∈� as a (not necessarily induced) subgraph. Enright and Meeks (Algorithmica, 2018) gave an algorithm to solve �-FREE EDGE DELETION whose running time on an n-vertex graph G of treewidth tw(�) is bounded by 2�(|�|tw(�)�)�, if every graph in � has at most r vertices. We complement this result by showing that �-FREE EDGE DELETION is W[1]-hard when parameterized by tw(�)+|�|. We also show that �-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 � is the set �ℎ+1 of all trees on ℎ+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 �ℎ+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�ℎ vertices and 2�ℎ2+� edges, when parameterized by �+ℎ.