14
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ "For any epsilon" and "natural" seem hard or impossible to satisfy simultaneously, depending on your definition of "natural." $\endgroup$ – Huck Bennett Dec 24 '19 at 19:29
  • 6
    $\begingroup$ 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. $\endgroup$ – Laakeri Dec 24 '19 at 20:06
  • 8
    $\begingroup$ 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$. $\endgroup$ – David Eppstein Dec 25 '19 at 2:13
  • 1
    $\begingroup$ @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. $\endgroup$ – vb le Dec 26 '19 at 15:06
  • 2
    $\begingroup$ 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. $\endgroup$ – Neal Young Dec 29 '19 at 20:28
16
+100
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Essentially, this answers my question, thank you. Happy New Year! $\endgroup$ – vb le Jan 1 at 0:12
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ Because of the dummies 1: is such a problem ´natural´ ? $\endgroup$ – G. Baum Dec 29 '19 at 19:27
  • $\begingroup$ @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. $\endgroup$ – Mohsen Ghorbani Dec 29 '19 at 20:05
  • 7
    $\begingroup$ @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”. $\endgroup$ – Emil Jeřábek Dec 29 '19 at 22:41
  • 3
    $\begingroup$ @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. $\endgroup$ – vb le Dec 30 '19 at 10:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.