Scribd
Upload
35 views20 pages

Vertex Cover Problem: NP-Completeness Explained

The Vertex Cover Problem is classified as NP-complete, meaning it is both in NP and NP-hard. It involves decision problems regarding the existence of vertex covers of specific sizes in a graph, as well as the optimization problem of finding the minimum vertex cover. The document discusses the concepts of NP-completeness and reductions between problems to establish this classification for the Vertex Cover Problem.

Uploaded by

sindhuvaishnavi5
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
35 views20 pages

Vertex Cover Problem: NP-Completeness Explained

The Vertex Cover Problem is classified as NP-complete, meaning it is both in NP and NP-hard. It involves decision problems regarding the existence of vertex covers of specific sizes in a graph, as well as the optimization problem of finding the minimum vertex cover. The document discusses the concepts of NP-completeness and reductions between problems to establish this classification for the Vertex Cover Problem.

Uploaded by

sindhuvaishnavi5
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

VERTEX COVER PROBLEM

Dr. [Link]
Asst. Prof., Dept of CSE
NP HARD AND NP COMPLETE

 A problem X is NP-complete if X ∈NP and X is NP-


hard.

 A problem X is NP-hard if every problem Y ∈NP


reduces to X.

 A reduction from problem A to problem B is a


polynomial-time algorithm that converts inputs to
problem A into equivalent inputs to problem B.
Equivalent means that both problem A and problem B
must output the same YES or NO answer for the input
and converted input.
NP Completeness-Proofs by
reduction
Vertex Cover Problem
Minimum Vertex Cover Problem
[Link]
qRKpU&t=29s
Vertex Cover Problem
Vertex Cover Problem
Vertex Cover Problem
Decision Problem

 Is there a Vertex cover of size 2 in the

graph?

 Is there a Vertex cover of size 3 in the

graph?

 Is there a Vertex cover of size k in the graph?


Optimization Problem

 Finding a Minimum vertex cover in the graph.


Minimum Vertex Cover Problem
Minimum Vertex Cover Problem
Minimum Vertex Cover Problem
Minimum Vertex Cover Problem
Minimum Vertex Cover Problem
Minimum Vertex Cover Problem
Minimum Vertex Cover Problem
Vertex Cover Problem is
NP Complete
Proof:Vertex Cover Problem is
NP Complete
Vertex Cover Problem is
NP Complete

You might also like