Reductions from Vertex Cover: Detailed Proofs
Introduction
Vertex Cover is a fundamental covering problem proven NP-complete by reduction from Independent Set. This post provides detailed proofs following the standard template for reducing from Vertex Cover to prove other problems are NP-complete.
Problem Definition: Vertex Cover
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: A subset of vertices such that every edge has at least one endpoint in the cover.
Q1: How do you reduce Vertex Cover to Set Cover?
Answer: Encode edges as elements and vertices as sets.
Key Insight:
- Each edge must be covered by at least one endpoint
- Encode edges as universe elements
- Encode vertices as sets (edges incident to that vertex)
Hint: Think of covering edges as covering elements. Each vertex becomes a set containing all edges incident to it. A vertex cover corresponds to a set cover.
1. NP-Completeness Proof of Set Cover: Solution Validation
Set Cover Problem:
- Input: Universe U, collection C of subsets of U, integer k
- Output: YES if there exists subcollection C’ ⊆ C with
|C'|≤ k covering U, NO otherwise
Set Cover ∈ NP:
Verification Algorithm: Given a candidate solution (subcollection C’):
- Check that C’ ⊆ C: O(
|C'|) time - Check that
|C'|≤ k: O(1) time - Check that ∪_{S ∈ C’} S = U: O(
|U|·|C'|) time
Total Time: O(|U| · |C'|), which is polynomial.
Conclusion: Set Cover ∈ NP.
2. Reduce Vertex Cover to Set Cover
2.1 Input Conversion
Given a Vertex Cover instance: graph G = (V, E), integer k.
Construction:
- Universe U = E (all edges)
- For each vertex v ∈ V, create set Sᵥ = {e ∈ E : v ∈ e} (edges incident to v)
- Collection C = {Sᵥ : v ∈ V}
- Return Set Cover instance: universe U, collection C, integer k
Key Property: Vertex cover of size k ↔ Set cover of size k
2.2 Output Conversion
Given: Set Cover solution C’ ⊆ C with |C'| ≤ k covering U
Extract Vertex Cover:
- S = {v ∈ V : Sᵥ ∈ C’}
|S|=|C'|≤ k- S is vertex cover (each edge covered by at least one set Sᵥ)
3. Correctness Justification
3.1 If Vertex Cover has a solution, then Set Cover has a solution
Given: Vertex Cover instance has solution S of size ≤ k in G.
Construct Set Cover:
- C’ = {Sᵥ : v ∈ S}
|C'|=|S|≤ k- For each edge e = (u, v) ∈ E:
- Since S is vertex cover, at least one of u, v ∈ S
- Therefore, e ∈ Sᵤ or e ∈ Sᵥ
- Edge e is covered by C’
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 has no solution of size ≤ k in G.
Proof by Contradiction:
- Assume Set Cover has solution C’ of size ≤ k
- Then S = {v : Sᵥ ∈ C’} is vertex cover of size ≤ k
- Contradiction
Conclusion: Set Cover has no solution.
3.2b If Set Cover has a solution, then Vertex Cover has a solution
Given: Set Cover instance has solution C’ ⊆ C with |C'| ≤ k covering U.
Extract Vertex Cover:
- S = {v ∈ V : Sᵥ ∈ C’}
|S|=|C'|≤ k- For each edge e ∈ E:
- Since C’ covers U, e is in some set Sᵥ ∈ C’
- Therefore, v ∈ S, so e is covered by S
Conclusion: Vertex Cover has a solution.
Polynomial Time: O(n + m) to create sets.
Therefore, Set Cover is NP-complete.
Q2: How do you reduce Vertex Cover to Hitting Set?
1. NP-Completeness Proof of Hitting Set: Solution Validation
Hitting Set Problem:
- Input: Collection C of subsets of universe U, integer k
- Output: YES if there exists set H ⊆ U with
|H|≤ k hitting all sets in C, NO otherwise
Hitting Set ∈ NP:
Verification Algorithm: Given a candidate solution (set H):
- Check that H ⊆ U: O(
|H|) time - Check that
|H|≤ k: O(1) time - For each set S ∈ C, check if S ∩ H ≠ ∅: O(
|C|·|U|) time
Total Time: O(|C| · |U|), which is polynomial.
Conclusion: Hitting Set ∈ NP.
2. Reduce Vertex Cover to Hitting Set
2.1 Input Conversion
Given a Vertex Cover instance: graph G = (V, E), integer k.
Construction:
- Universe U = V (all vertices)
- Collection C = {Sₑ : e ∈ E} where Sₑ = {u, v} for edge e = (u, v)
- Return Hitting Set instance: universe U, collection C, integer k
Key Property: Vertex cover of size k ↔ Hitting set of size k
2.2 Output Conversion
Given: Hitting Set solution H ⊆ U with |H| ≤ k hitting all sets
Extract Vertex Cover:
- S = H
|S|=|H|≤ k- S is vertex cover (each edge e has Sₑ ∩ H ≠ ∅)
3. Correctness Justification
3.1 If Vertex Cover has a solution, then Hitting Set has a solution
Given: Vertex Cover instance has solution S of size ≤ k in G.
Construct Hitting Set:
- H = S
|H|=|S|≤ k- For each edge e = (u, v) ∈ E:
- Since S is vertex cover, at least one of u, v ∈ S
- Therefore, Sₑ ∩ H ≠ ∅
- Set Sₑ is hit
Conclusion: Hitting Set has a solution.
3.2a If Vertex Cover does not have a solution, then Hitting Set has no solution
Given: Vertex Cover instance has no solution of size ≤ k in G.
Proof by Contradiction:
- Assume Hitting Set has solution H of size ≤ k
- Then H is vertex cover of size ≤ k
- Contradiction
Conclusion: Hitting Set has no solution.
3.2b If Hitting Set has a solution, then Vertex Cover has a solution
Given: Hitting Set instance has solution H ⊆ U with |H| ≤ k hitting all sets.
Extract Vertex Cover:
- S = H
|S|=|H|≤ k- For each edge e = (u, v) ∈ E:
- Since H hits Sₑ, Sₑ ∩ H ≠ ∅
- Therefore, at least one of u, v ∈ H = S
- Edge e is covered
Conclusion: Vertex Cover has a solution.
Polynomial Time: O(m) to create collection.
Therefore, Hitting Set is NP-complete.
Q3: How do you reduce Vertex Cover to Independent Set?
1. NP-Completeness Proof of Independent Set: Solution Validation
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 ∈ NP:
Verification Algorithm: Given a candidate solution (set S of vertices):
- Check that S ⊆ V: O(
|S|) time - Check that
|S|≥ k: O(1) time - For each pair (u, v) in S, check if (u, v) ∈ E: O(
|S|²) time
Total Time: O(|S|²), which is polynomial.
Conclusion: Independent Set ∈ NP.
2. Reduce Vertex Cover to Independent Set
2.1 Input Conversion
Given a Vertex Cover instance: graph G = (V, E), integer k.
Construction:
- Return Independent Set instance: graph G, integer k’ = n - k
Key Property: S is vertex cover ↔ V \ S is independent set
2.2 Output Conversion
Given: Independent Set solution S’ of size k’ = n - k
Extract Vertex Cover:
- S = V \ S’
|S|= n - k’ = k- S is vertex cover (complement of independent set)
3. Correctness Justification
3.1 If Vertex Cover has a solution, then Independent Set has a solution
Given: Vertex Cover instance has solution S of size ≤ k in G.
Construct Independent Set:
- S’ = V \ S
|S'|= n -|S|≥ n - k = k’- S’ is independent set (complement of vertex cover)
Conclusion: Independent Set has a solution.
3.2a If Vertex Cover does not have a solution, then Independent Set has no solution
Given: Vertex Cover instance has no solution of size ≤ k in G.
Proof by Contradiction:
- Assume Independent Set has solution S’ of size ≥ k’
- Then S = V \ S’ is vertex cover of size ≤ k
- Contradiction
Conclusion: Independent Set has no solution.
3.2b If Independent Set has a solution, then Vertex Cover has a solution
Given: Independent Set instance has solution S’ of size ≥ k’ = n - k.
Extract Vertex Cover:
- S = V \ S’
|S|= n -|S'|≤ n - k’ = k- S is vertex cover (complement of independent set)
Conclusion: Vertex Cover has a solution.
Polynomial Time: O(1) (trivial transformation).
Therefore, Independent Set is NP-complete.
Reduction Patterns and Hints
Pattern 1: Set Encoding
- Key Insight: Edges become elements, vertices become sets
- Hint: Each vertex covers its incident edges
- Example: Vertex Cover → Set Cover
Pattern 2: Covering Structure
- Key Insight: Vertex cover naturally encodes covering
- Hint: Map covering relationships directly
- Example: Vertex Cover → Hitting Set
Pattern 3: Complement Relationship
- Key Insight: Vertex cover ↔ Independent set (complement)
- Hint: Use V \ S relationship
- Example: Vertex Cover → Independent Set
Key Takeaways
- Set Encoding: Edges → elements, vertices → sets
- Covering Structure: Natural for covering problems
- Complement Relationship: Vertex Cover ↔ Independent Set
- Template Structure: All reductions follow rigorous format
- Hints: Use set representations and complement relationships
Vertex Cover reductions demonstrate how covering structures can be encoded as set problems.