Vertex Cover Problem
Problem Statement
Given an undirected graph, find the minimum vertex cover — the smallest set of vertices such that every edge in the graph has at least one endpoint in the set.
Example:
- Input:
V = 5, edges = [(0,1),(0,2),(1,3),(3,4),(4,5),(5,3)] - Output:
Minimum vertex cover: {0, 3, 5}(size 3)
Noob-Friendly Explanation
Imagine you have security cameras and a hallway system. Each hallway connects two rooms. A camera in a room can watch all hallways connected to it. You want to place the fewest cameras so that every hallway is watched by at least one camera.
Each room is a vertex, each hallway is an edge. You need to choose the smallest set of rooms to put cameras in so that every hallway has a camera at one of its endpoints.
Approach 1: Brute Force (Try All Subsets)
Intuition
Try every possible subset of vertices. For each subset, check if it forms a valid vertex cover (every edge has at least one endpoint in the subset). Track the smallest valid subset.
Algorithm
- Generate all 2^V subsets of vertices.
- For each subset, check if every edge is covered.
- Return the smallest subset that covers all edges.
import java.util.*;
public class VertexCoverBrute {
public static List<Integer> minVertexCover(int V, int[][] edges) {
List<Integer> best = null;
for (int mask = 0; mask < (1 << V); mask++) {
List<Integer> subset = new ArrayList<>();
Set<Integer> inCover = new HashSet<>();
for (int i = 0; i < V; i++) {
if ((mask & (1 << i)) != 0) {
subset.add(i);
inCover.add(i);
}
}
// Check if this subset covers all edges
boolean valid = true;
for (int[] edge : edges) {
if (!inCover.contains(edge[0]) && !inCover.contains(edge[1])) {
valid = false;
break;
}
}
if (valid && (best == null || subset.size() < best.size())) {
best = new ArrayList<>(subset);
}
}
return best;
}
public static void main(String[] args) {
int V = 6;
int[][] edges = {{0,1},{0,2},{1,3},{3,4},{4,5},{5,3}};
List<Integer> cover = minVertexCover(V, edges);
System.out.println("Minimum vertex cover: " + cover);
System.out.println("Size: " + cover.size());
}
}Complexity Analysis
- Time Complexity: O(2^V * E) - 2^V subsets, each checked against E edges
- Space Complexity: O(V) - for storing the current subset
Approach 2: Optimal (Greedy Approximation)
Intuition
The minimum vertex cover problem is NP-hard, so there's no known polynomial algorithm for exact solution. However, a 2-approximation greedy algorithm exists: repeatedly pick any uncovered edge and add BOTH endpoints to the cover. This gives a cover at most twice the optimal size.
For small V, the brute force above is exact. For larger graphs, the greedy approach is practical.
Algorithm
- Mark all edges as uncovered.
- While there are uncovered edges: a. Pick any uncovered edge (u, v). b. Add both u and v to the cover. c. Remove all edges incident to u or v.
- Return the cover.
import java.util.*;
public class VertexCoverOptimal {
public static Set<Integer> approxVertexCover(int V, int[][] edges) {
Set<Integer> cover = new HashSet<>();
boolean[] edgeCovered = new boolean[edges.length];
for (int i = 0; i < edges.length; i++) {
if (!edgeCovered[i]) {
int u = edges[i][0], v = edges[i][1];
cover.add(u);
cover.add(v);
// Mark all edges incident to u or v as covered
for (int j = i; j < edges.length; j++) {
if (edges[j][0] == u || edges[j][1] == u ||
edges[j][0] == v || edges[j][1] == v) {
edgeCovered[j] = true;
}
}
}
}
return cover;
}
public static void main(String[] args) {
int V = 6;
int[][] edges = {{0,1},{0,2},{1,3},{3,4},{4,5},{5,3}};
Set<Integer> cover = approxVertexCover(V, edges);
System.out.println("Approximate vertex cover: " + cover);
System.out.println("Size: " + cover.size());
}
}Complexity Analysis
- Time Complexity: O(V * E) in worst case for the greedy approach (or O(2^V * E) for exact brute force)
- Space Complexity: O(V) - for the cover set