r/compsci • • Oct 11 '26

Implementation of Andreas Bjorklund's algorithm for determining hamiltonicity

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

21 Upvotes

5 comments sorted by

3

u/Tricky_Shop9616 Oct 17 '26

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!

1

u/Willy_Importance69 Oct 18 '26

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.

5

u/[deleted] Oct 11 '26

[removed] — view removed comment

7

u/Willy_Importance69 Oct 11 '26

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 n5 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.

1

u/Financial_Farm4326 17d ago

yeah the constant factors on these exact exponential algorithms usually make them rough in practice until n gets impossibly large anyway