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

Abstract

Given an undirected graph G=(V,E) and two integers k and h, we study Th+1 -FREE EDGE DELETION, where the goal is to remove at most k edges such that the resulting graph does not contain any tree on h+1 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 Th+1 -FREE EDGE DELETION whose running time on an n-vertex graph G of treewidth tw(G) is bounded by O((tw(G)h)2tw(G)n) . However, it remains open whether the problem might belong to FPT when parameterized only by the treewidth tw(G) ; 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 Th+1 -FREE EDGE DELETION is indeed W[1]-hard when parameterized by tw(G) alone. We resolve two additional open questions posed by Enright and Meeks (Algorithmica, 2018) concerning the complexity of Th+1 -FREE EDGE DELETION on planar graphs and Th+1 -FREE ARC DELETION. We prove that the Th+1 -FREE EDGE DELETION problem is NP-complete even when restricted to planar graphs. We also show that the Th+1 -FREE ARC DELETION problem is W[2]-hard when parameterized by the solution size on directed acyclic graphs.