Recognizing circulant graphs of prime order in polynomial time (Q1386147): Difference between revisions

A digraph can be regarded as a pair \((X;\gamma)\), where \(X\) is a finite set and \(\gamma\) is a binary relation on \(X\). The Weisfeiler-Leman algorithm in time \(O(| X|^3\log(| X|))\) yields the minimal coherent configuration \((X;\Gamma)\), where \(\Gamma\) contains \(\gamma\) [\textit{Babel, Baumann, Lüdecke} and \textit{Tinhofer}, STABCOL: Graph isomorphism testing based on the Weisfeiler-Leman algorithm. TUM-M9702, Munich, 45 p. (1997)]. There is an open problem to recognize the circulant property of digraphs \(X\) with an algorithm with time-complexity polynomial in \(X\). The authors present such an algorithm when \(| X| = p\), a prime, with time-complexity at most \(O(p^5\ln(p)^2)\). They start with the above coherent configuration (in this case, association scheme), and then utilize favorable facts on permutation groups and association schemes when \(| X|\) is a prime \(p\).