Theory of Computing
-------------------
Title : The Complexity of Parity Graph Homomorphism: An Initial Investigation
Authors : John Faben and Mark Jerrum
Volume : 11
Number : 2
Pages : 35-57
URL : http://www.theoryofcomputing.org/articles/v011a002
Abstract
--------
Given a graph G, we investigate the problem of determining the
parity of the number of homomorphisms from G to some other fixed
graph H. We conjecture that this problem exhibits a complexity
dichotomy, such that all parity graph homomorphism problems are either
polynomial-time solvable or (+)P--complete, and provide a
conjectured characterisation of the easy cases.
We show that the conjecture is true for the restricted case in which
the graph H is a tree, and provide some tools that may be useful in
further investigation into the parity graph homomorphism problem, and
the problem of counting homomorphisms for other moduli.