Nella teoria dei grafi, un insieme indipendente o insieme stabile è un insieme di vertici in un grafo, nessuno dei quali è adiacente a due a due. Cioè, è un insieme I di vertici tale che per ogni due vertici in I, non c'è nessuno spigolo che connette i due. Equivalentemente, ciascuno spigolo del grafo ha al massimo un estremo in I. La dimensione di un insieme indipendente è il numero di vertici che esso contiene. Gli insiemi indipendenti sono stati chiamati anche insiemi internamente stabili.[1]
Un insieme indipendente massimale è un insieme indipendente tale che aggiungere un qualsiasi vertice all'insieme costringe l'insieme stesso a contenere uno spigolo.
Un insieme indipendente massimo è un insieme indipendente della più grande dimensione possibile per un dato grafo G. Questa dimensione è chiamata numero d'indipendenza di G, e denotata α(G).[2] Il problema di trovare un tale insieme è chiamato problema del massimo insieme indipendente ed è un problema di ottimizzazione NP-difficile. Come tale, è improbabile che esista un algoritmo efficiente per trovare un insieme indipendente massimo di un grafo.
Ogni massimo insieme indipendente è anche massimale, ma l'implicazione inversa non è necessariamente valida.
Un insieme è indipendente se e solo se è una cricca nel complemento del grafo, così i due concetti sono complementari. Infatti, grafi sufficientemente grandi senza grandi cricche hanno grandi insiemi indipendenti, un tema che è esplorato nella teoria di Ramsey.
Un insieme è indipendente se e solo se il suo complemento è una copertura dei vertici.[3] Perciò, la somma della dimensione del più grande insieme indipendente α(G), e della dimensione della minima coperrtura dei vertici β(G), è uguale al numero di vertici nel grafo.
La colorazione dei vertici di un grafo G corrisponde a una partizione dell'insieme dei suoi vertici in sottoinsiemi indipendenti. Quindi il numero minimale di colori richiesti in una colorazione dei vertici, il numero cromatico χ(G), è almeno il quoziente tra il numero di vertici in G e il numero indipendente α(G).
In un grafo bipartito senza vertici isolati, il numero di vertici in un insieme indipendente massimo uguaglia il numero di spigoli in una copertura degli spigoli minima; questo è il teorema di König.
Un insieme indipendente che non è il sottoinsieme di un altro insieme indipendente è chiamato massimale. Tali insiemi sono insiemi dominanti. Ogni grafo contiene al più 3n/3 insiemi indipendenti massimali,[4] ma molti grafi ne hanno di gran lunga di meno. Il numero di insiemi indipendenti massimali nei grafi ciclo con n vertici è dato dai numeri di Perrin, e il numero di insiemi indipendenti massimali nei grafi cammino con n vertici è dato dalla successione di Padovan.[5] Perciò, entrambi i numeri sono proporzionali alle potenze di 1,324718, il numero plastico.
In informatica, sono stati studiati parecchi problemi computazionali collegati agli insiemi indipendenti.
I primi tre di questi problemi sono tutti importanti in applicazioni pratiche; il problema di decisione dell'insieme indipendente non lo è, ma è necessario per applicare la teoria della NP-completezza ai problemi collegati agli insiemi indipendenti.
Il problema dell'insieme indipendente e il problema della cricca sono complementari: una cricca in G è un insieme indipendente nel grafo complemento di G e viceversa. Perciò, molti risultati computazionali possono essere applicati ugualmente bene a entrambi i problemi. Per esempio, i risultati legati al problema della cricca hanno i seguenti corollari:
Malgrado la stretta relazione tra le cricche massime e gli insiemi indipendenti massimi nei grafi arbitrari, I problemi dell'insieme indipendente e della cricca possono essere molto diversi quando sono ristretti a classi speciali di grafi. Ad esempio, per i grafi sparsi (grafi nei quali il numero degli spigoli è al massimo una costante per il numero dei vertici in qualsiasi sottografo), la cricca massima ha dimensione limitata e può essere trovata esattamente in tempo lineare;[6] tuttavia, per le stesse classi di grafi, o anche per la classe più ristretta dei grafi di grado limitato, trovare l'insieme indipendente massimo è MAXSNP-completo, implicando che, per qualche costante c (a seconda del grado), è NP-difficile trovare una soluzione approssimata che giunga entro un fattore di c dell'ottimo.[7]
Il problema del massimo insieme indipendente è NP-difficile. Tuttavia, esso può essere risolto in modo più efficiente che nel tempo O(n2 2n) che sarebbe dato da un algoritmo ingenuo forza bruta che esamina ogni sottoinsieme dei vertici e controlla se è un insieme indipendente.
Un algoritmo di Robson (1986) risolve il problema nel tempo O(1,2108n) usando lo spazio esponenziale. Quando si restringe allo spazio polinomiale, c'è un algoritmo nel tempo O(1,2127n).[8] che migliora rispetto a un più semplice algoritmo O(1,2209n).[9]
In alcune classi di grafi, compresi i grafi senza stella e i grafi perfetti, l'insieme indipendente massimo può essere trovato in tempo polinomiale.[10]
In un grafo bipartito, tutti i nodi che non sono nella copertura minima dei vertici possono essere inclusi nell'insieme indipendente massimo; vedi teorema di König. Perciò, le coperture minime dei vertici possono essere trovate usando un algoritmo di accoppiamento.
Il problema generale del massimo insieme indipendente non può essere approssimato a un fattore costante in tempo polinomiale (a meno che P=NP). Tuttavia, ci sono algoritmi di approssimazione efficienti per classi ristrette di grafi.
Nei grapi planari, il massimo insieme indipendente può essere approssimato entro un qualsiasi rapporto di approssimazione c < 1 in tempo polinomiale; simili schemi di approssimazione in tempo polinomiale esistono in qualsiasi famiglia di grafi chiusi mentre individuano minori.[11]
Nei grafi di grado limitato, si conoscono algoritmi di approssimazione efficaci con rapporti di approssimazione peggiori di quelli costanti; ad esempio, un algoritmo goloso (greedy) che forma un insieme indipendente massimale scegliendo, a ogni passo, il vertice di grado minimo nel grafo e rimuovendo i suoi vicini, consegue un rapporto di approssimazione di (Δ+2)/3 sui grafi con grado massimo Δ.[12]
Un grafo d'intervallo è un grafo in cui i nodi sono intervalli monodimensionali (ad es. intervalli temporali) e c'è uno spigolo tra due intervalli se e solo se essi si intersecano. Un insieme indipendente in un grafo d'intervallo è appunto un insieme di intervalli non sovrapposti. Il problema di trovare insiemi indipendenti massimi nei grafi d'intervallo è stato studiato, ad esempio, nel contesto della schedulazione di lavori: dato un insieme di lavori che deve essere eseguito su un computer, trovare un insieme massimo di lavori che possono essere eseguiti senza inferire l'uno con l'altro. Questo problema può essere risolto esattamente in tempo polinomiale usando la schedulazione "prima la scadenza più immediata" (earliest deadline first).
Un grafo d'intersezione geometrica è un grafo in cui i nodi sono forme geometriche e c'è uno spigolo tra due forme se e solo se esse si intersecano. Un insieme indipendente in un grafo d'intersezione geometrica è appunto un insieme di forme disgiunte (non sovrapposte). Il problema di trovare insiemi indipendenti massimi nei grafi d'intersezione geometrica è stato studiato, ad esempio, nel contesto del posizionamento automatico di etichette: dato un insieme di località su una mappa, trovare un insieme massimo di etichette rettangolari disgiunte vicino a queste località.
Trovare un insieme indipendente massimo nei grafi d'intersezione è ancora NP-completo, ma è più facile da approssimare del problema generale del massimo insieme indipendente. Una rassegna recente può essere trovata nell'introduzione di Chan & Har-Peled (2012).
Il problema di trovare un insieme indipendente massimale può essere risolto in tempo polinomiale da un banale algoritmo goloso.[13] Tutti gli insiemi indipendenti massimali possono essere trovati nel tempo O(3n/3) = O(1.4423n).
Nome | Licenza | Linguaggio API | Breve info |
---|---|---|---|
igraph Archiviato il 14 febbraio 2014 in Internet Archive. | GPL | C, Python, R, Ruby | soluzione esatta. "L'attuale implementazione fu convertita in igraph dalla Very Nauty Graph Library da Keith Briggs e usa l'algoritmo proveniente dal saggio S. Tsukiyama, M. Ide, H. Ariyoshi e I. Shirawaka, "A new algorithm for generating all the maximal independent sets", SIAM J Computing, 6, pp. 505–517, 1977. |
NetworkX | BSD | Python | soluzione approssimata, vedi la routine maximum_independent_set |
OpenOpt | BSD | Python | soluzione esatta e approssimata, possibilità di spedificare i nodi che devono essere inclusi / esclusi; vedi la classe STAB per maggiori dettagli ed esempi |