Deciding Graph Homomorphism is in general NP-Complete.

Are there any results which study this problem when the underlying graphs have algebraic structure (such as deciding homomorphisms from Cayley or Cayley coset graphs to other graphs with some definite structure as well)? In addition complexity results I am also interested in helpful algebraic and/or spectral techniques.


2 Answers 2


If $\mathcal{G}$ is a class of graphs with bounded treewidth, then the homomorphism problem from graphs in $\mathcal{G}$ is polynomial-time solvable. This can be generalized to the more general property of "graphs whose core has bounded treewidth."

Grohe proves a converse: if the cores of the graphs in $\mathcal{G}$ have unbounded treewidth, then the homomorphism problem from $\mathcal{G}$ is not polynomial-time solvable (assuming $FPT\neq W[1]$). Therefore, if you restrict the left-hand side graph to Cayley graphs etc., then what matters is whether the cores have bounded treewidth.


Note that this does not completely answer your question: in the result of Grohe, it is assumed that the right-hand side graph is arbitrary. You seem to be interested in results where the right-hand side graph is also restricted to some specific class of graphs.

  • $\begingroup$ Yes both the graphs have some structure. I am not just looking for complexity results. I am looking for algebraic aspects as well. $\endgroup$
    – Turbo
    Apr 24, 2012 at 16:38

Deciding if there is a graph homomorphism is easier than counting the number of (weighted) graph homomorphisms.

Weighted Case

For undirected target graphs $H$ (i.e. the number of weighted graph homomorphisms from an input graph $G$ to $H$), there is a dichotomy theorem.

Jin-Yi Cai, Xi Chen, Pinyan Lu. Graph Homomorphisms with Complex Values: A Dichotomy Theorem.

That is, every target graph $H$ either defines a #P-hard or polynomial time computable counting problem (see Theorem 1.1).

It is a bit difficult to explain which graphs $H$ define polynomial computable problems (see Theorem 5.7 for the statement and page 4 for the index of the conditions), but it is also polynomial time computable to decided if a target graph $H$ defines a easy problem (see Theorem 1.2).

The tractability follows from the ability to efficiently compute the exponential sum over a sequence of variables modulo $q$ that form a quadratic polynomial in the exponent of a $q$th root of unity, where $q$ is a prime power (see the beginning of section 12).

Unweighted Case

The unweighted case is much simpler. Below, I state Theorem 1.1 from the following paper.

Martin Dyer, Catherine Greehill. The complexity of counting graph homomorphisms. (Also this direct link to a free PDF.)

Theorem 1:

Let $H$ be a fixed graph. Then problem of counting $H$-colourings of graphs is #P-complete if $H$ has a connected component which is not a complete graph with all loops present or a complete bipartite graph with no loops present. Otherwise, the counting problem is in P.

  • $\begingroup$ The unweighed case is much simpler. I will update my answer with this information. $\endgroup$ Apr 30, 2012 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.