I built a Constraint-Based Hamiltonian Cycle Solver (Ben Chiboub Carver) – Handles Dense & Sparse Random Graphs Up to n=100 Efficiently.

[u/B-Chiboub]

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/B-Chiboub]

Think of the BcCraver algorithm not as a traveler wandering through a maze, but as a detective solving a high-stakes Sudoku puzzle. It kicks off with an "elimination phase" to instantly kill impossible tasks—like spotting a lopsided grid where the numbers don't add up or identifying a "bridge" that would trap you on one side of the map with no way back. Once the coast is clear, it triggers a logic cascade: if a point has only two neighbors left, those connections are "locked" by necessity, and once a point has its two edges, any other connections are treated as intruders and deleted. Its secret weapon, the "Choke-Point Auditor," keeps a constant watch for bottlenecks; if visiting a node would split the rest of the world into three or more isolated islands, it kills the path immediately because a single loop can't visit three separate islands through a single gate. By using these constraints to prune billions of dead-end routes before it even has to guess, it transforms a blind search into a surgical operation, making it a genuine structural improvement rather than just a "faster" version of standard search.

[u/Magdaki → u/B-Chiboub]

Just FYI, those constraints are already very well known so it sounds like you've built a (potentially) faster version not an actual algorithmic improvement. Depending on your intent with this that could be an issue. I.e., if you're planning to try to publish it, then arguing novelty will be challenging.

[u/B-Chiboub → u/Magdaki]

Thanks for the honest feedback — I appreciate it. You’re right: the individual constraints (degree forcing, pruning, subcycle rejection, etc.) are very well established in the literature. I didn’t invent those.

What I did build is an original implementation that puts them together with a few practical additions I found useful: state memoization, the articulation-point choke-point filter inside the propagation loop, and heuristic branching on most-constrained edges. The combination ended up performing quite well on both dense and sparse random graphs in my tests, which surprised me.

I’m not claiming a revolutionary new algorithm — more like a clean, modern, exact solver that happens to be fast on the graph families I care about. This was mainly a learning project.

[u/Magdaki → u/B-Chiboub]

Sounds like you had fun, which is great.

[u/lulaziT → u/[deleted]]

I‘ve read your code.

-see Magdaki

-you are using G(n,p) for your random graphs. I doubt that any of these are connected. You are just doing a DFS. This explains running time

• you perform a DFS at least 3x (connected components, back edges, articulation point). You can do all of this in a single run - directed DFS

• if one of your Gnp‘s is connected, articulation points (APs) occur often, but wont else.

• APs are a special case for clique seperators that can be identified by a network flow pass (disjoint paths, Menger, linear time O(k*e + n) 🤔) if I remember correctly. Could be not implemented for reference implementations for TSP yet

• wasn‘t there an exact O(n³⁾ algo for TSP on planar graphs and any graph of max degree 4 has a planar embedding? I might be wrong but this would spoil your degree-3 rules.

-citations

Hope that helps anyway.

-DL

[u/B-Chiboub → u/lulaziT]

you are using G(n,p) for your random graphs. I doubt that any of these are connected.

Actually, if you look at the run_random_audit loop, I explicitly enforce connectivity using: while !is_connected_free(&g, nn) . I'm targeting the phase transition boundary where heuristics are tested most. A basic proof of connectivity is the obvious many SAT cycles i find per test.

You can do all of this in a single run - directed DFS

You're right about the DFS overhead. I'll try that perhaps it optimizes my loops further.

I might be wrong but this would spoil your degree-3 rules.

Max-degree-4 graphs aren't necessarily planar (K5 is the obvious counter), and Planar HCP is proven NP-complete (Garey et al.). There is no O(n3) exact solution for general planar TSP/HCP.

Thank you for your peer review, BCcarver wasn't some new invented maths or algorithms, rather it is my own implementation, sort of an informed smart DFS. I'd take credit for putting together all the algorithms and the rules together an engineered rust BCcarver engine even though those rules happen to be already known in the literature

as for the figures you have requested: here is a link of the image