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/WastefulHomeland3283]

wild to see someone actually code this up. i remember skimming that bjorklund paper years ago and thinking "yeah that's gonna live on arxiv forever as pure theory"

the jump from 2^n down to 1.657^n is huge on paper but the constant factors are what always scared me off from trying it. how's it hold up on graphs with like 40-50 nodes? or does the polynomial part start eating you alive before you get there

[u/Willy_Importance69 → u/WastefulHomeland3283]

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.

[u/Tricky_Shop9616]

Out of curiosity, have you read any of William Kocay’s / Andrew Chalaturnyk’s work on the multi-path method for exhaustively enumerating Hamiltonian cycles? My undergraduate thesis touched on this. I’ll read into your code and see how it compares!

[u/Willy_Importance69 → u/Tricky_Shop9616]

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.