Hola buenas, tengo dudas de la solución de este tipo de ejercicios NP-completitud, si alguien me pudiera dar una solución detallada con los pasos se lo agradecería.
El enunciado del ejercicio es:
Dado un conjunto U de objetos, una familia S={S1,...,Sn} de subconjuntos de U y un numero k, el problema SET-COVER consiste en determinar si existe una subfamilia T ? S de a lo sumo k subconjuntos cuya unión es igual a U. Demostrar que el problema SET-COVER es NP-completo utilizando el problema de decisión de la cobertura de vértices PDCV.
(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)