VF2 graph isomorphism takes very long or is stuck

[Gábor Csárdi]

See the attached two graphs

library(igraph)
g1 <- read.graph("graph_first.txt", dir=FALSE)
g2 <- read.graph("graph_second.txt", dir=FALSE)
graph.isomorphic.vf2(g1, g2)

[Gábor Csárdi (gabor.csardi)]

Here is the second graph

[Tamás Nepusz (ntamas)]

Could be a particularly hard problem instance for VF2; it manages to match 48 vertices out of 70 and then keeps on backtracking. When the algorithm gets stuck, it is trying to match vertices of degree 4 with each other.

I guess that the VF2 algorithm makes an erroneous assignment very early and then it takes a long time until it manages to backtrack there.

[Tamás Nepusz (ntamas)]

Running since 48 hours and still counting. It would be interesting to check whether the original VF2 implementation behaves this way as well or not.

[Gábor Csárdi (gabor.csardi)]

Tamás, anything going on with this? I did some checks, too, and it seems that it just takes too long.

I could start a run, with a check that the algorithm is progressing (e.g. checking the mapping vector, and that every time we go down in the search tree, it advances), and let it run it for a couple of days......

[Tamás Nepusz (ntamas)]

No progress since then; I killed the process after a while and I'm pretty much convinced that the algorithm just takes too long (although I wonder why it takes so long when LAD can figure it out almost instantly). The only thing I worry about right now is whether it is possible for the algorithm to get stuck in an infinite loop where it traverses the same part of the search tree over and over again, and I'm afraid that putting in a counter won't help with that.

[Gábor Csárdi (gabor.csardi)]

It is not a counter. You have the matching vector, and you can imagine that this vector is a big number of base |V|+1, each element of the vector is one digit. If you matched 'm' vertices so far, then you only use the first 'm' digits from the vector, the rest is assumed to be zero. Then, as the algorithm progresses, that number must increase when you are stepping down in the search tree. When you are stepping up the tree, then the number temporarily decreases, but that is fine, because you cannot step up too many times before stepping down.

So if you always make sure that stepping down increases the matching vector, then, you avoid infinite loops.

If you know what I mean, sorry, this is quite dense.

[Tamás Nepusz (ntamas)]

Ah, I understand. (I thought that you intend to use a counter to count how many partial matches have been tried so far). Sounds reasonable so go ahead if you wish.

[Gábor Csárdi (gabor.csardi)]

It is actually more difficult than I thought, because the vertices are matched by a heuristic order, and this makes it hard(er) to enumerate the partially matching configurations.

So I suggest we postpone this to 0.7.

[Gábor Csárdi (gabor.csardi)]

The development of igraph has moved to github, so please do not comment on this bug here. You are of course welcome to comment on github, here:
https://github.com/igraph/igraph/issues/238