Parameterized Complexity of the -Free Edge Deletion Problem Th+1

Abstract

Given an undirected graph and two integers k and h, we study -FREE EDGE DELETION, where the goal is to remove at most k edges such that the resulting graph does not contain any tree on vertices as a (not necessarily induced) subgraph, that is, we delete at most k 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. Enright and Meeks (Algorithmica, 2018) gave an algorithm to solve -FREE EDGE DELETION whose running time on an n-vertex graph G of treewidth is bounded by . However, it remains open whether the problem might belong to FPT when parameterized only by the treewidth ; they conjectured that treewidth alone is not enough, and that the problem is W[1]-hard with respect to this parameterization. We resolve this conjecture by showing that -FREE EDGE DELETION is indeed W[1]-hard when parameterized by alone. We resolve two additional open questions posed by Enright and Meeks (Algorithmica, 2018) concerning the complexity of -FREE EDGE DELETION on planar graphs and -FREE ARC DELETION. We prove that the -FREE EDGE DELETION problem is NP-complete even when restricted to planar graphs. We also show that the -FREE ARC DELETION problem is W[2]-hard when parameterized by the solution size on directed acyclic graphs.