Insieme indipendente (teoria dei grafi)

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.

Lo stesso argomento in dettaglio: Insieme indipendente massimale.

Un insieme indipendente che non è il sottoinsieme di un altro insieme indipendente è chiamato massimale. Tali insiemi sono insiemi dominanti. Ogni grafo contiene al più 3^n/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.

Lo stesso argomento in dettaglio: Problema della cricca.

In informatica, sono stati studiati parecchi problemi computazionali collegati agli insiemi indipendenti.

• Nel problema del massimo insieme indipendente, l'entrata è un grafo indiretto, e l'uscita è un insieme indipendente massimo del grafo. Se ci sono insiemi indipendenti massimi mutipli, solo uno deve essere l'uscita. Questo problema è indicato talvolta come "impacchettamento dei vertici".
• Nel problema dell'insieme indipendente con il massimo peso, l'entrata è un grafo indiretto con i pesi sui suoi vertici e l'uscita è un insieme indipendente con il massimo peso totale. Il problema del massimo insieme indipendente è il caso speciale in cui i pesi sono uno.
• Nel problema dell'elencazione degli insiemi indipendenti massimali, l'entrata è un grafo indiretto, e l'uscita è un elenco di tutti i suoi insiemi indipendenti massimali. Il problema del massimo insieme indipendente può essere risolto usando come subroutine un algoritmo per il problema dell'elencazione degli insiemi indipendenti massimali, perché il massimo insieme indipendente deve essere incluso fra tutti gli insiemi indipendenti massimali.
• Nel problema di decisione dell'insieme indipendente, l'entrata è un grafo indiretto e un numero k, e l'uscita è un valore booleano: vero se il grafo contiene un insieme indipendente di dimensione k, e falso altrimenti.

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:

• Il problema decisionale dell'insieme indipendente è NP-completo, e quindi non si crede che vi sia un algoritmo efficiente per risolverlo.
• Il problema del massimo insieme indipendente è NP-difficile ed è anche difficile da approssimare.

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]

Lo stesso argomento in dettaglio: Problema della cricca § Trovare le cricche massime in grafi arbitrari.

Il problema del massimo insieme indipendente è NP-difficile. Tuttavia, esso può essere risolto in modo più efficiente che nel tempo O(n² 2ⁿ) 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,2108ⁿ) usando lo spazio esponenziale. Quando si restringe allo spazio polinomiale, c'è un algoritmo nel tempo O(1,2127ⁿ).^[8] che migliora rispetto a un più semplice algoritmo O(1,2209ⁿ).^[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]

Lo stesso argomento in dettaglio: Schedulazione di intervalli.

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).

Lo stesso argomento in dettaglio: Insieme disgiunto massimo.

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).

Lo stesso argomento in dettaglio: Insieme indipendente massimale.

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(3^n/3) = O(1.4423ⁿ).

• Un insieme indipendente di spigoli è un insieme di spigoli nessuno dei quali ha un vertice in comune a due a due. È chiamato di solito accoppiamento.
• Una colorazione dei vertici è una partizione dell'insieme dei vertici in insiemi indipendenti.

• Wikimedia Commons contiene immagini o altri file su insieme indipendente

• (EN) Eric W. Weisstein, Insieme indipendente, su MathWorld, Wolfram Research.
• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring, su nlsde.buaa.edu.cn. URL consultato il 22 marzo 2014 (archiviato dall'url originale il 29 maggio 2013).
• Independent Set and Vertex Cover, Hanan Ayad.

Portale Informatica

Portale Matematica