[prev] 78 [next]

Vertex Cover (cont)

size of vertex cover C …    |C|  (number of elements in C)

optimal vertex cover …    a vertex cover of minimum size

Theorem.
Determining whether a graph has a vertex cover of a given size k is an NP-complete problem.