r/compsci • u/Willy_Importance69 • 10d ago

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

96% Upvoted

4 comments sorted by

5

u/WastefulHomeland3283 10d ago

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

6

u/Willy_Importance69 10d ago

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.

3

u/Tricky_Shop9616 4d ago

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!