r/algorithms • u/Willy_Importance69 • 6d ago

Research/Papers 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^*(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

20 Upvotes

92% Upvoted

15 comments sorted by

13

u/LightofAngels 6d ago

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

6

u/bartekltg 6d ago

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

in github :)

8

u/Willy_Importance69 6d ago

It was 4AM and I had been coding for 12 hours so some typos are expected 😅

9

u/TemperatureNo3082 5d ago

In this day and age typos are a badge of honor

4

u/Willy_Importance69 5d ago

How things have been going, understanding what the hell you are actually typing and not being just a flesh jockey is an honor.

Sidenote I've never understood people online who vibe code as a hobby, the reason I started learning to code and want to work in this field is the problem solving and making something that you've made.

4

u/LightofAngels 5d ago

Same, I cannot stand the slop anymore, I want to go back to systems programming or anything more interesting, that have problem solving.

2

u/Willy_Importance69 5d ago

Yeah I'm kind of lucky that I'm 17 because I can directly try to go to does fields where ai will be slower in adoption. But at the end of the day ai is a glorified search engine and it's only good in stuff like webdev which have been oversaturated for years :/

1

u/AnOnlineHandle 5d ago

There's a bunch of red flags which I look for when it comes to obvious bot accounts, and one of them is they drop the final full stops while using punctuation pretty well elsewhere. I don't doubt those are only the worst attempts at it, and there's better attempts I don't notice run by people who ensure there's mistakes in the text.

1

u/dnabre 4d ago

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

1

u/Phytor_c 4d ago

I was advised to deliberately include typos in my papers to make them look more human lmao

7

u/NarrMaster 5d ago

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.

3

u/Willy_Importance69 5d ago

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 (n5 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 :).

3

u/NarrMaster 5d ago

So am I.

3

u/Willy_Importance69 5d ago

I'd love to see your project when you finish it :)

3

u/NarrMaster 5d ago

Forgot to mention the graphs are cubic, until I can figure out how to work with max degree 3 instead.

#Vertex-Covers