Return to Question

A new algorithm of Graph Isomorphism is invented by PCT/CN2020/134861, roughly speaking time complexity $\leqslant5n^2$ except for regular graph, automorphism group can be known as by-product. Peer reviewed paper can be downloaded from www.getpaperfree.com by search "同构", it is written in Chinese.

Except strongly regular graph, all other regular graph's isomorphism can be decided in $O(n^3)$.

After 2 years' hard work, though I am almost sure that time complexity $\lt\lt O(n^{\ln n})$ when $n$ is big enough for all graphs, time complexity $\leqslant O(n^5)$ for almost all strongly regular graphs, , fail to know what's the worst case.

If you know a good classification of strongly regular graphs or other useful algorithm for them, please answer the question. Thank you!

*** update CaiFurerImmermanGraph defeat my algorithm after test, but my original paper claims that almost all graphs has less than $5n^2$ time complexity , weaker than the claim in question ***

A new algorithm of Graph Isomorphism is invented by PCT/CN2020/134861, roughly speaking time complexity $\leqslant5n^2$ except for regular graph, automorphism group can be known as by-product. Peer reviewed paper can be downloaded from www.getpaperfree.com by search "同构", it is written in Chinese.

Except strongly regular graph, all other regular graph's isomorphism can be decided in $O(n^3)$.

After 2 years' hard work, though I am almost sure that time complexity $\ll O(n^{\ln n})$ when $n$ is big enough for all graphs, time complexity $\leqslant O(n^5)$ for almost all strongly regular graphs, fail to know what's the worst case.

If you know a good classification of strongly regular graphs or other useful algorithm for them, please answer the question. Thank you!

Update. CaiFurerImmermanGraph defeat my algorithm after test, but my original paper claims that almost all graphs has less than $5n^2$ time complexity, weaker than the claim in question.

A new algorithm of Graph Isomorphism is invented by PCT/CN2020/134861, roughly speaking time complexity $\leqslant5n^2$ except for regular graph, automorphism group can be known as by-product. Peer reviewed paper can be downloaded from www.getpaperfree.com by search "同构", it is written in Chinese.

Except strongly regular graph, all other regular graph's isomorphism can be decided in $O(n^3)$.

After 2 years' hard work, though I am almost sure that time complexity $\lt\lt O(n^{\ln n})$ when $n$ is big enough for all graphs, time complexity $\leqslant O(n^5)$ for almost all strongly regular graphs, , fail to know what's the worst case.

If you know a good classification of strongly regular graphs or other useful algorithm for them, please answer the question. Thank you!

*** update including test code for potential counterexamples, but Sagemath failed to relabel graphs, confused***

import time 
G = graphs.RandomGNP(20,0.4)
CFI, p = graphs.CaiFurerImmermanGraph(G)
H, r =  graphs.CaiFurerImmermanGraph(G,twisted = true)
print(H.degree_sequence() == CFI.degree_sequence())
print(H.automorphism_group()== CFI.automorphism_group())
print(H.automorphism_group().order())
n = H.order()
CFI.relabel(range(n))
Mg = dict()
for i in CFI.vertex_iterator():
    Mg[i] = set(CFI.neighbors(i))
H.relabel(range(n))
Mk = dict()
for i in H.vertex_iterator():
    Mk[i] = set(H.neighbors(i))
print (time.ctime())
print(iso(Mg,Mk,set(range(n)),set(range(n))))
print (time.ctime())
print(H.is_isomorphic(CFI))
print (time.ctime())

A new algorithm of Graph Isomorphism is invented by PCT/CN2020/134861, roughly speaking time complexity $\leqslant5n^2$ except for regular graph, automorphism group can be known as by-product. Peer reviewed paper can be downloaded from www.getpaperfree.com by search "同构", it is written in Chinese.

Except strongly regular graph, all other regular graph's isomorphism can be decided in $O(n^3)$.

After 2 years' hard work, though I am almost sure that time complexity $\lt\lt O(n^{\ln n})$ when $n$ is big enough for all graphs, time complexity $\leqslant O(n^5)$ for almost all strongly regular graphs, , fail to know what's the worst case.

If you know a good classification of strongly regular graphs or other useful algorithm for them, please answer the question. Thank you!

*** update CaiFurerImmermanGraph defeat my algorithm after test, but my original paper claims that almost all graphs has less than $5n^2$ time complexity , weaker than the claim in question ***

A new algorithm of Graph Isomorphism is invented by PCT/CN2020/134861, roughly speaking time complexity $\leqslant5n^2$ except for regular graph, automorphism group can be known as by-product. Peer reviewed paper can be downloaded from www.getpaperfree.com by search "同构", it is written in Chinese.

Except strongly regular graph, all other regular graph's isomorphism can be decided in $O(n^3)$.

After 2 years' hard work, though I am almost sure that time complexity $\lt\lt O(n^{\ln n})$ when $n$ is big enough for all graphs, time complexity $\leqslant O(n^5)$ for almost all strongly regular graphs, , fail to know what's the worst case.

If you know a good classification of strongly regular graphs or other useful algorithm for them, please answer the question. Thank you!

*** update including test code for potential counterexamples, but Sagemath failed to relabel graphs, confused***

import time 
G = graphs.RandomGNP(20,0.4)
CFI, p = graphs.CaiFurerImmermanGraph(G)
H, r =  graphs.CaiFurerImmermanGraph(G,twisted = true)
print(H.degree_sequence() == CFI.degree_sequence())
print(H.automorphism_group()== CFI.automorphism_group())
print(H.automorphism_group().order())
n = H.order()
CFI.relabel(range(n))
Mg = dict()
for i in CFI.vertex_iterator():
    Mg[i] = set(CFI.neighbors(i))
H.relabel(range(n))
Mk = dict()
for i in H.vertex_iterator():
    Mk[i] = set(H.neighbors(i))
print (time.ctime())
print(iso(Mg,Mk,set(range(n)),set(range(n))))
print (time.ctime())
print(H.is_isomorphic(G))
print (time.ctime())

A new algorithm of Graph Isomorphism is invented by PCT/CN2020/134861, roughly speaking time complexity $\leqslant5n^2$ except for regular graph, automorphism group can be known as by-product. Peer reviewed paper can be downloaded from www.getpaperfree.com by search "同构", it is written in Chinese.

Except strongly regular graph, all other regular graph's isomorphism can be decided in $O(n^3)$.

After 2 years' hard work, though I am almost sure that time complexity $\lt\lt O(n^{\ln n})$ when $n$ is big enough for all graphs, time complexity $\leqslant O(n^5)$ for almost all strongly regular graphs, , fail to know what's the worst case.

If you know a good classification of strongly regular graphs or other useful algorithm for them, please answer the question. Thank you!

*** update including test code for potential counterexamples, but Sagemath failed to relabel graphs, confused***

import time 
G = graphs.RandomGNP(20,0.4)
CFI, p = graphs.CaiFurerImmermanGraph(G)
H, r =  graphs.CaiFurerImmermanGraph(G,twisted = true)
print(H.degree_sequence() == CFI.degree_sequence())
print(H.automorphism_group()== CFI.automorphism_group())
print(H.automorphism_group().order())
n = H.order()
CFI.relabel(range(n))
Mg = dict()
for i in CFI.vertex_iterator():
    Mg[i] = set(CFI.neighbors(i))
H.relabel(range(n))
Mk = dict()
for i in H.vertex_iterator():
    Mk[i] = set(H.neighbors(i))
print (time.ctime())
print(iso(Mg,Mk,set(range(n)),set(range(n))))
print (time.ctime())
print(H.is_isomorphic(CFI))
print (time.ctime())