Some NP-Complete Problems Fit Through Subexponential Gaps

The usual story around NP-complete problems is that we do not expect polynomial-time algorithms. But that still leaves a lot of room between polynomial time and the trivial exhaustive search bound.

For many exact algorithms, progress means shaving the exponential base. For 3-SAT, the naive bound

$$O(2^{n}n)$$

can be improved by more careful branching to a single-exponential bound with a smaller base, such as

$$O(1.913^n).$$

Later algorithms improve this further. These are still exponential, but less brutal.

This is still called single-exponential time. In this context, single-exponential means the running time has the form

$$2^{O(n)}.$$

For example,

$$3^{n}n=2^{{\log }_2(3)n}n\subseteq 2^{O(n)}.$$

Even base $3$ is still single-exponential, because changing the constant base only changes the constant hidden inside $O(n)$.

A sharper question is whether an NP-complete problem can be solved in subexponential time, meaning time strictly better than $2^{O(n)}$ in the exponent, such as $2^{o(n)}$. Toy examples show that the answer can be yes if the input is restricted in the right way.

Consider a variant of vertex cover where the input graph on $n$ vertices is promised to contain at most $\sqrt{n}$ edges. Call it sparse vertex cover. It is still NP-complete: membership in NP is inherited from vertex cover, and any vertex-cover instance can be padded with isolated vertices until the number of vertices is large enough that the edge bound holds.

But the padded problem has a subexponential algorithm in terms of the padded input size. Only vertices incident to edges matter. With at most $\sqrt{n}$ edges, there are at most $2\sqrt{n}$ non-isolated vertices. All other vertices can be ignored.

Trying all subsets of the active vertices takes at most

$$2^{2\sqrt{n}}=2^{O(\sqrt{n})},$$

which is subexponential in $n$.

This example is artificial. It gets subexponential time by padding the input with irrelevant isolated vertices. The more interesting question is whether natural NP-complete problems have subexponential algorithms. That depends on the problem and on what parameter is used as the input size. The point is that NP-completeness alone does not tell us the exact exponential scale.