Clique NP-Hardness Reduction, in depth: 3-SAT to CLIQUE, both proof directions, tested code and what hardness means in practice

The two problems, precisely

CLIQUE. Input: an undirected graph G = (V, E) and an integer k. Question: is there a set S of k vertices such that every pair in S is joined by an edge? The decision version is what we reduce to; the optimisation version, find the largest clique, is at least as hard.

3-SAT. Input: a Boolean formula in conjunctive normal form, an AND of m clauses, each an OR of exactly three literals, where a literal is a variable or its negation. Question: is there an assignment of true or false to the variables that makes every clause true?

CLIQUE is in NP because a claimed clique is easy to check. Given S, confirm |S| = k and test each of the k(k-1)/2 pairs against an adjacency set, which is polynomial. Membership in NP is half of NP-completeness; the reduction supplies the other half, NP-hardness. The direction matters: we transform any 3-SAT instance into a CLIQUE instance, so a fast CLIQUE algorithm would give a fast 3-SAT algorithm. Reducing CLIQUE to 3-SAT would prove nothing about CLIQUE's hardness.

from itertools import combinations

def verify_clique(adj, S, k):
    """adj: dict vertex -> set of neighbours. Polynomial-time NP verifier."""
    return len(set(S)) == k and all(v in adj[u] for u, v in combinations(S, 2))

The construction

Given a formula with m clauses C1 ... Cm:

1. For every literal occurrence, create one vertex labelled with its clause index and the literal. Three literals per clause gives 3m vertices. A variable that appears in several clauses gets several vertices.
2. Add an edge between two vertices if and only if they are in different clauses and their literals are not complementary, meaning one is not the negation of the other.
3. Set k = m.

The two rules each encode one constraint of satisfiability. No edges inside a clause means a clique can contain at most one vertex per clause, so a clique of size m must pick exactly one literal from every clause. No edges between x and its negation means the chosen literals never contradict each other, so they can all be made true at once.

The two problems, precisely

CLIQUE. Input: an undirected graph G = (V, E) and an integer k. Question: is there a set S of k vertices such that every pair in S is joined by an edge? The decision version is what we reduce to; the optimisation version, find the largest clique, is at least as hard.

3-SAT. Input: a Boolean formula in conjunctive normal form, an AND of m clauses, each an OR of exactly three literals, where a literal is a variable or its negation. Question: is there an assignment of true or false to the variables that makes every clause true?

CLIQUE is in NP because a claimed clique is easy to check. Given S, confirm |S| = k and test each of the k(k-1)/2 pairs against an adjacency set, which is polynomial. Membership in NP is half of NP-completeness; the reduction supplies the other half, NP-hardness. The direction matters: we transform any 3-SAT instance into a CLIQUE instance, so a fast CLIQUE algorithm would give a fast 3-SAT algorithm. Reducing CLIQUE to 3-SAT would prove nothing about CLIQUE's hardness.

from itertools import combinations

def verify_clique(adj, S, k):
    """adj: dict vertex -> set of neighbours. Polynomial-time NP verifier."""
    return len(set(S)) == k and all(v in adj[u] for u, v in combinations(S, 2))

The construction

Given a formula with m clauses C1 ... Cm:

1. For every literal occurrence, create one vertex labelled with its clause index and the literal. Three literals per clause gives 3m vertices. A variable that appears in several clauses gets several vertices.
2. Add an edge between two vertices if and only if they are in different clauses and their literals are not complementary, meaning one is not the negation of the other.
3. Set k = m.

The two rules each encode one constraint of satisfiability. No edges inside a clause means a clique can contain at most one vertex per clause, so a clique of size m must pick exactly one literal from every clause. No edges between x and its negation means the chosen literals never contradict each other, so they can all be made true at once.

Worked example

Take the formula in the diagram: (x1 ∨ x2 ∨ ¬x3) ∧ (¬x1 ∨ x3 ∨ x2) ∧ (¬x2 ∨ ¬x3 ∨ x1). There are three clauses, so k = 3 and there are 9 vertices. Between any two clauses there are 3 × 3 = 9 vertex pairs, so 27 cross-clause pairs in total. Six of them are complementary: x1 in C1 with ¬x1 in C2, ¬x1 in C2 with x1 in C3, x2 in C1 with ¬x2 in C3, x2 in C2 with ¬x2 in C3, ¬x3 in C1 with x3 in C2, and x3 in C2 with ¬x3 in C3. That leaves 21 edges.

One 3-clique is {x1 from C1, x3 from C2, ¬x2 from C3}: the three pairs are in different clauses and none is complementary. Read back as an assignment, x1 = true, x3 = true, x2 = false. Check it: C1 holds through x1, C2 through x3, C3 through ¬x2. The graph found a satisfying assignment because a clique is exactly a consistent choice of one true literal per clause.

Proof in both directions

A reduction is correct only if it preserves the answer in both directions: the formula is satisfiable if and only if the graph has a k-clique.

Satisfiable implies clique. Fix a satisfying assignment. Every clause has at least one true literal; pick one vertex for such a literal in each clause, giving m vertices. Any two of them are in different clauses. They cannot be complementary, because both literals are true under the same assignment and a literal and its negation cannot both be true. So every pair is joined by an edge, and the m vertices form a clique of size k.

Clique implies satisfiable. Let S be a clique of size m. Vertices in the same clause are not adjacent, so S has exactly one vertex per clause. No two vertices in S are complementary, so the set of literals in S is consistent: set each variable so its literal in S is true, and set any variable not mentioned arbitrarily. Every clause contains a literal from S, which is true, so every clause is satisfied.

Polynomial time. The graph has 3m vertices and at most 9 · m(m-1)/2 edges, and each edge test is constant time, so construction is O(m²). Together with NP membership, this proves CLIQUE is NP-complete.

Code: reduction, certificates and a cross-check

The proof translates directly into code, and writing the certificate maps in both directions is the best way to check you have understood it. The cross-check compares the reduction against brute-force satisfiability on random small formulas, using a Bron–Kerbosch search with pivoting to find the largest clique.

from itertools import combinations, product
import random

def reduce_3sat_to_clique(clauses):
    """clauses: list of 3-tuples of non-zero ints, -v meaning NOT v. Returns (V, E, k)."""
    V = [(i, lit) for i, cl in enumerate(clauses) for lit in cl]
    E = {(a, b) for a, b in combinations(range(len(V)), 2)
         if V[a][0] != V[b][0] and V[a][1] != -V[b][1]}
    return V, E, len(clauses)

def clique_to_assignment(V, clique):
    return {abs(lit): lit > 0 for _, lit in (V[i] for i in clique)}

def assignment_to_clique(V, clauses, assign):
    picked = []
    for i, cl in enumerate(clauses):
        lit = next(l for l in cl if assign[abs(l)] == (l > 0))   # a true literal
        picked.append(V.index((i, lit)))
    return picked

def max_clique(n, E):
    adj = {v: set() for v in range(n)}
    for a, b in E:
        adj[a].add(b); adj[b].add(a)
    best = []
    def bk(R, P, X):
        nonlocal best
        if not P and not X:
            best = R if len(R) > len(best) else best
            return
        u = max(P | X, key=lambda w: len(adj[w] & P))          # pivot
        for v in list(P - adj[u]):
            bk(R + [v], P & adj[v], X & adj[v])
            P, X = P - {v}, X | {v}
    bk([], set(range(n)), set())
    return best

def brute_sat(clauses, n):
    for bits in product([False, True], repeat=n):
        a = {v + 1: bits[v] for v in range(n)}
        if all(any(a[abs(l)] == (l > 0) for l in cl) for cl in clauses):
            return a
    return None

rng = random.Random(7)
for _ in range(2000):
    n, m = rng.randint(3, 4), rng.randint(4, 14)
    cls = [tuple(rng.choice([1, -1]) * v for v in rng.sample(range(1, n + 1), 3))
           for _ in range(m)]
    V, E, k = reduce_3sat_to_clique(cls)
    assert (brute_sat(cls, n) is not None) == (len(max_clique(len(V), E)) == k)

Run as written, the loop passes on all 2,000 formulas, 48 of which are unsatisfiable, so both directions are exercised. A sharper test is the formula made of all eight clauses over x1, x2, x3 with every sign pattern, which no assignment satisfies. Its graph has 24 vertices and 204 edges, k = 8, and the largest clique has 7 vertices. That 7 is meaningful: every assignment falsifies exactly one of the eight clauses, so the maximum clique size equals the maximum number of simultaneously satisfiable clauses. The construction therefore also maps MAX-3-SAT to maximum clique, which is the starting point for the approximation results below.

Clique, independent set and vertex cover

Clique has two siblings that come almost for free. S is a clique in G exactly when S is an independent set (no two adjacent) in the complement graph, so CLIQUE and INDEPENDENT SET reduce to each other by complementing the edges, an O(n²) step. And S is independent exactly when V \ S is a vertex cover (touches every edge), so G has an independent set of size k if and only if it has a vertex cover of size n - k. All three are NP-complete, and a result for one usually transfers to the others, with one important exception: approximation. Vertex cover has a simple factor-2 approximation, while clique and independent set do not admit anything close, because the complement step preserves exact optima but not ratios.

What hardness does and does not mean

NP-completeness is a worst-case statement about the problem when k is part of the input. It leaves a lot of room in practice, and knowing that room is as useful as the proof.

• Fixed k is polynomial, but badly. Checking every k-subset costs O(n^k · k²), which is polynomial for k = 3 (triangle finding, which also has faster matrix-multiplication methods) and hopeless for k = 30. Clique is W[1]-complete in parameterized complexity, the standard evidence that no algorithm runs in f(k) · n^c time for a constant c.
• Approximation is essentially impossible in the worst case. Håstad showed that maximum clique cannot be approximated within n^(1-ε) for any ε > 0 unless NP = ZPP, and Zuckerman later derandomised this to the assumption P ≠ NP. In the worst case, no polynomial algorithm can do much better than returning a single vertex.
• Structured graphs are often easy. Planar graphs have no clique larger than 4, so every candidate can be enumerated in polynomial time. Bipartite graphs have no clique larger than 2. Chordal graphs, and perfect graphs more generally, admit polynomial maximum-clique algorithms. Check whether your input class has such structure before reaching for an exponential solver; the planar algorithms article covers the planar case.
• Real instances are often tractable. Sparse graphs from social networks, biology and code analysis have small degeneracy, and Bron–Kerbosch with pivoting and a degeneracy ordering lists all maximal cliques quickly on them. Its worst case is O(3^(n/3)), matching the Moon–Moser bound on how many maximal cliques a graph can have.

Clique in real systems

When you meet clique in real work it rarely says so. Finding the largest group of mutually compatible items (tasks that can share a resource, records that pairwise match, configurations that pairwise co-exist) is maximum clique on the compatibility graph. If you have a conflict graph instead, the largest conflict-free set is maximum independent set on it, which is clique on its complement.

Three tool families cover most cases. Exact branch-and-bound solvers prune with an upper bound from greedy colouring, because a clique needs a different colour for every vertex, so a colouring with c colours proves no clique exceeds c; the graph colouring article explains those greedy orderings. Integer programming solvers take the formulation: maximise the sum of x_v subject to x_u + x_v ≤ 1 for every non-edge, which works well with good cuts, as in integer and linear programming. And for very large graphs, heuristics such as greedy construction plus local search give good cliques with no optimality proof, which is acceptable when the result is a recommendation rather than a guarantee. Always set a time limit and report the best bound alongside the best clique, so a caller knows how far from optimal the answer may be.

Common mistakes in clique reductions

• Reducing in the wrong direction. Turning a CLIQUE instance into SAT and calling it a hardness proof shows only that SAT is at least as hard as CLIQUE.
• Proving one direction. Showing a satisfying assignment yields a clique, but not that every k-clique yields an assignment, leaves room for spurious cliques. The no-edges-within-a-clause rule is what closes it.
• Adding edges inside clauses. Then a clique could take two literals from one clause and skip another, and the converse fails.
• Forgetting unmentioned variables. A clique fixes only the variables it mentions; the rest must be set arbitrarily, and the proof must say so.
• Confusing k with the input. "Clique is NP-hard" does not mean triangle detection is hard; it means k growing with n is.
• Transferring approximation results through the complement. A 2-approximate vertex cover says nothing useful about approximating clique.

What to do next

1. Reproduce the worked example by hand: draw the nine vertices, list the six missing pairs and find every 3-clique.
2. Run the code, then break it on purpose by adding within-clause edges and watch the cross-check fail.
3. Write the reduction from CLIQUE to INDEPENDENT SET and to VERTEX COVER, with the k and n - k mappings, and test both against brute force.
4. Practise the proof template on another reduction, such as 3-SAT to 3-colouring, and compare it with the 2-SAT algorithm to see why two literals per clause stays polynomial.
5. For a real compatibility problem, check the graph class first (planar, bipartite, chordal, sparse), then try Bron–Kerbosch with pivoting before an ILP or branch-and-bound solver.
6. Whatever solver you use, set a time limit and report both the best clique found and the best upper bound.