2
$\begingroup$

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.

Improve this question
$\endgroup$
12
  • $\begingroup$ Also posted to solveforum.com/forums/threads/… (but what does PCT/CN2020/134861 mean?). $\endgroup$
    – Gerry Myerson
    Commented Jul 14, 2022 at 7:50
  • $\begingroup$ @GerryMyerson Thank you for post it at other place. The Patent Cooperation Treaty (PCT) . By search PCT/CN2020/134861 on patentscope.wipo.int/search/en/search.jsf, you can find translated versions of abstract from original apply in Chinese. But the offical translation is very bad done by machine. $\endgroup$
    – shen lixing
    Commented Jul 14, 2022 at 8:37
  • 2
    $\begingroup$ How does the algorithm in question perform on the graphs from Cai, JY., Fürer, M. & Immerman, N. An optimal lower bound on the number of variables for graph identification. Combinatorica 12, 389–410 (1992). doi.org/10.1007/BF01305232 They provide counterexamples to all the claimed in the past polynomial time complexity graph isomorphism algorithms. $\endgroup$
    – Dima Pasechnik
    Commented Jul 14, 2022 at 8:47
  • 1
    $\begingroup$ The potential counterexamples are described in the paper I cited. From what you wrote, it appears to me that your algorithm is actually just a randomised heuristic. No amount of experiments can show you have an algorithm. $\endgroup$
    – Dima Pasechnik
    Commented Jul 15, 2022 at 9:34
  • 1
    $\begingroup$ "almost all" graphs - it's known, I think, that almost all graphs have simple spectrum of the adjacency matrix, and for such a case there is an old polynomial time algorithm by Babai, Grigoriev, and Mount doi.org/10.1145/800070.802206 $\endgroup$
    – Dima Pasechnik
    Commented Jul 24, 2022 at 7:18

1 Answer 1

Reset to default
-1
$\begingroup$

Surprised to know there are two $O(n^3)$ isomorphic algorithms for simple and undirected graphs based on distance matrix.

DOI 10.16383/j.aas.c230025. Wang Zhuo, Wang Cheng-Hong "Isomorphism determination methods for simple undirected graphs", Acta Automatica Sinica, 2023, 49(9): 1878-1888

After read it carefully, a much simpler method is invented based on $$ Fg :=Ag + M + r \cdot I $$ where

  • $Ag$ is the adjacency matrix,
  • $M$ is a $n\times n$ matrix whose entries are equal to $m$
  • $I$ is the identity matrix,
  • $m$, $r$ are free variables.

Under the above conditions, then $$ \det(Fg) = \det(Fh) \iff g\text{ and }h\text{ are isomorphic.} $$ Note that

  • this is true for all undirected graphs (except for one unknown case: $g$ has different number loop for nodes).
  • It's similar to Jones polynomial generalized to HOMFLY for knot theory (by introducing a second variable $m$).

Though it is strong, but for digraphs, it is not always true even with more constrains.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Is $M$ a matrix with every element equal to $m$? If so your claim fails for every pair of graphs that are cospectral with cospectral complements. There are many such pairs, for example any pair of cospectral regular graphs. $\endgroup$
    – Brendan McKay
    Commented Jan 6 at 1:54
  • 1
    $\begingroup$ The DOI cannot be resolved: I added a direct link to the cited paper, though it may get "old". $\endgroup$
    – Daniele Tampieri
    Commented Jan 6 at 9:51
  • $\begingroup$ @BrendanMcKay Thank you, you are right. There is a gap between my "prove". $\endgroup$
    – shen lixing
    Commented Jan 7 at 3:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .