I am interested in knowing the best complexity upper bounds for the following graph isomorphism problems (best theoretical deterministic upper bound). For some of those I already have some references (which I mention) but they seem outdated (decades old). I expect more recent uppe bounds that improves the old ones.
--Isomorphism of (di)graphs of bounded valence. What is the best present upper bound complexity for these ? [[Update 24 may 2025. Babai, Kantor and Luks (FOCS 1983) gave an isomorphism test for graphs of bounded degree d of time n^O(d/ log d). In 2018, for maximum degree d the best isomorphism algorithm was n^O((log d)^c) time for constant c (Grohe, Neuen & Schweitzer, 2018). So for this the best known algorithms up to 2018 are non-uniform (constant depends on bound). Although they do not belong to this category it should be noted that at present strongly regular graphs has not a better upper bound than the general of Babai, while before this general quasi-polynomial bound there was much improvement for them. As this issue of bounded valence is clarified up to 2018 I am adding the following category]].
--Isomorphism of (di)graphs of fixed valence (d-regular). Maybe if you fix the valence the above bound for graphs of maximum valence d improves.[[Update 24 may 2025. I correct myself. This is included in Luks result. It is the same as for degree d-bounded]].
--Isomorphism of (di)graphs of valence 3. The best (well known) reference I have regarding this one is Luks,1982: Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time* and this is what he comments: The trivalent algorithm was presented here in a manner which clearly justifies the polynomial-time claim and which easily generalizes. However, with somewhat more effort, one can make several ad-hoc modifications which improve the efficiency. Our best algorithm for determining whether two connected n-vertex trivalent graphs are isomorphic requires O(n^5) steps. We update some of the remarks of Section 4. The O(n^5) bound for trivalent graphs (Section 4.1) was improved to O(n^4 log n) by C. Schnorr and A. Weber, to O(n^4) by C. Hoffman and, most recently, to O(n^3 log n) by Z. Galil, E. Luks, C. Schnorr, and A. Weber. It has rained a lot since 1982. When you fix the degree you can get an uniform algorithm. Maybe in 2025 this problem can be solved linearly ?. [[Update 24 may 2025. Regarding this category I have browsed Luks paper and I also have found a couple of recent theses (2012 and 2015) about this result. Several comments that I hope clarify the situation. First, I missinterpreted above comments: the result refers to graphs of degree at most 3 and not to graphs of degree of exact 3 or 3-regular. Second Luks method works by reducing this isomorphism problem to some problem on p-groups. For instance for case of valence 3 it reduces the problem to 2-groups. For cases of higher valence it will be a different (higher) p than 2. So higher degree means higher complexity: that´s what the non uniform algorithm above means. Theses clarify that up to 2015 there had not been progress on this front of bounded degree graphs. After that the one of 2018 already mentioned in a point above that improves Luks result]].
--Isomorphism of circulant (di)graphs. The best reference I have for this is: 2004. A SOLUTION OF THE ISOMORPHISM PROBLEM FOR CIRCULANT GRAPHS. M. MUZYCHUK. And this is what he comments. Thus we obtain an algorithm of complexity O(n^4).... A better algorithm is obtained if the key of a partition is used. In this algorithm we first compute the keys...A rough estimation shows that this procedure takes about O(n^2) operations. If the keys are different, then the graphs are not isomorphic. If...the running time of the algorithm is bounded by O(n^2). Another relevant paper is: 2003. CIRCULANT GRAPHS:RECOGNIZING AND ISOMORPHISM TESTING IN POLYNOMIAL TIME. S. A. EVDOKIMOV AND I. N. PONOMARENKO. However they don´t give concrete upper bounds, just n^O(1). [[Update 24 may 2025. Circulants are Cayley graphs of cyclic groups. Therefore their degree is unlimited as groups grow in size. Meaning that this general algorithm if for cases of unbounded degree. But the algorithm is not only polynomial but uniform. Update 25. I have founnd a 2017 paper from Muzychuk: FINDING A CYCLE BASE OF A PERMUTATION GROUP IN POLYNOMIAL TIME MIKHAIL MUZYCHUK AND ILIA PONOMARENKO. They refer to previous results about isomorphism of circulants: Finally, a cycle base technique was applied for polynomial-time recognizing and testing isomorphism of arbitrary circulant graphs [3, 11]. In particular, an efficient algorithm was proposed in [3] to construct a cycle base of the automorphism group of a graph. References 3 and 11 are the two already mentioned. So up to 2017, no progress in the general circulant case]].
--Isomorphism of 2-circulants (in general of d-circulants, i.e. isomorphism of d-generated circulants). I have no reference for this.[[Update 24 may 2025. In my view isomorphism of these and those in the next category also 2-generated should be able to be done in log time (maybe lower complexity,i.e. constant); just an impression after having researched shortly isomorphism of a special 2-generated case of direct products, that is next category]]. [[Update 25 may 2025. Most of the literature of isomorphism problem of Cayley (di)graphs focus on the (D)CI-property. And it turns out that circulants are 2-DCI groups (2-DCI means 2-generated circulants digraphs). When a group has the (D)CI property isomorphism problem is easier, but I don´t know how this translates into computation and concrete complexity bounds (which is what interest me the most). The reference for this resulta is L. Sun, Isomorphisms ofcirculants with degree 2, J. Beijing Ins. Technol. 9 (1984) 42 – 46 which I have not found online. Of course it would be interesting to know the situation for d-generated case. Already for the 3-generated case there are cyclic groups that does not have the DCI property. A very recent survey about this line of research is: 2025 CYCLIC m-DCI-GROUPS AND m-CI-GROUPS ISTVAN KOVACS AND LUKA SINKOVEC. It is important to note that DCI and CI are not equivalent. Finally I found a reference that refers specifically to the 2-generated case and is algorithmic in approach: Isomorphism testing for circulant graphs Cn(a, b). Sara Nicoloso ∗ Ugo Pietropaoli March 10, 2010 This is their summary: The computational complexity of applying this theorem depends on the complexity of computing the four gcd’s and that of twice solving the linear congruence (2) to determine the two block-jumps. This can be done in O(log n) elementary operations, by Euclid’s algorithm [9] (in an arithmetic complexity model). ** The mapping function between two isomorphic Cn(a, b) and Cn(a′, b′) can be constructed in linear time**They think that their method can be applied to other d-generated cases, but they do not address it in this paper. This result macht my expectations for 2-generated, as my result for the special case of a 2-generated special direct product is very similar to this: to test isomorphism you just have to check if the value of two parameters of each of the two digraphs are the same (therefore 4 values), and the four parameter values can be obtained very directly. However I have not analyzed yet the method froma computational complexity point of view. With this I consider the 2-generated circulant question answered. Still interested in other concrete d-generated cases]].
--Isomorphism of direct product of 2 cycles (for ZnxZm, with n and m not coprimes and n divides m; i.e. cases not "reducible" to circulants). I have a couple of references relevant for this, but again they don´t give concrete bounds so I do not mention them. I made a recent question about these graphs in this same platform and I mention them there.[[Update 25 may 2025. For completeness I will comment here about the two references relevant for this category. The firste is of theoretical interest: 1998. On isomorphisms of connected Cayley graphs Cai Heng Li, Theorem 4.2 1), which I copy bellow:
Theorem 4.2. Suppose that G is an abelian group and that p is the least prime divisor of |G|. Then: (1) G is a connected p-DCI-group; (2) if G is a p-group then G is a connected 2p-CI-group.
That means that many (but not all) nof the 2-generated direct products of two cicles are 2-DCI groups. Also many circulants, as he refers to abelian. However fot these there is the more general result mentioned in previous category. But no algorithm nor bounds (at least explicit).
The second reference is more practical and more specialized in a kind of groups: 2017. RECOGNIZING AND TESTING ISOMORPHISM OF CAYLEY GRAPHS OVER AN ABELIAN GROUP OF ORDER 4p IN POLYNOMIAL TIME. ROMAN NEDELA AND ILIA PONOMARENKO. From the paper: Now we are ready to present the main results of the paper. Theorem 1.1. For an abelian group G of order n = 4p with prime p, the Problems CRG and CGI can be solved in time poly(n). There are exactly two non-isomorphic abelian groups of order 4p: the cyclic group C4p and the group E4×Cp, where E4 = C2×C2 is the Klein group. In the former case, Theorem 1.1 follows from [4]. In the latter case, G is a CI-group [11, Theorem 1.2] and hence every graph has at most one Cayley representation over G (up to equivalence). Thus Theorem 1.1 is an immediate consequence of the following theorem. Theorem 1.2. Given a graph X with n = 4p vertices (p is a prime), one can test in time poly(n) whether X is isomorphic to a Cayley graph over the group G = E4 × Cp and (if so) find a Cayley representation of X over G within the same time. Probably there are more results regarding direct products of more than 2 cycles (i.e d-generated) that of course I would be interested in knowing]]
I have seen that there are many families of graphs for which isomorphism problems are of low complexity. For instance for planar this problem is L-complete. But I am interested mainly in variation of complexity of this problem with degree and symmetry. Regarding this it should be noted that isomorphism problem for regular graphs is GI-Complete. As far as I know nobody as shown the same for vertex transitive graphs, but many experts think that this won´t help neither (for Cayley graphs we have already commented).
If you have some references old or updated that I have not mentioned for any of the aforementioned problems (even if not for all) it would be great. Thanks in advance for any comment.
