Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Edge Deletion to Restrict the Size of an Epidemic   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$.

2
The categories of this paper are: math
10
The categories of this paper are: q-bio
0
The categories of this paper are: hep-ph
16
The categories of this paper are: stat
18
The categories of this paper are: econ
32
The categories of this paper are: atom-ph
15
The categories of this paper are: nucl-ex
30
The categories of this paper are: q-alg
7
The categories of this paper are: hep-th
17
The categories of this paper are: q-fin
35
The categories of this paper are: mtrl-th
36
The categories of this paper are: cmp-lg
11
The categories of this paper are: hep-lat
24
The categories of this paper are: dg-ga
6
The categories of this paper are: astro-ph
9
The categories of this paper are: nlin