Given a graph $G=(V,E)$, a set $\mathcal{F}$ of forbidden subgraphs, we study $\mathcal{F}$-Free Edge Deletion, where the goal is to remove minimum number of edges such that the resulting graph does not contain any $F\in \mathcal{F}$ as a subgraph. For the parameter treewidth, the question of whether the problem is FPT has remained open. Here we give a negative answer by showing that the problem is W[1]-hard when parameterized by the treewidth, which rules out FPT algorithms under common assumption. Thus we give a solution to the conjecture posted by Jessica Enright and Kitty Meeks in [Algorithmica 80 (2018) 1857-1889]. We also prove that the $\mathcal{F}$-Free Edge Deletion problem is W[2]-hard when parameterized by the solution size $k$, feedback vertex set number or pathwidth of the input graph. A special case of particular interest is the situation in which $\mathcal{F}$ is the set $\mathcal{T}_{h+1}$ of all trees on $h+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 disease in transmission network. We prove that the $\mathcal{T}_{h+1}$-Free Edge Deletion problem is fixed-parameter tractable (FPT) when parameterized by the vertex cover number. We also prove that it admits a kernel with $O(hk)$ vertices and $O(h^2k)$ edges, when parameterized by combined parameters $h$ and the solution size $k$.
翻译:根据一个图形 $G= (V, E) $, 一个固定 $mathcal{F} 美元, 一个固定的被禁止的子图, 我们研究 $\ mathcal{F} $- fe- fe- fetion, 目标是删除最小边缘数, 这样产生的图形不会包含任何$F\ in $\ mathcal{Fnal{F} 美元作为子图。 对于参数树宽度, 问题是否为 FPT 。 这里我们给出了一个否定的答案, 以树宽度为参数时, 问题是 W[ 1 硬度 。 树宽度将 FPT 的算法限制在共同假设下, FPT 的算法程程 。 因此, 由 80 20 18 18 18 18 18 18 18 18 18 。 我们还证明 $ 美元 平面 平面 问题是 W[ 2 硬度 问题, 当答案以 美元, 平面 平面或路径为我们 平面 平面 平面 显示 美元 美元 。