Introduction

The Clique Problem is a fundamental graph problem that plays a crucial role in understanding NP-completeness. It’s one of the classic problems used to demonstrate reduction techniques from 3-SAT and serves as a gateway to understanding many other NP-complete graph problems. In this post, we’ll explore the Clique Problem and its place in computational complexity theory.

What is a Clique?

A clique in an undirected graph is a subset of vertices where every pair of vertices is connected by an edge. In other words, it’s a complete subgraph - a subgraph where all vertices are pairwise adjacent.

Problem Definition

Clique Decision Problem:

Input:

  • An undirected graph G = (V, E)
  • An integer k

Output: YES if G contains a clique of size at least k, NO otherwise

Clique Optimization Problem:

Input: An undirected graph G = (V, E)

Output: The size of the largest clique in G (called the clique number, denoted omega(G))

Example

Consider the following graph:

    1---2
    | /|
    | X |
    |/ |
    3---4
  • Cliques of size 2: {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}
  • Cliques of size 3: {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}
  • Clique of size 4: {1,2,3,4} (this is a 4-clique, also called a complete graph K_4)

So the clique number of this graph is 4.

Visual Example

A graph showing both a clique and a non-clique:

        1---2
        |\ /|     ← Clique {1,2,3}: triangle (all pairs connected)
        | X |
        |/ \|
        3   4---5
            |     ← Non-clique {4,5,6}: missing edge 5-6
            6

Clique {1, 2, 3} ✓:

  • All three vertices form a complete triangle:
    • Edge 1-2 exists
    • Edge 1-3 exists
    • Edge 2-3 exists (diagonal)
  • Since every pair is connected, {1, 2, 3} is a 3-clique ✓

Non-clique {4, 5, 6} ✗:

  • Not all pairs are connected:
    • Edge 4-5 exists ✓
    • Edge 4-6 exists ✓
    • Edge 5-6 is missing ✗
  • Since 5 and 6 are not connected, {4, 5, 6} is NOT a clique ✗

Why Clique is in NP

To show that Clique is NP-complete, we first need to show it’s in NP.

Clique ∈ NP:

Given a candidate solution (a set of k vertices), we can verify in polynomial time:

  1. Check that the set has exactly k vertices: O(n) time (since k ≤ n)
  2. Check that every pair of vertices in the set is connected by an edge: O(n²) time (check all pairs, since k ≤ n)

Since k ≤ n, this verification takes polynomial time in the input size. Therefore, Clique is in NP.

NP-Completeness: Reduction from 3-SAT

To prove Clique is NP-complete, we need to show it’s NP-hard by reducing a known NP-complete problem to it. We’ll reduce 3-SAT to Clique.

Reduction Strategy

Given a 3-SAT instance with m clauses, we construct a graph G such that:

  • The 3-SAT instance is satisfiable if and only if G has a clique of size m

Construction

For a 3-SAT formula φ = C_1 ∧ C_2 ∧ … ∧ C_m where each clause C_i has 3 literals:

  1. Create vertices: For each literal occurrence in each clause, create a vertex
    • Label vertices as (i, j) where i is the clause number and j is the literal position
    • Example: For clause C_1 = (x₁ ∨ ! x₁ ∨ x₁), create vertices (1,1) for x₁, (1,2) for ! x₁, and (1,3) for x₁
  2. Add edges: Connect two vertices (i_1, j_1) and (i_2, j_2) with an edge if:
    • They are in different clauses (i_1 neq i_2)
    • The literals are not complementary (one is not the negation of the other)
  3. Set k = m: We’re looking for a clique of size m (one vertex per clause)

Why This Works

Intuition:

  • A clique of size m means we pick one literal from each clause
  • Since vertices in different clauses are connected only if literals are not complementary, a clique ensures we never pick both x and ! x
  • Therefore, a clique corresponds to a satisfying assignment

Formal Proof:

Forward Direction (3-SAT satisfiable → Clique exists):

  • If φ is satisfiable, there exists an assignment that makes at least one literal true in each clause
  • Pick the vertex corresponding to that true literal from each clause
  • These m vertices form a clique because:
    • They’re from different clauses (so edges exist by construction)
    • They can’t be complementary (both can’t be true simultaneously)

Reverse Direction (Clique exists → 3-SAT satisfiable):

  • If there’s a clique of size m, we have one vertex (literal) from each clause
  • Set variables to make these literals true:
    • If literal is x_i, set x_i = TRUE
    • If literal is ! x_i, set x_i = FALSE
  • Since no complementary literals are in the clique, this assignment is consistent
  • This assignment satisfies all clauses

Example Reduction

Consider the 3-SAT instance: φ = (x₁ ∨ x₁ ∨ x₁) ∧ (! x₁ ∨ x₁ ∨ ! x₁) ∧ (x₁ ∨ ! x₁ ∨ x₁)

Step 1: Create vertices

  • Clause 1: (1,1) for x₁, (1,2) for x₁, (1,3) for x₁
  • Clause 2: (2,1) for ! x₁, (2,2) for x₁, (2,3) for ! x₁
  • Clause 3: (3,1) for x₁, (3,2) for ! x₁, (3,3) for x₁

Step 2: Add edges

  • Connect vertices from different clauses if literals are not complementary
  • For example: (1,1) (represents x₁) connects to (2,2) (x₁) and (2,3) (! x₁) and (3,1) (x₁) and (3,2) (! x₁) and (3,3) (x₁)
  • But (1,1) does NOT connect to (2,1) because x₁ and ! x₁ are complementary
  • Similarly, (1,3) does NOT connect to (2,3) because x₁ and ! x₁ are complementary

Step 3: Find clique of size 3

  • One possible clique: {(1,2), (2,2), (3,3)} representing x₁ from clause 1, x₁ from clause 2, and x₁ from clause 3
  • This corresponds to assignment: x₁ = TRUE (arbitrary), x₁ = TRUE, x₁ = TRUE
  • Verify: All clauses satisfied!

Relationship to Other Graph Problems

The Clique Problem is closely related to several other NP-complete problems:

Independent Set

An independent set is a set of vertices where no two are adjacent (opposite of a clique).

Key Relationship:

  • S is a clique in G if and only if S is an independent set in G̅ (the complement graph)
  • Therefore, Clique and Independent Set are polynomially equivalent

Vertex Cover

A vertex cover is a set of vertices that covers all edges (every edge has at least one endpoint in the set).

Key Relationship:

  • S is an independent set if and only if V \setminus S is a vertex cover
  • This connects Clique to Vertex Cover through Independent Set

Graph Coloring

The chromatic number \chi(G) is the minimum number of colors needed to color vertices so no adjacent vertices share a color.

Key Relationship:

  • omega(G) ≤ chi(G) (clique number is a lower bound for chromatic number)
  • Finding the clique number helps bound the chromatic number

Practical Implications

Why Clique is Hard

The Clique Problem is NP-complete, which means:

  1. No Known Polynomial-Time Algorithm: Best known algorithms have exponential time complexity
  2. Brute Force: Check all C(n,k) subsets of size k - exponential in k
  3. Dynamic Programming: Can solve in O(2^n · n^2) time using inclusion-exclusion or bitmask DP
  4. Branch and Bound: Practical for small instances, but still exponential worst-case

Approximation

The Clique Problem is particularly difficult to approximate:

  • No PTAS: Unless P = NP, there is no polynomial-time approximation scheme
  • Hard to Approximate: Cannot be approximated within n^{1-\epsilon} for any \epsilon > 0 (unless P = NP)
  • This makes Clique one of the hardest problems to approximate

Real-World Applications

Despite being NP-complete, clique-finding has applications:

  1. Social Networks: Finding communities (groups where everyone knows everyone)
  2. Bioinformatics: Finding protein complexes, gene clusters
  3. Data Mining: Finding dense subgraphs in networks
  4. Cryptography: Some cryptographic protocols rely on clique hardness
  5. Network Analysis: Identifying tightly-knit groups in communication networks

Special Cases

Some restricted versions of Clique are tractable:

  • Planar Graphs: Clique is polynomial-time solvable (maximum clique size is at most 4)
  • Bounded Treewidth: Can be solved efficiently using tree decomposition
  • Interval Graphs: Polynomial-time algorithms exist
  • Perfect Graphs: Clique and coloring can be solved in polynomial time

Runtime Analysis

Brute Force Approach

Algorithm: Check all C(n,k) subsets of size k

  • Time Complexity: O(C(n,k) · k^2) = O(n^k · k^2)
  • Space Complexity: O(k) for storing current subset
  • Analysis: For each subset, check all C(k,2) pairs of vertices for edges

Dynamic Programming

Algorithm: Use bitmask DP to track visited vertices

  • Time Complexity: O(2^n · n^2)
  • Space Complexity: O(2^n · n)
  • Subproblem: dp[mask][v] = true if there exists a clique in vertices mask ending at v
  • Recurrence: dp[mask][v] = \bigvee_{u ∈ mask, (u,v) ∈ E} dp[mask \setminus {v}][u]

Branch-and-Bound

Algorithm: Systematic search with pruning

  • Time Complexity: Exponential worst-case, but better than brute force with good pruning
  • Space Complexity: O(n) for recursion stack
  • Pruning: Stop exploring branches that can’t lead to clique of size k

Bron-Kerbosch Algorithm (Maximum Clique)

Algorithm: Recursive backtracking for finding all maximal cliques

  • Time Complexity: O(3^{n/3}) worst-case (tight bound)
  • Space Complexity: O(n)
  • Practical Performance: Very efficient for sparse graphs

Verification Complexity

Given a candidate clique of size k:

  • Time Complexity: O(n²) - check all pairs (since k ≤ n)
  • Space Complexity: O(1) additional space
  • This polynomial-time verifiability shows Clique is in NP

Key Takeaways

  1. Clique is NP-Complete: Proven by reduction from 3-SAT
  2. Reduction Pattern: The 3-SAT → Clique reduction is a classic example showing how to encode logical constraints as graph structures
  3. Graph Problem Relationships: Clique is closely related to Independent Set, Vertex Cover, and Graph Coloring
  4. Hard to Approximate: Clique is particularly difficult to approximate, making it a benchmark for approximation hardness
  5. Practical Algorithms: Despite NP-completeness, various techniques (DP, branch-and-bound, heuristics) work well for many practical instances

Reduction Summary

3-SAT ≤ₚ Clique:

  • Given 3-SAT instance with m clauses
  • Create graph with vertices for each literal occurrence
  • Connect vertices from different clauses if literals are not complementary
  • 3-SAT satisfiable ↔ Graph has clique of size m

This reduction is polynomial-time because:

  • Number of vertices: 3m (at most)
  • Number of edges: O(m^2) (check all pairs)
  • Construction time: Polynomial in input size

Further Reading

  • Garey & Johnson: “Computers and Intractability” - Standard reference for NP-completeness proofs
  • Approximation Hardness: Research on why Clique is hard to approximate
  • Perfect Graphs: Special graph classes where Clique is tractable
  • Social Network Analysis: Applications of clique detection in real networks

Practice Problems

  1. Construct the graph for the 3-SAT instance: (x₁ ∨ x₁ ∨ ! x₁) ∧ (! x₁ ∨ x₁ ∨ x₁) ∧ (x₁ ∨ ! x₁ ∨ x₁) Find a clique of size 3 and determine the corresponding satisfying assignment.

  2. Prove the relationship: Show that S is a clique in G if and only if S is an independent set in G̅ (the complement graph).

  3. Reduction practice: Given that Clique is NP-complete, show that Independent Set is also NP-complete using the complement graph relationship.

  4. Algorithm design: Design a dynamic programming algorithm to find the maximum clique size in a graph. What is its time complexity?

  5. Special cases: Research why the Clique problem is polynomial-time solvable for planar graphs. What is the maximum clique size possible in a planar graph?

Understanding the Clique Problem and its NP-completeness proof provides crucial insight into reduction techniques and the interconnected nature of NP-complete problems. The 3-SAT → Clique reduction is a fundamental example that demonstrates how logical constraints can be encoded as graph structures.