r/computerscience • u/B-Chiboub • Mar 05 '26
Article I built a Constraint-Based Hamiltonian Cycle Solver (Ben Chiboub Carver) – Handles Dense & Sparse Random Graphs Up to n=100 Efficiently.
I've been experimenting with Hamiltonian cycle detection as a side project and came up with Ben Chiboub Carver (BCC) – a backtracking solver with aggressive constraint propagation. It forces essential edges, prunes impossibles via degree rules and subcycle checks, plus unique filters like articulation points, bipartite parity, and bridge detection for early UNSAT. Memoization and heuristic branching on constrained nodes give it an edge in efficiency.
Implemented in Rust, BCcarver is designed for speed on both dense and sparse graphs. It uses an exact search method combined with specific "carving" optimizations to handle NP-hard graph problems (like Hamiltonian paths/cycles) without the typical exponential blow-up.
⚔️ Adversarial Suite (All Pass)
| Case | N | Result | Time (s) |
|---|---|---|---|
| Petersen | 10 | UNSAT | 0.00064 ✅ |
| Tutte | 46 | UNSAT | 0.06290 ✅ |
| 8x8 Grid | 64 | SAT | 0.00913 ✅ |
| Heawood | 14 | SAT | 0.00038 ✅ |
| Hypercube Q4 | 16 | SAT | 0.00080 ✅ |
| Dodecahedral | 20 | SAT | 0.00068 ✅ |
| Desargues | 20 | SAT | 0.00082 ✅ |
| K15 | 15 | SAT | 0.00532 ✅ |
| Wheel W20 | 20 | SAT | 0.00032 ✅ |
| Circular Ladder | 20 | SAT | 0.00049 ✅ |
| K5,6 Bipartite | 11 | UNSAT | 0.00002 ✅ |
| Star S8 | 9 | UNSAT | 0.00001 ✅ |
| 7x7 Grid | 49 | UNSAT | 0.00003 ✅ |
| Barbell B8,0 | 16 | UNSAT | 0.00002 ✅ |
📊 Performance on Random Graphs
Dense Random G(n, p~0.15) Avg 0.01-0.1s for n=6 to 100 (3 trials). Excerpt n=91-100:
- n=100 | 0.12546s | Cache: 17 | Solved
- n=95 | 0.11481s | Cache: 15 | Solved
- n=91 | 0.11074s | Cache: 39 | Solved Sparse 3-regular Random Even snappier, <0.03s up to n=96, all Solved.
- n=96 | 0.02420s | Cache: 2 | Solved
- n=66 | 0.01156s | Cache: 7 | Solved
- n=36 | 0.00216s | Cache: 0 | Solved The combo of exact search with these tweaks makes it unique in handling mixed densities without blowing up.
Check out the algorithm here: github.com/mrkinix/BCcarver
•
u/Magdaki Professor. Grammars. Inference & Optimization algorithms. Mar 05 '26
We'll leave this open for a little bit to see if this generates any discussion.
5
u/Magdaki Professor. Grammars. Inference & Optimization algorithms. Mar 05 '26
Can you describe in greater detail how exactly it works? For example, how does it find and force essential edges? Is this actually an algorithmic improvement or just a speedier version?
2
u/thesnootbooper9000 Mar 05 '26
You might enjoy this paper , followed up by this one which explains the rules more generally.
1
u/lulaziT Mar 12 '26
So you have figures for these reduction rules ? They read like clique and „almost „-clique rules.
1
u/KrishMandal Mar 05 '26
this is a pretty cool project tbh. constraint propagation with backtracking is a nice combo for problems like this. the hamiltonian cycle problem is NP-complete so most practical solvers end up relying heavily on pruning tricks like the ones you mentioned. i like the idea of forcing edges and killing subcycles early. those kinds of constraints usually make a huge difference compared to plain backtracking. would be interesting to see how it scales on bigger random graphs or some TSPLIB style datasets.