Finding a cycle of a given length can actually be done in time `O(e^k n^2.3)` where `k` is the length of the cycle, using the cool technique of color coding. B

Finding a cycle of a given length can actually be done in time `O(e^k n^2.3)` where `k` is the length of the cycle, using the cool technique of color coding. Basically, to find a cycle of length 6, you repeatedly color every node in one of 6 colors at random. Then you look for a cycle with all different colored nodes, which can be done efficiently using dynamic programming. You succeed in finding a particular 6 cycle exactly if each node in it has gotten a different color, but the chance of this is not bad. In the case of the OP it's even better, since there are probably many such cycles to find.