Display between graph and supplement

Question

I have two isomorphic graphs.

Given a self-completing graph G, is there a faster algorithm to find the mapping of vertices between Gand its complement

I think there should be a faster way, because we know that 2 graphs are isomorphic and complementary .

EDIT Sorry, I was more clear: I already know the VF2 algorithm, which has O (V ^ 2) time complexity at best and O (V! · V) at worst. This makes it difficult to calculate mappings for large graphs (1k vertices, 500k edges) that I work with.

I just asked if this particular case of graphs gives both isomorphic and additional , there is a faster solution.

Answer 1

This is an isomorphism problem for self-complementary graphs.

One would expect that an isomorphism problem would actually be easier to solve when limited to self-complementary diagrams or digraphs, because of their strong structural properties. He turns out, however [Colbourn and Colbourn 1978, 1979] that the isomorphism problem for self-sufficient graphs is polynomially equivalent to the general isomorphism problem; , , , , . SC-; , , ( 1,59). . O , ( ) , P , .

.97 : : . Alastair Farrugia 1999 .

http://www.alastairfarrugia.net/sc-graph/sc-graph-survey.pdf