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^*(2^n) to O^*(1.657^n) for general graphs(this is what i've managed to implement as of right not) and for bipartite its O^*(1.414^n).

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

I literally just needed something like this.

Didn't even search, this was on my feed.

The project I'm working on, for now, requires the graphs I use to be Hamiltonian.

When I say needed, I mean I'm working on it at this moment and need to have some Hamiltonian check in front.

Thank you very much.

[u/Willy_Importance69 → u/NarrMaster]

Happy to be helpful :) tough fair warning the algorithm is still pretty slow only good for about n in the range 20-30, for smaller graphs held karp could be even faster because this algorithm (bjorklund) has a large (n⁵ if I'm not wrong) polynomial time complexity. If I remember correctly from what I've read the best way to check hamilonicity in a graph is translating the problem to a SAT problem and using a SAT solver. I may be wrong but I think that's like the standard. Rn I'm checking out some optimizations I'll push them in an hour or so, mainly with making some part run paralel.

Also something fun (another lil project I'm planning for the near future) there is some research on using GNNs to find hamilonicity and I want to see what's the extent of their use in that.

Also sidenote this algorithm is a monte Carlo algorithm if it returns true the graph has a Hamiltonian cycle but if it returns false there is a very small chance there is a Hamiltonian cycle (it can give false-negatives) but it's pretty miniscule. If you want you can check the paper it give the exact probability.

Sorry for the long answer I'm really interested in this topic :).

[u/LightofAngels]

You know this post isn’t written by AI, when OP is saying weather instead of whether.

[u/bartekltg → u/LightofAngels]

Also,
> This algorithm lowered the exponential part of the time complexity from O∗(2^n) to O∗(2^n).

in github :)

[u/dnabre → u/LightofAngels]

Just wait until AI offer a slider to set how many mistakes it should include to look more human.