Independent Set Inherits 3-SAT's Exponential Barrier

The usual reduction from 3-SAT to independent set does more than prove NP-hardness. It also preserves enough size information to transfer a subexponential lower-bound intuition.

If independent set had a subexponential algorithm in the number of vertices, then 3-SAT would inherit one. Under the exponential time hypothesis, that should not happen.

Clauses become choice gadgets

Start with a 3-SAT formula $F$ with $m$ clauses. For each clause, create one small clique whose vertices are the literals in that clause. Set

$$k=m.$$

The clique forces the independent set to choose at most one literal from each clause. Asking for an independent set of size $m$ then forces it to choose exactly one literal from every clause.

The independent set is doing the same job as a satisfying assignment, but locally. It chooses one witness literal per clause.

Conflicts enforce consistency

Choosing one literal per clause is not enough. The choices must also be consistent: we must not choose both $x$ and $\neg x$.

So the reduction adds conflict edges between complementary literals in different clause gadgets. An independent set cannot contain both endpoints of an edge, so it cannot select contradictory literals.

Now the correctness is visible. A satisfying assignment gives one true literal from each clause, and no two chosen true literals conflict. Conversely, an independent set of size $m$ picks one literal from each clause and contains no contradiction, so those choices can be extended to a satisfying assignment.

The size of the reduction matters

For NP-hardness, it is enough that the reduction is polynomial. For ETH-style lower bounds, polynomial is too coarse. We need to know how the output size grows.

The reduction creates one vertex for each literal occurrence. Since this is 3-SAT,

$$|V(G)|=3m.$$

This linear relation is the important part. The independent-set instance is not merely polynomially larger than the formula; it is only linearly larger in the number of clauses.

Why a subexponential independent-set algorithm would be dangerous

Suppose there were an algorithm $A$ for independent set running in time

$$2^{|V{|}^{0.99}}\cdot |V{|}^{10}.$$

Given a 3-SAT formula with $m$ clauses, first reduce it to $(G,k)$. Since $|V|=3m$, running $A$ would take

$$2^{(3m{)}^{0.99}}\cdot (3m{)}^{10}=2^{O(m^{0.99})}.$$

This is subexponential in $m$.

At first, this seems to use $m$ rather than the number of variables $n$. That is exactly where the equivalent forms of ETH matter. Impagliazzo, Paturi, and Zane show that ruling out $2^{o(n)}$ algorithms for 3-SAT is equivalent to ruling out $2^{o(m)}$ algorithms.

Therefore a subexponential algorithm for independent set would give a subexponential algorithm for 3-SAT and contradict ETH.

So the reduction carries two things at once: logical satisfiability becomes independent choice, and the linear size blow-up preserves the exponent scale.