Klickproblem

Brute force-algoritmen hittar en 4-klicka i denna 7-vertex-graf (komplementet till 7-vertex- banan ) genom att systematiskt kontrollera alla C (7,4) = 35 4-vertex-subgrafer för fullständighet.

Inom datavetenskap är klickproblemet det beräkningsmässiga problemet att hitta klicker (delmängder av hörn, alla intill varandra , även kallade kompletta subgrafer ) i en graf . Den har flera olika formuleringar beroende på vilka klick, och vilken information om klicken, som ska finnas. Vanliga formuleringar av klickproblemet inkluderar att hitta en maximal klick (en klick med största möjliga antal hörn), hitta en maximal vikt klick i en viktad graf, lista alla maximala klick (klick som inte kan förstoras) och lösa beslutsproblemet att testa om en graf innehåller en klick som är större än en given storlek.

Klickproblemet uppstår i följande verkliga miljö. Tänk på ett socialt nätverk , där grafens hörn representerar människor och grafens kanter representerar ömsesidig bekantskap. Då representerar en klick en undergrupp av människor som alla känner varandra, och algoritmer för att hitta klicker kan användas för att upptäcka dessa grupper av gemensamma vänner. Tillsammans med sina tillämpningar i sociala nätverk har klickproblemet också många tillämpningar inom bioinformatik och beräkningskemi .

De flesta versioner av klickproblemet är svåra. Klickbeslutsproblemet är NP-komplett (ett av Karps 21 NP-kompletta problem) . Problemet med att hitta den maximala klicken är både svårlöst med fasta parametrar och svårt att uppskatta . Och att lista alla maximala klick kan kräva exponentiell tid eftersom det finns grafer med exponentiellt många maximala klick. Därför ägnas mycket av teorin om klickproblemet åt att identifiera speciella typer av grafer som tillåter mer effektiva algoritmer, eller att fastställa beräkningssvårigheten för det allmänna problemet i olika beräkningsmodeller.

För att hitta en maximal klick kan man systematiskt inspektera alla delmängder, men denna typ av brute-force-sökning är för tidskrävande för att vara praktiskt för nätverk som omfattar mer än ett par dussin hörn. Även om ingen polynomisk tidsalgoritm är känd för detta problem, är mer effektiva algoritmer än brute-force-sökningen kända. Till exempel Bron–Kerbosch-algoritmen användas för att lista alla maximala klick i värsta tänkbara optimal tid, och det är också möjligt att lista dem i polynomtid per klick.

Historik och applikationer

Studiet av kompletta subgrafer i matematik föregår "klick"-terminologin. Till exempel gör kompletta subgrafer ett tidigt framträdande i den matematiska litteraturen i den grafteoretiska omformuleringen av Ramsey-teorin av Erdős & Szekeres (1935) . Men termen "klick" och problemet med att algoritmiskt lista klick kommer båda från samhällsvetenskapen, där kompletta subgrafer används för att modellera sociala klicker , grupper av människor som alla känner varandra. Luce & Perry (1949) använde grafer för att modellera sociala nätverk och anpassade den samhällsvetenskapliga terminologin till grafteorin. De var de första som kallade kompletta subgrafer för "klick". Den första algoritmen för att lösa klickproblemet är den från Harary & Ross (1957), som motiverades av den sociologiska tillämpningen. Samhällsvetenskapliga forskare har också definierat olika andra typer av klicker och maximala klicker i sociala nätverk, "sammanhängande undergrupper" av människor eller aktörer i nätverket som alla delar en av flera olika typer av anslutningsrelationer. Många av dessa generaliserade föreställningar om klick kan också hittas genom att konstruera en oriktad graf vars kanter representerar relaterade par av aktörer från det sociala nätverket, och sedan tillämpa en algoritm för klickproblemet på denna graf.

Sedan Harary och Ross arbetat har många andra tagit fram algoritmer för olika versioner av klickproblemet. På 1970-talet började forskare studera dessa algoritmer utifrån värsta tänkbara analyser . Se till exempel Tarjan & Trojanowski (1977), ett tidigt arbete om det värsta tänkbara komplexiteten hos problemet med maximal klick. Också på 1970-talet, med början med Cooks (1971) och Karps (1972) arbete, började forskare använda teorin om NP-fullständighet och relaterade resultat av svårhanterlighet för att ge en matematisk förklaring till den upplevda svårigheten med klickproblemet. På 1990-talet, en genombrottsserie av artiklar som började med Feige et al. (1991) och rapporterad i The New York Times , visade att (förutsatt att P ≠ NP ) är det inte ens möjligt att approximera problemet exakt och effektivt.

Algoritmer för att hitta klick har använts inom kemi , för att hitta kemikalier som matchar en målstruktur och för att modellera molekylär dockning och bindningsställena för kemiska reaktioner. De kan också användas för att hitta liknande strukturer inom olika molekyler. I dessa applikationer bildar man en graf där varje vertex representerar ett matchat par av atomer, en från var och en av två molekyler. Två hörn är förbundna med en kant om matcherna som de representerar är kompatibla med varandra. Att vara kompatibel kan till exempel betyda att avstånden mellan atomerna inom de två molekylerna är ungefär lika, med en viss tolerans. En klick i denna graf representerar en uppsättning matchade par av atomer där alla matchningar är kompatibla med varandra. Ett specialfall av denna metod är användningen av den modulära produkten av grafer för att reducera problemet med att hitta den maximala gemensamma inducerade subgrafen av två grafer till problemet med att hitta en maximal klick i deras produkt.

I automatisk generering av testmönster kan det att hitta klick hjälpa till att begränsa storleken på en testuppsättning. Inom bioinformatik har algoritmer för att hitta klick använts för att sluta sig till evolutionära träd , förutsäga proteinstrukturer och hitta nära interagerande kluster av proteiner. Att lista klicken i en beroendegraf är ett viktigt steg i analysen av vissa slumpmässiga processer. Inom matematiken motbevisades Kellers gissning om sida-mot-öga sida vid sida av hyperkuber av Lagarias & Shor (1992), som använde en klickhittande algoritm på en tillhörande graf för att hitta ett motexempel.

Definitioner

Huvudartikel: Clique (grafteori)

Grafen som visas har en maximal klick, triangeln {1,2,5} och ytterligare fyra maximala klick, paren {2,3}, {3,4}, {4,5} och {4,6} .

En oriktad graf bildas av en ändlig uppsättning av hörn och en uppsättning oordnade par av hörn, som kallas kanter . Enligt konventionen, i algoritmanalys, betecknas antalet hörn i grafen med n och antalet kanter betecknas med m . En klick i en graf G är en komplett subgraf av G . Det vill säga, det är en delmängd K av hörnen så att varannan hörn i K är de två ändpunkterna för en kant i G . En maximal klick är en klick till vilken inga fler hörn kan läggas till. För varje vertex v som inte är en del av en maximal klick måste det finnas en annan vertex w som är i klicken och inte gränsar till v , vilket förhindrar att v läggs till i klicken. En maximal klick är en klick som inkluderar största möjliga antal hörn. Klicktalet ω ( G ) är antalet hörn i en maximal klick av G.

Flera närbesläktade problem att hitta klick har studerats.

• I problemet med maximal klick är ingången en oriktad graf, och utmatningen är en maximal klick i grafen. Om det finns flera maximala klick, kan en av dem väljas godtyckligt.
• I det viktade maximala klickproblemet är inmatningen en oriktad graf med vikter på dess hörn (eller, mindre ofta, kanter) och utmatningen är en klick med maximal totalvikt. Det maximala klickproblemet är specialfallet där alla vikter är lika. Förutom problemet med att optimera summan av vikter har andra mer komplicerade bikriteriumoptimeringsproblem också studerats.
• I det maximala klicklistningsproblemet är inmatningen en oriktad graf, och utgången är en lista över alla dess maximala klick. Det maximala klickproblemet kan lösas genom att använda som en subrutin en algoritm för det maximala klicklistningsproblemet, eftersom den maximala klicken måste inkluderas bland alla maximala klick.
• I k -klickproblemet är ingången en oriktad graf och ett tal k . Utdata är en klick med k hörn, om en sådan finns, eller ett speciellt värde som indikerar att det inte finns någon k -klick annars. I vissa varianter av detta problem bör utdata lista alla klicker av storlek k .
• I klickbeslutsproblemet är inmatningen en oriktad graf och ett tal k , och utgången är ett booleskt värde : sant om grafen innehåller en k -klick, och annars falskt.

De första fyra av dessa problem är alla viktiga i praktiska tillämpningar. Problemet med klickbeslut är inte av praktisk betydelse; den är formulerad på detta sätt för att tillämpa teorin om NP-fullständighet på klickhittande problem.

Klickproblemet och det oberoende mängdproblemet är komplementära: en klick i G är en oberoende mängd i komplementgrafen för G och vice versa. Därför kan många beräkningsresultat tillämpas lika bra på båda problemen, och vissa forskningsartiklar skiljer inte tydligt mellan de två problemen. De två problemen har dock olika egenskaper när de tillämpas på begränsade graffamiljer. Till exempel kan klickproblemet lösas i polynomtid för plana grafer medan det oberoende uppsättningsproblemet förblir NP-hårt på plana grafer.

Algoritmer

Att hitta en enda maximal klick

En maximal klick, ibland kallad inklusion-maximal, är en klick som inte ingår i en större klick. Därför ingår varje klick i en maximal klick. Maximala klick kan vara mycket små. En graf kan innehålla en icke-maximal klick med många hörn och en separat klick av storlek 2 som är maximal. Medan en maximal (dvs största) klick nödvändigtvis är maximal, gäller det omvända inte. Det finns några typer av grafer där varje maximal klick är maximal; dessa är komplementen till de väl täckta graferna , där varje maximal oberoende uppsättning är maximal. Andra grafer har dock maximala klick som inte är maximala.

En enda maximal klick kan hittas av en okomplicerad girig algoritm . Börja med en godtycklig klick (till exempel valfri enskild vertex eller till och med den tomma uppsättningen), odla den aktuella klicken en vertex i taget genom att loopa genom grafens återstående hörn. För varje hörn v som den här slingan undersöker, lägg till v till klicken om den ligger intill varje hörn som redan finns i klicken, och kassera v annars. Denna algoritm körs i linjär tid . På grund av hur lätt det är att hitta maximala klick, och deras potentiella lilla storlek, har mer uppmärksamhet ägnats åt det mycket svårare algoritmiska problemet att hitta en maximal eller på annat sätt stor klick. Men viss forskning i parallella algoritmer har studerat problemet med att hitta en maximal klick. I synnerhet har problemet med att hitta den lexikografiskt första maximala klicken (den som hittas av algoritmen ovan) visat sig vara komplett för klassen av polynom-tidsfunktioner . Detta resultat antyder att problemet sannolikt inte kommer att kunna lösas inom den parallella komplexitetsklassen NC .

Klick av fast storlek

Man kan testa om en graf G innehåller en k -vertex klick, och hitta någon sådan klick som den innehåller, med hjälp av en brute force algoritm . Denna algoritm undersöker varje subgraf med k hörn och kontrollerar om den bildar en klick. Det tar tid   O ( n ^k k ² ) , uttryckt med big O - notation . Detta beror på att det finns O ( n ^k ) subgrafer att kontrollera, som var och en har O ( k ² ) kanter vars närvaro i G måste kontrolleras. Således kan problemet lösas i polynomtid närhelst k är en fast konstant. Men när k inte har ett fast värde, utan istället kan variera som en del av indata till problemet, är tiden exponentiell.

Det enklaste icke-triviala fallet av klickhittningsproblemet är att hitta en triangel i en graf, eller på motsvarande sätt bestämma om grafen är triangelfri . I en graf G med m kanter kan det finnas högst Θ( m ^3/2 ) trianglar (med stor theta-notation för att indikera att denna gräns är snäv). Det värsta fallet för denna formel inträffar när G i sig är en klick. Därför måste algoritmer för att lista alla trianglar ta minst Ω( m ^3/2 ) tid i värsta fall (med hjälp av big omega notation ), och algoritmer är kända som matchar denna tidsbundna. Till exempel Chiba & Nishizeki (1985) en algoritm som sorterar hörnen i ordning från högsta grad till lägsta och sedan itererar genom varje hörn v i den sorterade listan och letar efter trianglar som inkluderar v och inte inkluderar någon tidigare hörn i lista. För att göra det markerar algoritmen alla grannar till v , söker igenom alla kanter som faller in på en granne till v och matar ut en triangel för varje kant som har två markerade ändpunkter, och tar sedan bort markeringarna och tar bort v från grafen. Som författarna visar är tiden för denna algoritm proportionell mot arboriciteten hos grafen (betecknad a ( G ) ) multiplicerat med antalet kanter, vilket är   O ( m a ( G ) ) . Eftersom arboriciteten är högst O ( m ^1/2 ) , körs denna algoritm i tiden O ( m ^3/2 ) . Mer generellt kan alla k -vertexklickar listas med en liknande algoritm som tar tid proportionell mot antalet kanter multiplicerat med arboriciteten i potensen ( k − 2) . För grafer med konstant arboricitet, såsom plana grafer (eller i allmänhet grafer från valfri icke-trivial minor-closed graffamilj ), tar denna algoritm O ( m ) tid, vilket är optimalt eftersom den är linjär i storleken på inmatningen.

Om man bara önskar en enda triangel, eller en försäkran om att grafen är triangelfri, är snabbare algoritmer möjliga. Som Itai & Rodeh (1978) observerar innehåller grafen en triangel om och endast om dess närliggande matris och kvadraten på närliggande matris innehåller poster som inte är noll i samma cell. Därför O ( n ^{2,376 )} för snabb matrismultiplikation användas för att hitta trianglar i tiden . Alon, Yuster & Zwick (1994) använde snabb matrismultiplikation för att förbättra O ( m ^3/2 ) -algoritmen för att hitta trianglar till O ( m ^1,41 ) . Dessa algoritmer baserade på snabb matrismultiplikation har också utvidgats till problem med att hitta k -klickar för större värden på k .

Listar alla maximala klick

Enligt ett resultat av Moon & Moser (1965) har varje n -vertexgraf som mest 3 ^{n /3} maximala klick. De kan listas med Bron–Kerbosch-algoritmen , en rekursiv bakåtspårningsprocedur av Bron & Kerbosch (1973) . Den huvudsakliga rekursiva subrutinen i denna procedur har tre argument: en delvis konstruerad (icke-maximal) klick, en uppsättning kandidathörn som kan läggas till klicken och en annan uppsättning hörn som inte bör läggas till (eftersom det skulle leda till till en klick som redan har hittats). Algoritmen försöker lägga till kandidatpunkten en efter en till den partiella klicken och gör ett rekursivt anrop för var och en. Efter att ha provat var och en av dessa hörn flyttas den till den uppsättning hörn som inte ska läggas till igen. Varianter av denna algoritm kan visa sig ha värsta möjliga körtid O (3 ^{n /3} ) , som matchar antalet klick som kan behöva listas. Därför ger detta en i värsta fall optimal lösning på problemet med att lista alla maximala klick. Vidare har Bron-Kerbosch-algoritmen rapporterats allmänt som snabbare i praktiken än dess alternativ.

Men när antalet klick är betydligt mindre än det värsta fallet kan andra algoritmer vara att föredra. Som Tsukiyama et al. (1977) visade, är det också möjligt att lista alla maximala klick i en graf under en tidsperiod som är polynom per genererad klick. En algoritm som deras där körtiden beror på utdatastorleken är känd som en utdatakänslig algoritm . Deras algoritm är baserad på följande två observationer, som relaterar de maximala klicken i den givna grafen G till de maximala klicken i en graf G \ v som bildas genom att ta bort en godtycklig vertex v från G :

• För varje maximal klick K av G \ v , fortsätter antingen K att bilda en maximal klick i G , eller så bildar K ⋃ { v } en maximal klick i G . Därför G minst lika många maximala klick som G \ v har.
• Varje maximal klick i G som inte innehåller v är en maximal klick i G \ v , och varje maximal klick i G som innehåller v kan bildas från en maximal klick K i G \ v genom att lägga till v och ta bort de icke-grannar av v från K .

Genom att använda dessa observationer kan de generera alla maximala klick i G genom en rekursiv algoritm som väljer en vertex v godtyckligt och sedan, för varje maximal klick K i G \ v , matar ut både K och klicken som bildas genom att addera v till K och ta bort non -grannar till v . Vissa klick av G kan dock genereras på detta sätt från mer än en föräldraklick av G \ v , så de eliminerar dubbletter genom att mata ut en klick i G endast när dess förälder i G \ v är lexikografiskt maximalt bland alla möjliga föräldraklick. På basis av denna princip visar de att alla maximala klick i G kan genereras i tiden O ( mn ) per klick, där m är antalet kanter i G och n är antalet hörn. Chiba & Nishizeki (1985) förbättrar detta till O( ma ) per klick, där a är arboriciteten för den givna grafen. Makino & Uno (2004) tillhandahåller en alternativ utdatakänslig algoritm baserad på snabb matrismultiplikation. Johnson & Yannakakis (1988) visar att det till och med är möjligt att lista alla maximala klick i lexikografisk ordning med polynomfördröjning per klick. Valet av ordning är dock viktigt för effektiviteten hos denna algoritm: för den omvända ordningen finns det ingen polynomfördröjningsalgoritm om inte P = NP .

På basis av detta resultat är det möjligt att lista alla maximala klick i polynomtid, för familjer av grafer där antalet klick är polynomiellt avgränsat. Dessa familjer inkluderar ackordsgrafer , kompletta grafer , triangelfria grafer , intervallgrafer , grafer med avgränsad boxicitet och plana grafer . Speciellt har de plana graferna O ( n ) klick, av högst konstant storlek, som kan listas i linjär tid. Detsamma gäller för alla grafer som är både glesa (har ett antal kanter högst konstant gånger antalet hörn) och stängda under operationen att ta subgrafer.

Hitta maximala klick i godtyckliga grafer

Det är möjligt att hitta den maximala klicken, eller klicktalet, för en godtycklig n -vertexgraf i tiden O (3 ^{n /3} ) = O (1,4422 ⁿ ) genom att använda en av algoritmerna som beskrivs ovan för att lista alla maximala klick i grafen och returnerar den största. Men för denna variant av klickproblemet är bättre värsta tänkbara tidsgränser möjliga. Algoritmen av Tarjan & Trojanowski (1977) löser detta problem i tiden O (2 ^{n /3} ) = O (1,2599 ⁿ ) . Det är ett rekursivt backtracking-schema som liknar det för Bron–Kerbosch-algoritmen , men kan eliminera vissa rekursiva anrop när det kan visas att klicken som hittas i anropet kommer att vara suboptimala. Jian (1986) förbättrade tiden till O (2 ^{0,304 n} ) = O (1,2346 ⁿ ) och Robson (1986) förbättrade den till O (2 ^{0,276 n} ) = O (1,2108 ⁿ ) tid, på bekostnad av större utrymmesanvändning . Robsons algoritm kombinerar ett liknande backtracking-schema (med en mer komplicerad fallanalys) och en dynamisk programmeringsteknik där den optimala lösningen är förberäknad för alla små anslutna subgrafer av komplementgrafen . Dessa dellösningar används för att genväga backtracking-rekursionen. Den snabbaste algoritmen som är känd idag är en förfinad version av denna metod av Robson (2001) som körs i tiden O (2 ^{0,249 n} ) = O (1,1888 ⁿ ) .

Det har också gjorts omfattande forskning om heuristiska algoritmer för att lösa maximala klickproblem utan värsta körtidsgarantier, baserat på metoder inklusive branch and bound , lokal sökning , giriga algoritmer och begränsningsprogrammering . Icke-standardiserade beräkningsmetoder som har föreslagits för att hitta klick inkluderar DNA-beräkning och adiabatisk kvantberäkning . Problemet med maximal klick var föremål för en implementeringsutmaning sponsrad av DIMACS 1992–1993, och en samling grafer som användes som riktmärken för utmaningen, som är allmänt tillgänglig.

Särskilda klasser av grafer

I denna permutationsgraf motsvarar de maximala klicken de längst minskande undersekvenserna (4,3,1) och (4,3,2) av den definierande permutationen.

Plana grafer , och andra familjer av glesa grafer, har diskuterats ovan: de har linjärt många maximala klick, av begränsad storlek, som kan listas i linjär tid. Speciellt för plana grafer kan vilken klick som helst ha högst fyra hörn, enligt Kuratowskis teorem .

Perfekta grafer definieras av egenskaperna att deras klicknummer är lika med deras kromatiska nummer , och att denna likhet även gäller i var och en av deras inducerade subgrafer . För perfekta grafer är det möjligt att hitta en maximal klick i polynomtid, med hjälp av en algoritm baserad på semidefinite programmering . Denna metod är dock komplex och icke-kombinatorisk, och specialiserade klickhittande algoritmer har utvecklats för många underklasser av perfekta grafer. I komplementgraferna för tvådelade grafer tillåter Kőnigs teorem att det maximala klickproblemet kan lösas med hjälp av tekniker för matchning . I en annan klass av perfekta grafer, permutationsgraferna , är en maximal klick en längst minskande delsekvens av permutationen som definierar grafen och kan hittas med hjälp av kända algoritmer för det längst minskande subsekvensproblemet. Omvänt kan varje instans av det längst minskande följdproblemet beskrivas på samma sätt som ett problem med att hitta en maximal klick i en permutationsgraf. Till och med, Pnueli & Lempel (1972) tillhandahåller en alternativ kvadratisk tidsalgoritm för maximala klick i jämförbarhetsgrafer, en bredare klass av perfekta grafer som inkluderar permutationsgraferna som ett specialfall. I ackordsgrafer kan de maximala klicken hittas genom att lista hörnen i en elimineringsordning och kontrollera klickområdena för varje vertex i denna ordning.

I vissa fall kan dessa algoritmer utökas till andra, icke-perfekta, klasser av grafer också. Till exempel, i en cirkelgraf är grannskapet för varje vertex en permutationsgraf, så en maximal klick i en cirkelgraf kan hittas genom att tillämpa permutationsgrafalgoritmen på varje grannskap. På liknande sätt finns det i en enhetsdiskgraf (med en känd geometrisk representation) en polynomtidsalgoritm för maximala klick baserad på att tillämpa algoritmen för komplement av tvådelade grafer till delade stadsdelar av par av hörn.

Det algoritmiska problemet med att hitta en maximal klick i en slumpmässig graf från Erdős–Rényi-modellen (där varje kant visas med sannolikhet 1/2 , oberoende av de andra kanterna) föreslogs av Karp (1976) . Eftersom den maximala klicken i en slumpmässig graf har logaritmisk storlek med hög sannolikhet, kan den hittas genom en brute force-sökning på förväntad tid 2 ^{O (log 2 n )} . Detta är en kvasi-polynomisk tidsbunden . Även om klickantalet för sådana grafer vanligtvis är mycket nära 2 log ₂ n , hittar enkla giriga algoritmer såväl som mer sofistikerade randomiserade approximationstekniker bara klicker med storleken log ₂ n , hälften så stora. Antalet maximala klick i sådana grafer är med hög sannolikhet exponentiellt i log ² n , vilket förhindrar metoder som listar alla maximala klick från att köras i polynomtid. På grund av svårigheten med detta problem har flera författare undersökt med planterade klick , klickproblemet på slumpmässiga grafer som har utökats genom att lägga till stora klick. Även om spektrala metoder och semidefinite programmering o kan √n ) ) Ω detektera dolda klick med storleken ( √n ( ) , är inga polynomtidsalgoritmer för närvarande kända för att detektera de med storleken (uttryckt med little-o-notation .

Approximationsalgoritmer

Flera författare har övervägt approximationsalgoritmer som försöker hitta en klick eller oberoende uppsättning som, även om den inte är maximal, har en storlek så nära det maximala som kan hittas i polynomtid. Även om mycket av detta arbete har fokuserat på oberoende uppsättningar i glesa grafer, ett fall som inte är vettigt för det komplementära klickproblemet, har det också förekommit arbete med approximationsalgoritmer som inte använder sådana sparsitetsantaganden.

Feige (2004) beskriver en polynomisk tidsalgoritm som hittar en klick med storleken Ω((log n /log log n ) ² ) i vilken graf som helst som har klicknummer Ω( n /log ^k n ) för vilken konstant k som helst . Genom att använda denna algoritm när klicknumret för en given ingångsgraf är mellan n /log n och n /log ³ⁿ för , byta till en annan algoritm av Boppana & Halldórsson (1992) grafer med högre klicknummer, och välja en två- vertex klick om båda algoritmerna inte lyckas hitta något, tillhandahåller Feige en approximationsalgoritm som hittar en klick med ett antal hörn inom en faktor O( n (log log n ) ² /log ³ n ) av maximum. Även om approximationsförhållandet för denna algoritm är svagt, är det den mest kända hittills. Resultaten för approximationshårdhet som beskrivs nedan antyder att det inte kan finnas någon approximationsalgoritm med ett approximationsförhållande som är signifikant mindre än linjärt.

Nedre gränser

NP-fullständighet

3-CNF Satisfiability-instansen (x ∨ x ∨ y) ∧ (~x ∨ ~y ∨ ~y) ∧ (~x ∨ y ∨ y) reducerad till klick. De gröna hörnen bildar en 3-klick och motsvarar en tillfredsställande uppgift.

Klickbeslutsproblemet är NP-komplett . Det var ett av Richard Karps ursprungliga 21 problem som visades NP-komplett i hans papper från 1972 "Reducibility Among Combinatorial Problems". Detta problem nämndes också i Stephen Cooks artikel som introducerade teorin om NP-kompletta problem. På grund av beslutsproblemets hårdhet är problemet med att hitta en maximal klick också NP-hårt. Om man kunde lösa det skulle man också kunna lösa beslutsproblemet, genom att jämföra storleken på den maximala klicken med storleksparametern som ges som input i beslutsproblemet.

Karps NP-fullständighetsbevis är en mång-en minskning från det booleska tillfredsställbarhetsproblemet . Den beskriver hur man översätter booleska formler i konjunktiv normalform (CNF) till motsvarande instanser av problemet med maximal klick. Tillfredsställelsen visade sig i sin tur vara NP-komplett i Cook–Levin-satsen . Från en given CNF-formel bildar Karp en graf som har en vertex för varje par ( v , c ) , där v är en variabel eller dess negation och c är en sats i formeln som innehåller v . Två av dessa hörn är förbundna med en kant om de representerar kompatibla variabeltilldelningar för olika satser. Det vill säga att det finns en kant från ( v , c ) till ( u , d ) närhelst c ≠ d och u och v inte är varandras negationer. Om k anger antalet satser i CNF-formeln, så representerar k -vertex-klickarna i denna graf konsekventa sätt att tilldela sanningsvärden till några av dess variabler för att uppfylla formeln. Därför är formeln tillfredsställbar om och endast om en k -vertexklick existerar.

Vissa NP-kompletta problem (såsom resandeförsäljarproblemet i plana grafer ) kan lösas i tid som är exponentiell i en sublinjär funktion av indatastorleksparametern n , betydligt snabbare än en brute-force-sökning. Det är dock osannolikt att en sådan subexponentiell tidsgräns är möjlig för klickproblemet i godtyckliga grafer, eftersom det skulle innebära liknande subexponentiella gränser för många andra standardproblem med NP-kompletta problem.

Kretskomplexitet

En monoton krets för att detektera en k -klick i en n -vertexgraf för k = 3 och n = 4 . Varje ingång till kretsen kodar närvaron eller frånvaron av en viss (röd) kant i grafen. Kretsen använder en intern and-gate för att detektera varje potentiell k -klick.

Klickproblemets beräkningssvårigheter har lett till att det används för att bevisa flera lägre gränser för kretskomplexitet . Förekomsten av en klick av en given storlek är en monoton grafegenskap , vilket betyder att om en klick finns i en given graf kommer den att finnas i vilken supergraf som helst . Eftersom denna egenskap är monoton måste det finnas en monoton krets, som endast använder och grindar och /eller grindar , för att lösa klickbeslutsproblemet för en given fast klickstorlek. Storleken på dessa kretsar kan dock bevisas vara en superpolynomfunktion av antalet hörn och klickstorleken, exponentiell i kubroten av antalet hörn. Även om ett litet antal NOT-grindar tillåts, förblir komplexiteten superpolynomial. Dessutom måste djupet för en monoton krets för klickproblemet som använder grindar med begränsad fan-in vara åtminstone ett polynom i klickstorleken.

Beslutsträdets komplexitet

Ett enkelt beslutsträd för att upptäcka närvaron av en 3-klick i en graf med 4 vertex. Den använder upp till 6 frågor av formen "Finns den röda kanten?", som matchar den optimala gränsen n ( n − 1)/2.

Den (deterministiska) beslutsträdets komplexitet för att bestämma en grafegenskap är antalet frågor av formen "Finns det en kant mellan vertex u och vertex v ?" som måste besvaras i värsta fall för att avgöra om en graf har en viss egenskap. Det vill säga, det är minimihöjden för ett booleskt beslutsträd för problemet. Det finns n ( n − 1)/2 möjliga frågor att ställa. Därför kan vilken grafegenskap som helst bestämmas med högst n ( n − 1)/2 frågor. Det är också möjligt att definiera slumpmässigt och kvantbeslutsträdskomplexitet för en egenskap, det förväntade antalet frågor (för ett värsta fall) som en randomiserad eller kvantalgoritm måste ha besvarat för att korrekt avgöra om den givna grafen har egenskapen .

Eftersom egenskapen att innehålla en klick är monoton, omfattas den av Aanderaa–Karp–Rosenberg-förmodan, som säger att den deterministiska beslutsträdets komplexitet för att bestämma en icke-trivial monoton grafegenskap är exakt n ( n − 1)/2 . För godtyckliga monotona grafegenskaper förblir denna gissning obevisad. Men för deterministiska beslutsträd, och för alla k i intervallet 2 ≤ k ≤ n , visades egenskapen att innehålla en k -klick ha beslutsträdskomplexitet exakt n ( n − 1)/2 av Bollobás (1976) . Deterministiska beslutsträd kräver också exponentiell storlek för att detektera klicker, eller stor polynomstorlek för att detektera klicker av begränsad storlek.

Aanderaa–Karp–Rosenbergs gissning anger också att den randomiserade beslutsträdskomplexiteten för icke-triviala monotona funktioner är Θ( n ² ) . Gissningen förblir återigen obevisad, men har lösts för egenskapen att innehålla en k -klick för 2 ≤ k ≤ n . Denna egenskap är känd för att ha randomiserad beslutsträdskomplexitet Θ( n ² ) . För kvantbeslutsträd är den mest kända nedre gränsen Ω( n ) , men ingen matchningsalgoritm är känd för fallet k ≥ 3 .

Intraktabilitet med fasta parametrar

Parameteriserad komplexitet är den komplexitetsteoretiska studien av problem som naturligt är utrustade med en liten heltalsparameter k och för vilka problemet blir svårare när k ökar, till exempel att hitta k -klickar i grafer. Ett problem sägs kunna hanteras med fasta parametrar om det finns en algoritm för att lösa det på ingångar av storlek n , och en funktion f , så att algoritmen körs i tiden f ( k ) n ^{O (1)} . Det vill säga, det är trakterbart med fasta parametrar om det kan lösas i polynomtid för vilket fast värde på k som helst och dessutom om exponenten för polynomet inte beror på k .

För att hitta k -vertexklickar har brute force-sökningsalgoritmen körtid O( n k ^k 2 ⁾ . Eftersom exponenten för n beror på k , är denna algoritm inte trakterbar med fasta parametrar. Även om det kan förbättras genom snabb matrismultiplikation har löptiden fortfarande en exponent som är linjär i k . Så även om körtiden för kända algoritmer för klickproblemet är polynom för alla fasta k , räcker dessa algoritmer inte för fixparameter medförbarhet. Downey & Fellows (1995) definierade en hierarki av parametriserade problem, W-hierarkin, som de förmodade inte hade algoritmer med fasta parametrar. De bevisade att oberoende uppsättning (eller motsvarande klick) är svårt för den första nivån i denna hierarki, W[1] . Sålunda, enligt deras gissningar, har klick ingen algoritm som kan hanteras med fasta parametrar. Dessutom ger detta resultat grunden för bevis på W[1]-hårdhet för många andra problem, och fungerar således som en analog till Cook- Levin-satsen för parameteriserad komplexitet.

Chen et al. (2006) visade att att hitta k -vertexklickar inte kan göras i tid n ^{o ( k )} om inte den exponentiella tidshypotesen misslyckas. Återigen ger detta bevis på att ingen algoritm med fasta parametrar är möjlig.

Även om problemen med att lista maximala klicker eller hitta maximala klicker osannolikt är hanteringsbara med fasta parametrar med parametern k , kan de vara hanteringsbara med fasta parametrar för andra parametrar med instanskomplexitet. Till exempel är båda problemen kända för att kunna hanteras med fasta parametrar när de parametriseras av indatagrafens degeneration .

Ungefärlig hårdhet

En graf över kompatibilitetsrelationer mellan 2-bitars sampel av 3-bitars provsträngar. Varje maximal klick (triangel) i denna graf representerar alla sätt att sampla en enda 3-bitars sträng. Beviset för att klickproblemet är ofrånkomligt involverar inducerade subgrafer av analogt definierade grafer för större antal bitar.

Svaga resultat som antyder att klickproblemet kan vara svårt att uppskatta har varit känt under lång tid. Garey & Johnson (1978) observerade att eftersom klicktalet antar små heltalsvärden och är NP-svårt att beräkna, kan det inte ha ett fullständigt polynom-tidsapproximationsschema . Om en för exakt uppskattning var tillgänglig, skulle avrundning av dess värde till ett heltal ge det exakta klicknumret. Men lite mer var känt förrän i början av 1990-talet, då flera författare började göra kopplingar mellan approximationen av maximala klicker och sannolikhetskontrollerbara bevis . De använde dessa anslutningar för att bevisa hårdheten av approximationsresultat för det maximala klickproblemet. Efter många förbättringar av dessa resultat är det nu känt att för varje reellt tal ε > 0 kan det inte finnas någon polynomtidsalgoritm som approximerar den maximala klicken till en faktor som är bättre än O ( n ^{1 − ε} ) , om inte P = NP .

Den grova idén med dessa inapproximability-resultat är att bilda en graf som representerar ett probabilistiskt kontrollerbart bevissystem för ett NP-komplett problem såsom det booleska tillfredsställbarhetsproblemet. I ett probabilistiskt kontrollerbart bevissystem representeras ett bevis som en sekvens av bitar. En instans av tillfredsställbarhetsproblemet bör ha ett giltigt bevis om och endast om det är tillfredsställbart. Beviset kontrolleras av en algoritm som, efter en polynom-tidsberäkning på ingången till tillfredsställbarhetsproblemet, väljer att undersöka ett litet antal slumpmässigt valda positioner av bevissträngen. Beroende på vilka värden som finns på det bitprovet, kommer kontrollören antingen att acceptera eller förkasta beviset, utan att titta på resten av bitarna. Falska negativa meddelanden är inte tillåtna: ett giltigt bevis måste alltid accepteras. Ett ogiltigt bevis kan dock ibland av misstag accepteras. För varje ogiltigt bevis måste sannolikheten att kontrollören accepterar det vara låg.

För att omvandla ett probabilistiskt kontrollerbart bevissystem av denna typ till ett klickproblem, bildar man en graf med en vertex för varje möjlig accepterande körning av beviskontrollen. Det vill säga, en vertex definieras av ett av de möjliga slumpmässiga valen av uppsättningar av positioner att undersöka, och av bitvärden för de positioner som skulle få kontrollören att acceptera beviset. Det kan representeras av ett delord med en 0 eller 1 vid varje undersökt position och ett jokertecken vid varje återstående position. Två hörn ligger intill varandra, i denna graf, om de motsvarande två accepterande körningarna ser samma bitvärden vid varje position som de båda undersöker. Varje (giltig eller ogiltig) bevissträng motsvarar en klick, uppsättningen av accepterande körningar som ser den bevissträngen, och alla maximala klick uppstår på detta sätt. En av dessa klick är stor om och bara om den motsvarar en provsträng som många provkontrollanter accepterar. Om den ursprungliga satisfiability-instansen är tillfredsställbar kommer den att ha en giltig bevissträng, en som accepteras av alla körningar av checkern, och denna sträng kommer att motsvara en stor klick i grafen. Men om den ursprungliga instansen inte är tillfredsställbar är alla bevissträngar ogiltiga, varje bevissträng har bara ett litet antal checkerkörningar som av misstag accepterar det, och alla klick är små. Därför, om man kunde skilja i polynomtid mellan grafer som har stora klick och grafer där alla klick är små, eller om man exakt skulle kunna approximera klickproblemet, då skulle applicering av denna approximation på graferna som genereras från satisfiability-instanser tillåta tillfredsställande instanser att särskiljas från otillfredsställande fall. Detta är dock inte möjligt om inte P = NP.

Anteckningar

Undersökningar och läroböcker

•   Arora, Sanjeev ; Barak, Boaz (2009), Computational Complexity: A Modern Approach , Cambridge University Press, ISBN 978-0-521-42426-4 .
•   Blair, Jean RS; Peyton, Barry (1993), "An introduction to chordal graphs and clique trees", Graph theory and sparse matrix computation , IMA Vol. Matematik. Appl., vol. 56, Springer, New York, sid. 1–29, doi : 10.1007/978-1-4613-8369-7_1 , MR 1320296 .
•   Bomze, IM; Budinich, M.; Pardalos, PM; Pelillo, M. (1999), "The maximum clique problem", Handbook of Combinatorial Optimization , vol. 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", Introduction to Algorithms (2nd ed.), MIT Press och McGraw-Hill, s. 1003–1006, ISBN 0-262-03293-7 .
•   Downey, RG; Fellows, MR (1999), Parameterized complexity , Springer-Verlag , ISBN 0-387-94883-X .
•   Golumbic, MC (1980), Algoritmisk grafteori och perfekta grafer , datavetenskap och tillämpad matematik, Academic Press , ISBN 0-444-51530-5 .
•   Grötschel, M .; Lovász, L .; Schrijver, A. (1988), "9.4 Coloring Perfect Graphs", Geometric Algorithms and Combinatorial Optimization , Algorithms and Combinatorics, vol. 2, Springer-Verlag , s. 296–298, ISBN 0-387-13624-X .
•   Gutin, G. (2004), "5.3 Independent sets and cliques", i Gross, JL; Yellen, J. (red.), Handbook of graph theory , Discrete Mathematics & Its Applications, CRC Press, s. 389–402, ISBN 978-1-58488-090-5 .
•   Muegge, Ingo; Rarey, Matthias (2001), "Small molecule docking and scoring", Reviews in Computational Chemistry , 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 , National Academies Press, doi : 10.17226/4886 , ISBN 978-0-309-05097-5 .
• Pelillo, Marcello (2009), "Heuristics for maximum clique and independent set", Encyclopedia of Optimization , Springer, s. 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 , MR 5 från 125, maj 2, originalet , 125 maj. 2012 .
•   Sipser, M. (1996), Introduction to the Theory of Computation , International Thompson Publishing , ISBN 0-534-94728-X .
•   Skiena, Steven S. (2009), The Algorithm Design Manual (2nd ed.), Springer, ISBN 978-1-84800-070-4 .
•   Valiente, Gabriel (2002), "Kapitel 6: Clique, Independent Set, and Vertex Cover", Algorithms on Trees and Graphs , Springer, s. 299–350, doi : 10.1007/978-3-662-04921-1_6 , S2CID 118777692 .
•   Wasserman, Stanley ; Faust, Katherine (1994), Social Network Analysis: Methods and Applications , Structural Analysis in the Social Sciences, vol. 8, Cambridge University Press, sid. 276, ISBN 978-0-521-38707-1 .

Populär press

• Kolata, Gina (26 juni 1990), "In a frenzy, Math Enters Age of Electronic Mail", The New York Times .

Forskningsartiklar

•   Abello, J.; Pardalos, PM; Resende, MGC (1999), "Om maximala klickproblem i mycket stora grafer" (PDF) , i Abello, J.; Vitter, J. (red.), External Memory Algorithms , DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 50, American Mathematical Society , s. 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", Random Structures & Algorithms , 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, Nederländerna , s. 354–364 .
•   Amano, Kazuyuki; Maruoka, Akira (2005), "En superpolynomial nedre gräns för en krets som beräknar klickfunktionen med högst ( 1/6) log N -negeringsgrindar", SIAM Journal on Computing , 35 (1): 201–216, doi : 10.1137/S0097539701396959 , MR 2178806 .
•    Arora, Sanjeev ; Lund, Carsten ; Motwani, Rajeev ; Sudan, Madhu ; Szegedy, Mario (1998), "Proof verification and the hardness of approximation problems", Journal of the ACM , 45 (3): 501–555, doi : 10.1145/278298.278306 , S2CID 8561542 , EC0CC8 TR98 . Ursprungligen presenterad vid 1992 års 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", Journal of the ACM , 45 (1): 70–122, doi : 10.1145/273865.273901 , S2CID 751563 . Ursprungligen presenterad vid 1992 års symposium om grunder för datavetenskap, doi : 10.1109 /SFCS.1992.267824 .
• Balas, E.; Yu, CS (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 maximum cliques", Information Processing Letters , 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 , Series B, 21 (1): 1–7, doi : 10.1016/0095-8956(76)90021-6 , ISSN 05095-89 .
•   Boppana, R.; Halldórsson, MM (1992), "Approximating av maximala oberoende mängder genom att utesluta subgrafer", BIT Numerical Mathematics , 32 (2): 180–196, doi : 10.1007/BF01994876 , S2CID 123335474 .
•   Bron, C.; Kerbosch, J. (1973), "Algorithm 457: finding all cliques of an undirected graph", Communications of the ACM , 16 (9): 575–577, doi : 10.1145/362342.362367 , S2CID 138867 .
• Carraghan, R.; Pardalos, PM (1990), "An exact algorithm for the maximum clique problem", Operations Research Letters , 9 (6): 375–382, doi : 10.1016/0167-6377(90)90057-C .
• Cazals, F.; Karande, C. (2008), "A not on the problem of reporting maximal cliques", Theoretical Computer Science , 407 (1): 564–568, doi : 10.1016/j.tcs.2008.05.010 .
• Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), "Strong computational lower bounds via parameterized complexity", 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 list algorithms", SIAM Journal on Computing , 14 (1): 210–223, doi : 10.1137/0214017 .
•   Childs, AM; Farhi, E.; Goldstone, J .; Gutmann, S. (2002) , "Finding cliques by quantum adiabatic evolution", Quantum Information and Computation , 2 (3): 181–191, arXiv : quant-ph/0012104 , Bibcode : 2000quant.ph.120 :121 : 120 : 121 /QIC2.3 , S2CID 33643794 .
•   Childs, AM; Eisenberg, JM (2005), "Quantum algorithms for subset finding", Quantum Information and Computation , 5 (7): 593–604, arXiv : quant-ph/0311038 , Bibcode : 2003quant.ph.11038C , doi .Q26IC : 26IC .7 , S2CID 37556989 .
• Clark, Brent N.; Colbourn, Charles J .; Johnson, David S. (1990), "Unit disk graphs", Discrete Mathematics , 86 (1–3): 165–177, doi : 10.1016/0012-365X(90)90358-O
•   Cook, SA (1971), "The complexity of theoremproving procedures", Proc . 3rd ACM Symposium on Theory of Computing , s. 151–158, doi : 10.1145/800157.805047 , S2CID 7573663 .
•   Cook, Stephen A. (1985), "A taxonomy of problems with fast parallel algorithms", Information and Control , 64 (1–3): 2–22, doi : 10.1016/S0019-9958(85)80041-3 , MR 0837088 .
•   Day, William HE; Sankoff, David (1986), "Computational complexity of inferring phylogenies by compatibility", Systematic Zoology , 35 (2): 224–229, doi : 10.2307/2413432 , JSTOR 2413432 .
• Downey, RG; Fellows, MR (1995), "Handbarhet och fullständighet med fasta parametrar. II. Om fullständighet för W[1]", Theoretical Computer Science , 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", Theoretical Computer Science , 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.11629 , 736C 5ID 45ID .
• Erdős, Paul ; Szekeres, George (1935), "Ett kombinatoriskt problem i geometri" (PDF) , Compositio Mathematica , 2 : 463–470 .
•   Even, S. ; Pnueli, A .; Lempel, A. (1972), "Permutation graphs and transitive graphs", Journal of the ACM , 19 (3): 400–410, doi : 10.1145/321707.321710 , S2CID 9501737 .
•   Fahle, T. (2002), "Enkelt och snabbt: Förbättring av en gren-och-bunden algoritm för maximal klick", Proc. 10th European Symposium on Algorithms , Lecture Notes in Computer Science, vol. 2461, Springer-Verlag, s. 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), "Approximating klick är nästan NP-komplett", Proc. 32:a IEEE Symp. on Foundations of Computer Science , s. 2–12, doi : 10.1109/SFCS.1991.185341 , ISBN 0-8186-2445-0 , S2CID 46605913 .
• Feige, U. ; Krauthgamer, R. (2000), "Hitta och certifiera en stor gömd klick i en semirandom graf", Random Structures and Algorithms , 16 (2): 195–208, doi : 10.1002/(SICI)1098-2418(20603) :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 , MR 0860518 .
•   Garey, MR ; Johnson, DS (1978), " Strong" NP-fullständighetsresultat: motivation, exempel och implikationer", Journal of the ACM , 25 (3): 499–508, doi : 10.1145/322077.322090 , S2CID 18371269 .
•   Garey, MR ; Johnson, DS ; Stockmeyer, L. (1976), "Some simplified NP-complete graph problems", Theoretical Computer Science , 1 (3): 237–267, doi : 10.1016/0304-3975(76)90059-1 , MR 0411240 .
• Gavril, F. (1973), "Algorithms for a maximum clique and a maximum independent set of a circle graph", Networks , 3 (3): 261–273, doi : 10.1002/net.3230030305 .
•   Goldmann, M.; Håstad, J. (1992), "En enkel nedre gräns för monoton klick med hjälp av ett kommunikationsspel" (PDF) , Information Processing Letters , 41 (4): 221–226, CiteSeerX 10.1.1.185.3065 , doi : 10.1016/002 -0190(92)90184-W .
• Gröger, Hans Dietmar (1992), "On the randomized complexity of monotone graph properties" (PDF) , Acta Cybernetica , 10 (3): 119–127 , hämtad 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, MM (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, JH (1998), "Testuppsättningskomprimeringsalgoritmer för kombinationskretsar", Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design , s. 283–289, doi : 10.1145/288548.288615 , S2CID 12258606 .
•    Harary, F. ; Ross, IC (1957), "A procedure for clique detection using the group matrix", Sociometri , American Sociological Association, 20 (3): 205–215, doi : 10.2307/2785673 , JSTOR 2785673 , MR 0110590 .
• Håstad, J. (1999), "Klick är svår att uppskatta inom n ^{1 − ε} ", Acta Mathematica , 182 (1): 105–142, doi : 10.1007/BF02392825 .
• Impagliazzo, R .; Paturi, R.; Zane, F. (2001), "Vilka problem har starkt exponentiell komplexitet?", 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), "En O (2 ^{0,304 n} ) algoritm för att lösa maximalt oberoende uppsättningsproblem", IEEE Transactions on Computers , IEEE Computer Society, 35 (9): 847–851, doi : 10.1109/TC.1986.1676847 , ISSN 0018-9340 .
•   Johnson, DS ; Trick, MA , red. (1996), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 11–13 oktober 1993 , DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26, American Mathematical Society , ISBN 0-8218-6609-5 .
• Johnson, DS ; Yannakakis, M. (1988), "On generating all maximum independent sets", Information Processing Letters , 27 (3): 119–123, doi : 10.1016/0020-0190(88)90065-8 .
• Karp, Richard M. (1972), "Reducibility among combinatorial problems", i Miller, RE; Thatcher, JW (red.), Complexity of Computer Computations (PDF) , New York: Plenum , s. 85–103, arkiverad från originalet (PDF) 2011-06-29 , hämtad 2009-12-17 .
• Karp, Richard M. (1976), "Probabilistic analysis of some combinatorial search problems", i Traub, JF (red.), Algorithms and Complexity: New Directions and Recent Results , New York: Academic Press , s. 1–19 .
• Katayama, K.; Hamamoto, A.; Narihisa, H. (2005), "An effective local search for the maximum clique problem", Information Processing Letters , 95 (5): 503–511, doi : 10.1016/j.ipl.2005.05.010 .
•    Khot, S. (2001), "Förbättrade inapproximability results for MaxClique, chromatic number and approximate graph coloring", Proc. 42:a IEEE Symp. Foundations of Computer Science , s. 600–609, doi : 10.1109/SFCS.2001.959936 , ISBN 0-7695-1116-3 , S2CID 11987483 .
• Kloks, T.; Kratsch, D.; Müller, H. (2000), "Att hitta och räkna små inducerade subgrafer effektivt", Information Processing Letters , 74 (3–4): 115–121, doi : 10.1016/S0020-0190(00)00047-8 .
• Konc, J.; Janežič, D. (2007), "En förbättrad gren och bunden algoritm för det maximala klickproblemet" (PDF) , MATCH Communications in Mathematical and in Computer Chemistry , 58 (3): 569–590 . Källkod
•   Kuhl, FS; Crippen, GM; Friesen, DK (1983), "A combinatorial algorithm for calculating ligand binding", Journal of Computational Chemistry , 5 (1): 24–34, doi : 10.1002/jcc.540050105 , S2CID 122923018 .
•    Lagarias, Jeffrey C .; Shor, Peter W. (1992), "Keller's cube-tiling conjecture is false in high dimensions", Bulletin of the American Mathematical Society , New Series, 27 (2): 279–283, arXiv : math/9210222 , doi : 10.1090 /S0273-0979-1992-00318-X , MR 1155280 , S2CID 6390600 .
•   Lipton, RJ ; Tarjan, RE (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) (PDF) , Proceedings of the VLDB Endowment, vol. 8, s. 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 , hdl : 10.1007 / BF02289146 14 , 52ID   .
•   Mackey, John (2002), "A cube tiling of dimension eight with no facesharing", Discrete and Computational Geometry , 28 (2): 275–279, doi : 10.1007/s00454-002-2801-9 , MR 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 4.42CID 5.42CID 5 .
•   Makino, K.; Uno, T. (2004), "New algorithms for enumerating all maximum cliques", Algorithm Theory: SWAT 2004 (PDF) , Lecture Notes in Computer Science, vol. 3111, Springer-Verlag , s. 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, JW; Moser, L. (1965), "On cliques in graphs", Israel Journal of Mathematics , 3 : 23–28, doi : 10.1007/BF02760024 , MR 0182577 , S2CID 9855414 .
• Nešetřil, J. ; Poljak, S. (1985), "Om subgrafproblemets komplexitet", Commentationes Mathematicae Universitatis Carolinae , 26 (2): 415–419 .
• Östergård, PRJ (2002), "En snabb algoritm för det maximala klickproblemet", Discrete Applied Mathematics , 120 (1–3): 197–207, doi : 10.1016/S0166-218X(01)00290-6 .
•   Ouyang, Q.; Kaplan, PD; Liu, S.; Libchaber, A. (1997), "DNA-lösning av det maximala klickproblemet", Science , 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", Information Processing Letters , 13 (4–5): 131–133, doi : 10.1016/0020-0190(81)90041-7 , MR 0651460 .
• Pardalos, PM; Rogers, GP (1992), "A branch and bound algorithm for the maximum clique problem", Computers & Operations Research , 19 (5): 363–375, doi : 10.1016/0305-0548(92)90067-F .
• Razborov, AA (1985), "Nedre gränser för den monotona komplexiteten hos vissa booleska funktioner", Proceedings of the USSR Academy of Sciences (på ryska), 281 : 798–801. Engelsk översättning i Sov. Matematik. Dokl. 31 (1985): 354–357 {{ citation }} : CS1 underhåll: efterskrift ( länk ) .
• Régin, J.-C. (2003), "Att använda begränsningsprogrammering för att lösa det maximala klickproblemet", Proc. 9:e Int. Konf. Principles and Practice of Constraint Programming – CP 2003 , Lecture Notes in Computer Science, vol. 2833, Springer-Verlag , s. 634–648, doi : 10.1007/978-3-540-45193-8_43 .
•   Rhodos, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), "CLIP: likhetssökning av 3D-databaser med hjälp av klickdetektion", Journal of Chemical Information and Computer Sciences , 43 ( 2): 443–448, doi : 10.1021/ci025605o , PMID 12653507 .
• Robson, JM (1986), "Algorithms for maximum independent sets", Journal of Algorithms , 7 (3): 425–440, doi : 10.1016/0196-6774(86)90032-5 .
• Robson, JM (2001), Hitta en maximal oberoende uppsättning i tid O (2 ^{n /4} ) .
• Rosgen, B; Stewart, L (2007), "Komplexitetsresultat på grafer med få klick" , Diskret matematik och teoretisk datavetenskap, 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 , MR 3296231 , S2CID 5 515 .
• 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 , S220171   .
•    Spirin, Victor; Mirny, Leonid A. (2003), "Protein complexes and functional modules in molecular networks", Proceedings of the National Academy of Sciences , 100 (21): 12123–12128, Bibcode : 2003PNAS..10012123S , do : 730/pnai. 2032324100 , PMC 218723 , PMID 14517352 .
• Tarjan, RE ; Trojanowski, AE (1977), "Finding a maximum independent set" (PDF) , SIAM Journal on Computing , 6 (3): 537–546, doi : 10.1137/0206038 .
•   Tomita, E.; Kameda, T. (2007), "En effektiv gren-och-bunden algoritm för att hitta en maximal klick med beräkningsexperiment", Journal of Global Optimization , 37 (1): 95–111, doi : 10.1007/s10898-006-9039 -7 , S2CID 21436014 .
•    Tomita, E.; Seki, T. (2003), "En effektiv gren-och-bunden algoritm för att hitta en maximal klick", Discrete Mathematics and Theoretical Computer Science , Lecture Notes in Computer Science, vol. 2731, Springer-Verlag, s. 278–289 , doi : 10.1007/3-540-45066-1_22 , ISBN 978-3-540-40505-4 , S2CID 21436014 .
• Tomita, E.; Tanaka, A.; Takahashi, H. (2006), "The worst-case time complexity for generating all maximum cliques and computational experiments", Theoretical Computer Science , 363 (1): 28–42, doi : 10.1016/j.tcs.2006.06.015 .
• Tsukiyama, S.; Ide, M.; Ariyoshi, I.; Shirakawa, I. (1977), "En ny algoritm för att generera alla maximala oberoende uppsättningar", SIAM Journal on Computing , 6 (3): 505–517, doi : 10.1137/0206036 .
•    Valiant, LG (1983), "Exponentiella nedre gränser för begränsade monotonkretsar", Proc. 15th ACM Symposium on Theory of Computing , s. 110–117, doi : 10.1145/800061.808739 , ISBN 0-89791-099-0 , S2CID 6326587 .
•   Vassilevska, V. ; Williams, R. (2009), "Hitta, minimera och räkna viktade subgrafer", Proc. 41st ACM Symposium on Theory of Computing , s. 455–464, CiteSeerX 10.1.1.156.345 , doi : 10.1145 /    , ISBN 978-1-50659ID 2. S. 1536414.1536477
•   Wegener, I. (1988), "Om komplexiteten av förgreningsprogram och beslutsträd för klickfunktioner", Journal of the 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", Information Processing Letters , 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. 38:e ACM Symp. Theory of Computing , s. 681–690, doi : 10.1145/1132516.1132612 , ISBN 1-59593-134-1 , S2CID 5713815 , ECCC TR05-100 .