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.

  1. Vertex Cover = {A, C} => Total Weight = 2+2 = 4
  2. Vertex Cover = {B, D} => Total Weight = 1+3 = 4
  3. 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.

      A-----B(1)
       |   /
       |  /
       | /
    D---C(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.