Insieme indipendente massimale

Il grafo del cubo ha sei diversi insiemi indipendenti massimali, mostrati come i vertici rossi.

Nella teoria dei grafi, un insieme indipendente massimale o insieme stabile massimale è un insieme indipendente che non è un sottoinsieme di nessun altro insieme indipendente. Cioè, è un insieme S tale che ogni spigolo del grafo ha almeno un estremo non in S e ogni vertice non in S ha almeno un vicino in S. Un insieme indipendente massimale è anche un insieme dominante nel grafo, e ogni insieme dominante che è indipendente deve essere indipendente massimale, così gli insiemi massimali indipendenti sono chiamati anche insiemi dominanti indipendenti. Un grafo può avere molti insiemi indipendenti massimali di dimensioni ampiamente variabili; un insieme indipendente massimale più grande è chiamato insieme indipendente massimo.

Per esempio, nel grafo P₃, un cammino con tre vertici a, b e c e due spigoli ab e bc, gli insiemi {b} e {a,c} sono entrambi massimamente indipendenti. L'insieme {a} è indipendente, ma non è massimamente indipendente, perché è un sottoinsieme dell'insieme indipendente più grande {a,c}. In questo stesso grafo, le cricche massimali sono gli insiemi {a,b} e {b,c}.

La locuzione "insieme indipendente massimale" si usa anche per descrivere sottoinsiemi massimali di elementi indipendenti in strutture matematiche diverse dai grafi, e in particolare negli spazi vettoriali e nei matroidi.

Insiemi di vertici correlati

Se S è un insieme indipendente massimale in qualche grafo, è una cricca massimale o un sottografo completo massimale nel grafo complementare. Una cricca massimale è un insieme di vertici che induce un sottografo completo, e che non è un sottoinsieme dei vertici di nessun sottografo completo più grande. Cioè, è un insieme S tale che ogni coppia di vertici in S è connessa da uno spigolo e ad ogni vertice non in S manca uno spigolo per almeno un vertice in S. Un grafo può avere molte cricche massimali, di dimensioni variabili; trovare la più grande di queste è il problema della cricca massima.

Alcuni autori includono la massimalità come parte della definizione di una cricca, e si riferiscono alle cricche massimali semplicemente come cricche.

Il complemento di un insieme indipendente massimale, cioè, l'insieme di vertici non appartenenti all'insieme indipendente, forma una copertura dei vertici minimale. Cioè, il complemento è una copertura dei vertici, un insieme di vertici che include almeno un estremo di ciascuno spigolo, ed è minimale nel senso che nessuno dei suoi vertici può essere rimosso mentre si preserva la proprietà che è una copertura. Le coperture di vertici minimali sono state studiate in meccanica statistica in connessione con il modello del gas di reticolo a sfere rigide, un'astrazione matematica delle transizioni di stato fluido-solido.

Ogni insieme indipendente massimale è un insieme dominante, un insieme di vertici tale che ogni vertice nel grafo o appartiene all'insieme o è adiacente all'insieme stesso. Un insieme di vertici è un insieme indipendente massimale se e solo se è un insieme dominante indipendente.

Caratterizzazioni delle famiglie di grafi

Certe famiglie di grafi sono state caratterizzate anche in termini delle loro cricche massimali e dei loro insiemi indipendenti massimali. Gli esempi includono i grafi irriducibili alle cricche massimali e i grafi ereditari irriducibili alle cricche massimali. Si dice che un grafo è irriducibile alle cricche massimali se ogni cricca massimale ha uno spigolo che non appartiene a nessun'altra cricca massimale, ed ereditario irriducibile alle cricche massimali se la stessa proprietà è vera per ogni sottografo indotto. I grafi ereditari irriducibili alle cricche massimali includono i grafi senza triangoli, i grafi bipartiti e i grafi d'intervallo.

I cografi possono essere caratterizzati come grafi nei quali ogni cricca massimale interseca ogni insieme indipendente massimale, e nei quali la stessa proprietà è vera in tutti i sottografi indotti.

Limitare i numeri degli insiemi

Moon & Moser (1965) mostrarono che qualsiasi grafo con n vertici ha al più 3^n/3 crocche massimali. Complementarmente, anche qualsiasi grafo con n vertici ha al più 3^n/3 insiemi indipendenti massimali. Un grafo con esattamente 3^n/3 insiemi indipendenti massimali è facile da costruire: si prende semplicemente l'unione disgiunta di n/3 grafi con triangoli. Qualsiasi insieme indipendente massimale in questo grafo è formato scegliendo un vertice da ciascun grafo. Il grafo complementare, con esattamente 3^n/3 cricche massimali, è un tipo speciale di grafo di Turán; a causa della loro connessione con il limite di Moon e Moser, questi grafi talvolta sono chiamati anche grafi di Moon-Moser. Limiti più rigidi sono possibili se si limita la dimensione degli insiemi indipendenti massimali: il numero di insiemi indipendenti massimali di dimensione k in qualsiasi grafo con n vertici è al più

$\lfloor n/k\rfloor ^{k-(n{\bmod {k}})}\lfloor n/k+1\rfloor ^{n{\bmod {k}}}.$

I grafi che raggiungono questo limite sono ancora grafi di Turán.

Certe famiglie di grafi possono, tuttavia, avere limiti molto più restrittivi sui numeri degli insiemi massimali indipendenti e delle cricche massimali. Se tutti i grafi con n vertici in una famiglia di grafi hanno O(n) spigoli, e se ogni sottografo di un grafo della famiglia appartiene anch'esso alla famiglia, allora ciascun grafo nella famiglia può avere al più O(n) cricche massimali, le quali hanno tutte dimensione O(1). Ad esempio, queste condizioni sono vere per i grafi planari: ogni grafo planare con n vertici ha al più 3n − 6 spigoli, e il sottografo di un grafo planare è sempre planare, dal cui segue che ciascun grafo planare ha O(n) cricche massimale (al massimo quattro). Anche i grafi d'intervallo e i grafi cordali hanno al massimo n cricche massimali, anche se non sempre sono grafi sparsi.

Il numero di insiemi indipendenti massimali nei grafi ciclo con n vertici è dato da numeri di Perrin, e il numero di insiemi indipendenti massimali nei grafi cammino è dato dalla successione di Padovan. Perciò, entrambi i numeri sono proporzionali alle potenze di 1,324718, il numero plastico.

Algoritmi per l'elencazione di insiemi

Un algoritmo per elencare tutti gli insiemi indipendenti massimali o tutte le cricche massimali in un grafo può essere usato come subroutine per risolvere molti problemi di grafi NP-completi. È assai ovvio che le soluzioni per il problema del massimo insieme indipendente, il problema della cricca massima e il problema del minimo dominante indipendente devono essere tutte insiemi indipendenti massimali o cricche massimali, e possono essere trovate da un algoritmo che elenca tutti gli insiemi indipendenti massimali o le cricche massimali e conserva quelli con la dimensione più grande o più piccola. Similmente, la copertura minima dei vertici può essere trovata come il complemento di uno degli insiemi indipendenti massimali. Lawler (1976) osservò che elencare gli insiemi indipendenti massimali può essere usato anche per trovare le 3-colorazioni dei grafi: un grafo può essere 3-colorato se e solo se il complemento di uno dei suoi insiemi indipendenti massimali è bipartito. Usò questo approccio non solo per la 3-colorazione ma come parte di un più generale algoritmo di colorazione dei grafi, e da allora approcci simili alla colorazione dei grafi sono stati perfezionati da altri autori. Anche altri problemi più complessi possono essere modellati per trovare una cricca o un insieme indipendente di tipo specifico. Questo giustifica il problema algoritmico di elencare tutti gli insiemi indipendenti massimali (o equivalentemente, tutte le cricche massimali) in modo efficiente.

È immediato trasformare una dimostrazione del limite 3^n/3 di Moon e Moser sul limite di insiemi indipendenti massimali in un algoritmo che elenca tutti gli insiemi di questo tipo nel tempo O(3^n/3). Per i grafi che hanno il massimo numero possibile di insiemi indipendenti massimali, questo algoritmo impiega un tempo costante per ogni insieme delle uscite. Tuttavia, un algoritmo con questo limite temporale può essere altamente inefficiente per i grafi con numeri più limitati di insiemi indipendenti. Per questa ragione, molti ricercatori hanno studiato algoritmi che elencano tutti gli insiemi indipendenti massimali in tempo polinomiale per ogni insieme delle uscite. Il tempo per ogni insieme indipendente massimale è proporzionale a quello per la moltiplicazione di matrici nei grafi densi, o più veloce in varie classi di grafi sparsi.

Bibliografia

• R. Bisdorff e J.-L. Marichal, Counting non-isomorphic maximal independent sets of the n-cycle graph, 2007, arXiv:math.CO/0701647.
• I. M. Bomze, M. Budinich, P. M. Pardalos e M. Pelillo, The maximum clique problem, in Handbook of Combinatorial Optimization, vol. 4, Kluwer Academic Publishers, 1999, 1–74, CiteSeerX: 10.1.1.48.4074.
• J. M. Byskov, Algorithms for k-colouring and finding maximal independent sets, in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003, 456–457.
• N. Chiba e T. Nishizeki, Arboricity and subgraph listing algorithms, in SIAM J. on Computing, vol. 14, n. 1, 1985, 210–223, DOI:10.1137/0214017.
• C. Croitoru, On stables in graphs, in Proc. Third Coll. Operations Research, Babeş-Bolyai University, Cluj-Napoca, Romania, 1979, 55–60.
• D. Eppstein, Small maximal independent sets and faster exact graph coloring (PDF), in Journal of Graph Algorithms and Applications, vol. 7, n. 2, 2003, 131–140, arXiv:cs.DS/0011009.
• D. Eppstein, All maximal independent sets and dynamic dominance for sparse graphs, in Proc. Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, 451–459, arXiv:cs.DS/0407036.
• P. Erdős, On cliques in graphs, in Israel J. Math., vol. 4, n. 4, 1966, 233–234, DOI:10.1007/BF02771637, MR 0205874.
• R. Euler, The Fibonacci number of a grid graph and a new class of integer sequences, in Journal of Integer Sequences, vol. 8, n. 2, 2005, 05.2.6.
• 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.
• E. Jennings e L. Motycková, A distributed algorithm for finding all maximal cliques in a network graph, in Proc. First Latin American Symposium on Theoretical Informatics, Lecture Notes in Computer Science, vol. 583, Springer-Verlag, 1992, 281–293.
• D. S. Johnson, M. Yannakakis e C. H. Papadimitriou, On generating all maximal independent sets, in Information Processing Letters, vol. 27, n. 3, 1988, 119–123, DOI:10.1016/0020-0190(88)90065-8.
• E. L. Lawler, A note on the complexity of the chromatic number problem, in Information Processing Letters, vol. 5, n. 3, 1976, 66–67, DOI:10.1016/0020-0190(76)90065-X.
• E. L. Lawler, J. K. Lenstra e A. H. G. Rinnooy Kan, Generating all maximal independent sets: NP-hardness and polynomial time algorithms, in SIAM Journal on Computing, vol. 9, n. 3, 1980, 558–565, DOI:10.1137/0209042.
• J. Y.-T. Leung, Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs, in Journal of Algorithms, vol. 5, 1984, 22–35, DOI:10.1016/0196-6774(84)90037-3.
• Y. D. Liang, S. K. Dhall e S. Lakshmivarahan, On the problem of finding all maximum weight independent sets in interval and circular arc graphs, Proc. Symp. Applied Computing, 1991, 465–470.
• K. Makino e T. Uno, New algorithms for enumerating all maximal cliques, Proc. Ninth Scandinavian Workshop on Algorithm Theory, Lecture Notes in Compute Science, vol. 3111, Springer-Verlag, 2004, 260–272.
• N. Mishra e L. Pitt, Generating all maximal independent sets of bounded-degree hypergraphs, in Proc. Tenth Conf. Computational Learning Theory, 1997, 211–217, DOI:10.1145/267460.267500, ISBN 0-89791-891-6.
• J. W. Moon e L. Moser, On cliques in graphs, in Israel Journal of Mathematics, vol. 3, 1965, 23–28, DOI:10.1007/BF02760024, MR 0182577.
• V. Stix, Finding all maximal cliques in dynamic graphs, in Computational Optimization Appl., vol. 27, n. 2, 2004, pp. 173–186, DOI:10.1023/B:COAP.0000008651.28952.b6.
• E. Tomita, A. Tanaka e H. Takahashi, The worst-case time complexity for generating all maximal cliques and computational experiments, in Theoretical Computer Science, vol. 363, n. 1, 2006, 28–42, DOI:10.1016/j.tcs.2006.06.015.
• S. Tsukiyama, M. Ide, H. Ariyoshi e I. Shirakawa, A new algorithm for generating all the maximal independent sets, in SIAM J. on Computing, vol. 6, n. 3, 1977, 505–517, DOI:10.1137/0206036.
• Martin Weigt e Alexander K. Hartmann, Minimal vertex covers on finite-connectivity random graphs: A hard-sphere lattice-gas picture, in Phys. Rev. E, vol. 63, n. 5, 2001, 056127, DOI:10.1103/PhysRevE.63.056127, arXiv:cond-mat/0011446.
• C.-W. Yu e G.-H. Chen, Generate all maximal independent sets in permutation graphs, in Internat. J. Comput. Math., vol. 47, 1993, 1–8, DOI:10.1080/00207169308804157.