Проблем клике
У рачунској теорији комплексности, проблем клике је НП-комплетан проблем из теорије графова. Ово је био један од првобитних Карпових 21 НП-комплетних проблема, које је показао НП-комплетност 1972. у раду Сводљивост међу комбинаторним проблемима. Овај проблем је поменут и у Куковом раду који је увео теорију НП-комплетних проблема.
Клика у графу је скуп чворова, такав да су сви чворови из скупа узајамно суседни. Другим речима, клика је индуковани подграф, који је комплетан. У графу са десне стране, чворови 1, 2 и 5 чине клику, јер сваки има грану која води ка свим осталима.
Проблем клике је проблем одређивања да ли граф садржи клику не мању од дате величине k. Када пронађемо k или више чворова који чине клику, тривијално је проверити да ли они заиста граде клику, па је зато проблем клике у класи НП. Одговарајући оптимизациони проблем, проблем максималне клике, је проблем проналажења највеће клике у графу.
НП-комплетност проблема клике следи тривијално из НП-комплетности проблема независног скупа, јер постоји клика величине не мање од k ако и само ако постоји независан скуп величине не мање од k у комплементарном графу. Ово је лако видети, јер ако је подграф комплетан, његов комплементаран подграф нема ниједну грану.
Алгоритми[уреди | уреди извор]
Алгоритам грубе силе да се нађе клика у графу се састоји у испитивању сваког подграфа с најмање k чворова, да ли формира клику. Овај алгоритам је полиномијалан ако је k број чворова, или константа мања од овога, али није ако је k на пример половина броја чворова; број могућих клика величине k у графу величине V је једнак .
Хеуристика се састоји у томе да се почне тако што се сваки чвор посматра као клика величине један, и да се спајају клике у све веће клике све док се више не могу извршити спајања. Две клике, A и B се могу спојити, ако је сваки чвор из клике A суседан сваком чвору из клике B. Ово захтева само линеарно време (линеарно по броју чворова), али може се десити да не пронађе велике клике, јер су два или више делова велике клике већ повезана са чворовима који нису у тој клики. Међутим, овако се проналази бар једна максимална клика, што је клика која није део ниједне веће клике. Овај алгоритам је најефикасније имплементирати коришћењем алгоритма за налажење унија.
Неки посебни случајеви се могу решити у времену мањем од експоненцијалног. За k = 3, постоји O(n1,41) алгоритам, где је n број чворова.