Vertex cover problem
As we have seen in the previous article all the NP-complements are equal in the way that it is a polynomial-time algorithm, meaning any problem will take polynomial time to be solved.
What is the vertex cover problem?
Find the minimum size vertex cover, when there is a given graph of n nodes and m edges.
What is vertex cover?
The vertex cover of a graph refers to the subset of its vertices, sich for every edge in the graph, that is from every vertex u to v, at least one must be the part of the subset.
The vertex cover problem falls under the category of NP-complete problem. It implies that there is no polynomial-time solution for finding the minimum vertex cover of a graph, until and unless we can prove P=NP. Though, there exist polynomial-time approximate algorithms to find the vertex cover of the graph.
The naive approach:
The problem can be naively solved by iterating over all the subsets of the vertices. We then select only those vertices and form a graph containing the edges contained by the vertices. We need to check if the graph newly plotted has all the edges of the original graph and is not based on something that is a candidate for the vertex cover. The set with the minimum size is printed.
The runtime complexity for the naive approach is exponential.
Though, we prefer the algorithms that have polynomial runtime complexity. An algorithm following a different approach is written below:
Step 1: We initialize the vertex cover set as empty.
Step 2: Let us assume the set of all edges in the graph to be E.
Step 3: When E is not empty:
We pick a random edge from the initialized set E. Then we add its constituent nodes into the vertex cover set. Let the constituent nodes be u and v. We remove the edges that have u and v as their part.
Step 4: Then we finally return the vertex cover set, after the set E is empty.
The time complexity for the algorithm will be O(n+m), where n is the number of nodes and m is the number of edges.
The space complexity for the algorithm will be O(n).
Set cover problem:
A set cover problem is defined as follows:
There are a set whose domain is X of n points, and m subsets. We need to find the least number of subsets to cover all the points.
The approach to solving it is as follows:
We pick the set covering the maximum number of points and throw out all the points covered.
The set cover problem is also an NP-complete problem.
Reference