L’idea: scegli alcuni vertici e controlla soltanto i collegamenti fra quelli scelti. Se anche una sola coppia è collegata da un arco, il gruppo non è indipendente.
Esempio 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. Anche {A,D} e {B,D} vanno bene. Con K=3 la risposta è no: ogni terna contiene almeno una coppia collegata.
Indipendente non significa isolato: A può essere collegato a B, purché B resti fuori dal gruppo. A e C possono anche essere connessi dal percorso A—B—C: quello che è vietato è un arco diretto fra due vertici scelti.
Perché appartiene a NP: il certificato è l’elenco dei K vertici. 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.
Perché è NP-hard: si può tradurre 3-SAT in questo problema. Per ogni clausola si crea un triangolo con un vertice per ogni occorrenza di letterale; così puoi sceglierne al massimo uno per clausola. Si collegano inoltre le occorrenze opposte, come x e ¬x, per impedirti di sceglierle insieme. Chiedere tanti vertici indipendenti quante sono le clausole equivale a scegliere un letterale vero per ciascuna, senza contraddizioni: esiste quel gruppo 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