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

CC BY-SA 4.0
2019-12-29T19:27:56.887Z
Because of the dummies 1: is such a problem ´natural´ ?
G. Baum
CC BY-SA 4.0
2019-12-29T20:05:57.397Z
@G.Baum It is depends on the natural's  definition.  if we take  npc sets that are p-isomorphism to SAT as natural problems then it is natural, in the other cases  I think it is not.
Mohsen Ghorbani
CC BY-SA 4.0
2019-12-29T22:41:29.063Z
@G.Baum Considering that the question asks for an infinite sequence of different problems (depending on $\epsilon$), this kind of a padding construction is as natural as it gets. Anyway, including the word “natural” in a question just means “I’m too lazy to formulate a sensible question in a proper way, so I’ll put this in so that I can arbitrarily dismiss answers that I don’t like”.
Emil Jeřábek
CC BY-SA 4.0
2019-12-30T10:35:42.070Z
@Emil: I do like simple padding argument! But I believe 'more natural' problems should exist... I am very sorry for being too lazy to formulate the question in a proper way.
vb le
CC BY-SA 4.0
2019-12-29T19:01:39.670Z
2019-12-29T19:01:39.670Z
Mohsen Ghorbani
<p>The desired property holds for Independent Set (and probably other problems) in graphs of suitably bounded tree width.</p>

<p>Fix any constant <span class="math-container">$\epsilon&gt;0$</span> and consider the Independent Set problem restricted to graphs of tree width at most <span class="math-container">$n \log_2(1+\epsilon) = \Theta(\epsilon n)$</span>, where <span class="math-container">$n$</span> is the number of vertices.  Call this problem <span class="math-container">$\Pi_\epsilon$</span>.</p>

<p><strong>Lemma 1.</strong> <em>The problem <span class="math-container">$\Pi_\epsilon$</span> has an algorithm running in time <span class="math-container">$O((1+\epsilon)^n n^{O(1)})$</span>.</em></p>

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

<p><strong>Lemma 2.</strong> <em>Assuming ETH, there is no algorithm for <span class="math-container">$\Pi_\epsilon$</span> that runs in time <span class="math-container">$2^{o(n)}$</span>.</em></p>

<p><em>Proof.</em> Per [2] Theorem 3.3, assuming ETH, there is no <span class="math-container">$2^{o(n)}$</span>-time algorithm for Independent Set.  Suppose for contradiction that there is an algorithm <span class="math-container">$A$</span> for <span class="math-container">$\Pi_\epsilon$</span> running in time <span class="math-container">$2^{o(n)}$</span>.  Construct an algorithm <span class="math-container">$B$</span> for Independent Set as follows:</p>

<p>Algorithm <span class="math-container">$B$</span> on input <span class="math-container">$G$</span>, an arbitrary graph with <span class="math-container">$n$</span> vertices:</p>

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

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

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

<p>[1] <a href="https://scholar.google.com/scholar?cluster=11398752987759375514&amp;hl=en&amp;as_sdt=0,22" rel="noreferrer">Invitation to Fixed-parameter Algorithms</a>. Rolf Niedermeier. Oxford Lecture Series in Mathematics and its Applications, Vol. 31. Oxford University Press, Oxford</p>

<p>[2] <a href="https://scholar.google.com/scholar?cluster=11013158519268532487&amp;hl=en&amp;as_sdt=0,22" rel="noreferrer">Lower bounds based on the exponential time hypothesis</a>. D Lokshtanov, D Marx, S Saurabh - Bulletin of the EATCS no 105, pp. 41 71, October 2011</p>

CC BY-SA 4.0
2020-01-01T00:12:38.707Z
Essentially, this answers my question, thank you. Happy New Year!
vb le
CC BY-SA 4.0
2019-12-30T16:01:28.587Z
2019-12-31T02:43:42.517Z
2019-12-31T02:43:42.517Z
Neal Young
<p>NP-hard problems with very fast exact exponential-time algorithms, say with <span class="math-container">$O(1.01^n)$</span> time, are very rare. </p>

<p>Is any fact like </p>

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

<p>in the literature somewhere? </p>

<p>(Actually, I am not able to find such an NP-hard problem that can be solved in time near <span class="math-container">$O(1.01^n)$</span>.)</p>

<hr>

<p>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?)<br>
Searching the literature I found the following <a href="https://link.springer.com/article/10.1007/s00224-012-9412-5" rel="noreferrer">paper</a> which is very close to my question.<br>
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 <span class="math-container">$\epsilon$</span>: 
Given <span class="math-container">$\epsilon$</span>, is there such a problem, depending on <span class="math-container">$\epsilon$</span>, that can solved in 
<span class="math-container">$O((1+\epsilon)^n)$</span> time?)             </p>

CC BY-SA 4.0
2019-12-24T19:29:03.003Z
"For any epsilon" and "natural" seem hard or impossible to satisfy simultaneously, depending on your definition of "natural."
Huck Bennett
CC BY-SA 4.0
2019-12-24T20:06:27.557Z
What is $n$? If it is the number of bits in the input, then most of the classical NP-complete graph problems like Clique have $O((1 + \varepsilon)^n)$ algorithms for every positive $\varepsilon$ when the input is given as an adjacency matrix.
Laakeri
CC BY-SA 4.0
2019-12-25T02:13:42.317Z
Many NP-hard problems on planar graphs have algorithms exponential in $\sqrt{n}$ rather than in $n$, and are therefore $O((1+\varepsilon)^n)$ for every positive $\varepsilon$.
David Eppstein
CC BY-SA 4.0
2019-12-26T15:06:47.507Z
@David: many thanks for your comment. Indeed, every problem solvable in $O(2^{o(n)})$ time can be solved in $O((1+\epsilon)^n)$ time for every constant $\epsilon>0$. I improved the question to clear which problems (depending on $\epsilon$) I am actually  looking for.
vb le
CC BY-SA 4.0
2019-12-29T20:28:45.207Z
Many graph problems have poly-time algorithms when restricted to inputs with constant tree-width.  Perhaps you could get what you want by restricting instead to inputs with tree-width $f(n)$ where $f$ grows sufficiently slowly.  (E.g. $f(n)$ is something like $\epsilon n/\log n$.) Not sure if you'd call that "natural".  Similarly, you could consider SAT restricted to inputs of length $n$ but having, say, at most $\epsilon n$ variables.
Neal Young
CC BY-SA 4.0
2019-12-30T10:34:41.503Z
@Neal: I am not sure if it is 'natural' to restrict the number of variables. But much people consider treewidth restriction natural. Would you please provide a treewidth answer with more details?
vb le
CC BY-SA 4.0
2019-12-31T14:46:21.350Z
Okay, I added an answer.
Neal Young
<ds.algorithms><reference-request><exp-time-algorithms>
NP-hard problems with very fast exponential-time algorithms
vb le
# NP-hard problems with very fast exponential-time algorithms

(Asked by: username_0 on 2019-12-24)

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](https://link.springer.com/article/10.1007/s00224-012-9412-5) 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?)

**Tags:** ds.algorithms, reference-request, exp-time-algorithms
> **Comments:**
> **username_1**: "For any epsilon" and "natural" seem hard or impossible to satisfy simultaneously, depending on your definition of "natural."  
> **username_2**: What is $n$? If it is the number of bits in the input, then most of the classical NP-complete graph problems like Clique have $O((1 + \varepsilon)^n)$ algorithms for every positive $\varepsilon$ when the input is given as an adjacency matrix.  
> **username_3**: Many NP-hard problems on planar graphs have algorithms exponential in $\sqrt{n}$ rather than in $n$, and are therefore $O((1+\varepsilon)^n)$ for every positive $\varepsilon$.  
> **username_0**: @David: many thanks for your comment. Indeed, every problem solvable in $O(2^{o(n)})$ time can be solved in $O((1+\epsilon)^n)$ time for every constant $\epsilon>0$. I improved the question to clear which problems (depending on $\epsilon$) I am actually  looking for.  
> **username_4**: Many graph problems have poly-time algorithms when restricted to inputs with constant tree-width.  Perhaps you could get what you want by restricting instead to inputs with tree-width $f(n)$ where $f$ grows sufficiently slowly.  (E.g. $f(n)$ is something like $\epsilon n/\log n$.) Not sure if you'd call that "natural".  Similarly, you could consider SAT restricted to inputs of length $n$ but having, say, at most $\epsilon n$ variables.  
> **username_0**: @Neal: I am not sure if it is 'natural' to restrict the number of variables. But much people consider treewidth restriction natural. Would you please provide a treewidth answer with more details?  
> **username_4**: Okay, I added an answer.  

---

## 2 answers

### Answer by username_4 on 2019-12-30. Score: 16 | Accepted answer

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](https://scholar.google.com/scholar?cluster=11398752987759375514&hl=en&as_sdt=0,22). 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](https://scholar.google.com/scholar?cluster=11013158519268532487&hl=en&as_sdt=0,22). D Lokshtanov, D Marx, S Saurabh - Bulletin of the EATCS no 105, pp. 41 71, October 2011

> **Comments:**
> **username_0**: Essentially, this answers my question, thank you. Happy New Year!  

---

### Answer by username_5 on 2019-12-29. Score: 3

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)$.

> **Comments:**
> **username_6**: Because of the dummies 1: is such a problem ´natural´ ?  
> **username_5**: @G.Baum It is depends on the natural's  definition.  if we take  npc sets that are p-isomorphism to SAT as natural problems then it is natural, in the other cases  I think it is not.  
> **username_7**: @G.Baum Considering that the question asks for an infinite sequence of different problems (depending on $\epsilon$), this kind of a padding construction is as natural as it gets. Anyway, including the word “natural” in a question just means “I’m too lazy to formulate a sensible question in a proper way, so I’ll put this in so that I can arbitrarily dismiss answers that I don’t like”.  
> **username_0**: @Emil: I do like simple padding argument! But I believe 'more natural' problems should exist... I am very sorry for being too lazy to formulate the question in a proper way.  

---

