Scegli alcuni vertici e controlla soltanto i collegamenti fra quelli scelti: se anche una sola coppia è collegata da un arco, il gruppo non è indipendente.
Sul cammino A-B-C-D, con K=2, {A,C} va bene, perché non c'è un arco diretto A-C. {A,B} non va bene, perché l'arco A-B collega due vertici scelti. Vanno bene anche {A,D} e {B,D}. Con K=3 la risposta è no: ogni terna contiene almeno una coppia collegata.
Indipendente non vuol dire isolato: A può essere collegato a B, purché B resti fuori dal gruppo, e A e C possono essere connessi dal percorso A-B-C. È vietato solo un arco diretto fra due vertici scelti.
Il problema sta in NP: il certificato è l'elenco dei K vertici, e si controlla che siano distinti e che nessuna delle loro coppie formi un arco. Verificare un gruppo già proposto è polinomiale; trovare un gruppo adatto può essere molto più difficile.
È NP-hard perché 3-SAT si traduce in questo problema. Per ogni clausola si crea un triangolo con un vertice per ogni occorrenza di letterale, così se ne può scegliere al massimo uno per clausola. Si collegano poi le occorrenze opposte, come x e ¬x, perché non si possano scegliere insieme. Chiedere tanti vertici indipendenti quante sono le clausole equivale allora a scegliere un letterale vero in ciascuna senza contraddizioni: il gruppo esiste se e solo se la formula è soddisfacibile.
Complemento e collegamenti
Nessun complemento associato.
- una clique in G è un insieme indipendente nel grafo complementare
- S è indipendente se e solo se il resto dei nodi copre tutti gli archi
- 3-SAT si riduce a INDEPENDENT SET
INDEPENDENT SET è NP-completo