Graph Homomorphism using Python

Question

My idea is to write a python program which would take as arguments two finite simple undirected graphs say G,H and returns the number hom(G,H) of graph homomorphisms from G to H.

Examples: If G=K_1 (one-vertex graph) then hom(G,H) equals the number of vertices of H. If G=K_2 (or equivalently, P_2), then hom(G,H) = 2 times the number of edges of H.

Can anyone please help me out? Thanks.

Answer 1

In general it's NP-hard. If the graph G has n vertices and the graph H has m vertices, a naive approach could be to check all n^m possible assignment functions between the two graphes.

This is equivalent to do m chained loops over range(n).

I know two ways to do it in python:

1)You can generate m lists [1...n] and use itertools.product to get the cartesian product between these lists.

2)You can generate a string with these chained loops code and execute it in python with the exec built-in function.

If you use the first solution, it's highly parallelizable. So you can speed up quite a bit.

An implementation of the first idea without parallelization would be something like this:

from itertools import product

def verify(G, H, f):
   homomorphism = True

   for edge in G:
       if not ((f[edge[0]], f[edge[1]]) in H):
           homomorphism = False
           break

   return homomorphism

def solve(G, H, n, m):
   rangeG = [i for i in range(n)]
   assignments = list(product(rangeG, repeat=m))
   cnt = 0

   for f in assignments:
       if verify(G, H, f):
           cnt += 1

   return cnt

Here the graphs G and H are stored as a set of tuples. The tuples represent the edges. This representation is very convenient to test the homomorphism condition and to apply assignment functions in a fast way. The parameters n and m are the number of vertices in each graph.

For example, if you want G = S4 and H = P4 it would be something like this: G = {(0, 1), (1, 0), (0, 2), (2, 0), (0, 3), (3, 0)} and H = {(0, 1), (1, 0), (1, 2), (2, 1), (2, 3), (3, 2)}. Then you call the function solve(G, H, 4, 4).

I tested it with some examples of the section 2.3 of this paper and it seems to be working well.

As I said, the speed can be improved a lot with parallelization. This code is parallelizable almost everywhere. It needs some testing to see what is worth to execute in parallel.