Problema di copertura delle cricche
# 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 probalma 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.

