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.

Proprietà

Relazione con altri parametri dei grafi

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.

Insieme indipendente massimale

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.

Trovare gli insiemi indipendenti

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.

Insiemi indipendenti massimi e cricche massime

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]

Trovare gli insiemi indipendenti massimi

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

Algoritmi esatti

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.

Algoritmi di approssimazione

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]

Insiemi indipendenti nei grafi d'intersezione di intervalli

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

Insiemi indipendenti nei grafi d'intersezione geometrica

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

Trovare insiemi indipendenti massimali

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

Programmi liberi per la ricerca del massimo insieme indipendente

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

Note

^ Korshunov (1974)
^ Godsil & Royle (2001), p. 3.
^ DIMOSTRAZIONE: Un insieme V di vertici è un insieme indipendente se e solo se ogni spigolo nel grafo è adiacente al più a un solo membro di V; se e solo se ogni spigolo nel grafo è adiacente almeno a un solo membro non in V; se e solo se il complemento di V è una copertura dei vertici.
^ Moon & Moser (1965).
^ Füredi (1987).
^ Nishizeki (1985).
^ Berman199, Berman e Fujito (1995).
^ Bourgeois, Escoffier, Paschos & van Rooij (2010)
^ Fomin, Grandoni & Kratsch (2009)
^ Per i grafi senza stella, vedi Sbihi (1980). Per i grafi perfetti, vedi Grötschel, Lovász & Schrijver (1988).
^ Baker (1994); Grohe (2003).
^ Halldórsson & Radhakrishnan (1997).
^ Luby (1986).

Bibliografia

Brenda S. Baker, Approximation algorithms for NP-complete problems on planar graphs, in Journal of the ACM, vol. 41, n. 1, 1994, 153–180, DOI:10.1145/174644.174650.
Piotr Berman e Toshihiro Fujito, On approximation properties of the Independent set problem for degree 3 graphs, in Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, vol. 955, Springer-Verlag, 1995, 449–460, DOI:10.1007/3-540-60220-8_84.
Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos e Johan M. M. van Rooij, A bottom-up method and fast algorithms for MAX INDEPENDENT SET, in Algorithm theory—SWAT 2010, Lecture Notes in Computer Science, vol. 6139, Berlino, Springer, 2010, 62–73, DOI:10.1007/978-3-642-13731-0_7, MR 2678485.
T. M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, in Journal of Algorithms, vol. 46, n. 2, 2003, 178–189, DOI:10.1016/s0196-6774(02)00294-8.
T. M. Chan e S. Har-Peled, Approximation algorithms for naximum independent set of pseudo-disks, in Discrete & Computational Geometry, vol. 48, n. 2, 2012, 373, DOI:10.1007/s00454-012-9417-5.
N. Chiba e T. Nishizeki, Arboricity and subgraph listing algorithms, in SIAM Journal on Computing, vol. 14, n. 1, 1985, 210–223, DOI:10.1137/0214017.
T. Erlebach, K. Jansen e E. Seidel, Polynomial-Time Approximation Schemes for Geometric Intersection Graphs, in SIAM Journal on Computing, vol. 34, n. 6, 2005, 1302, DOI:10.1137/s0097539702402676.
Fedor V. Fomin, Fabrizio Grandoni e Dieter Kratsch, A measure & conquer approach for the analysis of exact algorithms, in Journal of ACM, vol. 56, n. 5, 2009, 1–32, DOI:10.1145/1552285.1552286.
Z. Füredi, The number of maximal independent sets in connected graphs, in Journal of Graph Theory, vol. 11, n. 4, 1987, 463–470, DOI:10.1002/jgt.3190110403.
Chris Godsil e Gordon Royle, Algebraic Graph Theory, New York, Springer, 2001, ISBN 0-387-95220-9.
Martin Grohe, Local tree-width, excluded minors, and approximation algorithms, in Combinatorica, vol. 23, n. 4, 2003, 613–632, DOI:10.1007/s00493-003-0037-9.
M. Grötschel, L. Lovász e A. Schrijver, 9.4 Coloring Perfect Graphs, in Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2, Springer–Verlag, 1988, 296–298, ISBN 0-387-13624-X.
M. M. Halldórsson e J. Radhakrishnan, Greed is good: Approximating independent sets in sparse and bounded-degree graphs, in Algorithmica, vol. 18, n. 1, 1997, 145–163, DOI:10.1007/BF02523693.
Michael Luby, A simple parallel algorithm for the maximal independent set problem, in SIAM Journal on Computing, vol. 15, n. 4, 1986, 1036–1053, DOI:10.1137/0215074, MR 861369.
J. W. Moon e Leo Moser, On cliques in graphs, in Israel Journal of Mathematics, vol. 3, n. 1, 1965, 23–28, DOI:10.1007/BF02760024, MR 0182577.
J. M. Robson, Algorithms for maximum independent sets, in Journal of Algorithms, vol. 7, n. 3, 1986, 425–440, DOI:10.1016/0196-6774(86)90032-5.
(FR) Najiba Sbihi, Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile, in Discrete Mathematics, vol. 29, n. 1, 1980, 53–76, DOI:10.1016/0012-365X(90)90287-R, MR 553650.
(UK) A.D. Korshunov, Coefficient of Internal Stability, in Kibernetika, vol. 10, n. 1, 1974, 17–28, DOI:10.1007/BF01069014.

Voci correlate

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.

Altri progetti

Wikimedia Commons

Wikimedia Commons contiene immagini o altri file su insieme indipendente

Collegamenti esterni

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