Introduction

Independent Set is a fundamental graph problem proven NP-complete by reduction from 3-SAT. This post provides detailed proofs following the standard template for reducing from Independent Set to prove other problems are NP-complete.

Problem Definition: Independent Set

Independent Set Problem:

  • Input: Graph G = (V, E) and integer k
  • Output: YES if G has an independent set of size ≥ k, NO otherwise

Independent Set: A subset of vertices where no two vertices are connected by an edge.

Q1: How do you reduce Independent Set to Clique?

Answer: Use complement graph.

Key Insight:

  • S is an independent set in G ↔ S is a clique in G̅ (complement graph)
  • Complement graph reverses edge relationships

Hint: The complement graph G̅ has an edge (u,v) if and only if G does not have edge (u,v). This transforms “no edges” into “all edges”.

1. NP-Completeness Proof of Clique: Solution Validation

Clique Problem:

  • Input: Graph G = (V, E) and integer k
  • Output: YES if G has a clique of size ≥ k, NO otherwise

Clique ∈ NP:

Verification Algorithm: Given a candidate solution (set S of vertices):

  1. Check that S ⊆ V: O(|S|) time
  2. Check that |S| ≥ k: O(1) time
  3. For each pair (u, v) in S, check if (u, v) ∈ E: O(|S|²) time
  4. If all pairs connected, return YES; else return NO

Total Time: O(|S|²) ≤ O(n²), which is polynomial.

Conclusion: Clique ∈ NP.

2. Reduce Independent Set to Clique

2.1 Input Conversion

Given an Independent Set instance: graph G = (V, E), integer k.

Construction:

  • Create complement graph G̅ = (V, E̅) where:
    • V(G̅) = V(G)
    • E̅ = {(u, v) : u, v ∈ V, u ≠ v, (u, v) ∉ E}
  • Return Clique instance: graph G̅, integer k

Key Property: S is independent set in G ↔ S is clique in G̅

2.2 Output Conversion

Given: Clique S of size k in G̅

Extract Independent Set:

  • S is clique in G̅ ↔ S is independent set in G
  • Return S as independent set

3. Correctness Justification

3.1 If Independent Set has a solution, then Clique has a solution

Given: Independent Set instance has solution S of size k in G.

Construct Clique:

  • S is independent set in G
  • By definition of complement graph: S is clique in G̅
  • Therefore, S is clique of size k in G̅

Conclusion: Clique has a solution.

3.2a If Independent Set does not have a solution, then Clique has no solution

Given: Independent Set instance has no solution of size k in G.

Proof by Contradiction:

  • Assume Clique has solution S of size k in G̅
  • Then S is independent set of size k in G
  • Contradiction

Conclusion: Clique has no solution.

3.2b If Clique has a solution, then Independent Set has a solution

Given: Clique instance has solution S of size k in G̅.

Extract Independent Set:

  • S is clique in G̅ ↔ S is independent set in G
  • Therefore, S is independent set of size k in G

Conclusion: Independent Set has a solution.

Polynomial Time: O(n²) to create complement graph.

Therefore, Clique is NP-complete.

Q2: How do you reduce Independent Set to Vertex Cover?

Answer: Use complement relationship.

Key Insight:

  • S is an independent set ↔ V \ S is a vertex cover
  • Independent set of size k ↔ Vertex cover of size n - k

Hint: If S is an independent set, then V \ S covers all edges (since no edge has both endpoints in S). This is a simple set complement transformation.

1. NP-Completeness Proof of Vertex Cover: Solution Validation

Vertex Cover Problem:

  • Input: Graph G = (V, E) and integer k
  • Output: YES if G has a vertex cover of size ≤ k, NO otherwise

Vertex Cover ∈ NP:

Verification Algorithm: Given a candidate solution (set S of vertices):

  1. Check that S ⊆ V: O(|S|) time
  2. Check that |S| ≤ k: O(1) time
  3. For each edge (u, v) ∈ E, check if u ∈ S or v ∈ S: O(m) time
  4. If all edges covered, return YES; else return NO

Total Time: O(m), which is polynomial.

Conclusion: Vertex Cover ∈ NP.

2. Reduce Independent Set to Vertex Cover

2.1 Input Conversion

Given an Independent Set instance: graph G = (V, E), integer k.

Construction:

  • Return Vertex Cover instance: graph G, integer k’ = n - k

Key Property: S is independent set ↔ V \ S is vertex cover

2.2 Output Conversion

Given: Vertex Cover S’ of size k’ = n - k

Extract Independent Set:

  • S = V \ S’
  • |S| = n - |S'| = n - (n - k) = k
  • S is independent set (complement of vertex cover)

3. Correctness Justification

3.1 If Independent Set has a solution, then Vertex Cover has a solution

Given: Independent Set instance has solution S of size k in G.

Construct Vertex Cover:

  • S’ = V \ S
  • |S'| = n - k = k’
  • S’ is vertex cover (complement of independent set)

Verify Coverage:

  • For any edge (u, v) ∈ E:
    • Since S is independent set, not both u, v ∈ S
    • Therefore, at least one of u, v ∈ S’ = V \ S
    • Edge is covered

Conclusion: Vertex Cover has a solution.

3.2a If Independent Set does not have a solution, then Vertex Cover has no solution

Given: Independent Set instance has no solution of size k in G.

Proof by Contradiction:

  • Assume Vertex Cover has solution S’ of size k’
  • Then S = V \ S’ is independent set of size k
  • Contradiction

Conclusion: Vertex Cover has no solution.

3.2b If Vertex Cover has a solution, then Independent Set has a solution

Given: Vertex Cover instance has solution S’ of size k’ = n - k.

Extract Independent Set:

  • S = V \ S’
  • |S| = n - k’ = k
  • S is independent set (complement of vertex cover)

Verify Independence:

  • For any edge (u, v) ∈ E:
    • Since S’ is vertex cover, at least one of u, v ∈ S’
    • Therefore, not both u, v ∈ S = V \ S’
    • No edge within S

Conclusion: Independent Set has a solution.

Polynomial Time: O(1) (trivial transformation).

Therefore, Vertex Cover is NP-complete.

Q3: How do you reduce Independent Set to Maximum Cut?

1. NP-Completeness Proof of Maximum Cut: Solution Validation

Maximum Cut Problem:

  • Input: Graph G = (V, E) and integer k
  • Output: YES if G has a cut (S, V \ S) with at least k edges crossing, NO otherwise

Maximum Cut ∈ NP:

Verification Algorithm: Given a candidate solution (partition S, V \ S):

  1. Check that S ⊆ V: O(|S|) time
  2. Count edges crossing cut: O(m) time
  3. Check if count ≥ k: O(1) time

Total Time: O(m), which is polynomial.

Conclusion: Maximum Cut ∈ NP.

2. Reduce Independent Set to Maximum Cut

2.1 Input Conversion

Given an Independent Set instance: graph G = (V, E), integer k.

Construction:

  • Create complete graph G’ = (V, E’) where E’ contains all possible edges
  • Return Maximum Cut instance: graph G’, target = k(n - k)

Key Idea: Independent set of size k → Cut with k vertices on one side, no edges within that side

2.2 Output Conversion

Given: Maximum Cut (S, V \ S) with at least k(n - k) edges crossing

Extract Independent Set:

  • If |S| = k, return S as independent set
  • If |V \ S| = k, return V \ S as independent set
  • Otherwise, need refinement

3. Correctness Justification

3.1 If Independent Set has a solution, then Maximum Cut has a solution

Given: Independent Set instance has solution S of size k in G.

Construct Cut:

  • Partition: (S, V \ S)
  • Number of crossing edges = |S| · |V \ S| = k(n - k)
  • Since S is independent set, no edges within S
  • All edges incident to S cross the cut

Conclusion: Maximum Cut has a solution.

3.2a If Independent Set does not have a solution, then Maximum Cut has no solution

Given: Independent Set instance has no solution of size k in G.

Proof:

  • For any partition (S, V \ S) with |S| = k:
    • If S is not independent set, there are edges within S
    • These edges don’t cross the cut
    • Maximum crossing edges < k(n - k)
  • Similar argument for |V \ S| = k

Conclusion: Maximum Cut has no solution.

3.2b If Maximum Cut has a solution, then Independent Set has a solution

Given: Maximum Cut instance has solution (S, V \ S) with at least k(n - k) edges crossing.

Extract Independent Set:

  • If |S| = k and no edges within S, return S
  • If |V \ S| = k and no edges within V \ S, return V \ S
  • Otherwise, refine partition

Conclusion: Independent Set has a solution.

Polynomial Time: O(n²) to create complete graph.

Therefore, Maximum Cut is NP-complete.

Reduction Patterns and Hints

Pattern 1: Complement Graph

  • Key Insight: S is independent set ↔ S is clique in complement graph
  • Hint: Create complement graph G̅ where edges exist where G doesn’t
  • Example: Independent Set → Clique

Pattern 2: Complement Set

  • Key Insight: S is independent set ↔ V \ S is vertex cover
  • Hint: Use set complement relationship
  • Example: Independent Set → Vertex Cover

Pattern 3: Partition/Cut

  • Key Insight: Independent set forms one side of partition
  • Hint: Use independent set as one partition in cut problems
  • Example: Independent Set → Maximum Cut

Key Takeaways

  1. Complement Graph: Powerful tool for Clique reductions
  2. Complement Set: Natural for Vertex Cover reductions
  3. Partition Structure: Useful for Cut problems
  4. Template Structure: All reductions follow the same rigorous format
  5. Hints: Look for complement relationships and partition structures

Independent Set reductions demonstrate the power of complement relationships and graph transformations in NP-completeness proofs.