Vertex Cover Problem

Problem Statement

Given a graph of n nodes and m edges, find its minimum size vertex cover.

Vertex Cover: The vertex Cover of a graph is defined as a subset of its vertices, such for every edge in the graph, from vertex u to v, at least one of them must be a part of the vertex cover set.

Sample Test Cases:

Input 1:

Output 1:

[2, 4]

Explanation 1:

A valid vertex cover of the graph can be [2, 4]. [4, 0] is also a valid vertex cover.

Input 2:

Output 2:

[0, 1, 3, 4, 5, 6]

Explanation 2:

The vertex cover for the above graph can be seen to be made of the set [0, 1, 3, 4, 5, 6].

Approach

The vertex cover problem is an NP-Complete problem, which means that there is no known polynomial-time solution for finding the minimum vertex cover of a graph unless it can be proven that P = NP. There, however, exists polynomial-time approximate algorithms to find the vertex cover of a graph.

Naive Approach:

We can naively solve the problem by iterating over all the subsets of the vertices and using only those vertices, forming a new graph containing all the edges contained by these vertices. Then we can check if this new graph, contains all the edges of the original graph or not based on which it can be a candidate for the vertex cover. Out of all the candidates, we print the set, which has the minimum size.

This naive approach will have an exponential runtime complexity.

Approach 2(Approximate Algorithm for Vertex Cover):

The algorithms which are of interest to us in lieu of the vertex cover problem are the approximation algorithms that run in polynomial time complexity. A simple approximate algorithm for the vertex cover problem is described below:

• Initialize the vertex cover set as empty.
• Let the set of all edges in the graph be called E.
• While E is not empty:
  • Pick a random edge from the set E, add its constituent nodes, u and v into the vertex cover set.
  • For all the edges, which have either u or v as their part, remove them from the set E.
• Return the final obtained vertex cover set, after the set E is empty.

Pseudo Code for the above algorithm

It can be proven that the above algorithm will always find a vertex cover that is never greater than twice the size of the optimal vertex cover for the given graph.

Implementation/Code:

C++ Code

void vertexCover(vector < int > edges[], int n, int m) {
  vector < bool > vis(n, false);
  for (int i = 0; i < n; i++) {
    if (!vis[i]) {
      for (auto x: edges[i]) {
        if (!vis[x]) {
          vis[x] = true;
          vis[i] = true;
          break;
        }
      }
    }
  }
  for (int i = 0; i < n; i++) {
    if (vis[i]) {
      cout << i << " ";
    }
  }
  cout << endl;
}

Java Code

public static void vertexCover(LinkedList < Integer > edges[], int n, int m) {
  boolean[] vis = new boolean[n];
  Arrays.fill(vis, false);
  for (int i = 0; i < n; i++) {
    if (!vis[i]) {
      for (Integer x: edges[i]) {
        if (!vis[x]) {
          vis[x] = true;
          vis[i] = true;
          break;
        }
      }
    }
  }
  for (int i = 0; i < n; i++) {
    if (vis[i]) {
      System.out.print(i + " ");
    }
  }
  System.out.println();
}

Python Code

def vertexCover(edges, n, m):
    vis = [False] * n
    for i in range(n):
        if not vis[i]:
            for x in edges[i]:
                if not vis[x]:
                    vis[x] = True
                    vis[i] = True
                    break
    for i in range(n):
        if vis[i]:
            print(i, end=" ")
    print()

Complexity Analysis:

• Time Complexity: O(n + m) // n = number of nodes, m = number of edges
• Space Complexity: O(n)

FAQs

1. Can the vertex cover problem be solved in polynomial time if there are some constraints on the graphs?

A. Yes, it can be solved in polynomial time for Trees and Bipartite Graphs.

2. What algorithms are used to solve the vertex cover problem for bipartite graphs?

A. Flows can be used to solve the vertex cover problem for bipartite graphs.