Reducing 3-SAT to Clique

The Reduction Idea

A reduction can translate a question about logical assignments into a question about a graph. For 3-SAT, the key is to make a choice of one true literal from each clause. A graph can enforce the consistency of those choices: connect two choices when their literals can both be true. Then a clique that contains one choice from every clause represents a consistent selection.

We use a 3-CNF formula \(\varphi=C_1\land\cdots\land C_m\), where each clause has at most three literal occurrences. A literal is a variable or its negation. Repeated literals count as separate occurrences; for example, the three occurrences in \((x\lor x\lor x)\) are distinct positions. Clauses may be empty, in which case the formula is unsatisfiable. The formula with no clauses, \(m=0\), is true. These conventions make the construction and its boundary cases precise.

For each literal occurrence, create a vertex labelled by its clause and its position in that clause. Two vertices are adjacent precisely when they represent compatible literals in different clauses. In particular, occurrences in the same clause are never adjacent, even if their literals are identical.

The clause labels play an essential role. They ensure that a clique cannot select two occurrences from one clause. The compatibility condition plays the other role: it prevents the selected literals from requiring contradictory values for a variable.

Why Satisfiability Matches Clique Size

Proof. First suppose \(\varphi\) is satisfiable. In each clause choose one literal occurrence that is true under a satisfying assignment. If \(m=0\), this makes no choices, and the empty set is a clique of size \(0\). If \(m\ge 1\), the chosen occurrences lie in distinct clauses. No two chosen literals can be complementary: a variable and its negation cannot both be true under one assignment. Therefore each pair of chosen vertices is adjacent by the construction. They form a clique of size \(m\), so \(G_\varphi\) has a clique of size at least \(m\).

Conversely, suppose \(G_\varphi\) has a clique \(S\) of size at least \(m\). If \(m=0\), the formula has no clauses and is true. Now suppose \(m\ge1\). No two vertices in \(S\) can come from the same clause, because there are no edges between vertices from the same clause. Hence \(|S|\le m\), since there are only \(m\) clauses. Together with \(|S|\ge m\), this gives \(|S|=m\). Moreover, \(S\) contains exactly one occurrence from each clause: it contains at most one per clause, and \(m\) vertices distributed among \(m\) clauses must occupy all \(m\) clauses.

Because \(S\) is a clique, every pair of its selected literals is compatible. Thus no variable is selected both positively and negatively. Assign each variable that appears positively among the selected literals the value true, and each variable that appears negatively the value false. These instructions do not conflict. Assign any remaining variables arbitrarily. In each clause, the selected occurrence is now true, so every clause is true and \(\varphi\) is satisfiable. This proves both directions. \(\square\)

An empty clause causes no exception to the argument: it contributes no vertex, so a clique cannot contain one vertex from that clause. When \(m\ge1\), a clique of size \(m\) is therefore impossible. This matches the fact that a formula containing an empty clause is unsatisfiable.

Worked Constructions

Polynomial Size and Construction Time

Let \(L\) be the number of literal occurrences in the formula. Since there are at most three occurrences per clause, \(L\le3m\). The graph has exactly \(L\) vertices. To build its edge set, examine each pair of occurrences, check whether their clause labels differ, and check whether their literals are complementary. There are at most \(L(L-1)/2\) pairs to examine. The checks use the encoded variable names and signs, so each takes time polynomial in the formula’s encoding length. Writing the vertices and all accepted pairs also takes polynomial space and time. The output integer \(m\) has polynomial encoding length. Therefore \(\varphi\mapsto(G_\varphi,m)\) is computable in polynomial time and produces an output of polynomial size.

This is a polynomial-time many-one reduction: the theorem proves that the formula is a yes-instance of 3-SAT exactly when the produced pair is a yes-instance of CLIQUE. The direction matters: the output asks for a clique of size equal to the number of clauses, not for a clique of some unrelated size.

Why CLIQUE Is in NP

To verify membership in NP, a yes-instance needs a certificate whose length is polynomial in the input size and a deterministic verification procedure that runs in polynomial time. For a CLIQUE input \((G,k)\) with \(n=|V(G)|\), use an \(n\)-bit vector to specify a subset \(S\subseteq V(G)\). The verifier counts the selected vertices, checks \(|S|\ge k\), and checks every pair of distinct selected vertices against the graph’s edge list (or adjacency matrix). These checks take polynomial time in the explicit graph encoding, and the certificate has length \(n\). If \(k>n\), the size check rejects; if \(k=0\), the empty certificate set is accepted.

Common Mistake: Adding Edges Within Clauses

A tempting but incorrect variation is to connect every pair of compatible occurrences, including occurrences from the same clause. This removes the guarantee that a clique of size \(m\) represents one choice from each of the \(m\) clauses.

For the unsatisfiable formula \((x\lor x\lor x)\land(\neg x\lor\neg x\lor\neg x)\), adding within-clause edges would make \(a_1a_2\) an edge, since both occurrences represent \(x\). The mistaken graph would then have a 2-clique \(\{a_1,a_2\}\), even though the formula is unsatisfiable and the target is \(m=2\). The error is that both vertices came from the first clause. In the correct construction there are no within-clause edges, so every clique of size \(m\) must select once from every clause.