Problema di copertura delle cricche
Nella teoria della complessità computazionale, trovare una copertura delle cricche minima è un problema NP-completo di teoria dei grafi. Il problema era uno dei 21 problemi originali di Richard Karp che erano stati dimostrati NP-completi nel suo saggio del 1972 Riducibilità tra problemi combinatori (Reducibility among Combinatorial Problems).
IL problema di copertura delle cricche (a volte chiamato anche partizione in cricche) è il problema di determinare se i vertici di un grafo possono essere ripartiti in k cricche. Data una partizione dei vertici in k insiemi, si può verificare in tempo polinomiale che ciascun insieme forma una cricca, per cui il problema è in NP. La NP-completezza della copertura delle cricche consegue mediante riduzione dalla k-colorabilità del grafo. Per vedere questo, si trasformi dapprima un'istanza G di k-colorabilità del grafo nel suo grafo complemento G'. Una partizione di G' in k cricche corrisponde allora a trovare una partizione dei vertici di G in k insiemi indipendenti; a ognuno di questi insiemi si può allora assegnare un colore per creare una k-colorazione.
Il problema correlato della copertura degli spigoli delle cricche considera gli insiemi delle cricche che comprendono tutti gli spigoli di un dato grafo. Anch'esso è NP-completo.
Bibliografia[modifica | modifica wikitesto]
- Richard Karp, Reducibility Among Combinatorial Problems (PDF), in R. E. Miller e J. W. Thatcher (a cura di), Proceedings of a Symposium on the Complexity of Computer Computations, Plenum Press, 1972, pp. 85–103. URL consultato il 29 agosto 2008 (archiviato dall'url originale il 4 marzo 2016).
- Michael R. Garey e David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, ISBN 0-7167-1045-5. A1.2: GT19, p. 194.
