Problem

Given an undirected graph, find the minimum set of vertices such that every edge in the graph is incident to at least one vertex in the set (vertex cover). The goal is to minimize the size of this set.

Examples

Example 1

graph LR;
	A(0) --- B(1):::green
	B --- C(2)
	C --- D(3):::green & E(4):::green
	D --- E
	D --- F(5)
	E --- F
	D --- G(6)
	
classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff; 	
  
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

Input:
n = 7
edges = [[0,1],[1,2],[2,3],[3,4],[3,5],[4,5],[3,6]]

Output: [1,3,4]

Explanation:
- The graph (nodes 0..6) has edges: (0,1), (1,2), (2,3), (3,4), (3,5), (4,5), (3,6).
- The vertex set {1,3,4} covers every edge:
  * (0,1) covered by 1
  * (1,2) covered by 1
  * (2,3) covered by 3
  * (3,4) covered by 3 or 4
  * (3,5) covered by 3
  * (4,5) covered by 4
  * (3,6) covered by 3
- Therefore {1,3,4} is a valid vertex cover. In this example the minimum cover size is 3, and {1,3,4} is one optimal choice.

Solution

Method 1 – Greedy 2-Approximation Algorithm

Intuition

Since the problem is NP-hard, we use a greedy algorithm that repeatedly picks an edge and adds both its endpoints to the cover, removing all edges incident to those vertices. This gives a cover at most twice the size of the minimum.

Approach

  1. Initialize the cover set as empty.
  2. While there are uncovered edges:
  • Pick any uncovered edge (u, v).
  • Add both u and v to the cover set.
  • Remove all edges incident to u or v.
  1. Return the cover set.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
  std::unordered_set<int> vertexCover(const std::vector<std::vector<int>>& edges, int n) {
    std::unordered_set<int> cover;
    std::vector<std::vector<int>> adj(n);
    for (const auto& e : edges) {
      adj[e[0]].push_back(e[1]);
      adj[e[1]].push_back(e[0]);
    }
    std::vector<bool> removed(n, false);
    for (int u = 0; u < n; ++u) {
      for (int v : adj[u]) {
        if (!removed[u] && !removed[v]) {
          cover.insert(u);
          cover.insert(v);
          removed[u] = removed[v] = true;
        }
      }
    }
    return cover;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
  public Set<Integer> vertexCover(List<int[]> edges, int n) {
    Set<Integer> cover = new HashSet<>();
    boolean[] removed = new boolean[n];
    Map<Integer, List<Integer>> adj = new HashMap<>();
    for (int i = 0; i < n; i++) adj.put(i, new ArrayList<>());
    for (int[] e : edges) {
      adj.get(e[0]).add(e[1]);
      adj.get(e[1]).add(e[0]);
    }
    for (int u = 0; u < n; u++) {
      for (int v : adj.get(u)) {
        if (!removed[u] && !removed[v]) {
          cover.add(u);
          cover.add(v);
          removed[u] = removed[v] = true;
        }
      }
    }
    return cover;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
  def vertex_cover(self, edges: list[list[int]], n: int) -> set[int]:
    cover = set()
    removed = [False] * n
    adj = [[] for _ in range(n)]
    for u, v in edges:
      adj[u].append(v)
      adj[v].append(u)
    for u in range(n):
      for v in adj[u]:
        if not removed[u] and not removed[v]:
          cover.add(u)
          cover.add(v)
          removed[u] = removed[v] = True
    return cover

Complexity

  • ⏰ Time complexity: O(N + M), where N is the number of vertices and M is the number of edges, since each edge and vertex is processed at most once.
  • 🧺 Space complexity: O(N + M), for adjacency lists and bookkeeping.