# Fine-Grained Hardness for Undirected Hamiltonicity

The fastest known algorithm for detecting Hamiltonian cycles in directed graphs on $$n$$ nodes runs in essentially $$2^n\text{poly}(n)$$ time. However, for undirected graphs on $$n$$ nodes, there is an algorithm running exponentially faster, which takes $$1.657^n\text{poly}(n)$$ time.

Do we have any interesting conditional lower bounds ruling out substantially faster exact algorithms for detecting Hamiltonian cycles in undirected graphs? Is there any constant $$\epsilon > 0$$ for which getting a $$(1+\epsilon)^n$$ time algorithm for this problem would refute some plausible conjectures about the exact time complexity of other problems of interest?

• We don't know how to prove a $1.99^n$ lower bound for directed Hamiltonicity nor $1.6^n$ for undirected Hamiltonicity under well-established hardness assumptions. But you can get a lower bound of $(1+\varepsilon)$ from SETH for an explicit $\varepsilon>0$. For this, just take any standard reduction from SAT to HAM. It will construct a graph with $C(n+m)$ vertices for a fixed constant $C>0$, where $n$ and $m$ are the numbers of SAT variables and clauses. By the sparsification lemma, you can essentially ignore the $m$ term, which would lead to a lower bound of $2^{n/(C+\delta)}$ under SETH. Oct 19 at 18:20