Vertex Cover
- Vertex Cover Definition
- Vertex Cover ≤ρ Clique
- Clique ≤ρ Vertex Cover
- Vertex Cover ϵ NP
1) Vertex Cover:
Definition: – It represents a set of vertex or node in a graph G (V, E), which gives the connectivity of a complete graph
According to the graph G of vertex cover which you have created, the size of Vertex Cover =2
2) Vertex Cover ≤ρ Clique
In a graph G of Vertex Cover, you have N vertices which contain a Vertex Cover K. There must exist of Clique Size of size N-K in its complement.
According to the graph G, you have
Number of vertices=6
Size of Clique=N-K=4
You can also create the Clique by complimenting the graph G of Vertex Cover means in simpler form connect the vertices in Vertex Cover graph G through edges where edges don?t exist and remove all the existed edges
You will get the graph G with Clique Size=4
3) Clique ≤ρ Vertex Cover
Here through the Reduction process, you can get the Vertex Cover form Clique by just complimenting the Clique graph G within the polynomial time.
4) Vertex Cover ϵ NP
As you know very well, you can get the Vertex Cover through Clique and to convert the decision-based NP problem into Clique firstly you have to convert into 3CNF and 3CNF into SAT and SAT into CIRCUIT SAT that comes from NP.
Proof of NPC:-
- Reduction from Clique to Vertex Cover has been made within the polynomial time. In the simpler form, you can convert into Vertex Cover from Clique within the polynomial time
- And verification has also been done when you convert Vertex Cover to Clique and Clique to 3CNF and satisfy/verified the output within a polynomial time also, so it concluded that Reduction and Verification had been done in the polynomial time that means Vertex Cover also comes in NPC