Cai-Furer-Immerman showed that the W-L(Weisfeiler-Lehman ) hierarchy cannot distinguish general graphs except at linear dimension.
Even besides CFI's result, there is good reason to believe that purely combinatorial methods cannot work for general graphs. Even for the "bounded parameter" families for which we have polynomial-time algorithms, the group-theory method is generally required.
Furthermore, the "algebraic structure" of the GI problem seems essential to its potential tractability, since every generalization of GI that destroys the algebraic structure is NP-complete.
But I can not find any error in this quasi-polynomial claim, which proposition is wrong?
The algorithm does not depend on W-L method entirely though .
This post is motivated by this query .
Link of the claim :'Quasi polynomial claim for a restricted class Graph Isomorphism'
To select a couple things out of many to pick on:
Prop 2.4: The proof begins by saying "To determine whether $G \simeq H$, try all possible permutations of $G$. Assume $G \simeq H$. It will take $T(n)$ number of permutations necessary to reorder $G$ exactly like $H$ for $n$ vertices, if they are isomorphic." Where does this $T(n)$ number come from? Is this how they are defining it? There are $n!$ possible permutations. It also talks about "trying all possible $n$ vertices of $G$ as the $n$th vertex of $H$", it is not clear what this means. You can put vertex $i$ from $G$ in position $j$ and test if that can be extended to an isomorphism? It is not well explained, requires permutations of other vertices to see if it will work, and it is possible that many vertices can be put here with the local structure carrying over, but not extending to an isomorphism. All the surrounding context suggests there are deep problems related to the evaluation of the complexity.
Prop 2.5: This is essentially only proved for the special example given earlier in the paper. Also, it does not address the complexity involved in actually partitioning the graph as described in the method.
Another big red flag is the title. It states that this is the number of matrices to check. But what is the complexity of checking each matrix? It is not a constant, it will depend on $n$.
The most basic way to test is to write an implementation of the algorithm. Does it actually detect that two isomorphic graphs are isomorphic?