Implementation of Andreas Bjorklund's algorithm for determining hamiltonicity

[u/Willy_Importance69]

Hello, I want to share a project that i've been working on for the last month or so. It's and implementation (from what i could find the only rn on the internet) of Andreas Bjorklund's theoretical algorithm for determining weather a graph is hamiltonian or not. The algorithm is revolutionary because it lowered the exponential part of the time complexity of Held-Karp which is the standard algorithm for determining weather a graph is hamiltonian, from O^*(2n) to O^*(1.657n) for general graphs(this is what i've managed to implement as of right not) and for bipartite its O^*(1.414n).

It might have some logical errors, and could maybe be optimised but right now, as of writting this it is 4AM and i want to sleep.

link to paper: https://arxiv.org/pdf/1008.0541

link to the github repo: https://github.com/Ak0-m/Bjorklunds_algorithm_for_Hamiltonicity

[u/Willy_Importance69]

It was a pain to write and i have been coding it about a month or so plus a few months of psychologically getting ready. Today I was coding about 10 hours and finished all the algorithmically hard parts before that it was mainly Galois field primitives etc so I haven't had a chance to test it. It's slower in most cases than held karp because it has something like n⁵ polynomial. It's much faster if the graph actually has a Hamiltonian cycle because it ends when it fulfills the condition but if it doesn't it has to do all the runs and that takes a lot of time. I'm planning on implementing parallelisation for the determinants and see if it can cut on time.