Eliminar vértices hasta que no queden bordes
Dado un grafo no dirigido G(V,E), encuentre el número mínimo de vértices a eliminar para que el conjunto de aristas del grafo quede vacío.
En otras palabras: si eliminamos un vértice, eliminamos ese vértice junto con todos los bordes conectados a ese vértice. Encuentre el número mínimo de vértices a eliminar para que no queden aristas en G después de su eliminación.
Respuestas
Parece que usted mismo encontró la respuesta, está describiendo Vertex Cover , que en muchos aspectos son muy similares a Independent Set, ambos problemas son NP-completos .
La relación con el Conjunto Independiente es que en un gráfico$G = (V,E)$, un conjunto$S$es una cobertura mínima de vértice si y solo si$V \setminus S$es un conjunto independiente máximo.
Si sabe que Independent Set es NP-completo, se deduce que Vertex Cover también es NP-completo.
En otras palabras, también estás buscando un Conjunto Independiente máximo.
Cubierta de vértice . Dado un gráfico$G = (V,E)$y un entero$k$, existe un conjunto$S \subseteq V$de tamaño como máximo$k$tal que todos los bordes en$G$ son incidentes a un vértice en$S$?
Conjunto independiente . Dado un gráfico$G = (V,E)$y un entero$k$, existe un conjunto$S \subseteq V$de tamaño por lo menos$k$tal que la gráfica inducida $G[S]$no tiene bordes?