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.