Clique problém - Clique problem
v počítačová věda, klika problém je výpočetní problém hledání kliky (podmnožiny vrcholů, všechny přilehlý navzájem, také volal kompletní podgrafy ) v graf. Má několik různých formulací podle toho, které kliky a jaké informace o klikách by se měly najít. Mezi běžné formulace problému s klikou patří nalezení a maximální klika (klika s největším možným počtem vrcholů), nalezení kliky o maximální hmotnosti ve váženém grafu se seznamem všech maximální kliky (kliky, které nelze zvětšit) a řešení rozhodovací problém testování, zda graf obsahuje kliku větší než daná velikost.
Problém s klikami nastává v následujícím reálném prostředí. Zvažte a sociální síť, kde je graf vrcholy představují lidi a grafy hrany představují vzájemné seznámení. Potom klika představuje podmnožinu lidí, kteří se navzájem znají, a k vyhledání těchto skupin společných přátel lze použít algoritmy pro nalezení kliky. Spolu se svými aplikacemi v sociálních sítích má problém s klikami také mnoho aplikací v bioinformatika, a výpočetní chemie.
Většina verzí problému s klikami je těžká. Problém rozhodování o klikání je NP-kompletní (jeden z Karpových 21 NP-úplných problémů ). Problém nalezení maximální kliky je obojí pevný parametr nepoddajný a těžko aproximovat. Seznam všech maximálních kliků může vyžadovat exponenciální čas protože existují grafy s exponenciálně mnoha maximálními klikami. Proto se velká část teorie o problému klikání věnuje identifikaci speciálních typů grafů, které připouštějí efektivnější algoritmy, nebo stanovení výpočetní obtížnosti obecného problému v různých modelech výpočtu.
K nalezení maximální kliky lze systematicky kontrolovat všechny podmnožiny, ale tento druh vyhledávání hrubou silou je příliš časově náročné na to, aby to bylo praktické pro sítě zahrnující více než několik desítek vrcholů. Ačkoli ne polynomiální čas algoritmus je pro tento problém známý, efektivnější algoritmy než je známo vyhledávání hrubou silou. Například Bron – Kerboschův algoritmus lze použít k vypsání všech maximálních klik v nejhorším optimálním čase a je také možné je vypsat v polynomiálním čase na jednu klik.
Historie a aplikace
Studium úplných podgrafů v matematice předchází „klikatou“ terminologii. Například úplné podgrafy se brzy objevují v matematické literatuře v graficko-teoretické formulaci Ramseyova teorie podle Erdős & Szekeres (1935). Termín „klika“ a problém algoritmického vypisování kliek však pocházejí ze společenských věd, kde se k modelování používají úplné podgrafy sociální kliky, skupiny lidí, kteří se navzájem znají. Luce & Perry (1949) použil grafy k modelování sociálních sítí a přizpůsobil terminologii společenských věd teorii grafů. Jako první nazývali úplné podgrafy „klikami“. První algoritmus pro řešení problému s klikou je algoritmus Harary & Ross (1957),[1] kteří byli motivováni sociologickou aplikací. Vědci v oblasti sociální vědy také definovali různé další typy klik a maximálních klik v sociální síti, „soudržné podskupiny“ lidí nebo aktérů v síti, z nichž všichni sdílejí jeden z několika různých druhů vztahu konektivity. Mnoho z těchto zobecněných pojmů kliky lze najít také vytvořením neorientovaného grafu, jehož hrany představují související dvojice aktérů ze sociální sítě, a poté aplikováním algoritmu pro problém kliky na tento graf.[2]
Od práce Hararyho a Rosse mnozí další vymysleli algoritmy pro různé verze problému s klikami.[1] V sedmdesátých letech začali vědci studovat tyto algoritmy z hlediska nejhorší analýza. Viz například Tarjan & Trojanowski (1977), raná práce na nejhorším případě složitosti problému s maximální klikou. Také v 70. letech, počínaje prací Cook (1971) a Karp (1972), začali vědci používat teorii NP-úplnost a související výsledky neřešitelnosti, aby poskytly matematické vysvětlení vnímané obtížnosti problému kliky. V 90. letech 20. století začala průlomová řada příspěvků Feige a kol. (1991) a nahlášeno v The New York Times,[3] ukázal, že (za předpokladu P ≠ NP ) to ani není možné přibližný problém přesně a efektivně.
Algoritmy pro vyhledání kliky byly použity v chemie, abyste našli chemikálie, které odpovídají cílové struktuře[4] a modelovat molekulární dokování a vazebná místa chemických reakcí.[5] Mohou být také použity k nalezení podobných struktur v různých molekulách.[6]V těchto aplikacích jeden tvoří graf, ve kterém každý vrchol představuje párový atom, jeden z každé ze dvou molekul. Dva vrcholy jsou spojeny hranou, pokud jsou shody, které představují, vzájemně kompatibilní. Být kompatibilní může znamenat například to, že vzdálenosti mezi atomy uvnitř dvou molekul jsou přibližně stejné, v rámci určité dané tolerance. Klika v tomto grafu představuje sadu spárovaných párů atomů, ve kterých jsou všechny shody navzájem kompatibilní.[7] Zvláštním případem této metody je použití modulární součin grafů snížit problém hledání maximální společný indukovaný podgraf dvou grafů k problému nalezení maximální kliky v jejich produktu.[8]
v automatické generování testovacího vzoru, nalezení klik může pomoci omezit velikost testovací sady.[9] v bioinformatika, k odvození byly použity algoritmy pro vyhledání klik evoluční stromy,[10] předpovídat proteinové struktury,[11] a najít úzce interagující shluky proteinů.[12] Výpis kliků v a graf závislosti je důležitým krokem v analýze určitých náhodných procesů.[13] V matematice Kellerova domněnka na obklad tváří v tvář hyperkrychle byl vyvrácen uživatelem Lagarias & Shor (1992), který použil algoritmus pro vyhledání kliky na přidruženém grafu k nalezení protipříkladu.[14]
Definice
An neorientovaný graf je tvořen a konečná množina z vrcholy a sada neuspořádané páry vrcholů, které se nazývají hrany. Podle konvence je v analýze algoritmů počet vrcholů v grafu označen n a počet hran je označen m. A klika v grafu G je kompletní podgraf z G. To znamená, že se jedná o podmnožinu K. vrcholů tak, že každé dva vrcholy v K. jsou dva koncové body hrany v G. A maximální klika je klika, do které nelze přidat žádné další vrcholy. Pro každý vrchol proti která není součástí maximální kliky, musí existovat další vrchol w který je v klice a nesousedí s proti, prevence proti od přidání do kliky. A maximální klika je klika, která zahrnuje největší možný počet vrcholů. Číslo kliky ω(G) je počet vrcholů v maximální klikě G.[1]
Bylo studováno několik úzce souvisejících problémů s hledáním klik.[15]
- V problému maximální kliky je vstupem neorientovaný graf a výstupem je maximální klika v grafu. Pokud existuje více maximálních klik, může být jedna z nich zvolena libovolně.[15]
- V problému váženého maxima kliky je vstupem neorientovaný graf s váhami na jeho vrcholech (nebo méně často na okrajích) a výstupem je klika s maximální celkovou hmotností. Problémem maximální kliky je speciální případ, kdy jsou všechny váhy stejné.[16] Kromě problému optimalizace součtu vah byly studovány také další komplikovanější problémy s optimalizací dvoukritérií.[17]
- V problému se seznamem maximálních klik je vstupem neorientovaný graf a výstupem je seznam všech jeho maximálních klik. Problém maximální kliky lze vyřešit pomocí podprogramu algoritmu pro problém se seznamem maximálních kliky, protože maximální klika musí být zahrnuta mezi všechny maximální kliky.[18]
- V k-klikový problém, vstupem je neorientovaný graf a číslo k. Výstupem je klika s k vrcholy, pokud existují, nebo speciální hodnota označující, že neexistuje k-klika jinak. V některých variantách tohoto problému by měl výstup obsahovat seznam všech velikostí klik k.[19]
- V problému s rozhodnutím o klikání je vstupem neorientovaný graf a číslo ka výstup je a Booleovská hodnota: true, pokud graf obsahuje a k-klika a jinak false.[20]
První čtyři z těchto problémů jsou všechny důležité v praktických aplikacích. Problém rozhodování o klikách nemá praktický význam; je formulován tímto způsobem za účelem uplatnění teorie NP-úplnost k problémům s hledáním klik.[20]
Problém kliky a problém nezávislé množiny se doplňují: klika dovnitř G je nezávislá sada v doplňkový graf z G a naopak.[21] Proto lze mnoho výpočtových výsledků aplikovat stejně dobře na oba problémy a některé výzkumné práce tyto dva problémy jasně nerozlišují. Tyto dva problémy však mají odlišné vlastnosti při použití na omezené rodiny grafů. Například problém kliky lze vyřešit v polynomiálním čase pro rovinné grafy[22] zatímco problém nezávislých množin zůstává na rovinných grafech NP-tvrdý.[23]
Algoritmy
Nalezení jediné maximální kliky
A maximální klika, někdy nazývaná inkluze-maximální, je klika, která není zahrnuta do větší kliky. Proto je každá klika obsažena v maximální klice.[24]Maximální kliky mohou být velmi malé. Graf může obsahovat ne-maximální kliku s mnoha vrcholy a samostatnou kliku o velikosti 2, která je maximální. Zatímco maximální (tj. Největší) klika je nutně maximální, konverzace neplatí. Existují některé typy grafů, ve kterých je každá maximální klika maximální; tohle jsou doplňuje z dobře pokryté grafy, ve kterém je každá maximální nezávislá množina maximální.[25]Jiné grafy však mají maximální kliky, které nejsou maximální.
Jedinou maximální kliku najdete přímo chamtivý algoritmus. Počínaje libovolnou klikou (například libovolný jeden vrchol nebo dokonce prázdná množina) zvětšete aktuální kliku po jednom vrcholu procházením zbývajícími vrcholy grafu. Pro každý vrchol proti které tato smyčka zkoumá, přidejte proti do kliky, pokud sousedí s každým vrcholem, který je již v klice, a zahodit proti v opačném případě. Tento algoritmus běží lineární čas.[26] Kvůli snadnému nalezení maximálních klik a jejich potenciálně malé velikosti byla věnována větší pozornost mnohem těžšímu algoritmickému problému s hledáním maximální nebo jinak velké kliky, než tomu bylo věnováno problému s nalezením jediné maximální kliky. nějaký výzkum v paralelní algoritmy studoval problém nalezení maximální kliky. Zejména problém najít lexikograficky první Ukázalo se, že maximální klika (nalezená algoritmem výše) kompletní pro třída polynomiálně-časových funkcí. Tento výsledek naznačuje, že je nepravděpodobné, že by problém byl řešitelný v rámci paralelní třídy složitosti NC.[27]
Kliky pevné velikosti
Lze otestovat, zda graf G obsahuje a k-vertexová klika a pomocí a. najděte jakoukoli takovou kliku, kterou obsahuje algoritmus hrubé síly. Tento algoritmus zkoumá každý podgraf s k vrcholy a zkontroluje, zda tvoří kliku. Chce to čas Ó(nk k2), vyjádřeno pomocí velká O notace Je to proto, že existují Ó(nk) podgrafy ke kontrole, z nichž každý má Ó(k2) hrany, jejichž přítomnost v G je třeba zkontrolovat. Problém tedy lze vyřešit v polynomiální čas kdykoli k je pevná konstanta. Kdy však k nemá pevnou hodnotu, ale místo toho se může lišit jako součást vstupu do problému, čas je exponenciální.[28]
Nejjednodušším netriviálním případem problému s nalezením kliky je nalezení trojúhelníku v grafu nebo ekvivalentní určení, zda je graf bez trojúhelníků.V grafu G s m hran, může jich být maximálně Θ (m3/2) trojúhelníky (pomocí velká theta notace což naznačuje, že tato vazba je těsná). Nejhorší případ pro tento vzorec nastane, když G je sama klika. Algoritmy pro vypsání všech trojúhelníků proto musí trvat alespoň Ω (m3/2) čas v nejhorším případě (pomocí velká omega notace ) a jsou známy algoritmy, které odpovídají této časové vazbě.[29] Například, Chiba a Nishizeki (1985) popsat algoritmus, který třídí vrcholy v pořadí od nejvyššího stupně po nejnižší a poté iteruje každým vrcholem proti v seřazeném seznamu hledejte trojúhelníky, které obsahují proti a do seznamu nezahrnují žádný předchozí vrchol. K tomu algoritmus označí všechny sousedy proti, prohledá všechny hrany dopadající na souseda proti výstup trojúhelníku pro každou hranu, která má dva označené koncové body, a poté značky odstraní a odstraní proti z grafu. Jak ukazují autoři, čas pro tento algoritmus je úměrný času arboricita grafu (označeno A(G)) vynásobený počtem hran, což je Ó(m A(G)). Protože arboricita je nanejvýš Ó(m1/2), tento algoritmus běží v čase Ó(m3/2). Obecněji vše k-vertexové kliky lze vypsat podobným algoritmem, který zabere čas úměrný počtu hran vynásobený arboricitou k síle (k − 2). Pro grafy s konstantní arboricitou, jako jsou rovinné grafy (nebo obecně grafy z jiných než triviálních) malá uzavřená rodina grafů ), tento algoritmus trvá Ó(m) čas, který je optimální, protože je lineární ve velikosti vstupu.[19]
Pokud si přejete pouze jeden trojúhelník nebo ujištění, že graf neobsahuje trojúhelníky, jsou možné rychlejší algoritmy. Tak jako Itai & Rodeh (1978) pozorovat, graf obsahuje trojúhelník právě tehdy, je-li jeho matice sousedství a čtverec matice sousedství obsahuje nenulové položky ve stejné buňce. Proto techniky rychlého násobení matic, jako je Coppersmith – Winogradův algoritmus lze použít k nalezení trojúhelníků v čase Ó(n2.376). Alon, Yuster & Zwick (1994) použil rychlé násobení matic ke zlepšení Ó(m3/2) algoritmus pro hledání trojúhelníků do Ó(m1.41). Tyto algoritmy založené na rychlém násobení matic byly také rozšířeny na problémy hledání k-kliky pro větší hodnoty k.[30]
Seznam všech maximálních kliků
Výsledkem Moon & Moser (1965), každý n-vertexový graf má maximálně 3n/3 maximální kliky. Mohou být uvedeny podle Bron – Kerboschův algoritmus, rekurzivní ustoupit postup Bron & Kerbosch (1973). Hlavní rekurzivní podprogram tohoto postupu má tři argumenty: částečně vytvořenou (ne-maximální) kliku, sadu kandidátských vrcholů, které lze přidat do kliky, a další sadu vrcholů, které by neměly být přidány (protože by to vedlo do kliky, která již byla nalezena). Algoritmus se pokusí přidat kandidátní vrcholy jeden po druhém do částečné kliky, čímž provede rekurzivní volání pro každý z nich. Po vyzkoušení každého z těchto vrcholů ji přesune na sadu vrcholů, které by se neměly znovu přidávat. Je možné ukázat, že varianty tohoto algoritmu mají nejhorší dobu běhu Ó(3n/3), což odpovídá počtu kliků, které mohou být uvedeny.[31] Proto to poskytuje nejhorší případ optimálního řešení problému se seznamem všech maximálních klik. Dále se uvádí, že algoritmus Bron – Kerbosch je v praxi rychlejší než jeho alternativy.[32]
Pokud je však počet klik výrazně nižší než v nejhorším případě, mohou být vhodnější jiné algoritmy. Tak jako Tsukiyama a kol. (1977) ukázáno, je také možné vypsat všechny maximální kliky v grafu v čase, který je polynomický na vygenerovanou kliku. Algoritmus, jako je jejich, ve kterém doba běhu závisí na velikosti výstupu, je známý jako algoritmus citlivý na výstup. Jejich algoritmus je založen na následujících dvou pozorováních, týkajících se maximálních klik daného grafu G na maximální kliky grafu G \ proti vytvořený odstraněním libovolného vrcholu proti z G:
- Pro každou maximální kliku K. z G \ proti, buď K. pokračuje ve vytváření maximální kliky Gnebo K. ⋃ {proti} tvoří maximální klik G. Proto, G má alespoň tolik maximálních kliků jako G \ proti dělá.
- Každá maximální klika G který neobsahuje proti je maximální klika v G \ protia každá maximální klika dovnitř G který obsahuje proti lze vytvořit z maximální kliky K. v G \ proti přidáváním proti a odstranění nesousedů z proti z K..
Pomocí těchto pozorování mohou generovat všechny maximální kliky G rekurzivním algoritmem, který zvolí vrchol proti libovolně a poté pro každou maximální kliku K. v G \ proti, výstupy oba K. a klika vytvořená přidáním proti na K. a odstranění nesousedů z proti. Některé kliky z G lze generovat tímto způsobem z více než jedné nadřazené kliky G \ proti, takže eliminují duplikáty výstupem kliky dovnitř G pouze když je jeho rodič v G \ proti je lexikograficky maximum ze všech možných nadřazených klik. Na základě tohoto principu ukazují, že všechny maximální kliky jsou v G mohou být generovány včas Ó(mn) na kliku, kde m je počet hran v G a n je počet vrcholů. Chiba a Nishizeki (1985) vylepšit to Ó(ma) na kliku, kde A je arboricita daného grafu. Makino & Uno (2004) poskytují alternativní algoritmus citlivý na výstup založený na rychlém násobení matic. Johnson & Yannakakis (1988) ukázat, že je dokonce možné vypsat všechny maximální kliky lexikografický řád s polynomiální zpoždění na kliku. Pro efektivitu tohoto algoritmu je však důležitá volba pořadí: pro obrácení tohoto pořadí neexistuje žádný algoritmus polynomiálního zpoždění, pokud P = NP.
Na základě tohoto výsledku je možné vypsat všechny maximální kliky v polynomiálním čase pro rodiny grafů, ve kterých je počet kliček polynomiálně ohraničen. Mezi tyto rodiny patří chordální grafy, kompletní grafy, grafy bez trojúhelníků, intervalové grafy, grafy ohraničené boxicita, a rovinné grafy.[33] Zejména rovinné grafy mají Ó(n) kliky, maximálně konstantní velikosti, které mohou být uvedeny v lineárním čase. Totéž platí pro každou rodinu grafů, která je obojí řídký (s počtem hran maximálně konstantní násobkem počtu vrcholů) a Zavřeno v provozu pořizování podgrafů.[19][34]
Nalezení maxima klik v libovolných grafech
Je možné najít maximum kliky nebo číslo kliky libovolné n-vrcholový graf v čase Ó(3n/3) = Ó(1.4422n) pomocí jednoho z výše popsaných algoritmů k vypsání všech maximálních klik v grafu a vrácení největšího. U této varianty problému s klikou jsou však možné lepší nejhorší časové hranice. Algoritmus Tarjan & Trojanowski (1977) řeší tento problém včas Ó(2n/3) = Ó(1.2599n). Je to rekurzivní schéma zpětného sledování podobné schématu Bron – Kerboschův algoritmus, ale je schopen eliminovat některá rekurzivní volání, když lze prokázat, že kliky nalezené v rámci volání budou neoptimální. Jian (1986) zlepšil čas na Ó(20.304n) = Ó(1.2346n), a Robson (1986) vylepšil na Ó(20.276n) = Ó(1.2108n) času, na úkor většího využití prostoru. Robsonův algoritmus kombinuje podobné schéma zpětného sledování (s komplikovanější analýzou případů) a a dynamické programování technika, při které je předpočítáno optimální řešení pro všechny malé spojené podgrafy doplňkový graf. Tato částečná řešení se používají ke zkrácení zpětné rekurze. Nejrychlejším dnes známým algoritmem je vylepšená verze této metody od Robson (2001) který běží v čase Ó(20.249n) = Ó(1.1888n).[35]
Došlo také k rozsáhlému výzkumu heuristické algoritmy pro řešení maximálních klikových problémů bez nejhorších záruk za běhu na základě metod včetně větev a svázaný,[36] místní vyhledávání,[37] chamtivé algoritmy,[38] a programování omezení.[39] Mezi nestandardní výpočetní metodiky, které byly navrženy pro hledání klik, patří Výpočet DNA[40] a adiabatický kvantový výpočet.[41] Problém maximální kliky byl předmětem implementační výzvy sponzorované společností DIMACY v letech 1992–1993,[42] a sbírka grafů používaných jako měřítka pro výzvu, která je veřejně dostupná.[43]
Speciální třídy grafů
Rovinné grafy a další rodiny řídkých grafů byly diskutovány výše: mají lineárně mnoho maximálních klik, omezené velikosti, které lze vypsat v lineárním čase.[19] Zejména u rovinných grafů může mít každá klika maximálně čtyři vrcholy o Kuratowského věta.[22]
Perfektní grafy jsou definovány vlastnostmi, kterým se jejich počet klik rovná chromatické číslo, a že tato rovnost platí i v každém z nich indukované podgrafy. Pro dokonalé grafy je možné najít maximální kliku v polynomiálním čase pomocí algoritmu založeného na semidefinitní programování.[44]Tato metoda je však složitá a nekombinatorní a pro mnoho podtříd dokonalých grafů byly vyvinuty specializované algoritmy pro hledání klik.[45] V doplňkové grafy z bipartitní grafy, Kőnigova věta umožňuje vyřešit maximální problém s klikou pomocí technik pro vhodný. V další třídě dokonalých grafů je permutační grafy, maximální klika je a nejdelší klesající posloupnost permutace definující graf a lze ji najít pomocí známých algoritmů pro nejdelší problém s klesající subsekvencí. Naopak každou instanci problému s nejdelší klesající subsekvencí lze ekvivalentně popsat jako problém s nalezením maximální kliky v permutačním grafu.[46] Even, Pnueli & Lempel (1972) poskytnout alternativní algoritmus kvadratického času pro maximální kliky v srovnatelné grafy, širší třída dokonalých grafů, která obsahuje permutační grafy jako speciální případ.[47] v chordální grafy, maximální kliky lze najít uvedením vrcholů v eliminačním pořadí a kontrolou kliky sousedství každého vrcholu v tomto pořadí.[48]
V některých případech lze tyto algoritmy rozšířit i na jiné nedokonalé třídy grafů. Například v a kruhový graf, sousedství každého vrcholu je permutační graf, takže maximální klika v kruhovém grafu může být nalezena použitím algoritmu permutačního grafu na každé sousedství.[49] Podobně v a graf jednotkového disku (se známým geometrickým vyjádřením) existuje polynomiální časový algoritmus pro maximální kliky založený na aplikaci algoritmu pro doplňky bipartitních grafů na sdílená sousedství dvojic vrcholů.[50]
Algoritmický problém nalezení maximální kliky v a náhodný graf čerpáno z Erdős – Rényiho model (ve kterém se každá hrana objeví s pravděpodobností 1/2, nezávisle na ostatních okrajích) navrhl Karp (1976). Protože maximální klika v náhodném grafu má logaritmickou velikost s vysokou pravděpodobností, lze ji najít vyhledáváním hrubou silou v očekávaném čase 2Ó(log2n). Tohle je kvazi-polynomiální časová vazba.[51] Přestože počet takových grafů je obvykle velmi blízký 2 log2n, jednoduché chamtivé algoritmy stejně jako sofistikovanější techniky randomizované aproximace najdou pouze kliky s velikostí log2n, napůl tak velký. Počet maximálních klik v takových grafech je s vysokou pravděpodobností exponenciální log2n, což brání metodám, které vypisují všechny maximální kliky, v polynomiálním čase.[52] Kvůli obtížnosti tohoto problému několik autorů zkoumalo zasazená klika problém, problém s klikami na náhodných grafech, které byly rozšířeny přidáním velkých klik.[53] Zatímco spektrální metody[54] a semidefinitní programování[55] dokáže detekovat skryté kliky velikosti Ω (√n), v současné době nejsou známy žádné algoritmy polynomiálního času, které by detekovaly algoritmy velikosti Ó(√n) (vyjádřeno pomocí malý-o zápis ).[56]
Aproximační algoritmy
Zvažovalo to několik autorů aproximační algoritmy pokus o nalezení kliky nebo nezávislé množiny, která, i když není maximální, má velikost tak blízkou maximu, jaké lze najít v polynomiálním čase. Ačkoli se velká část této práce zaměřila na nezávislé množiny v řídkých grafech, případ, který nedělá smysl pro problém doplňkové kliky, také se pracovalo na aproximačních algoritmech, které takové předpoklady řídkosti nepoužívají.[57]
Feige (2004) popisuje polynomiální časový algoritmus, který najde velikostní kliku Ω ((logn/ log logn)2) v každém grafu, který má číslo kliky Ω (n/ logkn) pro jakoukoli konstantu k. Použitím tohoto algoritmu, když je číslo kliky daného vstupního grafu mezi n/ logn a n/ log3n, přepnutí na jiný algoritmus Boppana & Halldórsson (1992) pro grafy s vyšším počtem klik a výběr dvouvertexové kliky, pokud oba algoritmy nic nenajdou, Feige poskytuje aproximační algoritmus, který najde kliku s počtem vrcholů v rámci faktoru Ó(n(log logn)2/ log3n) maxima. Ačkoliv přibližný poměr tohoto algoritmu je slabý, je dosud nejznámější.[58] Výsledky na tvrdost aproximace popsané níže naznačují, že nemůže existovat žádný aproximační algoritmus s aproximačním poměrem výrazně menším než lineární.
Dolní hranice
NP-úplnost
Problém s klikovým rozhodnutím je NP-kompletní. Byl to jeden z Původních 21 problémů Richarda Karpa ukázal NP-complete ve svém článku z roku 1972 „Reducibility Among Combinatorial Problems“.[60] Tento problém byl také zmíněn v Stephen Cook příspěvek představující teorii NP-úplných problémů.[61] Kvůli tvrdosti rozhodovacího problému je problém s nalezením maximální kliky také NP-tvrdý. Pokud by to někdo dokázal vyřešit, mohl by také vyřešit problém s rozhodováním, a to porovnáním velikosti maximální kliky s parametrem size uvedeným jako vstup v problému s rozhodnutím.
Důkaz úplnosti NP společnosti Karp je a mnoho-jedna redukce z Booleovský problém uspokojivosti Popisuje, jak převést booleovské vzorce do jazyka konjunktivní normální forma (CNF) do ekvivalentních případů maximálního problému s klikou.[62]Splnitelnost se zase ukázala jako NP-úplná v EU Cook – Levinova věta. Z daného vzorce CNF vytvoří Karp graf, který má vrchol pro každou dvojici (proti,C), kde proti je proměnná nebo její negace a C je klauzule ve vzorci, který obsahuje proti. Dva z těchto vrcholů jsou spojeny hranou, pokud představují kompatibilní přiřazení proměnných pro různé klauze. To znamená, že existuje výhoda z (proti,C) na (u,d) kdykoli C ≠ d a u a proti nejsou vzájemnými negacemi. Li k označuje počet klauzulí ve vzorci CNF, poté k-vertexové kliky v tomto grafu představují konzistentní způsoby přiřazování pravdivostní hodnoty k některým jeho proměnným, aby splnil vzorec. Proto je vzorec uspokojivý právě tehdy, když a k-vertexová klika existuje.[60]
Některé NP-úplné problémy (například problém obchodního cestujícího v rovinné grafy ) lze vyřešit v čase, který je exponenciální ve sublearní funkci parametru vstupní velikosti n, výrazně rychlejší než vyhledávání hrubou silou.[63]Je však nepravděpodobné, že taková subexponenciální časová vazba je možná pro problém kliky v libovolných grafech, protože by to znamenalo podobně subexponenciální hranice pro mnoho dalších standardních NP-úplných problémů.[64]
Složitost obvodu
Výpočtová obtížnost problému s klikou vedla k jeho použití k prokázání několika dolních mezí složitost obvodu. Existence kliky dané velikosti je a vlastnost monotónního grafu, což znamená, že pokud v daném grafu existuje klika, bude existovat v kterémkoli supergraf. Protože tato vlastnost je monotónní, musí existovat monotónní obvod, který používá pouze a brány a nebo brány, vyřešit problém s rozhodnutím kliky pro danou pevnou velikost kliky. Velikost těchto obvodů však může být prokázána jako superpolynomiální funkce počtu vrcholů a velikosti kliky, exponenciální v kořenové krychli počtu vrcholů.[65] I když malý počet NE brány jsou povoleny, složitost zůstává superpolynomiální.[66] Navíc hloubka monotónního obvodu pro problém kliky pomocí bran ohraničeného fan-in musí být ve velikosti kliky alespoň polynom.[67]
Složitost rozhodovacího stromu
(Deterministický) složitost rozhodovacího stromu stanovení a vlastnost grafu je počet otázek ve formuláři „Existuje hrana mezi vrcholem u a vrchol proti? ", které musí být zodpovězeny v nejhorším případě, aby bylo možné určit, zda má graf určitou vlastnost. To znamená, že se jedná o minimální výšku logické hodnoty rozhodovací strom kvůli problému. Existují n(n − 1)/2 možné otázky. Proto lze libovolnou vlastnost grafu určit nanejvýš n(n − 1)/2 otázky. Je také možné definovat složitost vlastnosti náhodného a kvantového rozhodovacího stromu, očekávaný počet otázek (pro vstup v nejhorším případě), na které musí náhodný nebo kvantový algoritmus odpovědět, aby správně určil, zda daný graf má vlastnost .[68]
Protože vlastnost obsahující kliku je monotónní, je pokryta Aanderaa – Karp – Rosenbergova domněnka, který uvádí, že deterministická složitost rozhodovacího stromu při určování jakékoli netriviální vlastnosti monotónního grafu je přesná n(n − 1)/2. Pro vlastnosti libovolného monotónního grafu zůstává tato domněnka neprokázaná. Pro deterministické rozhodovací stromy a pro všechny k v dosahu 2 ≤ k ≤ n, vlastnost obsahující a k-klique bylo prokázáno, že má složitost rozhodovacího stromu přesně n(n − 1)/2 podle Bollobás (1976). Deterministické rozhodovací stromy také vyžadují exponenciální velikost pro detekci klik, nebo velkou velikost polynomu pro detekci klik s omezenou velikostí.[69]
Domněnka Aanderaa – Karp – Rosenberg také uvádí, že složitost randomizovaného rozhodovacího stromu netriviálních monotónních funkcí je Θ (n2). Domněnka opět zůstává neprokázaná, ale byla vyřešena pro vlastnost obsahující a k klika pro 2 ≤ k ≤ n. O této vlastnosti je známo, že má randomizovanou složitost rozhodovacího stromu Θ (n2).[70] U kvantových rozhodovacích stromů je nejznámější dolní mez Ω (n), ale není znám žádný algoritmus shody pro případ k ≥ 3.[71]
Nepostižitelnost s pevnými parametry
Parametrizovaná složitost je teoretická složitost studium problémů, které jsou přirozeně vybaveny malým celočíselným parametrem k a pro které se problém stává obtížnějším k zvyšuje, jako je hledání k-kliky v grafech. Říká se, že problém je vyřešitelný s pevnými parametry, pokud existuje algoritmus pro jeho řešení na vstupech velikosti na funkce F, takže algoritmus běží v čase F(k) nÓ(1). To znamená, že je fixovatelný s pevnými parametry, pokud jej lze vyřešit v polynomiálním čase pro jakoukoli pevnou hodnotu k a navíc, pokud exponent polynomu nezávisí na k.[72]
Pro nalezení k-vertexové kliky, algoritmus pro vyhledávání hrubou silou má dobu běhu Ó(nkk2). Protože exponent n záleží na k, tento algoritmus není fixovatelný s pevným parametrem. Ačkoli jej lze zlepšit rychlým násobením matice, doba běhu má stále exponent, který je lineární k I když je tedy doba běhu známých algoritmů pro problém s klikou polynomická pro všechny pevné k, tyto algoritmy nestačí pro fixovatelnost s pevnými parametry. Downey & Fellows (1995) definovali hierarchii parametrizovaných problémů, hierarchii W, o které se domnívali, neměli fixovatelné algoritmy s pevnými parametry. Dokázali, že nezávislý soubor (nebo ekvivalentně klika) je pro první úroveň této hierarchie obtížný, W [1]. Podle jejich domněnky tedy klika nemá žádný traktovatelný algoritmus s pevnými parametry. Tento výsledek navíc poskytuje základ pro důkazy tvrdosti W [1] mnoha dalších problémů, a slouží tak jako analogie Cook – Levinova věta pro parametrizovanou složitost.[73]
Chen a kol. (2006) ukázal toto zjištění k-vertexové kliky nelze provést včas nÓ(k) pokud exponenciální časová hypotéza selže. To opět poskytuje důkaz, že není možný žádný traktovatelný algoritmus s pevnými parametry.[74]
Ačkoli je nepravděpodobné, že by problémy se seznamem maximálních klik nebo hledáním maximálních klik byly odstranitelné s pevným parametrem k, mohou být fixovatelné s jinými parametry složitosti instance. Například je známo, že oba problémy jsou fixovatelné, pokud jsou parametrizovány parametrem zvrhlost vstupního grafu.[34]
Tvrdost aproximace
Slabé výsledky, které naznačují, že problém s klikami lze jen těžko odhadnout, jsou známy již dlouhou dobu. Garey & Johnson (1978) poznamenal, že vzhledem k tomu, že číslo kliky přebírá malé celočíselné hodnoty a je těžké jej vypočítat, nemůže mít schéma plně polynomiálního času. Pokud by byla k dispozici příliš přesná aproximace, zaokrouhlením její hodnoty na celé číslo by se získalo přesné číslo kliky. O něco více však bylo známo až do začátku 90. let, kdy několik autorů začalo vytvářet spojení mezi aproximací maximálních klik a pravděpodobnostně ověřitelné důkazy. Použili tato spojení k prokázání tvrdost aproximace výsledky pro maximální problém s klikou.[75]Po mnoha vylepšeních těchto výsledků je nyní známo, že pro každého reálné číslo ε > 0, nemůže existovat žádný algoritmus polynomiálního času, který aproximuje maximální kliku na faktor lepší než Ó(n1 − ε), pokud P = NP.[76]
Hrubou myšlenkou těchto výsledků nepřístupnosti je vytvoření grafu, který představuje pravděpodobnostně kontrolovatelný kontrolní systém pro NP-úplný problém, jako je například Booleovský problém uspokojivosti. V pravděpodobnostně ověřitelném systému kontroly je důkaz představován jako posloupnost bitů. Instance problému uspokojivosti by měla mít platný důkaz, pouze a jen v případě, že je uspokojivý. Důkaz je kontrolován algoritmem, který se po výpočtu polynomiálního času na vstupu do problému uspokojivosti rozhodne prozkoumat malý počet náhodně vybraných pozic řetězce důkazu. V závislosti na tom, jaké hodnoty jsou u daného vzorku bitů nalezeny, kontrola buď přijme, nebo odmítne důkaz, aniž by se podíval na zbývající bity. Falešné negativy nejsou povoleny: vždy musí být přijat platný důkaz. Někdy však může být omylem přijat neplatný důkaz. U každého neplatného důkazu musí být nízká pravděpodobnost, že jej dáma přijme.[77]
K transformaci pravděpodobnostně ověřitelného systému kontroly tohoto typu na problém klikání se vytvoří graf s vrcholem pro každý možný přijímací chod kontroly kontroly. To znamená, že vrchol je definován jednou z možných náhodných voleb sad pozic, které se mají zkoumat, a bitovými hodnotami pro ty pozice, které by způsobily, že kontrola přijme důkaz. Může to být reprezentováno a částečné slovo s 0 nebo 1 v každé zkoumané poloze a a zástupný znak na každé zbývající pozici. Two vertices are adjacent, in this graph, if the corresponding two accepting runs see the same bit values at every position they both examine. Each (valid or invalid) proof string corresponds to a clique, the set of accepting runs that see that proof string, and all maximal cliques arise in this way. One of these cliques is large if and only if it corresponds to a proof string that many proof checkers accept. If the original satisfiability instance is satisfiable, it will have a valid proof string, one that is accepted by all runs of the checker, and this string will correspond to a large clique in the graph. However, if the original instance is not satisfiable, then all proof strings are invalid, each proof string has only a small number of checker runs that mistakenly accept it, and all cliques are small. Therefore, if one could distinguish in polynomial time between graphs that have large cliques and graphs in which all cliques are small, or if one could accurately approximate the clique problem, then applying this approximation to the graphs generated from satisfiability instances would allow satisfiable instances to be distinguished from unsatisfiable instances. However, this is not possible unless P = NP.[77]
Poznámky
- ^ A b C Bomze a kol. (1999); Gutin (2004).
- ^ Wasserman & Faust (1994).
- ^ Kolata (1990).
- ^ Rhodes et al. (2003).
- ^ Kuhl, Crippen & Friesen (1983).
- ^ National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995). Viz zejména str. 35–36.
- ^ Muegge & Rarey (2001). Viz zejména s. 6–7.
- ^ Barrow & Burstall (1976).
- ^ Hamzaoglu & Patel (1998).
- ^ Day & Sankoff (1986).
- ^ Samudrala & Moult (1998).
- ^ Spirin & Mirny (2003).
- ^ Frank & Strauss (1986).
- ^ The Keller graph used by Lagarias & Shor (1992) has 1048576 vertices and clique size 1024. They described a synthetic construction for the clique, but also used clique-finding algorithms on smaller graphs to help guide their search. Mackey (2002) simplified the proof by finding a clique of size 256 in a 65536-vertex Keller graph.
- ^ A b Valiente (2002); Pelillo (2009).
- ^ Pelillo (2009).
- ^ Sethuraman & Butenko (2015).
- ^ Valiente (2002).
- ^ A b C d Chiba a Nishizeki (1985).
- ^ A b Cormen a kol. (2001).
- ^ Cormen a kol. (2001), Exercise 34-1, p. 1018.
- ^ A b Papadimitriou & Yannakakis (1981); Chiba a Nishizeki (1985).
- ^ Garey, Johnson & Stockmeyer (1976).
- ^ Viz např. Frank & Strauss (1986).
- ^ Plummer (1993).
- ^ Skiena (2009), str. 526.
- ^ Cook (1985).
- ^ Např. Viz Downey & Fellows (1995).
- ^ Itai & Rodeh (1978) provide an algorithm with Ó(m3/2) running time that finds a triangle if one exists but does not list all triangles; Chiba a Nishizeki (1985) list all triangles in time Ó(m3/2).
- ^ Eisenbrand & Grandoni (2004); Kloks, Kratsch & Müller (2000); Nešetřil & Poljak (1985); Vassilevska & Williams (2009); Yuster (2006).
- ^ Tomita, Tanaka & Takahashi (2006).
- ^ Cazals & Karande (2008); Eppstein, Löffler & Strash (2013).
- ^ Rosgen & Stewart (2007).
- ^ A b Eppstein, Löffler & Strash (2013).
- ^ Robson (2001).
- ^ Balas & Yu (1986); Carraghan & Pardalos (1990); Pardalos & Rogers (1992); Östergård (2002); Fahle (2002); Tomita & Seki (2003); Tomita & Kameda (2007); Konc & Janežič (2007).
- ^ Battiti & Protasi (2001); Katayama, Hamamoto & Narihisa (2005).
- ^ Abello, Pardalos & Resende (1999); Grosso, Locatelli & Della Croce (2004).
- ^ Régin (2003).
- ^ Ouyang et al. (1997). Although the title refers to maximal cliques, the problem this paper solves is actually the maximum clique problem.
- ^ Childs et al. (2002).
- ^ Johnson & Trick (1996).
- ^ DIMACS challenge graphs for the clique problem Archivováno 2018-03-30 na Wayback Machine, accessed 2009-12-17.
- ^ Grötschel, Lovász & Schrijver (1988).
- ^ Golumbic (1980).
- ^ Golumbic (1980), str. 159.
- ^ Even, Pnueli & Lempel (1972).
- ^ Blair & Peyton (1993), Lemma 4.5, p. 19.
- ^ Gavril (1973); Golumbic (1980), str. 247.
- ^ Clark, Colbourn & Johnson (1990).
- ^ Song (2015).
- ^ Jerrum (1992).
- ^ Arora & Barak (2009), Example 18.2, pp. 362–363.
- ^ Alon, Krivelevich & Sudakov (1998).
- ^ Feige & Krauthgamer (2000).
- ^ Meka, Potechin & Wigderson (2015).
- ^ Boppana & Halldórsson (1992); Feige (2004); Halldórsson (2000).
- ^ Liu a kol. (2015): "In terms of the number of vertices in graphs, Feige shows the currently known best approximation ratio". Liu a kol. are writing about the maximální nezávislá množina but for purposes of approximation there is no difference between the two problems.
- ^ Převzato z Sipser (1996)
- ^ A b Karp (1972).
- ^ Cook (1971).
- ^ Cook (1971) gives essentially the same reduction, from 3-SAT instead of Satisfiability, to show that podgraf izomorfismus je NP-kompletní.
- ^ Lipton & Tarjan (1980).
- ^ Impagliazzo, Paturi & Zane (2001).
- ^ Alon & Boppana (1987). For earlier and weaker bounds on monotone circuits for the clique problem, see Valiant (1983) a Razborov (1985).
- ^ Amano & Maruoka (2005).
- ^ Goldmann & Håstad (1992) použitý složitost komunikace to prove this result.
- ^ Vidět Arora & Barak (2009), Chapter 12, "Decision trees", pp. 259–269.
- ^ Wegener (1988).
- ^ For instance, this follows from Gröger (1992).
- ^ Childs & Eisenberg (2005); Magniez, Santha & Szegedy (2007).
- ^ Downey & Fellows (1999). Technically, there is usually an additional requirement that F být vypočítatelná funkce.
- ^ Downey & Fellows (1995).
- ^ Chen a kol. (2006).
- ^ Kolata (1990); Feige et al. (1991); Arora & Safra (1998); Arora et al. (1998).
- ^ Håstad (1999) showed inapproximability for this ratio using a stronger complexity theoretic assumption, the inequality of NP a ZPP. Khot (2001) described more precisely the inapproximability ratio, but with an even stronger assumption. Zuckerman (2006) derandomizováno the construction weakening its assumption to P ≠ NP.
- ^ A b This reduction is originally due to Feige et al. (1991) and used in all subsequent inapproximability proofs; the proofs differ in the strengths and details of the probabilistically checkable proof systems that they rely on.
Reference
Průzkumy a učebnice
- Arora, Sanjeev; Barak, Boaz (2009), Výpočetní složitost: moderní přístup, Cambridge University Press, ISBN 978-0-521-42426-4.
- Blair, Jean R. S.; Peyton, Barry (1993), "An introduction to chordal graphs and clique trees", Graph theory and sparse matrix computation, IMA sv. Matematika. Appl., 56, Springer, New York, pp. 1–29, doi:10.1007/978-1-4613-8369-7_1, PAN 1320296.
- Bomze, I.M .; Budinich, M .; Pardalos, P. M .; Pelillo, M. (1999), „Maximum clique problem“, Příručka kombinatorické optimalizace, 4, Kluwer Academic Publishers, s. 1–74, CiteSeerX 10.1.1.48.4074.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "34.5.1 The clique problem", Úvod do algoritmů (2nd ed.), MIT Press and McGraw-Hill, pp. 1003–1006, ISBN 0-262-03293-7.
- Downey, R. G.; Fellows, M. R. (1999), Parametrizovaná složitost, Springer-Verlag, ISBN 0-387-94883-X.
- Golumbic, M. C. (1980), Algorithmic Graph Theory and Perfect Graphs, Computer Science and Applied Mathematics, Akademický tisk, ISBN 0-444-51530-5.
- Grötschel, M.; Lovász, L.; Schrijver, A. (1988), "9.4 Coloring Perfect Graphs", Geometric Algorithms and Combinatorial OptimizationAlgoritmy a kombinatorika, 2, Springer-Verlag, pp. 296–298, ISBN 0-387-13624-X.
- Gutin, G. (2004), "5.3 Independent sets and cliques", in Gross, J. L.; Yellen, J. (eds.), Příručka teorie grafů, Discrete Mathematics & Its Applications, CRC Press, pp. 389–402, ISBN 978-1-58488-090-5.
- Muegge, Ingo; Rarey, Matthias (2001), "Small molecule docking and scoring", Recenze v oblasti výpočetní chemie, 17: 1–60, doi:10.1002/0471224413.ch1, ISBN 9780471398455.
- National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995), Mathematical Challenges from Theoretical/Computational Chemistry, Národní akademie Press, doi:10.17226/4886, ISBN 978-0-309-05097-5.
- Pelillo, Marcello (2009), "Heuristics for maximum clique and independent set", Encyklopedie optimalizace, Springer, pp. 1508–1520, doi:10.1007/978-0-387-74759-0_264.
- Plummer, Michael D. (1993), "Well-covered graphs: a survey", Quaestiones Mathematicae, 16 (3): 253–287, doi:10.1080/16073606.1993.9631737, PAN 1254158.
- Sipser, M. (1996), Úvod do teorie výpočtu, International Thompson Publishing, ISBN 0-534-94728-X.
- Skiena, Steven S. (2009), Příručka pro návrh algoritmu (2. vyd.), Springer, ISBN 978-1-84800-070-4.
- Valiente, Gabriel (2002), "Chapter 6: Clique, Independent Set, and Vertex Cover", Algorithms on Trees and Graphs, Springer, pp. 299–350, doi:10.1007/978-3-662-04921-1_6.
- Wasserman, Stanley; Faust, Katherine (1994), Analýza sociálních sítí: metody a aplikace, Structural Analysis in the Social Sciences, 8, Cambridge University Press, str. 276, ISBN 978-0-521-38707-1.
Popular press
- Kolata, Gina (June 26, 1990), "In a Frenzy, Math Enters Age of Electronic Mail", The New York Times.
Články výzkumu
- Abello, J.; Pardalos, P. M .; Resende, M. G. C. (1999), "On maximum clique problems in very large graphs" (PDF), in Abello, J.; Vitter, J. (eds.), External Memory AlgorithmsSérie DIMACS o diskrétní matematice a teoretické informatice, 50, Americká matematická společnost, pp. 119–130, ISBN 0-8218-1184-3.
- Alon, N.; Boppana, R. (1987), "The monotone circuit complexity of boolean functions", Combinatorica, 7 (1): 1–22, doi:10.1007/BF02579196, S2CID 17397273.
- Alon, N.; Krivelevich, M.; Sudakov, B. (1998), "Finding a large hidden clique in a random graph", Náhodné struktury a algoritmy, 13 (3–4): 457–466, doi:10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO;2-W.
- Alon, N.; Yuster, R.; Zwick, U. (1994), "Finding and counting given length cycles", Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands, str. 354–364.
- Amano, Kazuyuki; Maruoka, Akira (2005), "A superpolynomial lower bound for a circuit computing the clique function with at most (1/6)log log N negation gates", SIAM Journal on Computing, 35 (1): 201–216, doi:10.1137/S0097539701396959, PAN 2178806.
- Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), "Proof verification and the hardness of approximation problems", Deník ACM, 45 (3): 501–555, doi:10.1145/278298.278306, S2CID 8561542, ECCC TR98-008. Originally presented at the 1992 Symposium on Foundations of Computer Science, doi:10.1109/SFCS.1992.267823.
- Arora, S.; Safra, S. (1998), "Probabilistic checking of proofs: A new characterization of NP", Deník ACM, 45 (1): 70–122, doi:10.1145/273865.273901, S2CID 751563. Originally presented at the 1992 Symposium on Foundations of Computer Science, doi:10.1109/SFCS.1992.267824.
- Balas, E.; Yu, C. S. (1986), "Finding a maximum clique in an arbitrary graph", SIAM Journal on Computing, 15 (4): 1054–1068, doi:10.1137/0215075.
- Barrow, H.; Burstall, R. (1976), "Subgraph isomorphism, matching relational structures and maximal cliques", Dopisy o zpracování informací, 4 (4): 83–84, doi:10.1016/0020-0190(76)90049-1.
- Battiti, R.; Protasi, M. (2001), "Reactive local search for the maximum clique problem", Algorithmica, 29 (4): 610–637, doi:10.1007/s004530010074, S2CID 1800512.
- Bollobás, Béla (1976), "Complete subgraphs are elusive", Journal of Combinatorial Theory, Řada B, 21 (1): 1–7, doi:10.1016/0095-8956(76)90021-6, ISSN 0095-8956.
- Boppana, R.; Halldórsson, M. M. (1992), "Approximating maximum independent sets by excluding subgraphs", BIT Numerická matematika, 32 (2): 180–196, doi:10.1007/BF01994876, S2CID 123335474.
- Bron, C.; Kerbosch, J. (1973), "Algorithm 457: finding all cliques of an undirected graph", Komunikace ACM, 16 (9): 575–577, doi:10.1145/362342.362367, S2CID 13886709.
- Carraghan, R.; Pardalos, P. M. (1990), "An exact algorithm for the maximum clique problem", Dopisy o operačním výzkumu, 9 (6): 375–382, doi:10.1016/0167-6377(90)90057-C.
- Cazals, F.; Karande, C. (2008), "A note on the problem of reporting maximal cliques", Teoretická informatika, 407 (1): 564–568, doi:10.1016/j.tcs.2008.05.010.
- Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A .; Xia, Ge (2006), „Silné výpočetní dolní meze prostřednictvím parametrizované složitosti“, Journal of Computer and System Sciences, 72 (8): 1346–1367, doi:10.1016 / j.jcss.2006.04.007
- Chiba, N .; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017.
- Childs, A. M .; Farhi, E .; Goldstone, J.; Gutmann, S. (2002), "Finding cliques by quantum adiabatic evolution", Kvantové informace a výpočet, 2 (3): 181–191, arXiv:quant-ph/0012104, Bibcode:2000quant.ph.12104C, doi:10.26421/QIC2.3, S2CID 33643794.
- Childs, A. M .; Eisenberg, J. M. (2005), "Quantum algorithms for subset finding", Kvantové informace a výpočet, 5 (7): 593–604, arXiv:quant-ph/0311038, Bibcode:2003quant.ph.11038C, doi:10.26421/QIC5.7, S2CID 37556989.
- Clark, Brent N.; Colbourn, Charles J.; Johnson, David S. (1990), "Unit disk graphs", Diskrétní matematika, 86 (1–3): 165–177, doi:10.1016/0012-365X(90)90358-O
- Cook, S. A. (1971), "The complexity of theorem-proving procedures", Proc. 3rd ACM Symposium on Theory of Computing, pp. 151–158, doi:10.1145/800157.805047, S2CID 7573663.
- Cook, Stephen A. (1985), "A taxonomy of problems with fast parallel algorithms", Informace a kontrola, 64 (1–3): 2–22, doi:10.1016/S0019-9958(85)80041-3, PAN 0837088.
- Day, William H. E.; Sankoff, David (1986), "Computational complexity of inferring phylogenies by compatibility", Systematická zoologie, 35 (2): 224–229, doi:10.2307/2413432, JSTOR 2413432.
- Downey, R. G.; Fellows, M. R. (1995), "Trvanlivost a úplnost s pevnými parametry. II. O úplnosti pro W [1]", Teoretická informatika, 141 (1–2): 109–131, doi:10.1016/0304-3975(94)00097-3.
- Eisenbrand, F.; Grandoni, F. (2004), "On the complexity of fixed parameter clique and dominating set", Teoretická informatika, 326 (1–3): 57–67, doi:10.1016/j.tcs.2004.05.009.
- Eppstein, David; Löffler, Maarten; Strash, Darren (2013), "Listing all maximal cliques in large sparse real-world graphs in near-optimal time", Journal of Experimental Algorithmics, 18 (3): 3.1, arXiv:1103.0318, doi:10.1145/2543629, S2CID 47515491.
- Erdős, Paul; Szekeres, George (1935), „Kombinatorický problém v geometrii“ (PDF), Compositio Mathematica, 2: 463–470.
- Dokonce, S.; Pnueli, A.; Lempel, A. (1972), "Permutation graphs and transitive graphs", Deník ACM, 19 (3): 400–410, doi:10.1145/321707.321710, S2CID 9501737.
- Fahle, T. (2002), "Simple and fast: Improving a branch-and-bound algorithm for maximum clique", Proc. 10th European Symposium on Algorithms, Přednášky v informatice, 2461, Springer-Verlag, pp. 47–86, doi:10.1007/3-540-45749-6_44, ISBN 978-3-540-44180-9.
- Feige, U. (2004), "Approximating maximum clique by removing subgraphs", SIAM Journal on Discrete Mathematics, 18 (2): 219–225, doi:10.1137/S089548010240415X.
- Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S; Szegedy, M. (1991), „Přibližná klika je téměř NP úplná“, Proc. 32. IEEE Symp. o základech informatiky, s. 2–12, doi:10.1109 / SFCS.1991.185341, ISBN 0-8186-2445-0, S2CID 46605913.
- Feige, U.; Krauthgamer, R. (2000), "Finding and certifying a large hidden clique in a semirandom graph", Random Structures and Algorithms, 16 (2): 195–208, doi:10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A.
- Frank, Ove; Strauss, David (1986), "Markov graphs", Journal of the American Statistical Association, 81 (395): 832–842, doi:10.2307/2289017, JSTOR 2289017, PAN 0860518.
- Garey, M. R.; Johnson, D. S. (1978), ""Strong" NP-completeness results: motivation, examples and implications", Deník ACM, 25 (3): 499–508, doi:10.1145/322077.322090, S2CID 18371269.
- Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1976), "Some simplified NP-complete graph problems", Teoretická informatika, 1 (3): 237–267, doi:10.1016/0304-3975(76)90059-1, PAN 0411240.
- Gavril, F. (1973), "Algorithms for a maximum clique and a maximum independent set of a circle graph", Sítě, 3 (3): 261–273, doi:10.1002/net.3230030305.
- Goldmann, M.; Håstad, J. (1992), "A simple lower bound for monotone clique using a communication game" (PDF), Dopisy o zpracování informací, 41 (4): 221–226, CiteSeerX 10.1.1.185.3065, doi:10.1016/0020-0190(92)90184-W.
- Gröger, Hans Dietmar (1992), "On the randomized complexity of monotone graph properties" (PDF), Acta Cybernetica, 10 (3): 119–127, vyvoláno 2009-10-02
- Grosso, A .; Locatelli, M.; Della Croce, F. (2004), "Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem", Journal of Heuristics, 10 (2): 135–152, doi:10.1023/B:HEUR.0000026264.51747.7f, S2CID 40764225.
- Halldórsson, M. M. (2000), "Approximations of Weighted Independent Set and Hereditary Subset Problems", Journal of Graph Algorithms and Applications, 4 (1): 1–16, doi:10.7155/jgaa.00020.
- Hamzaoglu, I.; Patel, J. H. (1998), "Test set compaction algorithms for combinational circuits", Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design, pp. 283–289, doi:10.1145/288548.288615, S2CID 12258606.
- Harary, F.; Ross, I. C. (1957), "A procedure for clique detection using the group matrix", Sociometrie, Americká sociologická asociace, 20 (3): 205–215, doi:10.2307/2785673, JSTOR 2785673, PAN 0110590.
- Håstad, J. (1999), "Clique is hard to approximate within n1 − ε", Acta Mathematica, 182 (1): 105–142, doi:10.1007/BF02392825.
- Impagliazzo, R.; Paturi, R.; Zane, F. (2001), "Which problems have strongly exponential complexity?", Journal of Computer and System Sciences, 63 (4): 512–530, doi:10.1006/jcss.2001.1774.
- Itai, A .; Rodeh, M. (1978), "Finding a minimum circuit in a graph", SIAM Journal on Computing, 7 (4): 413–423, doi:10.1137/0207033.
- Jerrum, M. (1992), "Large cliques elude the Metropolis process", Random Structures and Algorithms, 3 (4): 347–359, doi:10.1002/rsa.3240030402.
- Jian, T (1986), "An Ó(20.304n) algorithm for solving maximum independent set problem", Transakce IEEE na počítačích, IEEE Computer Society, 35 (9): 847–851, doi:10.1109/TC.1986.1676847, ISSN 0018-9340.
- Johnson, D. S.; Trick, M. A., eds. (1996), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 26, Americká matematická společnost, ISBN 0-8218-6609-5.
- Johnson, D. S.; Yannakakis, M. (1988), "On generating all maximal independent sets", Dopisy o zpracování informací, 27 (3): 119–123, doi:10.1016/0020-0190(88)90065-8.
- Karp, Richard M. (1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thatcher, J. W. (eds.), Složitost počítačových výpočtů (PDF), New York: Plénum, pp. 85–103.
- Karp, Richard M. (1976), "Probabilistic analysis of some combinatorial search problems", in Traub, J. F. (ed.), Algorithms and Complexity: New Directions and Recent Results, New York: Akademický tisk, s. 1–19.
- Katayama, K.; Hamamoto, A.; Narihisa, H. (2005), "An effective local search for the maximum clique problem", Dopisy o zpracování informací, 95 (5): 503–511, doi:10.1016/j.ipl.2005.05.010.
- Khot, S. (2001), "Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring", Proc. 42nd IEEE Symp. Základy informatiky, pp. 600–609, doi:10.1109/SFCS.2001.959936, ISBN 0-7695-1116-3, S2CID 11987483.
- Kloks, T.; Kratsch, D.; Müller, H. (2000), "Finding and counting small induced subgraphs efficiently", Dopisy o zpracování informací, 74 (3–4): 115–121, doi:10.1016/S0020-0190(00)00047-8.
- Konc, J.; Janežič, D. (2007), "Vylepšený algoritmus větvení a vázání pro maximální problém s klikou" (PDF), ZÁPASNÉ komunikace v matematické a počítačové chemii, 58 (3): 569–590. Zdrojový kód
- Kuhl, F. S.; Crippen, G. M.; Friesen, D. K. (1983), "A combinatorial algorithm for calculating ligand binding", Journal of Computational Chemistry, 5 (1): 24–34, doi:10.1002/jcc.540050105.
- Lagarias, Jeffrey C.; Shor, Peter W. (1992), "Keller's cube-tiling conjecture is false in high dimensions", Bulletin of the American Mathematical Society Nová řada, 27 (2): 279–283, arXiv:math/9210222, doi:10.1090/S0273-0979-1992-00318-X, PAN 1155280, S2CID 6390600.
- Lipton, R. J.; Tarjan, R. E. (1980), "Applications of a planar separator theorem", SIAM Journal on Computing, 9 (3): 615–627, doi:10.1137/0209046, S2CID 12961628.
- Liu, Yu; Lu, Jiaheng; Yang, Hua; Xiao, Xiaokui; Wei, Zhewei (2015), "Towards maximum independent sets on massive graphs", Proceedings of the 41st International Conference on Very Large Data Bases (VLDB 2015), Proceedings of the VLDB Endowment, 8, pp. 2122–2133, doi:10.14778/2831360.2831366, hdl:10138/157292.
- Luce, R. Duncan; Perry, Albert D. (1949), "A method of matrix analysis of group structure", Psychometrika, 14 (2): 95–116, doi:10.1007/BF02289146, PMID 18152948, S2CID 16186758.
- Mackey, John (2002), "A cube tiling of dimension eight with no facesharing", Diskrétní a výpočetní geometrie, 28 (2): 275–279, doi:10.1007/s00454-002-2801-9, PAN 1920144.
- Magniez, Frédéric; Santha, Miklos; Szegedy, Mario (2007), "Quantum algorithms for the triangle problem", SIAM Journal on Computing, 37 (2): 413–424, arXiv:quant-ph / 0310134, doi:10.1137/050643684, S2CID 594494.
- Makino, K .; Uno, T. (2004), „Nové algoritmy pro výčet všech maximálních klik“, Algorithm Theory: SWAT 2004 (PDF), Přednášky v informatice, 3111, Springer-Verlag, pp. 260–272, CiteSeerX 10.1.1.138.705, doi:10.1007/978-3-540-27810-8_23.
- Meka, Raghu; Potechin, Aaron; Wigderson, Avi (2015), "Sum-of-squares lower bounds for planted clique", Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC '15), New York, NY, USA: ACM, pp. 87–96, arXiv:1503.06447, doi:10.1145/2746539.2746600, ISBN 978-1-4503-3536-2, S2CID 2754095.
- Moon, J. W .; Moser, L. (1965), „O klikách v grafech“, Israel Journal of Mathematics, 3: 23–28, doi:10.1007 / BF02760024, PAN 0182577, S2CID 9855414.
- Nešetřil, J.; Poljak, S. (1985), "On the complexity of the subgraph problem", Komentáře Mathematicae Universitatis Carolinae, 26 (2): 415–419.
- Östergård, P. R. J. (2002), "A fast algorithm for the maximum clique problem", Diskrétní aplikovaná matematika, 120 (1–3): 197–207, doi:10.1016/S0166-218X(01)00290-6.
- Ouyang, Q.; Kaplan, P. D.; Liu, S .; Libchaber, A. (1997), "DNA solution of the maximal clique problem", Věda, 278 (5337): 446–449, Bibcode:1997Sci...278..446O, doi:10.1126/science.278.5337.446, PMID 9334300.
- Papadimitriou, Christos H.; Yannakakis, Mihalis (1981), "The clique problem for planar graphs", Dopisy o zpracování informací, 13 (4–5): 131–133, doi:10.1016/0020-0190(81)90041-7, PAN 0651460.
- Pardalos, P. M .; Rogers, G. P. (1992), "A branch and bound algorithm for the maximum clique problem", Počítače a operační výzkum, 19 (5): 363–375, doi:10.1016/0305-0548(92)90067-F.
- Razborov, A. A. (1985), "Lower bounds for the monotone complexity of some Boolean functions", Proceedings of the USSR Academy of Sciences (v Rusku), 281: 798–801. Anglický překlad v Sov. Matematika. Dokl. 31 (1985): 354–357.
- Régin, J.-C. (2003), "Using constraint programming to solve the maximum clique problem", Proc. 9. Int. Konf. Principles and Practice of Constraint Programming – CP 2003, Přednášky v informatice, 2833, Springer-Verlag, pp. 634–648, doi:10.1007/978-3-540-45193-8_43.
- Rhodes, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), "CLIP: similarity searching of 3D databases using clique detection", Journal of Chemical Information and Computer Sciences, 43 (2): 443–448, doi:10.1021/ci025605o, PMID 12653507.
- Robson, J. M. (1986), "Algorithms for maximum independent sets", Journal of Algorithms, 7 (3): 425–440, doi:10.1016/0196-6774(86)90032-5.
- Robson, J. M. (2001), Finding a maximum independent set in time Ó(2n/4).
- Rosgen, B; Stewart, L (2007), "Complexity results on graphs with few cliques", Diskrétní matematika a teoretická informatika, 9 (1): 127–136.
- Samudrala, Ram; Moult, John (1998), "A graph-theoretic algorithm for comparative modeling of protein structure", Journal of Molecular Biology, 279 (1): 287–302, doi:10.1006/jmbi.1998.1689, PMID 9636717.
- Sethuraman, Samyukta; Butenko, Sergiy (2015), "The maximum ratio clique problem", Computational Management Science, 12 (1): 197–218, doi:10.1007/s10287-013-0197-z, PAN 3296231, S2CID 46153055.
- Song, Y. (2015), "On the independent set problem in random graphs", International Journal of Computer Mathematics, 92 (11): 2233–2242, doi:10.1080/00207160.2014.976210, S2CID 6713201.
- Spirin, Victor; Mirny, Leonid A. (2003), "Protein complexes and functional modules in molecular networks", Sborník Národní akademie věd, 100 (21): 12123–12128, Bibcode:2003PNAS..10012123S, doi:10.1073/pnas.2032324100, PMC 218723, PMID 14517352.
- Tarjan, R. E.; Trojanowski, A. E. (1977), "Finding a maximum independent set" (PDF), SIAM Journal on Computing, 6 (3): 537–546, doi:10.1137/0206038.
- Tomita, E .; Kameda, T. (2007), "An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments", Journal of Global Optimization, 37 (1): 95–111, doi:10.1007/s10898-006-9039-7, S2CID 21436014.
- Tomita, E .; Seki, T. (2003), "An efficient branch-and-bound algorithm for finding a maximum clique", Diskrétní matematika a teoretická informatika, Přednášky v informatice, 2731, Springer-Verlag, str.278–289, doi:10.1007/3-540-45066-1_22, ISBN 978-3-540-40505-4.
- Tomita, E .; Tanaka, A .; Takahashi, H. (2006), „Nejhorší časová složitost pro generování všech maximálních klik a výpočetních experimentů“, Teoretická informatika, 363 (1): 28–42, doi:10.1016 / j.tcs.2006.06.015.
- Tsukiyama, S .; Ide, M .; Ariyoshi, I.; Shirakawa, I. (1977), „Nový algoritmus pro generování všech maximálních nezávislých množin“, SIAM Journal on Computing, 6 (3): 505–517, doi:10.1137/0206036.
- Valiant, L. G. (1983), "Exponential lower bounds for restricted monotone circuits", Proc. 15th ACM Symposium on Theory of Computing, pp. 110–117, doi:10.1145/800061.808739, ISBN 0-89791-099-0, S2CID 6326587.
- Vassilevska, V.; Williams, R. (2009), "Finding, minimizing, and counting weighted subgraphs", Proc. 41st ACM Symposium on Theory of Computing, pp. 455–464, CiteSeerX 10.1.1.156.345, doi:10.1145/1536414.1536477, ISBN 978-1-60558-506-2, S2CID 224579.
- Wegener, I. (1988), "On the complexity of branching programs and decision trees for clique functions", Deník ACM, 35 (2): 461–472, doi:10.1145/42282.46161, S2CID 11967153.
- Yuster, R. (2006), "Finding and counting cliques and independent sets in r-uniform hypergraphs", Dopisy o zpracování informací, 99 (4): 130–134, doi:10.1016/j.ipl.2006.04.005.
- Zuckerman, D. (2006), "Linear degree extractors and the inapproximability of max clique and chromatic number", Proc. 38th ACM Symp. Teorie výpočtu, pp. 681–690, doi:10.1145/1132516.1132612, ISBN 1-59593-134-1, S2CID 5713815, ECCC TR05-100.