¿Por qué el problema mínimo de la cubierta del vértice está en NP?

Question

Me refiero a la definición de la portada de vertex mínimo del libro Algoritmos de aproximación por Vijay V. Vazirani (Página 23):

es el tamaño de la cubierta mínima del vértice en $ g $ a la mayoría $ k $ ?

y justo después de esta definición, el autor afirma que este problema está en np .

My Pregunta : ¿Qué sería un certificado YES ?

De hecho, nuestro algoritmo no determinista podría adivinar un subconjunto de vértices, denotado por $ v '$ , y podemos verificar si $ v '$ es una cubierta de vértice de alguna cardinalidad en el tiempo polinomial, pero ¿cómo podríamos mostrar que $ v' $ es Mínimo En tiempo polinomial?

Answer 1

No tiene que verificar que $ v '$ es mínimo. La versión de decisión de la cubierta de vértices (que ha citado en su pregunta) solo le pide que decida si hay una cubierta de vértice de tamaño en la mayoría de $ k $ .

Para verificar que $ v '$ es un certificado sí válido para una instancia $ \ langosto g= (v, E), k \ rangle $ usted simplemente compruebe que:

• $ v '\ subespeteq v $ ,
• $ | v '|\ le k $ , y
• $ \ forall (u, v) \ in e, \ {u, v \ \ \ tap v '\ neq \ vaciarset $ .