Soy consciente de que Vertex Cover y Independent Set son complementos el uno del otro, pero también he oído que Independent Set se refiere a algo en relación con Clique; sólo que no recuerdo qué. No puede ser el complemento, porque si lo es, entonces Clique y Vertex cover serían lo mismo, ¿no?
Respuestas
¿Demasiados anuncios?
Un conjunto de vértices en un gráfico $\Gamma$ forman una camarilla si forman un conjunto independiente en el complemento de $\Gamma$ . ¿Es eso lo que buscabas?
En respuesta a su comentario: Las camarillas y los conjuntos independientes son conjuntos de vértices y no grafos, por lo que técnicamente no puede sean gráficos complementarios. Sin embargo, el subgrafo inducido abarcado por una camarilla es el complemento del subgrafo inducido abarcado por un conjunto independiente del mismo tamaño.
Craisis
Puntos
191
Si no recuerdo mal, todos son problemas Np-completos, lo que significa que pueden transformarse unos en otros en una cantidad de tiempo polinómica. Es decir, si se puede resolver el problema de la camarilla de manera eficiente, entonces se puede resolver la cubierta de vértices de manera eficiente. El problema de la camarilla suele transformarse en el problema de los 3 asientos.
