10
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – T.... Apr 24 '12 at 16:38
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. This sounds like an interesting answer. I will look into the answer. $\endgroup$ – T.... Apr 29 '12 at 15:54
  • $\begingroup$ The unweighed case is much simpler. I will update my answer with this information. $\endgroup$ – Tyson Williams Apr 30 '12 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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