Software for testing graph homomorphism

Question

I have graphs $G_k$ and $H_k$ with $|\mathcal{V}(G_k)|=|\mathcal{V}(H_k)|^{2k}=n^{2k}$ with $k\in\Bbb N$ that pass sanity checks such as no-homomorphism lemma. Are there free and easy to use tools to test graph homomorphism from $G$ to $H$?

Answer 1

The best way (in terms of laziness) is to use the freely available tool Sage which has the best support for graph theory.

Example

sage: G = graphs.PetersenGraph()
sage: G.has_homomorphism_to(graphs.CycleGraph(5))
False
sage: G.has_homomorphism_to(graphs.CompleteGraph(5))
{0: 0, 1: 1, 2: 0, 3: 1, 4: 2, 5: 1, 6: 0, 7: 2, 8: 2, 9: 1}

Answer 2

One approach would be to use a SAT solver.

Introduce a boolean variable $x_{t,v}$ for each vertex $t$ from $G$ and each vertex $v$ from $H$. The intuition is that $x_{t,v}$ will be true if the homomorphism maps $t \mapsto v$. (Of course, if you have a smaller candidate set of vertices that $t$ could map to -- maybe narrowed down using degree considerations or other local criteria -- then you can reduce the number of boolean variables accordingly. This kind of preprocessing might improve the efficiency of this approach significantly.)

Next, add two kinds of clauses/constraints:

• Add some clauses to require that this mapping forms a graph homomorphism. In particular, for each edge $(t,u) \in E(G)$, add the constraint

  $$\bigvee_{(v,w) \in E(H)} (x_{t,v} \land x_{u,w}).$$

  (You can convert this to 3CNF using the standard Tseitin transform.)

• Add some clauses to require that each vertex $t$ from $G$ maps to exactly one vertex $v$ from $H$. There are a number of standard methods for encoding this constraint. One simple way is, for each vertex $t \in V(G)$, add the clause

  $$\bigvee_{v \in V(H)} x_{t,v}$$

  and the clause

  $$\bigwedge_{v,w \in V(H)} (\neg x_{t,v} \lor \neg x_{t,w}).$$

Then, you can use any standard SAT solver. I don't know how well it will work in practice, but you could give it a try and see how it works out.

---

In the research literature, the graph homomorphism problem has been studied extensively for graphs with special properties (e.g., where $H$ is a clique, whre $H$ has bounded treewidth, and so on). If you know something special about the structure of your graphs, it may be possible to find better algorithms for your problem. For general graphs, this problem is known to be NP-hard.