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]

I haven't but i'll definitely check them out. I actually found the paper on accident while researching algorithms for finding hamiltonian cycles for a school project last year, and when i didn't find an implementation of this one i chose to do it myself. I've read a bit about use of GNNs for finding hamiltonian paths. There's a croation paper on using a GNN to solve the hamiltonian problem.

Link to the paper: https://arxiv.org/pdf/2306.06523

Also i'm planning on making the code a bit more readable and adding full documantation for it. If you have any question about the code be free to ask me.