Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Vertex Cover
1.3.
Sample Examples
2.
Approximate Solution
2.1.
Pseudo Code
2.2.
Implementation in C++
2.2.1.
Time Complexity 
2.2.2.
Space Complexity 
3.
Frequently Asked Questions
3.1.
What are graphs?
3.2.
What is the NP-Complete problem?
3.3.
What do you mean by vertex cover?
4.
Conclusion 📃
Last Updated: Mar 27, 2024
Medium

Vertex Cover Problem

Author Harsh
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

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.

Find Minimum Vertex Cover

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:

Example 1

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,

Example 2

Sample Examples

Input

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,

Explaination 1

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.

Explaination 2

 

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;
}

 

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What are graphs?

One common type of data structure is a graph, which consists of a finite number of nodes (also called vertices) and a finite number of connected edges. An edge is a pair (u, v) that denotes a connection between u and v vertices.
 

What is the NP-Complete problem?

"Nondeterministic polynomial-time complete" is the abbreviation for the term "NP-complete.". The NP-Complete problem cannot be solved in polynomial time unless P = NP.
 

What do you mean by 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).
 

Conclusion 📃

In this article, we have extensively discussed an NP-Complete problem known as a vertex cover problem. We have seen the implementation for the same.

If you think this blog has helped you enhance your knowledge about the above question, and if you would like to learn more, check out our articles 

and many more on our Website.

Visit our website to read more such blogs. Make sure that you enroll in the courses provided by us, take mock tests and solve problems and interview puzzles available. Also, you can pay attention to interview stuff- interview experiences and an interview bundle for placement preparations.

Please upvote our blog to help other ninjas grow.

Happy Learning!

Previous article
Count the Number of Triangles in an Undirected Graph
Next article
Find the Number of Nodes between two vertices in an Acyclic Graph using the Disjoint Union Method
Live masterclass