5
$\begingroup$

I would like to ask is there a computer program for counting graph homomorphisms?

$\endgroup$
3
  • $\begingroup$ What are the inputs and outputs? For instance, do you want to input two graphs $G,H$ and want as an output the number of homomorphisms from $G$ to $H$? $\endgroup$
    – j.c.
    Jun 20, 2018 at 1:58
  • $\begingroup$ Yes. That is exactly what I want. $\endgroup$ Jun 20, 2018 at 2:53
  • 1
    $\begingroup$ Graph.has_homomorphism_to in SAGE finds a homomorphism if there is one; an algorithm to find all homomorphisms does not seem to be available. $\endgroup$ Jun 20, 2018 at 7:28

2 Answers 2

9
$\begingroup$

EDIT: I have since found that the Digraphs package sometimes counts homomorphisms incorrectly. Perhaps this problem has been fixed in more recent versions though. I use Minion for counting homomorphisms instead.

The Digraphs package for GAP has several functions for finding homomorphisms of various types between graphs, including functions that will find all such homomorphisms, or all homomorphisms up to symmetries of the target graph. Once you have them all you can just count them to find the number. I really recommend this package, it seems to perform very well. For instance its chromatic number routine seems to be much faster than the chromatic number routine in SAGE.

$\endgroup$
1
  • 2
    $\begingroup$ I should probably also have mentioned Minion (constraintmodelling.org/minion), which is a more general constraint solver that you can use for finding and counting homomorphisms. I haven't used it much for this myself but I've heard it is also fast. I've been happy with how fast it is for other things. $\endgroup$ Jun 22, 2018 at 10:52
2
$\begingroup$

igraph (available for python, R and C) has a function count_subgraph_isomorphisms. Of course, this function only counts the injective graph homomorphisms.

Together with Carlo Beenakker's suggestion, one could of do the following:

  • Given a graph $G$, iterate over all isomorphism classes of smaller graphs $G'$ with fewer vertices.
  • If SAGE says that there is a homomorphism $G\to G'$, then compute the number of subgraph isomorphisms $G'\to H'$.
  • Sum up to obtain the number of all homomorphisms $G\to H'$.

(To iterate over all isomorphism classes, iterate over all graphs and check whether there is an isomorphism to some graph that was already visited.)

$\endgroup$

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.