Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Counting Homomorphisms to Trees Modulo a Prime   Many important graph theoretic notions can be encoded as counting graph
homomorphism problems, such as partition functions in statistical physics, in
particular, independent sets and colourings. In this article we study the
complexity of $\#_p\mathsf{H}$OMS$\mathsf{T}$O$H$, the problem of counting
graph homomorphisms from an input graph to a graph $H$ modulo a prime number
$p$. Dyer and Greenhill proved a dichotomy stating that the tractability of
non-modular counting graph homomorphisms depends on the structure of the input
graph. Many intractable cases in non-modular counting become tractable in
modular counting due to the common phenomenon of cancellation. However, in
subsequent studies on counting modulo $2$ the influence, the structure of $H$
has on the tractability, was shown to persist, yielding similar dichotomies.
  Our main result shows that for every tree $H$ and every prime $p$ the problem
$\#_p\mathsf{H}$OMS$\mathsf{T}$O$H$ is either polynomial time computable or
$\#_p\mathsf{P}$-complete. This addresses the conjecture of Faben and Jerrum
stating this dichotomy for every graph $H$ when counting modulo 2. In order to
prove this result, we study the structural properties of a homomorphism. As an
important interim, this study yields a dichotomy for the problem of weighted
counting independent sets in a bipartite graph modulo some prime $p$. Our
results are the first suggesting that such dichotomies hold not only for the
one-bit functions of the modulo~2 case but for the modular counting functions
of all primes $p$.

3
The categories of this paper are: physics
24
The categories of this paper are: dg-ga
35
The categories of this paper are: mtrl-th
6
The categories of this paper are: astro-ph
33
The categories of this paper are: plasm-ph
28
The categories of this paper are: alg-geom
15
The categories of this paper are: nucl-ex
34
The categories of this paper are: chem-ph
0
The categories of this paper are: hep-ph
26
The categories of this paper are: bayes-an
36
The categories of this paper are: cmp-lg
11
The categories of this paper are: hep-lat
5
The categories of this paper are: gr-qc
30
The categories of this paper are: q-alg
19
The categories of this paper are: eess
9
The categories of this paper are: nlin