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.