5
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Alex Golovnev
    Oct 19, 2021 at 18:20

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy