Introduction

This post provides a detailed proof that the Set Cover problem is NP-complete by reducing from Vertex Cover. Set Cover is a fundamental problem that generalizes Vertex Cover and Hitting Set, asking for a collection of sets that covers a universe.

Problem Definitions

Set Cover Problem

Input:

  • A universe U = {u₁, u₂, …, uₙ}
  • A collection of sets S = {S₁, S₂, …, Sₘ} where each Sᵢ ⊆ U
  • An integer k ≥ 0

Output: YES if there exists a collection of at most k sets from S whose union equals U (i.e., covers all elements of U), NO otherwise.

Note: This problem generalizes two known NP-complete problems: Vertex Cover and Hitting Set.

Vertex Cover Problem

Input:

  • An undirected graph G = (V, E)
  • Integer k ≥ 0

Output: YES if G has a vertex cover of size at most k (set of vertices covering all edges), NO otherwise.

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

Set Cover ∈ NP

Verification Algorithm: Given a candidate solution (collection C of at most k sets):

  1. Check that |C| ≤ k: O(1) time
  2. Check that C ⊆ S: O(n) time (since k ≤ n)
  3. Compute the union of sets in C: O(∑_{Sᵢ ∈ C} |Sᵢ|) time
  4. Check if the union equals U: O(n) time

Total Time: O(n + ∑_{Sᵢ ∈ C} |Sᵢ|), which is polynomial in input size.

Conclusion: Set Cover ∈ NP.

2. Reduce Vertex Cover to Set Cover

Key Insight: Given a Vertex Cover instance, we can reduce it to Set Cover by representing each edge as an element of the universe and each vertex as a set containing its incident edges. Then a vertex cover corresponds to a set cover.

Hint: An edge is covered by a vertex if the vertex is an endpoint. Therefore, covering all edges (vertex cover) is equivalent to covering all edge-elements (set cover) using sets corresponding to vertices.

2.1 Input Conversion

Given a Vertex Cover instance (G, k) where G = (V, E) with n vertices and m edges, we construct a Set Cover instance (U, S, k’).

Construction:

Step 1: Set Universe

  • U = E (edges become universe elements)
  • |U| = m

Step 2: Create Sets from Vertices

  • For each vertex v ∈ V:
    • Create set Sᵥ = {e ∈ E : e is incident to v} (set of all edges incident to v)
  • Collection S = {Sᵥ : v ∈ V}
  • |S| = n

Step 3: Set Parameter

  • k’ = k (same size constraint)

Step 4: Result

  • Set Cover instance: (U, S, k) where U = E and S contains one set per vertex

Detailed Example:

Consider Vertex Cover instance:

  • Graph G with vertices {1, 2, 3, 4}
  • Edges: E = {e₁ = (1,2), e₂ = (2,3), e₃ = (3,4), e₄ = (4,1)}
  • k = 2

Transformation:

  • U = {e₁, e₂, e₃, e₄}
  • Sets:
    • S₁ = {e₁, e₄} (edges incident to vertex 1)
    • S₂ = {e₁, e₂} (edges incident to vertex 2)
    • S₃ = {e₂, e₃} (edges incident to vertex 3)
    • S₄ = {e₃, e₄} (edges incident to vertex 4)
  • S = {S₁, S₂, S₃, S₄}
  • k’ = 2

Set Cover instance: (U, S, 2)

Note: A vertex cover {2, 4} corresponds to sets {S₂, S₄}, which cover U = {e₁, e₂, e₃, e₄}.

2.2 Output Conversion

Given: Set Cover solution (collection C of at most k sets covering U)

Extract Vertex Cover:

  • For each set Sᵥ in C, include vertex v in the vertex cover
  • This gives us a set C’ ⊆ V of size ≤ k

Verify Coverage:

  • For each edge e ∈ E = U:
    • Edge e must be covered by at least one set in C
    • If Sᵥ covers e, then vertex v is an endpoint of e
    • Therefore, at least one endpoint of e is in C’
    • Edge e is covered by C’
  • All edges are covered by C’

3. Correctness Justification

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

Given: Vertex Cover instance (G, k) has solution C (vertex cover of size ≤ k).

Construct Set Cover Solution:

  • For each vertex v ∈ C, include set Sᵥ in the collection
  • Collection C_sets = {Sᵥ : v ∈ C}
  • |C_sets| = |C| ≤ k

Verify Coverage:

For each element e ∈ U = E:

  • Edge e = (u, v) must be covered by C (since C is a vertex cover)
  • Therefore, at least one of u or v is in C
  • Without loss of generality, assume u ∈ C
  • Then Sᵤ ∈ C_sets and e ∈ Sᵤ (since e is incident to u)
  • Therefore, e is covered by C_sets
  • All elements of U are covered by C_sets

Conclusion: Set Cover has a solution.

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

Given: Vertex Cover instance (G, k) has no solution (no vertex cover of size ≤ k).

Proof:

Assume: Set Cover instance (U, S, k) has a solution (collection C of at most k sets covering U).

Extract Vertex Cover:

  • For each set Sᵥ in C, include vertex v in C’
  • C’ ⊆ V has size ≤ k

Check Coverage:

  • For each edge e = (u, v) ∈ E = U:
    • Edge e must be covered by at least one set in C
    • If Sᵥ covers e, then v is an endpoint of e
    • Therefore, at least one endpoint of e is in C’
    • Edge e is covered by C’
  • All edges are covered by C’

Contradiction:

  • C’ is a vertex cover of size ≤ k
  • This contradicts the assumption that G has no vertex cover of size ≤ k

Conclusion: Set Cover has no solution.

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

Given: Set Cover instance (U, S, k) has solution (collection C of at most k sets covering U).

Extract Vertex Cover:

  • For each set Sᵥ in C, include vertex v in C’
  • C’ ⊆ V has size ≤ k

Verify Coverage:

For each edge e = (u, v) ∈ E = U:

  • Edge e must be covered by at least one set in C
  • If Sᵥ covers e, then v is an endpoint of e and v ∈ C’
  • Therefore, at least one endpoint of e is in C’
  • Edge e is covered by C’

Key Insight:

  • Each edge corresponds to an element in the universe
  • Each vertex corresponds to a set containing its incident edges
  • Covering all edge-elements (set cover) means covering all edges (vertex cover)
  • Therefore, a set cover gives us a vertex cover

Conclusion: The set C’ covers all edges in G, so Vertex Cover has a solution.

Polynomial Time Analysis

Input Size:

  • Vertex Cover: Graph G with n vertices and m edges, integer k
  • Set Cover: Universe U with m elements, collection S with n sets, integer k

Construction Time:

  • Create universe U = E: O(m) time
  • For each vertex v: Create set Sᵥ containing incident edges: O(m) time total
  • Set k’ = k: O(1) time
  • Total: O(n + m) time

Conclusion: Reduction is polynomial-time.

Summary

We have shown:

  1. Set Cover ∈ NP: Solutions can be verified in polynomial time
  2. Vertex Cover ≤ₚ Set Cover: Polynomial-time reduction exists
  3. Correctness: Vertex Cover has solution ↔ Set Cover has solution

Therefore, Set Cover is NP-complete.

Key Insights

  1. Edge-to-Element Mapping: Each edge becomes an element in the universe
  2. Vertex-to-Set Mapping: Each vertex becomes a set containing its incident edges
  3. Coverage Equivalence: Covering all edges (vertex cover) is equivalent to covering all elements (set cover)
  4. Generalization: Set Cover generalizes Vertex Cover, making it a fundamental NP-complete problem

Relationship to Other Problems

Set Cover generalizes several NP-complete problems:

  1. Vertex Cover: As shown in this reduction, Vertex Cover is a special case where:
    • Universe = edges
    • Sets = vertices (each set contains incident edges)
    • Each element appears in exactly 2 sets

  2. Hitting Set: Set Cover and Hitting Set are dual problems (one is the complement of the other)

  3. Dominating Set: Can be reduced to Set Cover by representing vertices as elements and neighborhoods as sets

Practice Questions

  1. Modify the reduction to reduce Weighted Vertex Cover to Weighted Set Cover. How would you encode vertex weights?
  2. Extend the reduction to handle directed graphs. How would the sets change?
  3. Consider the optimization version: How would you reduce the optimization version of Vertex Cover to Set Cover?
  4. Prove the reverse reduction: Can we reduce Set Cover to Vertex Cover? How?
  5. Investigate special cases: For what set sizes is Set Cover polynomial-time solvable?

This reduction demonstrates how set systems can encode graph structures, enabling reductions between graph covering and set covering problems. Set Cover serves as a fundamental problem that unifies many NP-complete covering problems.