Timeline for What's the worst case for strongly regular graph's isomorphism algorithm?
Current License: CC BY-SA 4.0
26 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 6 at 9:51 | history | edited | Daniele Tampieri | CC BY-SA 4.0 |
Minor Math Jaxing
|
| Jan 6 at 0:54 | answer | added | shen lixing | timeline score: -1 | |
| Jul 24, 2022 at 7:18 | comment | added | Dima Pasechnik | "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 | |
| Jul 23, 2022 at 1:39 | history | edited | shen lixing | CC BY-SA 4.0 |
add some information
|
| Jul 23, 2022 at 1:32 | comment | added | shen lixing | @DimaPasechnik Bad news, after test, I found Cai-Immerman graphs defeat my algorithm. Thus I should edit my question to agree with my paper which claim that almost all graphs ' time complexity < $5n^2$ | |
| Jul 17, 2022 at 12:10 | comment | added | shen lixing | @DimaPasechnik I agree with you, though Cai-Immerman graphs are not strongly regular in general, it is tough for almost all algorithm. I try to modify my program to be able to handle graphs with complex label though algorithm's efficiency will come down . Within one week, answer will be there. Anyway I believe there is no polynomial algorithm for graph isomorphism. | |
| Jul 17, 2022 at 6:49 | comment | added | Dima Pasechnik | Cai-Immerman graphs are not strongly regular, in general. | |
| Jul 16, 2022 at 20:58 | history | edited | shen lixing | CC BY-SA 4.0 |
corrected spelling
|
| Jul 16, 2022 at 5:58 | comment | added | shen lixing | @DimaPasechnik Thank you very much! I like Sagemath, but it give me a surprise today, it can not relabel graphs as I edited in question. And as I observed one example that even if the graphs has 4960 nodes with 144115188075855872 automorphism_group().order(), according to my experiance, It can not become couterexample to my polynomial algorithm (except the graphs are strongly regular ). Please help me to relabel graph, I'am eager to know the test result. | |
| Jul 16, 2022 at 5:43 | history | edited | shen lixing | CC BY-SA 4.0 |
add some information
|
| Jul 15, 2022 at 9:55 | review | Close votes | |||
| Jul 20, 2022 at 3:04 | |||||
| Jul 15, 2022 at 9:41 | comment | added | Dima Pasechnik | you can generate these examples (Cai-Immerman graphs) in Sagemath: doc.sagemath.org/html/en/reference/graphs/sage/graphs/… | |
| Jul 15, 2022 at 9:34 | comment | added | Dima Pasechnik | 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. | |
| Jul 15, 2022 at 0:12 | history | edited | shen lixing | CC BY-SA 4.0 |
corrected spelling
|
| Jul 14, 2022 at 15:25 | history | edited | shen lixing | CC BY-SA 4.0 |
add some information
|
| Jul 14, 2022 at 13:35 | comment | added | shen lixing | @DimaPasechnik If you provide test set for such counterexamples, I am glad to test it . | |
| Jul 14, 2022 at 12:31 | comment | added | shen lixing | @DimaPasechnik your question is very good, the high efficiency is based on establishing equations ( select subgraphs) randomly and solve them easily, in other words, crossover classification of the two graphs' subgraph. Among 10^12 cases , no can defeat probability theory until now. If G and H are not isomorphic, for most cases, establishing equations not more than twice, we can see no solution for such equations, thus they are not isomorphic. Based on that, subgraph isomorphism algorithm is developed , it is more than 10000 times faster than one famous algorithm for difficult cases. | |
| Jul 14, 2022 at 10:00 | history | edited | shen lixing | CC BY-SA 4.0 |
corrected spelling
|
| Jul 14, 2022 at 8:47 | comment | added | Dima Pasechnik | 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. | |
| Jul 14, 2022 at 8:37 | comment | added | shen lixing | @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. | |
| Jul 14, 2022 at 8:19 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
edited body; edited tags
|
| Jul 14, 2022 at 8:15 | history | edited | shen lixing | CC BY-SA 4.0 |
corrected spelling
|
| Jul 14, 2022 at 7:50 | comment | added | Gerry Myerson | Also posted to solveforum.com/forums/threads/… (but what does PCT/CN2020/134861 mean?). | |
| Jul 14, 2022 at 1:08 | history | edited | shen lixing | CC BY-SA 4.0 |
corrected spelling
|
| Jul 14, 2022 at 1:02 | history | edited | shen lixing | CC BY-SA 4.0 |
corrected spelling
|
| Jul 14, 2022 at 0:40 | history | asked | shen lixing | CC BY-SA 4.0 |