Problem klike
U računskoj teoriji kompleksnosti, problem klike je NP-kompletan problem iz teorije grafova. Ovo je bio jedan od prvobitnih Karpovih 21 NP-kompletnih problema, koje je pokazao NP-kompletnost 1972. u radu Svodljivost među kombinatornim problemima. Ovaj problem je pomenut i u Kukovom radu koji je uveo teoriju NP-kompletnih problema.
Klika u grafu je skup čvorova, takav da su svi čvorovi iz skupa uzajamno susedni. Drugim rečima, klika je indukovani podgraf, koji je kompletan. U grafu sa desne strane, čvorovi 1, 2 i 5 čine kliku, jer svaki ima granu koja vodi ka svim ostalima.
Problem klike je problem određivanja da li graf sadrži kliku ne manju od date veličine k. Kada pronađemo k ili više čvorova koji čine kliku, trivijalno je proveriti da li oni zaista grade kliku, pa je zato problem klike u klasi NP. Odgovarajući optimizacioni problem, problem maksimalne klike, je problem pronalaženja najveće klike u grafu.
NP-kompletnost problema klike sledi trivijalno iz NP-kompletnosti problema nezavisnog skupa, jer postoji klika veličine ne manje od k ako i samo ako postoji nezavisan skup veličine ne manje od k u komplementarnom grafu. Ovo je lako videti, jer ako je podgraf kompletan, njegov komplementaran podgraf nema nijednu granu.
Algoritmi[uredi | uredi izvor]
Algoritam grube sile da se nađe klika u grafu se sastoji u ispitivanju svakog podgrafa s najmanje k čvorova, da li formira kliku. Ovaj algoritam je polinomijalan ako je k broj čvorova, ili konstanta manja od ovoga, ali nije ako je k na primer polovina broja čvorova; broj mogućih klika veličine k u grafu veličine V je jednak .
Heuristika se sastoji u tome da se počne tako što se svaki čvor posmatra kao klika veličine jedan, i da se spajaju klike u sve veće klike sve dok se više ne mogu izvršiti spajanja. Dve klike, A i B se mogu spojiti, ako je svaki čvor iz klike A susedan svakom čvoru iz klike B. Ovo zahteva samo linearno vreme (linearno po broju čvorova), ali može se desiti da ne pronađe velike klike, jer su dva ili više delova velike klike već povezana sa čvorovima koji nisu u toj kliki. Međutim, ovako se pronalazi bar jedna maksimalna klika, što je klika koja nije deo nijedne veće klike. Ovaj algoritam je najefikasnije implementirati korišćenjem algoritma za nalaženje unija.
Neki posebni slučajevi se mogu rešiti u vremenu manjem od eksponencijalnog. Za k = 3, postoji O(n1,41) algoritam, gde je n broj čvorova.