Vertex Cover Problem

Introduction

The vertex cover problem is an NP-Complete problem. An NP-Complete problem is a problem that cannot be solved in polynomial time. So to solve the vertex cover problem we will be using an approximate method to get the near-optimal solution.

In this blog, we will discuss the NP-Complete problem known as the Vertex cover problem. We will be solving the problem using an approximation method to get the near-optimal solution.

Problem Statement

In the vertex cover problem, you will be given an undirected graph G, your task is to find the Minimum vertex cover.

Vertex Cover

An undirected graph's vertex cover is a subset of its vertices that includes either "u" or "v" for each of the graph's edges (u, v).

For example:

The vertex cover for the above graph can be: {0, 1, 2}, {1, 3, 4} as all of the edges available in the graph are adjacent to these vertices. But we have to find the minimum size vertex cover that is why for the above graph the minimum vertex cover is {1, 2}. Also all of the edges are adjacent to vertex 1 and vertex 2.
 

Another Example,

Sample Examples

Input

Output

Vertex cover: 0 3 4 6

Explanation

We are basically selecting any random edge (u, v) then for that edge either u or v is in the output.

For example,

And the optimal vertex cover for the above input graph will be 0, 3, 4, 6 (there can be multiple answers also, but the minimum size will remain the same) because all of the edges available in the graph are adjacent to these vertices as shown in the below figure.

Approximate Solution

The vertex cover problem is an NP-Complete problem and it has been proven that the NP-Complete problem cannot be solved in polynomial time. So, we try to find the near optimal solution that finds a vertex cover. 

The approach mentioned below finds the vertex cover whose size is guaranteed to be no more than twice the size of an optimal vertex cover.
 

Approach to solve the problem

1. Initialize an empty set C to store the result
2. Consider a collection E of all the edges in a graph.
3. While E is not empty: 
   1. Pick an edge from collection E.
   2. Add u and v of the picked edge and store it in result set C.
   3. Remove all of the edges that incident on either u or v
4. Print result

Pseudo Code

SOLVE(){
    bool visited[total_vertices] <- {false, false, ......., false}
    for u <- 0 to total_vertices:
        if visited[u] is false:
            for v <- vertices[u]:
                if visited[v] is false:
                    visited[v] = visited[u] <- false
                    break;
    
    for i <- 0 to total_vertices:
        if visited[i] is true:
            print i
}

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// graph class
class undirected_graph{
public:

    // adj list
    vector<int> *vertices;
    int total_vertices;

    // constructor
    undirected_graph(int number_of_vertices){
        total_vertices = number_of_vertices;
        vertices = new vector<int>[number_of_vertices];
    }

    // function to add edge in our graph
    void addEdge(int v, int w){
        vertices[v].push_back(w);
        vertices[w].push_back(v);
    }

    // solving vertex cover problem
    void solve(){
        // visited boolean array
        vector<bool> visited(total_vertices, false);

        // visiting all of the vertices one by one
        for(int u = 0; u < total_vertices; u++){

            // if current vertex is not visited
            // process it
            if(!visited[u]){

                // visiting all of the vertices from 'u'
                for(int v : vertices[u]){

                    // if it's not already visited 
                    // mark it as visited and break the loop
                    if(!visited[v]){
                        visited[u] = visited[v] = true;
                        break;
                    }
                }
            }
        }

        // printing vertex cover
        for(int i = 0; i < total_vertices; i++){
            if(visited[i]) cout << i << " ";
        }
    }
};



int main(){ 
    // creating graph
    undirected_graph G(7);
    G.addEdge(0, 1);
    G.addEdge(1, 3);
    G.addEdge(3, 4);
    G.addEdge(4, 5);
    G.addEdge(4, 6);
    G.addEdge(5, 6);
    G.addEdge(6, 2);
    G.addEdge(2, 0);

    // calling the function for vertex cover problem
    cout << "Vertex cover: ";
    G.solve();
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Vertex Cover: 0 1 2 3 4 6

Time Complexity 

The Time Complexity of the above algorithm is O(V + E), where V is the number of vertices and E is the number of edges in our graph.
 

Space Complexity 

The Space Complexity of the above algorithm is O(V), where V is the number of vertices. As we are using a boolean array to keep the record of already visited vertices.

Read More - Time Complexity of Sorting Algorithms