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.