8
$\begingroup$

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

Improve this question
$\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.
    Commented Jun 20, 2018 at 1:58
  • $\begingroup$ Yes. That is exactly what I want. $\endgroup$
    – Xiao-Gang Wen
    Commented 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$
    – Carlo Beenakker
    Commented Jun 20, 2018 at 7:28

3 Answers 3

Reset to default
10
$\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.

Improve this answer
$\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$
    – David Roberson
    Commented Jun 22, 2018 at 10:52
4
$\begingroup$

In the past few months, we have been working towards a SageMath library for exact counting graph homomorphisms, based on the proof of Prop. 1.6 from "Homomorphisms Are a Good Basis for Counting Small Subgraphs" by Radu Curticapean, Holger Dell, and Dániel Marx: The algorithm is deterministic and runs in time $\exp(O(k)) + poly(k) \cdot n^{tw(H) + 1}$ for counting the number of homomorphisms from graph $H$ to graph $G$, where $k = |V(H)|$, $n = |V(G)|$, and $tw(H)$ is the treewidth of $H$.

The library is recently released on GitHub: https://github.com/guojing0/count-graph-homs

We are also working on merging it into the SageMath codebase, so that users could use it in Sage directly.

Example:

Open your favourite terminal emulator and run the following commands:

git clone https://github.com/guojing0/count-graph-homs.git
cd count-graph-homs
sage -n

After running the above commands, you should see a SageMath (Jupyter) notebook open in your browser. You may try to run the following to see if the library is working correctly:

from standard_hom_count import GraphHomomorphismCounter

square = graphs.CycleGraph(4)
bip = graphs.CompleteBipartiteGraph(2, 4)

counter = GraphHomomorphismCounter(square, bip)
count = counter.count_homomorphisms()
print(count)

The correct count should be 128.

Improve this answer
$\endgroup$
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.)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .