NP-hard problems with very fast exponential-time algorithms

Question

NP-hard problems with very fast exact exponential-time algorithms, say with $O(1.01^n)$ time, are very rare.

Is any fact like

"For any constant $\epsilon>0$ there is an NP-hard 'natural' problem $\Pi_{\epsilon}$ that is not solvable in subexponential time $O(2^{o(n)})$ (assuming ETH) but can be solved in $O\left((1+\epsilon)^n\right)$ time by an exact algorithm."

in the literature somewhere?

(Actually, I am not able to find such an NP-hard problem that can be solved in time near $O(1.01^n)$.)

---

I do not have a formal definition for natural problems. (but I think each of us has an idea what a natural problem should be?)
Searching the literature I found the following paper which is very close to my question.
The informal discussion on page 2 of this paper is perhaps what I mean by natural (graph)problems. On page 15, the authors also ask for (sporadic) problems not solvable in subexponential time but have very fast exponential-time algorithms. (My question goes a step further by expressing 'very fast' in $\epsilon$: Given $\epsilon$, is there such a problem, depending on $\epsilon$, that can solved in $O((1+\epsilon)^n)$ time?)

Answer 1

The desired property holds for Independent Set (and probably other problems) in graphs of suitably bounded tree width.

Fix any constant $\epsilon>0$ and consider the Independent Set problem restricted to graphs of tree width at most $n \log_2(1+\epsilon) = \Theta(\epsilon n)$, where $n$ is the number of vertices. Call this problem $\Pi_\epsilon$.

Lemma 1. The problem $\Pi_\epsilon$ has an algorithm running in time $O((1+\epsilon)^n n^{O(1)})$.

Proof. This is a direct corollary of a result in [1] --- that Independent Set has an algorithm running in time $O(2^{\text{tw}(G)} n^{O(1)})$, where $\text{tw}(G)$ is the tree width of the given graph $G$. $~~\Box$

Lemma 2. Assuming ETH, there is no algorithm for $\Pi_\epsilon$ that runs in time $2^{o(n)}$.

Proof. Per [2] Theorem 3.3, assuming ETH, there is no $2^{o(n)}$-time algorithm for Independent Set. Suppose for contradiction that there is an algorithm $A$ for $\Pi_\epsilon$ running in time $2^{o(n)}$. Construct an algorithm $B$ for Independent Set as follows:

Algorithm $B$ on input $G$, an arbitrary graph with $n$ vertices:

1. Let $G'$ be the graph obtained from $G$ by adding artificial vertices, each with no edges, to bring the total number of vertices to $n'=n/\log_2(1+\epsilon)$.
2. Run the algorithm $A$ for $\Pi_\epsilon$ on $G'$ to find a maximum independent set $I'$ in $G'$.
3. Let $I$ be $I'$ minus all artificial vertices. Return $I$.

Graph $G'$ has tree width at most $n'\log_2(1+\epsilon) = n$ because $G$ has tree width at most $n$. So $A$ returns a maximum independent set $I'$ for $G'$ in time $2^{o(n')} = 2^{o(n)}$. $I'$ must consist of a maximum independent set $I$ in $G$ together with all the artificial vertices. So $B$ returns a maximum independent set in $G$ in time $2^{o(n)}$, contradicting Theorem 3.3 of [2]. $~~~\Box$

Note: Edited 12/30/2019 to correct an error in the lower-bound argument.

[1] Invitation to Fixed-parameter Algorithms. Rolf Niedermeier. Oxford Lecture Series in Mathematics and its Applications, Vol. 31. Oxford University Press, Oxford

[2] Lower bounds based on the exponential time hypothesis. D Lokshtanov, D Marx, S Saurabh - Bulletin of the EATCS no 105, pp. 41 71, October 2011

Answer 2

We can create such problem by padding assuming ETH‌. Take an np-complete problem L such that L is decidable in time $O(2^n)$, by padding L with some dummies 1 create $L' = \{1^{n-(log_21.01)n} x:|x|=(log_21.01)n \land x \in L\}$ it is easy to prove that $L'$ is complete for np and the running time of $L'$ is exactly $O(1.01^n)$.