<p>Problem: Given an undirected simple graph <span class="math-container">$G=(V,E)$</span> on <span class="math-container">$n$</span> vertices, such that there are not more than <span class="math-container">$c^n$</span> (<span class="math-container">$c&lt;2$</span>) Hamiltonian cycles in <span class="math-container">$G$</span>, find a Hamiltonian Cycle in <span class="math-container">$G$</span> if there exists one.</p>
<p>I remember seeing a paper (by Björklund if I remember correctly) that gives an algorithm for this problem. I am having trouble relocating that paper. Any reference would be helpful.</p>

CC BY-SA 4.0
2023-04-05T16:12:02.577Z
Presumably there is a [parsimonious reduction](https://en.wikipedia.org/wiki/Parsimonious_reduction) from [UNAMBIGUOUS-SAT](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Extensions_of_SAT) to Hamiltonian Cycle, so that the Hamiltonian Cycle problem restricted to graphs with at most one Hamiltonian Cycle is essentially NP-hard (NP-hard under randomized reductions)...  So what kind of algorithm are you hoping for?
Neal Young
CC BY-SA 4.0
2023-04-06T05:08:12.153Z
@NealYoung, I am looking for an exact exponential time algorithm for the problem. Thanks for pointing out the hardness.
jamal_asif
<reference-request><graph-algorithms><hamiltonian-paths>
Finding a Hamiltonian cycle in a graph if we are guaranteed that there are not many of them in the graph
jamal_asif
# Finding a Hamiltonian cycle in a graph if we are guaranteed that there are not many of them in the graph

(Asked by: username_0 on 2023-04-04)

Problem: Given an undirected simple graph $G=(V,E)$ on $n$ vertices, such that there are not more than $c^n$ ($c<2$) Hamiltonian cycles in $G$, find a Hamiltonian Cycle in $G$ if there exists one.

I remember seeing a paper (by Björklund if I remember correctly) that gives an algorithm for this problem. I am having trouble relocating that paper. Any reference would be helpful.

**Tags:** reference-request, graph-algorithms, hamiltonian-paths

> **Comments:**
> **username_1**: Presumably there is a [parsimonious reduction](https://en.wikipedia.org/wiki/Parsimonious_reduction) from [UNAMBIGUOUS-SAT](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Extensions_of_SAT) to Hamiltonian Cycle, so that the Hamiltonian Cycle problem restricted to graphs with at most one Hamiltonian Cycle is essentially NP-hard (NP-hard under randomized reductions)...  So what kind of algorithm are you hoping for?  
> **username_0**: @NealYoung, I am looking for an exact exponential time algorithm for the problem. Thanks for pointing out the hardness.  

---

## 0 answers

