Definition 17 ([1]}) 
Let \(G\)  be a graph and \(k\)  a natural number. Let MIN-VC-DEC be the problem of deciding whether \(G\)  admits a vertex cover of size at most \(k\) . Similarly, let MIN-VC be the optimisation version of MIN-VC-DEC.

