Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Homomorphisms Are a Good Basis for Counting Small Subgraphs   We introduce graph motif parameters, a class of graph parameters that depend
only on the frequencies of constant-size induced subgraphs. Classical works by
Lov\'asz show that many interesting quantities have this form, including, for
fixed graphs $H$, the number of $H$-copies (induced or not) in an input graph
$G$, and the number of homomorphisms from $H$ to $G$.
  Using the framework of graph motif parameters, we obtain faster algorithms
for counting subgraph copies of fixed graphs $H$ in host graphs $G$: For graphs
$H$ on $k$ edges, we show how to count subgraph copies of $H$ in time
$k^{O(k)}\cdot n^{0.174k + o(k)}$ by a surprisingly simple algorithm. This
improves upon previously known running times, such as $O(n^{0.91k + c})$ time
for $k$-edge matchings or $O(n^{0.46k + c})$ time for $k$-cycles.
  Furthermore, we prove a general complexity dichotomy for evaluating graph
motif parameters: Given a class $\mathcal C$ of such parameters, we consider
the problem of evaluating $f\in \mathcal C$ on input graphs $G$, parameterized
by the number of induced subgraphs that $f$ depends upon. For every recursively
enumerable class $\mathcal C$, we prove the above problem to be either FPT or
#W[1]-hard, with an explicit dichotomy criterion. This allows us to recover
known dichotomies for counting subgraphs, induced subgraphs, and homomorphisms
in a uniform and simplified way, together with improved lower bounds.
  Finally, we extend graph motif parameters to colored subgraphs and prove a
complexity trichotomy: For vertex-colored graphs $H$ and $G$, where $H$ is from
a fixed class $\mathcal H$, we want to count color-preserving $H$-copies in
$G$. We show that this problem is either polynomial-time solvable or FPT or
#W[1]-hard, and that the FPT cases indeed need FPT time under reasonable
assumptions.

37
The categories of this paper are: supr-con
31
The categories of this paper are: ao-sci
14
The categories of this paper are: math-ph
12
The categories of this paper are: nucl-th
5
The categories of this paper are: gr-qc
3
The categories of this paper are: physics
28
The categories of this paper are: alg-geom
4
The categories of this paper are: cond-mat
9
The categories of this paper are: nlin
15
The categories of this paper are: nucl-ex
23
The categories of this paper are: solv-int
0
The categories of this paper are: hep-ph
21
The categories of this paper are: adap-org
18
The categories of this paper are: econ
8
The categories of this paper are: hep-ex
13
The categories of this paper are: quant-ph