Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: The Graph Motif problem parameterized by the structure of the input
  graph   The Graph Motif problem was introduced in 2006 in the context of biological
networks. It consists of deciding whether or not a multiset of colors occurs in
a connected subgraph of a vertex-colored graph. Graph Motif has been mostly
analyzed from the standpoint of parameterized complexity. The main parameters
which came into consideration were the size of the multiset and the number of
colors. Though, in the many applications of Graph Motif, the input graph
originates from real-life and has structure. Motivated by this prosaic
observation, we systematically study its complexity relatively to graph
structural parameters. For a wide range of parameters, we give new or improved
FPT algorithms, or show that the problem remains intractable. For the FPT
cases, we also give some kernelization lower bounds as well as some ETH-based
lower bounds on the worst case running time. Interestingly, we establish that
Graph Motif is W[1]-hard (while in W[P]) for parameter max leaf number, which
is, to the best of our knowledge, the first problem to behave this way.

28
The categories of this paper are: alg-geom
20
The categories of this paper are: acc-phys
23
The categories of this paper are: solv-int
37
The categories of this paper are: supr-con
0
The categories of this paper are: hep-ph
30
The categories of this paper are: q-alg
2
The categories of this paper are: math
8
The categories of this paper are: hep-ex
36
The categories of this paper are: cmp-lg
27
The categories of this paper are: comp-gas
26
The categories of this paper are: bayes-an
16
The categories of this paper are: stat
32
The categories of this paper are: atom-ph
17
The categories of this paper are: q-fin
22
The categories of this paper are: chao-dyn
5
The categories of this paper are: gr-qc