Vertex cover of a given size

Statement

Vertex cover of a given size

Given an undirected graph and a positive integer , is there a vertex cover using at most vertices, if so what is it?

Solutions

Theory

• Vertex cover of a given size is NP
• Vertex cover of a given size is NP-complete

Related problems

• Minimum vertex cover problem
• Independent set of a given size