Weighted Vertex Cover
The weighted vertex cover problem aims to find the minimum weight vertex cover in a graph where vertices have weights. It has applications in network optimization.
Some algorithms are:
 Dynamic programming
 Greedy approximation
 Branch and bound
Java  Dynamic programming:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 int minVertexCover(Graph graph) {
Integer[] dp = new Integer[1 << graph.V];
return dfs(graph, dp, 0, 0);
}
int dfs(Graph graph, Integer[] dp, int mask, int weight) {
if (dp[mask] != null) {
return dp[mask];
}
// Check if covered
dp[mask] = weight;
// Try adding each vertex
for (int v = 0; v < graph.V; v++) {
// Add vertex v
dp[mask] = Math.min(dp[mask],
dfs(graph, dp, mask  (1<<v), weight + graph.weight[v]));
}
return dp[mask];
}

C++  Greedy approximation:
1
2
3
4
5
6
7
8
9
10
11
12
13
 int greedyVertexCover(Graph graph) {
int weight = 0;
vector<bool> covered(graph.V, false);
for (auto edge : graph.edges) {
if (!covered[edge.u] && !covered[edge.v]) {
weight += min(graph.weight[edge.u], graph.weight[edge.v]);
covered[edge.u] = covered[edge.v] = true;
}
}
return weight;
}

Python  Branch and bound:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 def min_vertex_cover(graph):
min_weight = float("inf")
def backtrack(curr_cover, curr_weight):
if curr_weight >= min_weight:
return
if is_vertex_cover(graph, curr_cover):
global min_weight
min_weight = curr_weight
for v in graph:
if v not in curr_cover:
backtrack(curr_cover + [v], curr_weight + graph.weight[v])
backtrack([], 0)
return min_weight

Weighted vertex cover generalizes the problem for weighted graphs.
A vertex cover in a graph is a set of vertices such that every edge in the graph is incident to at least one vertex in the set. In a weighted vertex cover, each vertex has an associated weight, and the objective is to find a vertex cover with the minimum total weight.
In graph theory, a vertex cover is a set of vertices such that each edge in the graph is incident to at least one vertex from the set. When weights are added to the vertices, the problem becomes finding a vertex cover that minimizes the sum of the weights of the vertices in the cover. This is known as a Weighted Vertex Cover.
Graphical Representation:
Suppose we have a graph with 4 vertices and 4 edges, where each vertex has a weight.
Vertex Weights: A=2, B=1, C=2, D=3
A(2)B(1)
 /
 /
 /
D(3)C(2)
Textual Representation of Vertex Cover:
Here, we can have multiple weighted vertex covers, but let’s find one with the minimum total weight.
 Vertex Cover = {A, C} => Total Weight = 2+2 = 4
 Vertex Cover = {B, D} => Total Weight = 1+3 = 4
 Vertex Cover = {B, C} => Total Weight = 1+2 = 3 (Minimum Weight)
Minimum Weighted Vertex Cover = {B, C} with Total Weight = 3
In this graphical representation, if we choose vertices B and C (highlighted), all edges are covered and the total weight is minimized to 3.
AB(1)
 /
 /
 /
DC(2)
By choosing the vertices B and C, every edge is adjacent to at least one selected vertex, and the total weight is minimized. This is a simple example to illustrate the concept of a Weighted Vertex Cover.
Solution
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 import java.util.Arrays;
public class WeightedVertexCover {
static int[] weight; // weight of each vertex
static int[] dp; // dp array to store minimum weight
public static int minWeightCover(int u, boolean[] visited, int[][] graph) {
if (dp[u] != 1) return dp[u];
visited[u] = true;
int includeU = weight[u];
int excludeU = 0;
for (int v = 0; v < graph.length; v++) {
if (graph[u][v] == 1 && !visited[v]) {
visited[v] = true;
includeU += minWeightCover(v, visited, graph);
excludeU += weight[v];
}
}
dp[u] = Math.min(includeU, excludeU);
return dp[u];
}
public static void main(String[] args) {
int[][] graph = {
{0, 1, 0, 0},
{1, 0, 1, 1},
{0, 1, 0, 1},
{0, 1, 1, 0}
};
weight = new int[]{1, 2, 3, 4};
dp = new int[4];
Arrays.fill(dp, 1);
boolean[] visited = new boolean[4];
int result = minWeightCover(0, visited, graph);
System.out.println("Minimum Weight of Vertex Cover: " + result);
}
}

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> weight;
vector<int> dp;
int minWeightCover(int u, vector<bool>& visited, vector<vector<int>>& graph) {
if (dp[u] != 1) return dp[u];
visited[u] = true;
int includeU = weight[u];
int excludeU = 0;
for (int v = 0; v < graph.size(); ++v) {
if (graph[u][v] && !visited[v]) {
visited[v] = true;
includeU += minWeightCover(v, visited, graph);
excludeU += weight[v];
}
}
return dp[u] = min(includeU, excludeU);
}
int main() {
vector<vector<int>> graph = {
{0, 1, 0, 0},
{1, 0, 1, 1},
{0, 1, 0, 1},
{0, 1, 1, 0}
};
weight = {1, 2, 3, 4};
dp.resize(4, 1);
vector<bool> visited(4, false);
int result = minWeightCover(0, visited, graph);
cout << "Minimum Weight of Vertex Cover: " << result << endl;
}

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 def min_weight_cover(u, visited, graph):
if dp[u] != 1:
return dp[u]
visited[u] = True
include_u = weight[u]
exclude_u = 0
for v in range(len(graph)):
if graph[u][v] and not visited[v]:
visited[v] = True
include_u += min_weight_cover(v, visited, graph)
exclude_u += weight[v]
dp[u] = min(include_u, exclude_u)
return dp[u]
graph = [
[0, 1, 0, 0],
[1, 0, 1, 1],
[0, 1, 0, 1],
[0, 1, 1, 0]
]
weight = [1, 2, 3, 4]
dp = [1] * 4
visited = [False] * 4
result = min_weight_cover(0, visited, graph)
print("Minimum Weight of Vertex Cover:", result)

Key Takeaways
 Weighted vertex cover extends the concept of vertex cover by assigning weights to vertices.
 Dynamic programming is a common approach to solve this problem efficiently.
 The function
minWeightCover
finds the minimum weighted vertex cover starting from a given vertex.  Memoization is used to store the result of subproblems in
dp
array.