Is there any simple example to explain ullmann algorithm

Question

Im a freshman in learning the graph theory. Im learning the (sub)graph isomorphism now. there are two important algorithms: Ullmann's algorithm and vf2.

I have read the paper of Ullmann`s: An algorithm for Subgraph Isomorphism. I also googled it and google gave me a lot of applications of it, but I cannot understand the procedures of the algorithm.

Could you give me a simple explanation?

Ashram

Answer 1

This answer to a related question gives a source code of Ullmann's algorithm.

These slides give an example, but the main ingredient of the algorithm is mentioned only without an example on slide "Ullmann’s Algorithm V2".

So I will give an example below. We want to know whether GB has a subgraph isomorphic to GA. That is, we will be trying to map vertices of GA to vertices of GB so that edges of GA are mapped on edges of GB.

Note that both the original paper and the slides use a matrix, called M, but the code does not. That's because the matrix represents the same what possible_assignments[i] represent in the code. M[i][j] is 1 exactly if the i-th vertex can be mapped to the j-th vertex of GB. I will use candidates(u) etc. for the set of vertices of GB, where a vertex u of GB can be mapped.

First observation is that a vertex of GA can only be mapped to a vertex of GB of at least as large degree. So initially, candidates(u) = candidates(v) = {a,b,e,f,g}, candidates(w) = {f} and candidates of z are all the vertices of GB.

Now is the first time we do the "refine M" procedure, which is the main ingredient of the Ullmann's algorithm. That is, we check that whenever vertex x of GB is among candidates for a vertex y of GA, then every neighbor of y has at least one candidate among neighbors of x. If this check fails, then we remove x from candidates of y. We check for these removals until no further removals are possible.

For example, h is among candidates for z. However, w is a neighbor of z, but none of the neighbors of h (that is, g) is among cadidates(w)={f}. Therefore we will never be able to map z to h, because the edge {w,z} would be mapped to a non-edge. So we can safely remove h from candidates(z). The result of the refinement is: candidates(u) = candidates(v) = candidates(z) = {a,e,g} and candidates(w) = {f}.

Now we start backtracking.

We first try mapping u to a. That is, we set candidates(u) = {a} and remove a from the other candidate sets. Refine finds out that neither e nor g is a neighbor of a and so we remove e and g from candidates(v). This leaves candidates(v) empty and so we return from this branch; undoing the changes made to candidates.

Now, we try mapping u to e. Again, candidates(v) will end up empty.

Finally, we try mapping u to g with the same result.

We conclude that GA is not a subgraph of GB. Without having to try all the 8*7*6*5 assignments.

I forgot that Ullmann initially orders the vertices of GA in the order of decreasing degree. But it will not make much difference - we would only first find out that w can only be mapped to f and then we would continue branching on u with exactly the same results as we got.

Airsickness

great explanation! Do you have any idea what the running time might be about? – Jacqui

Let nA and nB be the number of vertices of GA and GB, respectively. In the worst case, we may need to backtrack through nearly all possible assignments and there are exponentially many of them; the exact number is nB*(nB-1)*...*(nB-nA+1)=nB!/(nB-nA)!. In the best case, no vertex of GB will have degree high enough for the first vertex of GA, and so the total time will be linear in the size of the input. Some estimates of the practical speed can be found e.g. in the paper "A Performance Comparison of Five Algorithms for Graph Isomorphism" by P Foggia, C Sansone and M Vento. – Airsickness