# NP-hard problems with very fast exponential-time algorithms

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?)

• "For any epsilon" and "natural" seem hard or impossible to satisfy simultaneously, depending on your definition of "natural." Dec 24, 2019 at 19:29
• 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. Dec 24, 2019 at 20:06
• 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$. Dec 25, 2019 at 2:13
• @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. Dec 26, 2019 at 15:06
• 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. Dec 29, 2019 at 20:28

## 2 Answers

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

• Essentially, this answers my question, thank you. Happy New Year! Jan 1, 2020 at 0:12

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

• Because of the dummies 1: is such a problem ´natural´ ? Dec 29, 2019 at 19:27
• @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. Dec 29, 2019 at 20:05
• @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”. Dec 29, 2019 at 22:41
• @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. Dec 30, 2019 at 10:35