On the Complexity of Identifying Strongly Regular Graphs
share
In this note, we show that Graph Isomorphism (GI) is not ^0-reducible to several problems, including the Latin Square Isotopy problem and isomorphism testing of several families of Steiner designs. As a corollary, we obtain that GI is not ^0-reducible to isomorphism testing of Latin square graphs and strongly regular graphs arising from special cases of Steiner 2-designs. We accomplish this by showing that the generator-enumeration technique for each of these problems can be implemented in β_2, which cannot compute Parity (Chattopadhyay, Torán, Wagner, ACM Trans. Comp. Theory, 2013).
READ FULL TEXT