15

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

vb le
  • 4,828
  • 1
  • 37
  • 46
  • 3
    "For any epsilon" and "natural" seem hard or impossible to satisfy simultaneously, depending on your definition of "natural." – Huck Bennett Dec 24 '19 at 19:29
  • 7
    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 Dec 24 '19 at 20:06
  • 8
    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 Dec 25 '19 at 02:13
  • 1
    @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 Dec 26 '19 at 15:06
  • 2
    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 Dec 29 '19 at 20:28
  • @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 Dec 30 '19 at 10:34
  • Okay, I added an answer. – Neal Young Dec 31 '19 at 14:46

2 Answers2

16

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

Neal Young
  • 10,546
  • 33
  • 60
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)$.

Mohsen Ghorbani
  • 327
  • 1
  • 2
  • 9
  • 4
    Because of the dummies 1: is such a problem ´natural´ ? – G. Baum Dec 29 '19 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. – Mohsen Ghorbani Dec 29 '19 at 20:05
  • 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”. – Emil Jeřábek Dec 29 '19 at 22:41
  • 4
    @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 Dec 30 '19 at 10:35