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

<p>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.</p>

<p><a href="http://dl.acm.org/authorize?951212">http://dl.acm.org/authorize?951212</a></p>

<p>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.</p>

CC BY-SA 3.0
2012-04-24T16:38:10.977Z
Yes both the graphs have some structure. I am not just looking for complexity results. I am looking for algebraic aspects as well.
Turbo
CC BY-SA 3.0
2012-04-24T09:16:02.800Z
2012-04-24T09:16:02.800Z
Daniel Marx
<p>Deciding if there is a graph homomorphism is easier than counting the number of (weighted) graph homomorphisms.</p>
<h2>Weighted Case</h2>
<p>For undirected target graphs <span class="math-container">$H$</span> (i.e. the number of weighted graph homomorphisms from an input graph <span class="math-container">$G$</span> to <span class="math-container">$H$</span>), there is a dichotomy theorem.</p>
<p>Jin-Yi Cai, Xi Chen, Pinyan Lu. <a href="http://pages.cs.wisc.edu/%7Ejyc/papers/Graph-Homo-Dichotomy.pdf" rel="nofollow noreferrer">Graph Homomorphisms with Complex Values: A Dichotomy Theorem</a>.</p>
<p>That is, every target graph <span class="math-container">$H$</span> either defines a #P-hard or polynomial time computable counting problem (see Theorem 1.1).</p>
<p>It is a bit difficult to explain which graphs <span class="math-container">$H$</span> 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 <span class="math-container">$H$</span> defines a easy problem (see Theorem 1.2).</p>
<p>The tractability follows from the ability to efficiently compute the exponential sum over a sequence of variables modulo <span class="math-container">$q$</span> that form a quadratic polynomial in the exponent of a <span class="math-container">$q$</span>th root of unity, where <span class="math-container">$q$</span> is a prime power (see the beginning of section 12).</p>
<h2>Unweighted Case</h2>
<p>The unweighted case is much simpler. Below, I state Theorem 1.1 from the following paper.</p>
<p>Martin Dyer, Catherine Greehill. <a href="http://onlinelibrary.wiley.com/doi/10.1002/1098-2418%28200010/12%2917:3/4%3C260::AID-RSA5%3E3.0.CO;2-W/abstract;jsessionid=44DB8EBE86DB2E1E15B90C505630AFC2.d01t01" rel="nofollow noreferrer">The complexity of counting graph homomorphisms</a>. (Also this direct <a href="http://pages.cs.wisc.edu/%7Ejyc/880/Dyer-Greenhill.pdf" rel="nofollow noreferrer">link</a> to a free PDF.)</p>
<h3>Theorem 1:</h3>
<p>Let <span class="math-container">$H$</span> be a fixed graph. Then problem of counting <span class="math-container">$H$</span>-colourings of graphs is #P-complete if <span class="math-container">$H$</span> 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.</p>

CC BY-SA 3.0
2012-04-30T13:05:07.333Z
The unweighed case is much simpler. I will update my answer with this information.
Tyson Williams
CC BY-SA 3.0
2012-04-29T14:45:17.620Z
2012-04-30T16:09:24.813Z
2020-06-17T09:38:08.363Z
Tyson Williams
<p>Deciding Graph Homomorphism is in general NP-Complete.</p>

<p>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.</p>

<cc.complexity-theory><graph-theory><co.combinatorics>
Deciding graph homomorphism
Turbo
# Deciding graph homomorphism

(Asked by: username_0 on 2012-04-23)

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.

**Tags:** cc.complexity-theory, graph-theory, co.combinatorics


---

## 2 answers

### Answer by username_1 on 2012-04-24. Score: 9

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.

<http://dl.acm.org/authorize?951212>

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.

> **Comments:**
> **username_0**: Yes both the graphs have some structure. I am not just looking for complexity results. I am looking for algebraic aspects as well.  

---

### Answer by username_2 on 2012-04-29. Score: 5

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](http://pages.cs.wisc.edu/%7Ejyc/papers/Graph-Homo-Dichotomy.pdf).

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](http://onlinelibrary.wiley.com/doi/10.1002/1098-2418%28200010/12%2917:3/4%3C260::AID-RSA5%3E3.0.CO;2-W/abstract;jsessionid=44DB8EBE86DB2E1E15B90C505630AFC2.d01t01). (Also this direct [link](http://pages.cs.wisc.edu/%7Ejyc/880/Dyer-Greenhill.pdf) 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.

> **Comments:**
> **username_2**: The unweighed case is much simpler. I will update my answer with this information.  

---

