Conjunto independiente

Es decir, es un conjunto V de vértices tal que para ningún par de ellos existe alguna arista que los conecten.En otras palabras, cada arista en el grafo contiene a lo más un vértice en V.Dado un grafo G, un subconjunto de vértices H ⊂ V(G) se llama conjunto independiente si no hay dos vértices en H que sean adyacentes.El problema de encontrar un conjunto con estas características se llama problema del máximo conjunto independiente y es NP-completo, por lo cual es poco probable que exista un algoritmo que lo resuelva eficientemente.Esto porque, si un grafo tiene un conjunto independiente de tamaño k, luego su grafo complemento tendrá un clique de tamaño k. El problema de decisión del conjunto independiente (al igual que el problema del clique) también es NP-completo.