Voir la source de Problème de la clique

[[Fichier:Brute force Clique algorithm.svg|thumb|upright=1.5|[[Recherche exhaustive]] d'une 4-[[clique (théorie des graphes)|clique]] dans ce graphe à 7 sommets en testant la [[graphe complet|complétude]] des [[Combinaison (mathématiques)|C]](7,4)=&nbsp;35 [[sous-graphe]]s à 4 sommets.]]
En [[informatique]], le '''problème de la clique''' est un [[problème algorithmique]] qui consiste à trouver des [[Clique (théorie des graphes)|cliques]] (sous-ensembles de [[Sommet (théorie des graphes)|sommets]] tous [[Arête (théorie des graphes)|adjacents]] deux à deux, également appelés [[Sous-graphe|sous-graphes]] [[Graphe complet|complets]]) dans un [[Graphe (mathématiques discrètes)|graphe]]. Ce problème a plusieurs formulations différentes selon les cliques et les informations sur les cliques devant être trouvées. Les formulations courantes du problème de la clique incluent :

* la recherche d'une clique maximum (une clique avec le plus grand nombre possible de sommets) ;
* la recherche d'une clique de poids maximum dans un [[graphe pondéré]] ;
* la liste de toutes les cliques maximums ;
* la résolution du [[problème de décision]] consistant à déterminer si un graphe contient une clique plus grande qu'une taille donnée.

Le problème de la clique apparaît dans la situation réelle suivante. Considérons un [[réseau social]], où les sommets du graphe représentent des personnes et les arêtes représentent la connaissance mutuelle entre les personnes. Une clique représente alors un sous-ensemble de personnes qui se connaissent toutes mutuellement, et des algorithmes pour trouver des cliques peuvent être utilisés pour découvrir ces groupes d'amis communs. Outre ses applications aux réseaux sociaux, le problème de la clique a également de nombreuses applications en [[bioinformatique]] et en [[chimie numérique]].

La plupart des versions du problème de la clique sont des problèmes difficiles. Le problème décisionnel de la clique est [[Problème NP-complet|NP-complet]] — c'est l'un des [[21 problèmes NP-complets de Karp]]. Le problème de trouver une {{Mvar|k}}-clique est à la fois [[Complexité paramétrée|intraitable à paramètre fixé]] (il n'est pas dans la classe de problèmes '''FPT''') et est {{Lien|trad=Hardness of approximation|fr=Dureté d'approximation|texte=difficile à approcher}}. Lister toutes les cliques maximums peut nécessiter un [[Complexité en temps|temps exponentiel]] car il existe des graphes avec un nombre de cliques maximums exponentiel en le nombre de sommets. Par conséquent, une grande partie de la théorie sur le problème de la clique est consacrée à l'identification de types particuliers de graphes qui admettent des algorithmes plus efficaces, ou à l'établissement de la difficulté algorithmique du problème général dans divers modèles de calcul.

Pour trouver une clique maximum, on peut inspecter tous les sous-ensembles du graphe, mais ce type de [[recherche exhaustive]] est trop long pour être utilisable dans des graphes comprenant plus de quelques dizaines de sommets. Bien qu'aucun algorithme de [[Complexité en temps|temps polynomial]] ne soit connu pour ce problème, des [[algorithme]]s plus efficaces que la recherche exhaustive sont connus. Par exemple, l'[[algorithme de Bron-Kerbosch]] peut être utilisé pour lister toutes les cliques maximums, [[Complexité dans le pire des cas|en temps optimal dans le pire cas]], et il est également possible de les lister en temps polynomial par clique.

== Histoire et applications ==
L'étude de sous-graphes complets en mathématiques est antérieure à la terminologie « clique ». Par exemple, les sous-graphes complets font une première apparition dans la littérature mathématique dans la reformulation de [[Théorie de Ramsey|la théorie de Ramsey]] du point de vue de la théorie des graphes par [[Paul Erdős|Erdős]] et [[George Szekeres|Szekeres]] (1935). Mais le terme {{citation|clique}} et le problème de lister les cliques de manière algorithmique proviennent tous deux des sciences sociales, où des sous-graphes complets sont utilisés pour modéliser des {{Lien|trad=Clique|fr=Clique (sociologie)|texte=cliques sociales}}, des groupes de personnes qui se connaissent toutes. En 1949, [[Robert Duncan Luce|Luce]] et [[Albert D. Perry|Perry]] ont utilisé des graphes pour modéliser les réseaux sociaux et ont adapté la terminologie des sciences sociales à la théorie des graphes. Ils ont été les premiers à appeler les sous-graphes complets {{citation|cliques}}. Le premier algorithme pour résoudre le problème de la clique est celui de Harary et Ross (1957)<ref name="bbpp">{{Référence Harvard|Bomze|Budinich|Pardalos|Pelillo|1999}}; {{Référence Harvard|Gutin|2004}}.</ref>, qui étaient motivés par les applications sociologiques. Les chercheurs en sciences sociales ont également défini divers autres types de cliques et de cliques maximales dans le cadre des réseaux sociaux, des {{citation|sous-groupes cohésifs}} de membres du réseau qui partagent tous l'un des différents types de relations. Beaucoup de ces notions généralisées de cliques peuvent également être retrouvées en construisant un graphe non orienté dont les arêtes représentent des paires liées de membres du réseau social, puis en appliquant à ce graphe un algorithme pour le problème de la clique{{Sfnp|Wasserman|Faust|1994}}.

Depuis les travaux de Harary et Ross, de nombreux autres ont conçu des algorithmes pour différentes versions du problème de la clique<ref name="bbpp"/>. Dans les années 1970, les chercheurs ont commencé à étudier ces algorithmes du point de vue de l'analyse du [[Complexité dans le pire des cas|pire cas]]. Par exemple, Tarjan et Trojanowski ont publié un premier travail sur la complexité du pire cas du problème de la clique maximum en 1977. Toujours dans les années 1970, en commençant par les travaux de Cook (1971) et Karp (1972), les chercheurs ont commencé à utiliser la théorie de la [[NP-complétude]] et notamment des résultats d'insolvabilité pour fournir une explication mathématique de la difficulté du problème de clique. Dans les années 1990, une série d'articles commençant par Feige et al. (1991) et rapportés dans ''[[The New York Times|le New York Times]]''{{Sfnp|Kolata|1990}} ont montré que (en supposant [[Problème P ≟ NP|P ≠ NP]]) il n'est même pas possible d'[[Algorithme d'approximation|approcher]] le problème avec précision et efficacité.

Des algorithmes de recherche de cliques ont été utilisés en [[chimie]], pour trouver des produits chimiques qui correspondent à une structure cible{{Sfnp|Rhodes|Willett|Calvet|Dunbar|2003}} et pour modéliser [[Amarrage (moléculaire)|l'ancrage moléculaire]] et les sites de liaison des réactions chimiques{{Sfnp|Kuhl|Crippen|Friesen|1983}}. Ils peuvent également être utilisés pour trouver des structures similaires dans différentes molécules{{Sfnp|National Research Council Committee on Mathematical Challenges from Computational Chemistry|1995}}. Dans ces applications, on forme un graphe dans lequel chaque sommet représente un couple d'atomes appariés, un de chacune des deux molécules{{Sfnp|Muegge|Rarey|2001}}. Deux sommets sont reliés par une arête si les paires qu'ils représentent sont compatibles entre elles. Être compatible peut signifier, par exemple, que les distances entre les atomes dans chacune des deux molécules sont approximativement égales, à une certaine tolérance donnée. Une clique dans ce graphique représente un ensemble de paires d'atomes compatibles les unes avec les autres. Un cas particulier de cette méthode est l'utilisation du produit modulaire de graphes afin de réduire le problème de trouver le sous-graphe induit commun maximum de deux graphes au problème de trouver une clique maximum dans leur produit{{Sfnp|Barrow|Burstall|1976}}.

Dans la génération automatique de modèles de test, la recherche de cliques peut aider à limiter la taille d'un ensemble de test{{Sfnp|Hamzaoglu|Patel|1998}}. En [[Bio-informatique|bioinformatique]], des algorithmes de recherche de clique ont été utilisés pour la génération d'[[Arbre phylogénétique|arbres d'évolutions]]{{Sfnp|Day|Sankoff|1986}}, [[Prédiction de la structure des protéines|la prédiction de structures protéiques]]{{Sfnp|Samudrala|Moult|1998}}, et pour trouver des groupes de protéines en interaction étroite{{Sfnp|Spirin|Mirny|2003}}. Lister les cliques d'un {{Lien|trad=Dependency graph|fr=graphe de dépendances}} est une étape importante dans l'analyse de certains processus aléatoires{{Sfnp|Frank|Strauss|1986}}. En mathématiques, [[Conjecture de Keller|la conjecture de Keller]] sur le pavage de l'espace euclidien par des [[Hypercube|hypercubes]] a été réfutée par Lagarias et Shor (1992), qui ont utilisé un algorithme de recherche de clique sur un graphe associé pour trouver un contre-exemple<ref>Le graphe que Keller utilisa pour {{Référence Harvard|Lagarias|Shor|1992}} a 1048576 sommets et un taille de clique de 1024. Ils décrivent une construction de clique, et utilise des algorithmes de recherche de cliques dans des graphes plus petits pour aider leur recherche. {{Référence Harvard|Mackey|2002}} a simplifié la preuve pour trouver une clique de taille 256 dans un graphe de Keller à 65536 sommets.</ref>.

== Cliques maximales et cliques maximums ==

Soit {{Math|§=''G''=(''V'',''E'')}} un [[graphe non orienté]], avec {{Mvar|V}} les sommets du graphe et {{Mvar|E}} les arêtes. Une [[Clique (théorie des graphes)|clique]] dans {{Mvar|G}} est un [[sous-graphe]] {{Math|§=''G'<nowiki/>''=(''V'<nowiki/>'',''E''')}} complet, ce qui signifie que tous les sommets dans {{Mvar|V'}} sont reliés entre eux. On distingue : 

* ''clique maximale'' : une clique de {{Mvar|G}} à laquelle on ne peut rajouter aucun sommet de {{Mvar|G}}, elle est maximale pour l'inclusion ;
* ''clique maximum'' : une clique de {{Mvar|G}} possédant le plus grand nombre de sommets, elle est donc maximale pour le cardinal.

Par conséquent, chaque clique est contenue dans une clique maximale{{Sfnp|Frank|Strauss|1986}}. Les cliques maximales peuvent être très petites. Un graphe peut contenir une clique non maximale avec de nombreux sommets et une autre clique d'ordre 2 qui est maximale. Alors qu'une clique maximum (c'est-à-dire la plus grande) est nécessairement maximale, l'inverse ne tient pas. Il existe certains types de graphes dans lesquels chaque clique maximale est maximum ; ce sont les [[Graphe complémentaire|complémentaires]] des [[Graphe bien couvert|graphes bien couverts]], dans lesquels chaque ensemble indépendant maximal est maximum{{Sfnp|Plummer|1993}}. Cependant, d'autres graphes ont des cliques maximales qui ne sont pas maximum.

Ces deux notions de cliques conduisent à définir différents problèmes algorithmiques qui seront définies dans la partie suivante.

== Algorithmes ==

=== Trouver une seule clique maximale ===
On peut trouver une clique maximale grâce à un [[algorithme glouton]] en [[Complexité en temps|temps linéaire]]{{Sfnp|Skiena|2009}}. En commençant par une clique arbitraire (par exemple, n'importe quel sommet unique ou même l'ensemble vide), augmentez la clique actuelle un sommet à la fois en faisant une boucle sur les sommets restants du graphe. Pour chaque sommet {{Mvar|v}} que cette boucle examine, ajoutez {{Mvar|v}} à la clique si {{Mvar|v}} est adjacent à chaque sommet qui est déjà dans la clique, et rejetez {{Mvar|v}} dans le cas contraire. En raison de la facilité de trouver des cliques maximales et de leur petite taille potentielle, plus d'attention a été accordée au problème algorithmique beaucoup plus difficile de trouver une clique maximum ou une plus grande qu'une taille donnée. Cependant, certaines recherches en [[Parallélisme (informatique)|algorithmique parallèle]] ont toutefois étudié le problème de la recherche d'une clique maximale. En particulier, le problème de la recherche de la première clique maximale [[Ordre lexicographique|lexicographique]] (celle trouvée par l'algorithme ci-dessus) s'est avéré [[Complet (complexité)|complet]] pour [[Fonction polynomiale|la classe des fonctions de temps polynomiales (FP)]]. Ce résultat implique qu'il est peu probable que le problème puisse être résolu dans la classe de complexité parallèle [[NC (complexité)|NC]]{{Sfnp|Cook|1985}}.

=== Cliques de taille fixée ===
On peut tester si un graphe {{Mvar|G}} contient une clique de taille k, et trouver une telle clique, en utilisant un [[Recherche exhaustive|algorithme de recherche exhaustive]]. Cet algorithme examine chaque sous-graphe avec {{Mvar|k}} sommets et vérifie s'il forme une clique. Cela s'effectue en temps <math>O(n^k k^2)</math>, tel qu'exprimé en utilisant la [[Comparaison asymptotique|notation O]]. En effet, il y a <math>O(n^k)</math> sous-graphes à vérifier, chacun d'entre eux ayant <math>O(k^2)</math> arêtes dont la présence dans le graphe {{Mvar|G}} doit être vérifiée. Ainsi, le problème peut être résolu en [[Complexité en temps|temps polynomial]] à condition que {{Mvar|k}} soit une constante fixe. Cependant, lorsque {{Mvar|k}} n'a pas de valeur fixe, et est une variable du problème, le temps est exponentiel{{Sfnp|Downey|Fellows|1995}}.

Le cas non trivial le plus simple du problème de recherche de clique est de trouver un triangle dans un graphe, ou de déterminer de manière équivalente si le graphe est sans [[Graphe sans triangle|triangle]]. Dans un graphe {{Mvar|G}} avec {{Mvar|m}} arêtes, il peut y avoir au plus {{Formule|Θ(''m''<sup>3/2</sup>)}} triangles (en utilisant la [[Comparaison asymptotique|notation grand thêta]] pour indiquer que cette borne est serrée). Le pire des cas pour cette formule se produit lorsque {{Mvar|G}} est lui-même une clique. Par conséquent, les algorithmes pour lister tous les triangles doivent prendre au moins {{Formule|Ω(''m''<sup>3/2</sup>)}} temps dans le pire des cas (en utilisant la [[Comparaison asymptotique|notation grand oméga]]), et des algorithmes sont connus qui correspondent à cette limite de temps{{Sfnp|Itai|Rodeh|1978}}. Par exemple, Chiba & Nishizeki (1985) décrivent un algorithme qui trie les sommets dans l'ordre du plus haut degré au plus bas, puis itère à travers chaque sommet {{Mvar|v}} de la liste triée, à la recherche de triangles qui incluent {{Mvar|v}} et n'incluent aucun sommet précédent dans le liste. Pour ce faire, l'algorithme marque tous les voisins de {{Mvar|v}}, recherche à travers tous les arêtes incidentes à un voisin de {{Mvar|v}}, produisant un triangle pour chaque arête qui a deux extrémités marquées, puis supprime les marques et supprime {{Mvar|v}} du graphe. Comme le montrent les auteurs, le temps de cet algorithme est proportionnel à l'[[arboricité]] du graphe (notée {{Formule|''a''(''G'')}} ) multipliée par le nombre d'arêtes, qui est <math>O(m\ a(G))</math>. L'arboricité étant au plus égale à <math>O(m^\frac{1}{2})</math>, cet algorithme s'exécute au temps <math>O(m^\frac{3}{2})</math>. Plus généralement, toutes les {{Mvar|k}} -cliques peuvent être listées par un algorithme similaire qui prend un temps proportionnel au nombre d'arêtes multiplié par l'arboricité à la puissance {{Formule|(''k''&nbsp;&minus;&nbsp;2)}}. Pour les graphes d'arboricité constante, tels que les graphes planaires (ou en général les graphes de toute [[Mineur (théorie des graphes)|famille de graphes mineurs fermés]] non triviale), cet algorithme prend un temps <math>O(m\ a(G))</math>, ce qui est optimal car il est linéaire dans la taille de l'entrée<ref name="CN85">{{Référence Harvard|Chiba|Nishizeki|1985}}</ref>.

Si l'on désire un seul triangle, ou l'assurance que le graphe est sans triangle, des algorithmes plus rapides sont possibles. Comme l'observe Itai & Rodeh (1978), le graphe contient un triangle si et seulement si sa [[matrice d'adjacence]] et le carré de sa matrice d'adjacence contiennent des entrées non nulles dans la même cellule. Par conséquent, des techniques de multiplication matricielle rapide telles que l'[[Algorithme de Coppersmith-Winograd|algorithme Coppersmith – Winograd]] peuvent être appliquées pour trouver des triangles dans le temps <math>O(n^{2.376})</math>. Alon, Yuster & Zwick (1994) ont utilisé la multiplication matricielle rapide pour améliorer l'algorithme en <math>O(m^\frac{3}{2})</math> pour trouver des triangles en <math>O(m^{1.41})</math>. Ces algorithmes basés sur la multiplication matricielle rapide ont également été étendus aux problèmes de recherche de {{Mvar|k}} -cliques pour des valeurs de {{Mvar|k}} plus grandes{{Sfnp|Eisenbrand|Grandoni|2004}}{{,}}{{Sfnp|Kloks|Kratsch|Müller|2000}}{{,}}{{Sfnp|Nešetřil|Poljak|1985}}{{,}}{{Sfnp|Vassilevska|Williams|2009}}{{,}}{{Sfnp|Yuster|2006}}.

=== Lister toutes les cliques maximales ===
D'après un résultat de Moon & Moser (1965), chaque graphe de taille <math>n</math> a au plus {{Formule|3<sup>''n''/3</sup>}} cliques maximales. Elles peuvent être listées par l'algorithme de Bron – Kerbosch, un algorithme de [[Retour sur trace|retour arrière]] créé par Bron & Kerbosch (1973). Le sous-programme récursif principal de cet algorithme a trois arguments: une clique partiellement construite (non maximale), un ensemble de sommets candidats qui pourraient être ajoutés à la clique, et un autre ensemble de sommets qui ne devraient pas être ajoutés (car cela conduirait à une clique déjà trouvée). L'algorithme essaie d'ajouter les sommets candidats un par un à la clique partielle, en effectuant un appel récursif pour chacun. Après avoir essayé chacun de ces sommets, il le déplace vers l'ensemble des sommets qui ne doivent plus être ajoutés. On peut montrer que des variantes de cet algorithme ont un temps d'exécution dans le pire des cas en <math>O(3^{n/3})</math>, correspondant au nombre de cliques qui pourraient avoir besoin d'être listées{{Sfnp|Tomita|Tanaka|Takahashi|2006}}. Par conséquent, cela fournit une solution optimale dans le pire des cas au problème de la liste de toutes les cliques maximales. De plus, l'algorithme de Bron – Kerbosch a été largement déclaré plus rapide en pratique que ses alternatives{{Sfnp|Eppstein|Löffler|Strash|2013}}.

Cependant, lorsque le nombre de cliques est significativement plus petit que celui du pire cas, d'autres algorithmes peuvent être préférables. Comme Tsukiyama et al. (1977) l'ont montré, il est également possible de lister toutes les cliques maximales dans un graphe dans un laps de temps qui est polynomial par clique générée. Un algorithme tel que le leur, dans lequel le temps d'exécution dépend de la taille de la sortie est appelé [[algorithme sensible à la sortie]]. Leur algorithme est basé sur les deux observations suivantes, reliant les cliques maximales du graphe {{Mvar|G}} de départ aux cliques maximales d'un graphe {{Formule|''G''&nbsp;\&nbsp;''v''}} formé en supprimant un sommet arbitraire {{Mvar|v}} de {{Mvar|G}} :

* Pour chaque clique maximale {{Mvar|K}} de {{Formule|''G''&nbsp;\&nbsp;''v''}}, soit {{Mvar|K}} continue de former une clique maximale dans {{Mvar|G}}, soit {{Formule|1=''K''&nbsp;⋃&nbsp;{''v''} }} forme une clique maximale dans {{Mvar|G}}. Par conséquent, {{Mvar|G}} a au moins autant de cliques maximales que {{Formule|''G''&nbsp;\&nbsp;''v''}}.
* Chaque clique maximale dans {{Mvar|G}} qui ne contient pas {{Mvar|v}} est une clique maximale dans {{Formule|''G''&nbsp;\&nbsp;''v''}}, et chaque clique maximale dans {{Mvar|G}} qui contient {{Mvar|v}} peut être formée à partir d'une clique maximale {{Mvar|K}} dans {{Formule|''G''&nbsp;\&nbsp;''v''}} en ajoutant {{Mvar|v}} et en supprimant les non-voisins de {{Mvar|v}} dans {{Mvar|K}}.

En utilisant ces observations, on peut générer toutes les cliques maximales dans {{Mvar|G}} par un algorithme récursif qui choisit {{Mvar|v}} puis, pour chaque clique maximale {{Mvar|K}} dans {{Formule|''G''&nbsp;\&nbsp;''v''}}, produit à la fois {{Mvar|K}} et la clique formée en ajoutant {{Mvar|v}} à {{Mvar|K}} et en supprimant les non-voisins de {{Mvar|v}}. Cependant, certaines cliques de {{Mvar|G}} peuvent être générées de cette manière à partir de plus d'une clique parente de {{Formule|''G''&nbsp;\&nbsp;''v''}}, donc ils éliminent les doublons en conservant une clique dans {{Mvar|G}} uniquement lorsque son parent dans {{Formule|''G''&nbsp;\&nbsp;''v''}} est le maximum lexicographique parmi toutes les cliques parentes possibles. Sur la base de ce principe, ils montrent que toutes les cliques maximales dans {{Mvar|G}} peuvent être générées en temps <math>O(mn)</math> par clique, où {{Mvar|m}} est le nombre d'arêtes dans {{Mvar|G}} et {{Mvar|n}} est le nombre de sommets. Chiba & Nishizeki (1985) l'améliorent à {{Formule|O(''ma'')}} par clique, où {{Mvar|a}} est l'arboricité du graphe donné. Makino & Uno (2004) proposent un algorithme alternatif sensible à la sortie basé sur une multiplication matricielle rapide. Johnson & Yannakakis (1988) montrent qu'il est même possible de lister toutes les cliques maximales dans l'[[ordre lexicographique]] avec un [[retard polynomial]] par clique. Cependant, le choix de l'ordre est important pour l'efficacité de cet algorithme: pour l'inverse de cet ordre, il n'y a pas d'algorithme à retard polynomial sauf si [[Problème P ≟ NP|P = NP]].

Sur la base de ce résultat, il est possible de lister toutes les cliques maximales en temps polynomial, pour des familles de graphes dans lesquelles le nombre de cliques est polynomialement borné. Ces familles comprennent les [[Graphe cordal|graphes cordaux]], [[Graphe complet|les graphes complets]], les graphes sans triangle, [[Graphe sans triangle|les graphes d'intervalles]], les graphes de {{Lien|trad=boxicity|fr=boxicité}} bornée et [[Graphe planaire|les graphes planaires]]{{Sfnp|Rosgen|Stewart|2007}}. En particulier, les graphes planaires ont <math>O(n)</math> cliques, de taille au plus constante, qui peuvent être listées en temps linéaire. Il en va de même pour toute famille de [[Densité d'un graphe|graphe clairsemés]] (ayant un nombre d'arêtes au plus constant multiplié par le nombre de sommets) [[Clôture (mathématiques)|fermée]] sous l'opération de prise de sous-graphes<ref name="CN85"/>{{,}}<ref name="ELS10"/>.

=== Rechercher une clique maximum ===
Il est possible de trouver une clique maximum, ou sa taille, d'un graphe arbitraire à ''n'' sommets dans le temps <math>O(3^{n/3})=O(1.4422^n)</math> en utilisant l'un des algorithmes décrits ci-dessus pour lister toutes les cliques maximales dans le graphe et celle de cardinal maximum. Cependant, pour cette variante du problème de clique, de meilleures limites de temps dans le pire des cas sont possibles. L'algorithme de Tarjan & Trojanowski (1977) résout ce problème en temps <math>O(2^{n/3})=O(1.2599^n)</math>. Il s'agit d'un algorithme de retour arrière récursif similaire à celui de l'[[algorithme de Bron-Kerbosch]], mais il est capable d'éliminer certains appels récursifs lorsqu'il peut être démontré que les cliques trouvées dans l'appel seront sous-optimales. Jian (1986) a amélioré le temps à <math>O(2^{0.304n})=O(1.2346^n)</math>, et Robson (1986) à <math>O(2^{0.276n})=O(1.2108^n)</math>, au détriment d'une plus grande complexité spatiale. L'algorithme de Robson combine un algorithme de retour arrière similaire (avec une analyse de cas plus compliquée) et une [[Programmation dynamique|technique de programmation dynamique]] dans laquelle la solution optimale est précalculée pour tous les petits sous-graphes connectés du [[graphe complémentaire]]. Ces solutions partielles sont utilisées pour raccourcir la longueur du retour arrière. L'algorithme le plus rapide connu aujourd'hui est une version raffinée de cette méthode par Robson (2001) qui s'exécute dans le temps <math>O(2^{0.249n})=O(1.1888^n)</math>{{Sfnp|Robson|2001}}.

Il y a également eu des recherches approfondies sur les [[Heuristique (mathématiques)|algorithmes heuristiques]] pour résoudre les problèmes de clique maximum sans garanties sur le temps d'exécution dans le pire cas, basées sur des méthodes comprenant la [[séparation et évaluation]]<ref>{{Référence Harvard|Balas|Yu|1986}}; {{Référence Harvard|Carraghan|Pardalos|1990}}; {{Référence Harvard|Pardalos|Rogers|1992}}; {{Référence Harvard|Östergård|2002}}; {{Référence Harvard|Fahle|2002}}; {{Référence Harvard|Tomita|Seki|2003}}; {{Référence Harvard|Tomita|Kameda|2007}}; {{Référence Harvard|Konc|Janežič|2007}}.</ref>, [[Recherche locale (optimisation)|la recherche locale]]<ref>{{Référence Harvard|Battiti|Protasi|2001}}; {{Référence Harvard|Katayama|Hamamoto|Narihisa|2005}}.</ref>, [[Algorithme glouton|les algorithmes gloutons]]<ref>{{Référence Harvard|Abello|Pardalos|Resende|1999}}; {{Référence Harvard|Grosso|Locatelli|Della Croce|2004}}.</ref>, et la [[programmation par contraintes]]{{Sfnp|Régin|2003}}. Les méthodologies de calcul non standards qui ont été suggérées pour trouver des cliques comprennent [[Ordinateur à ADN|le calcul ADN]] et le [[calcul quantique adiabatique]]{{Sfnp|Childs|Farhi|Goldstone|Gutmann|2002}}. Le problème de clique maximum a fait l'objet d'un défi de mise en œuvre parrainé par {{Lien|DIMACS}} en 1992–1993{{Sfnp|Johnson|Trick|1996}}, dont la collection de graphes utilisés comme points de repère pour le défi est accessible au public.

=== Familles spéciales de graphes ===
[[Fichier:Permutation_graph.svg|vignette| Dans ce [[graphe de permutation]], les cliques maximums correspondent aux [[Plus longue sous-suite strictement croissante|sous-suites décroissantes les plus longues]], (4,3,1) et (4,3,2) dans la permutation ici définie.]]
[[Graphe planaire|Les graphes planaires]], et d'autres familles de graphes clairsemés, ont été discutés ci-dessus: ils ont des cliques maximales linéairement nombreuses, de taille bornée, qui peuvent être listées en temps linéaire<ref name="CN85"/>. En particulier, pour les graphes planaires, toute clique peut avoir au plus quatre sommets, selon [[Théorème de Kuratowski|le théorème de Kuratowski]]<ref name="planar">{{Référence Harvard|Papadimitriou|Yannakakis|1981}}; {{Référence Harvard|Chiba|Nishizeki|1985}}.</ref>.

[[Graphe parfait|Les graphes parfaits]] sont définis comme étant les graphes qui vérifie la propriété d'avoir leur nombre de clique égal à leur [[Coloration de graphe|nombre chromatique]], et dont chaque [[Sous-graphe induit|sous-graphes induit]] vérifie aussi cette propriété. Pour des graphes parfaits, il est possible de trouver une clique maximum en temps polynomial, en utilisant un algorithme basé sur une [[Optimisation SDP|programmation semi-définie]]{{Sfnp|Grötschel|Lovász|Schrijver|1988}}. Cependant, cette méthode est complexe et non [[:wikt: combinatoire|combinatoire]], et des algorithmes de recherche de cliques spécialisés ont été développés pour de nombreuses sous-familles de graphes parfaits{{Sfnp|Golumbic|1980}}. Dans les [[Graphe complémentaire|graphes complémentaires]] des [[Graphe complémentaire|graphes]] [[Graphe biparti|bipartis]], [[Théorème de Kőnig (théorie des graphes)|le théorème de Kőnig]] permet de résoudre le problème de la clique maximum en utilisant des techniques de [[Couplage (théorie des graphes)|couplage]]. Dans une autre famille de graphes parfaits, les [[Graphe de permutation|graphes de permutation]], une clique maximum est une [[Plus longue sous-suite strictement croissante|sous-suite décroissante la plus longue]] de la permutation définissant le graphe et peut être trouvée en utilisant des algorithmes connus pour le problème de sous-suite décroissante la plus longue. Inversement, chaque instance du problème de sous-suite décroissante la plus longue peut être décrite de manière équivalente comme un problème de recherche d'une clique maximum dans un graphe de permutation. Even, Pnueli & Lempel (1972) fournissent un algorithme alternatif pour les cliques maximales dans [[Graphe de comparabilité|les graphes de comparabilité]], une famille plus large de graphes parfaits qui inclut les graphes de permutation<ref>{{Référence Harvard|Golumbic|1980}}, p. 159.</ref>. Cet algorithme s'exécute en temps quadratique{{Sfnp|Even|Pnueli|Lempel|1972}}. Dans [[Graphe cordal|les graphes cordaux]], les cliques maximales peuvent être trouvées en listant les sommets dans un ordre d'élimination, et en vérifiant les [[Voisinage (théorie des graphes)|voisinages]] de clique de chaque sommet dans cet ordre<ref>{{Référence Harvard|Blair|Peyton|1993}}, Lemme 4.5, p.&nbsp;19.</ref>.

Dans certains cas, ces algorithmes peuvent également être étendus à d'autres familles de graphes non parfaits. Par exemple, dans un [[Graphique circulaire|graphe circulaire]], le voisinage de chaque sommet est un graphe de permutation, donc une clique maximum dans un graphe circulaire peut être trouvée en appliquant l'algorithme de graphe de permutation à chaque voisinage<ref>{{Référence Harvard|Gavril|1973}}; {{Référence Harvard|Golumbic|1980}}, p. 247.</ref>. De même, dans un [[Graphe de disques|graphe de disque unitaire]] (avec une représentation géométrique connue), il existe un algorithme en temps polynomial pour les cliques maximums basé sur l'application de l'algorithme sur les complémentaires de graphes bipartis aux voisinages partagés par des paires de sommets{{Sfnp|Clark|Colbourn|Johnson|1990}}.

Le problème algorithmique de trouver une clique maximum dans un [[graphe aléatoire]] tiré du [[modèle Erdős – Rényi]] (dans lequel chaque arête apparaît avec une probabilité {{Formule|1/2}}, indépendamment des autres arêtes) a été suggéré par Karp (1976). Étant donné que la clique maximum dans un graphe aléatoire a une taille logarithmique avec une probabilité élevée, elle peut souvent être trouvée par une recherche par force brute dans le temps <math>2^{O(log^2(n))}</math>. Il s'agit d'une [[Complexité en temps|limite temporelle quasi polynomiale]]{{Sfnp|Song|2015}}. Bien que le nombre de cliques de ces graphes soit généralement très proche de {{Formule|2&nbsp;log<sub>2</sub>''n''}}, des [[Algorithme glouton|algorithmes gloutons]] simples ainsi que des techniques d'approximation aléatoire plus sophistiquées ne trouvent que des cliques de taille {{Formule|log<sub>2</sub>''n''}}, deux fois moins grandes. Le nombre de cliques maximales dans de tels graphes est avec une probabilité élevée exponentielle en {{Formule|log<sup>2</sup>''n''}}, ce qui empêche les méthodes qui répertorient toutes les cliques maximales de s'exécuter en temps polynomial{{Sfnp|Jerrum|1992}}. En raison de la difficulté de ce problème, plusieurs auteurs ont étudié le [[Clique plantée|problème de la clique plantée]], le problème de la clique sur des graphes aléatoires qui ont été augmentés en ajoutant de grandes cliques<ref>{{Référence Harvard|Arora|Barak|2009}}, Exemple 18.2, pp.&nbsp;362–363.</ref>. Alors que [[Théorie spectrale des graphes|les méthodes spectrales]]{{Sfnp|Alon|Krivelevich|Sudakov|1998}} et la [[Optimisation SDP|programmation semi-définie]]{{Sfnp|Feige|Krauthgamer|2000}} peuvent détecter les cliques cachées de taille <math>\Omega(\sqrt{n})</math>, aucun algorithme en temps polynomial n'est actuellement connu pour détecter celles de taille <math>o(\sqrt{n})</math> (exprimées en utilisant [[Comparaison asymptotique|la notation o]]){{Sfnp|Meka|Potechin|Wigderson|2015}}.

=== Algorithmes d'approximation ===
Plusieurs auteurs ont envisagé des [[Algorithme d'approximation|algorithmes d'approximation]] qui tentent de trouver une clique ou un ensemble indépendant qui, bien que non maximum, a une taille aussi proche du maximum que l'on peut trouver en temps polynomial. Bien qu'une grande partie de ce travail se soit concentrée sur des ensembles indépendants dans des graphes clairsemés, un cas qui n'a pas de sens pour le problème de la clique complémentaire, il y a également eu des travaux sur des algorithmes d'approximation pour des graphes non nécessairement clairsemés<ref>{{Référence Harvard|Boppana|Halldórsson|1992}}; {{Référence Harvard|Feige|2004}}; {{Référence Harvard|Halldórsson|2000}}.</ref>.

Feige (2004) décrit un algorithme en temps polynomial qui trouve une clique de taille {{Formule|Ω((log&nbsp;''n''/log&nbsp;log&nbsp;''n'')<sup>2</sup>)}} dans n'importe quel graphe contenant une clique de taille {{Formule|Ω(''n''/log<sup>''k''</sup>''n'')}} pour n'importe quelle constante <math>k</math>. En utilisant cet algorithme quand la taille de la clique maximum est entre {{Formule|''n''/log&nbsp;''n''}} et {{Formule|''n''/log<sup>3</sup>''n''}}, en utilisant un algorithme différent (de Boppana & Halldórsson (1992) ) pour les graphes dont les cliques maximums sont plus grandes, et en utilisant une 2-clique quand les deux algorithmes échouent, [[Uriel Feige|Feige]] fournit un algorithme d'approximation qui trouve une clique de taille proche du maximum à un facteur {{Formule|O(''n''(log&nbsp;log&nbsp;''n'')<sup>2</sup>/log<sup>3</sup>''n'')}}. Même si le [[Algorithme d'approximation|taux d'approximation]] de cet algorithme est faible, c'est le meilleur connu à ce jour<ref>{{Référence Harvard|Liu|Lu|Yang|Xiao|2015}}: {{citation|En termes de nombre de sommets d'un graphe, Feige propose le meilleur taux d'approximation connu à ce jour}}. Liu et al. écrivent à propos de {{citation|Ensemble indépendant maximum}}, qui est équivalent du point de vue de l'approximation</ref>. Les résultats portant sur la [[dureté d'approximation]] décrits ci-après suggèrent qu'il ne peut pas exister d'algorithme d'approximation de ratio significativement meilleur que linéaire.

== Limites théoriques ==

=== NP-complétude ===
[[Fichier:Sat_reduced_to_Clique_from_Sipser.svg|vignette| L'instance de satisfaction 3-FNC (x ∨ x ∨ y) ∧ (~ x ∨ ~ y ∨ ~ y) ∧ (~ x ∨ y ∨ y) réduite à une instance de Clique. Les sommets verts forment une 3-clique et correspondent à une affectation satisfaisante. ]]

Le [[problème de la décision]] de clique est [[Problème NP-complet|NP-complet]]. C'était l'un des [[21 problèmes NP-complets de Karp|21 problèmes originaux]] de [[Richard Karp]] montré NP-complet dans son article de 1972 {{citation|Réductibilité parmi les problèmes combinatoires}}. {{Sfnp|Karp|1972}} Ce problème a également été mentionné dans l'article de [[Stephen Cook]] présentant la théorie des problèmes NP-complets{{Sfnp|Cook|1971}}. En raison de la dureté du problème de décision, le problème de trouver une clique maximum est également NP-difficile. Si on pouvait le résoudre, on pourrait aussi résoudre le problème de décision, en comparant la taille de la clique maximum au paramètre de taille donné en entrée dans le problème de décision.

==== Démonstration de la NP-complétude ====

On passe en général par [[3-SAT]].

{{démonstration | titre=Réduction 3-SAT vers clique | contenu= 
Pour réduire le [[Problème SAT|problème 3-SAT]] vers celui de la [[Clique (théorie des graphes)|clique]], à chaque formule 3-CNF, on associe un [[graphe (théorie des graphes)|graphe]] non orienté dont le nombre de sommets est trois fois le nombre de [[clause de Horn|clauses]] de la manière suivante :

* à chacun des trois littéraux de chaque clause, on associe un sommet ;
* on relie les sommets par des arêtes de la manière suivante : deux sommets qui sont associés aux littéraux d'une même clause ne sont pas reliés par une arête, deux sommets qui sont associés à un littéral et sa négation ne sont pas reliés non plus, tous les autres couples de sommets sont reliés.

On démontre alors que la formule à <math>k</math> clauses est satisfiable si et seulement si le graphe a une clique d'ordre <math>k</math>.

Idée de la preuve :

Si la formule est satisfiable, il existe une assignation des variables pour laquelle la valeur d'au moins un littéral de chaque clause est VRAI. L'ensemble formé des sommets associés à l'un de ces littéraux par clause est une clique du graphe.

Si le graphe a une clique d'ordre <math>k</math>, elle contient exactement un sommet parmi les trois qui représentent les littéraux de chaque clause ; on peut définir une assignation des variables pour laquelle la valeur de ces littéraux est VRAI ; la valeur de la formule pour cette assignation est alors VRAI.
| déroulante=oui | style =  }}

Certains problèmes NP-complets (tels que le [[problème du voyageur de commerce]] dans [[Graphe planaire|les graphes planaires]] ) peuvent être résolus dans le temps qui est exponentiel en une fonction sous-linéaire du paramètre de taille d'entrée {{Mvar|n}}, significativement plus rapide qu'une recherche par force brute.{{Sfnp|Lipton|Tarjan|1980}} Cependant, il est peu probable qu'une telle limite temporelle sous-exponentielle soit possible pour le problème de clique dans des graphes arbitraires, car elle impliquerait des limites sous-exponentielles similaires pour de nombreux autres problèmes NP-complets standards. {{Sfnp|Impagliazzo|Paturi|Zane|2001}}

=== Complexité de circuit ===
[[File:Monotone circuit for 3-clique.svg|thumb|Un circuit monotone pour détecter une {{mvar|k}}-clique dans un graphe à {{mvar|n}}-sommets pour {{math|1=''k''&nbsp;=&nbsp;3}} et {{math|1=''n''&nbsp;=&nbsp;4}}. Chaque entrée dans ce circuit code l'absence ou la présence d'une arête précise (celle en rouge) sur le graphe. Le circuit utilise une porte logique et interne pour détecter chaque potentielle {{mvar|k}}-clique.]]
La complexité de résolution du problème de la clique a été utilisé pour trouver plusieurs bornes inférieures en [[:en:Circuit_complexity|complexité de circuit]]. L’existence d’une clique d’une taille donnée est une [[:en:Hereditary_property|propriété monotone de graphe]], ce qui signifie que s’il existe une clique dans un graphe, alors il existera dans tous les sur-graphes du premier graphe. La monotonie de la propriété implique qu’il existe un circuit monotone n’utilisant que des portes logiques [[Fonction OU|ou]] et [[Fonction ET|et]] permettant de résoudre le problème de décisions d’existence d’une clique de taille fixée. Cependant la taille de ces circuits est plus que polynomiale en la taille de la clique et en le nombre d’arêtes : il est exponentiel en la [[racine cubique]] du nombre d’arêtes{{Sfnp|Alon|Boppana|1987}}. Même si on autorise un petit nombre de portes [[Fonction NON|non]] la complexité reste plus que polynomiale{{Sfnp|Amano|Maruoka|2005}}. De plus la profondeur d’un circuit monotone résolvant le problème de la clique avec un nombre borné de [[fan-in]] doit être au moins polynomiale en la taille de la clique{{Sfnp|Goldmann|Håstad|1992}}.

=== Intraitabilité à paramètre fixé ===

[[Complexité paramétrée|La complexité paramétrée]] est l'[[Théorie de la complexité (informatique théorique)|étude théorique de]] la complexité de problèmes qui sont naturellement équipés d'un petit paramètre entier {{Mvar|k}} et pour lesquels le problème devient plus difficile à mesure que {{Mvar|k}} augmente, comme la recherche de {{Mvar|k}} -cliques dans les graphes. Un problème est dit traitable à paramètre fixé s'il existe un algorithme pour le résoudre sur des entrées de taille {{Mvar|n}}, et une fonction {{Mvar|f}}, telle que l'algorithme s'exécute au temps <math>f(k)n^{O(1)}</math><ref>{{Référence Harvard|Downey|Fellows|1999}}. Il y a une hypothèse technique supplémentaire qui demande que {{Mvar|f}} soit une [[Fonction calculable|computable function]].</ref>. Autrement dit, il est traitable à paramètre fixé s'il peut être résolu en temps polynomial pour toute valeur fixe de {{Mvar|k}} et de plus si l'exposant du polynôme ne dépend pas de {{Mvar|k}}.

Pour trouver des {{Mvar|k}}-cliques, l'algorithme de recherche par force brute a un temps d'exécution {{Formule|O(''n''<sup>''k''</sup>''k''<sup>2</sup>)}}. Comme l'exposant de {{Mvar|n}} dépend de {{Mvar|k}}, cet algorithme n'est pas traitable à paramètre fixe. Bien qu'il puisse être amélioré par une multiplication matricielle rapide, le temps d'exécution a toujours un exposant linéaire en {{Mvar|k}}. Ainsi, bien que le temps d'exécution des algorithmes connus pour le problème de clique soit polynomial pour tout {{Mvar|k}} fixe, ces algorithmes ne suffisent pas pour la traitabilité à paramètre fixé. Downey & Fellows (1995)<ref>{{Référence Harvard|Downey|Fellows|1995}}</ref> ont défini une hiérarchie de problèmes paramétrés, la hiérarchie W, dont ils ont supposé qu'elle n'avait pas d'algorithmes traitables à paramètres fixes. Ils ont prouvé que l'ensemble indépendant (ou, de manière équivalente, clique) est difficile pour le premier niveau de cette hiérarchie, [[Complexité paramétrée|W [1]]]. Ainsi, selon leur conjecture, la clique n'a pas d'algorithme traitable à paramètre fixe. De plus, ce résultat fournit la base des preuves de la dureté W [1] de nombreux autres problèmes, et sert ainsi d'analogue au [[Théorème de Cook|théorème de Cook-Levin]] pour la complexité paramétrée. {{Sfnp|Downey|Fellows|1995}}

Chen et al. (2006)<ref>{{Référence Harvard|Chen|Huang|Kanj|Xia|2006}}</ref> ont montré que trouver des k-cliques ne peut pas être fait en temps {{Formule|''n''<sup>''o''(''k'')</sup>}} sauf si l'[[hypothèse du temps exponentiel]] est invalide. Encore une fois, c'est un argument en faveur de l'intraitabilité à paramètre fixé.{{Sfnp|Chen|Huang|Kanj|Xia|2006}}

Bien que les problèmes d'énumération des cliques maximales ou de recherche de cliques maximums soient peu susceptibles d'être traitables à paramètre k fixé, ils peuvent être traitables à paramètre fixé pour d'autres paramètres de complexité d'instance. Par exemple, les deux problèmes sont connus pour être résolus à paramètre fixé lorsqu'ils sont paramétrés par la [[Dégénérescence (théorie des graphes)|dégénérescence]] du graphe d'entrée<ref name="ELS10">{{Référence Harvard|Eppstein|Löffler|Strash|2013}}</ref>.

=== Dureté d'approximation ===
[[File:Cube-face-intersection-graph.svg|thumb|Un graphe des relations de compatibilité pour des échantillons de 2 bits sur des preuves de 3 bits. Chaque clique maximale dans ce graphe représente toutes les manières d’échantillonner 3 bits. La preuve d'inaproximabilité du problème de la clique utilise des sous-graphes de graphes construits de même manière pour un plus grand nombre de bits.]]
De faibles résultats laissant à penser que le problème de la clique soit dur à approximer est connu depuis longtemps. Garey et Johnson en 1978{{Sfnp|Garey|Johnson|1978}} ont observé que parce que le nombre de petites cliques est NP-difficile à calculer il ne peut y avoir [[Schéma d'approximation en temps polynomial|un schéma d'approximation en temps polynomial]]. Si une approximation trop précise existait, arrondir le nombre obtenu par le schéma d'approximation à l'entier le plus proche donnerait le nombre précis de cliques.

Cependant, ce n'est qu'au début des années 1990 que d'autres résultats ont été prouvés lorsque des chercheuses et chercheurs ont fait le lien entre l'approximation du problème de la clique maximum et les [[Preuve vérifiable de manière probabiliste|preuves vérifiables de manière probabiliste]]. Elles et ils ont utilisé cette connexion pour montrer la dureté d'approximation du problème de la clique maximum{{Sfnp|Kolata|1990}}{{,}}{{Sfnp|Feige|Goldwasser|Lovász|Safra|1991}} {{Sfnp|Arora|Safra|1998}}{{,}}{{Sfnp|Arora|Lund|Motwani|Sudan|1998}}. Après de nombreuses améliorations, il est désormais connu que pour tout <math>\epsilon>0</math>, il ne peut exister un algorithme en temps polynomial approximant la clique maximum avec un meilleur facteur qu'un <math>O\left(n^{1-\epsilon}\right)</math> à moins que [[Problème P ≟ NP|P=NP]].

L'idée générale de ces résultats est que l'on peut créer un graphe représentant un système de preuves vérifiables de manière probabiliste pour un problème NP-complet comme le problème de satisfaisabilité booléenne. Dans un système de preuves vérifiables de manière probabiliste, une preuve est représentée par une séquence de bits. Une instance du problème de satisfaisabilité doit avoir une preuve valide si et seulement si l'instance est satisfaisable. La preuve est vérifiée et examinée par un algorithme qui, après un temps de calcul polynomial sur l'instance du problème, choisit d'examiner un petit nombre de positions aléatoirement choisies dans la chaine de caractère de la preuve. En fonction de la valeur trouvée sur cet échantillon de bits, l'algorithme acceptera ou non la preuve sans avoir à regarder les autres bits. Les faux négatifs ne sont pas autorisés : une preuve valide doit toujours être acceptée. Par contre, une preuve invalide peut parfois être acceptée. Cependant, pour chaque preuve invalide, la probabilité que l'algorithme l'accepte se doit d'être basse<ref name="inapprox-redux"/>.

Pour transformer un système de preuve vérifiable de manière probabiliste en une instance du problème de la clique, on forme un graphe avec comme sommets chaque portion de bits pouvant être choisie aléatoirement. Un sommet peut donc être représenté par une séquence de bits de la même taille que celle de la preuve avec des 0 ou des 1 sur les caractères examinés par l'algorithme et des $ pour les autres. Deux sommets sont reliés si les deux sommets ont les mêmes codes (0 ou 1) dans les positions que les deux examinent (i.e. là où il n'y a aucun $ dans les deux sommets). Chaque portion de preuve (valide ou invalide) correspond à une clique. Une de ces cliques est grande si et seulement si elle correspond à une portion de preuve que beaucoup d'algorithmes acceptent. Si l'instance originale du problème de satisfaisabilité est satisfaisable alors il aura une portion de preuve valide qui sera acceptée par tous les algorithmes et cette portion correspondra à la clique maximale dans le graphe. Au contraire, si ce n'est pas le cas alors toutes les portions de preuves sont invalides, et donc chaque portion de preuve sera acceptée par un très faible nombre d'algorithmes ce qui entraine le fait que toutes les cliques soient petites. C'est pourquoi, s'il existait un algorithme permettant de distinguer les graphes avec de grandes cliques et les graphes avec que des petites cliques, ou alors s'il existait un graphe approximant suffisamment bien le problème de la clique maximale, alors utiliser cet algorithme permettrait de distinguer en temps polynomial les instances satisfaisables et celles non satisfaisables, ce qui est impossible à moins que P=NP<ref name="inapprox-redux">La réduction est originellement due à {{Référence Harvard|Feige|Goldwasser|Lovász|Safra|1991}} et utilise  toutes les preuves d'inapproximation suivantes ; les preuves diffèrent dans les puissances et les détails des systèmes de preuves  probabilistes qu'elles utilisent.</ref>.
== Notes ==
{{Références}}

== Références ==

=== Ouvrages de synthèse et ouvrages généraux ===
{{refbegin|30em}}
*{{Ouvrage|titre=Computational Complexity: A Modern Approach |prénom1=Sanjeev |nom1=Arora |lien auteur1=Sanjeev Arora |prénom2=Boaz|nom2=Barak|éditeur=Cambridge University Press|année=2009|isbn= 978-0-521-42426-4}}.
*{{Ouvrage
 | nom1 = Blair | prénom1 = Jean R. S.
 | nom2 = Peyton | prénom2 = Barry
 | contribution = An introduction to chordal graphs and clique trees
 | doi = 10.1007/978-1-4613-8369-7_1
 | mr = 1320296
 | pages = 1–29
 | éditeur = Springer, New York
 | series = IMA Vol. Math. Appl.
 | titre = Graph theory and sparse matrix computation
 | volume = 56
 | année = 1993| url = https://digital.library.unt.edu/ark:/67531/metadc1319152/
 }}.
*{{Ouvrage|prénom1=I. M. |nom1=Bomze |prénom2=M. |nom2=Budinich |prénom3=P. M. |nom3=Pardalos |prénom4=M. |nom4=Pelillo |contribution=The maximum clique problem |titre=Handbook of Combinatorial Optimization |volume=4 |pages=1–74 |éditeur=Kluwer Academic Publishers |année=1999 |citeseerx=10.1.1.48.4074 }}.
*{{Ouvrage
 | nom1 = Cormen | prénom1 = Thomas H. | lien auteur1 = Thomas H. Cormen
 | nom2 = Leiserson | prénom2 = Charles E. | lien auteur2 = Charles E. Leiserson
 | nom3 = Rivest | prénom3 = Ronald L. | lien auteur3 = Ron Rivest
 | nom4 = Stein | prénom4 = Clifford | lien auteur4 = Clifford Stein
 | contribution = 34.5.1 The clique problem
 | edition = 2nd
 | isbn = 0-262-03293-7
 | passage = 1003–1006
 | éditeur = MIT Press and McGraw-Hill
 | titre = Introduction to Algorithms
 | année = 2001| lien titre = Introduction to Algorithms }}.
*{{Ouvrage |prénom1=R. G. |nom1=Downey |lien auteur2=Michael Fellows |prénom2=M. R. |nom2=Fellows |titre=Parameterized complexity | éditeur=[[Springer-Verlag]] | année=1999 |isbn = 0-387-94883-X}}.
*{{Ouvrage|prénom=M. C. |nom=Golumbic |lien auteur=Martin Charles Golumbic |titre=Algorithmic Graph Theory and Perfect Graphs |series=Computer Science and Applied Mathematics |éditeur=[[Academic Press]] |année=1980 |isbn=0-444-51530-5}}.
*{{Ouvrage |prénom1=M. |nom1=Grötschel | lien auteur1 = Martin Grötschel |prénom2=L. |nom2=Lovász |lien auteur2=László Lovász |prénom3=A. |nom3=Schrijver|lien auteur3=Alexander Schrijver |titre=Geometric Algorithms and Combinatorial Optimization |series=Algorithms and Combinatorics |volume=2 |éditeur=[[Springer-Verlag]] |année=1988 |contribution=9.4 Coloring Perfect Graphs |passage=296–298 |isbn=0-387-13624-X}}.
*{{Ouvrage |prénom=G. |nom=Gutin |contribution=5.3 Independent sets and cliques |titre=Handbook of graph theory |editor1-first=J. L. |editor1-last=Gross |editor2-first=J. |editor2-last=Yellen |éditeur=CRC Press |année=2004 |isbn=978-1-58488-090-5 |passage=389–402 |series=Discrete Mathematics & Its Applications}}.
*{{Ouvrage
 | nom1 = Muegge | prénom1 = Ingo
 | nom2 = Rarey | prénom2 = Matthias
 | doi = 10.1002/0471224413.ch1
 | isbn = 9780471398455
 | journal = Reviews in Computational Chemistry
 | pages = 1–60
 | titre = Small molecule docking and scoring
 | volume = 17
 | année = 2001}}.
*{{Ouvrage
 | auteur = National Research Council Committee on Mathematical Challenges from Computational Chemistry
 | doi = 10.17226/4886
 | isbn = 978-0-309-05097-5
 | éditeur = National Academies Press
 | titre = Mathematical Challenges from Theoretical/Computational Chemistry
 | année = 1995| url = https://digital.library.unt.edu/ark:/67531/metadc709300/
 }}.
*{{Ouvrage
 | nom = Pelillo | prénom = Marcello
 | contribution = Heuristics for maximum clique and independent set
 | doi = 10.1007/978-0-387-74759-0_264
 | passage = 1508–1520
 | éditeur = Springer
 | titre = Encyclopedia of Optimization
 | année = 2009}}.
*{{Ouvrage
 | nom = Plummer | prénom = Michael D. | lien auteur = Michael D. Plummer
 | issue = 3
 | journal = Quaestiones Mathematicae
 | mr = 1254158
 | pages = 253–287
 | titre = Well-covered graphs: a survey
 | url = http://handle.dtic.mil/100.2/ADA247861
 | volume = 16
 | année = 1993
 | doi=10.1080/16073606.1993.9631737}}.
*{{Ouvrage |prénom=M. |nom=Sipser |lien auteur=Michael Sipser |titre=Introduction to the Theory of Computation |éditeur=[[The Thomson Corporation|International Thompson Publishing]] |année=1996 |isbn=0-534-94728-X|lien titre=Introduction to the Theory of Computation }}.
*{{Ouvrage |titre=The Algorithm Design Manual|prénom=Steven S.|nom=Skiena|lien auteur=Steven Skiena|edition=2nd|éditeur=Springer|année=2009|isbn=978-1-84800-070-4}}.
*{{Ouvrage
 | nom = Valiente | prénom = Gabriel
 | titre = Chapter 6: Clique, Independent Set, and Vertex Cover
 | doi = 10.1007/978-3-662-04921-1_6
 | passage = 299–350
 | éditeur = Springer
 | titre ouvrage= Algorithms on Trees and Graphs
 | année = 2002}}.
*{{Ouvrage |titre=Social Network Analysis: Methods and Applications|volume=8|series=Structural Analysis in the Social Sciences|prénom1=Stanley|nom1=Wasserman|lien auteur1=Stanley Wasserman|prénom2=Katherine|nom2=Faust|éditeur=Cambridge University Press|année=1994|isbn=978-0-521-38707-1|page=276|url=https://books.google.com/books?id=CAm2DpIqRUIC&pg=PA276}}.
{{refend}}

=== Presse populaire ===
{{refbegin}}
*{{Ouvrage |titre=In a Frenzy, Math Enters Age of Electronic Mail |prénom=Gina |nom=Kolata |journal=[[The New York Times]] |url=https://www.nytimes.com/1990/06/26/science/in-a-frenzy-math-enters-age-of-electronic-mail.html |date=June 26, 1990}}.
{{refend}}

=== Articles de recherche ===
{{refbegin|30em}}
*{{Ouvrage |nom1=Abello |prénom1=J. |nom2=Pardalos |prénom2=P. M. |nom3=Resende |prénom3=M. G. C. |contribution=On maximum clique problems in very large graphs |titre=External Memory Algorithms |editor1-first=J. |editor1-last=Abello |editor2-first=J. |editor2-last=Vitter |editor2-link=Jeffrey Vitter |series=DIMACS Series on Discrete Mathematics and Theoretical Computer Science |volume=50 |pages=119–130 |année=1999 |éditeur=[[American Mathematical Society]] |contribution-url=http://www.mgvis.com/Papers/MassiveDataSets/Cliques.pdf |isbn=0-8218-1184-3}}.
*{{Article|prénom1=N. |nom1=Alon |lien auteur1=Noga Alon |prénom2=R. |nom2=Boppana |titre=The monotone circuit complexity of boolean functions |journal=[[Combinatorica]] |volume=7 |numéro=1 |année=1987 |pages=1–22 |doi=10.1007/BF02579196|s2cid=17397273 }}.
*{{Article |prénom1=N. |nom1=Alon |lien auteur1=Noga Alon |prénom2=M. |nom2=Krivelevich |prénom3=B. |nom3=Sudakov |titre=Finding a large hidden clique in a random graph |journal=Random Structures & Algorithms |volume=13 |numéro=3–4 |année=1998 |pages=457–466 |doi=10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO;2-W}}.
*{{Ouvrage | nom1 = Alon | prénom1 = N. | lien auteur1 = Noga Alon | nom2 = Yuster | prénom2 = R. | nom3 = Zwick | prénom3 = U. | lien auteur3 = Uri Zwick | contribution = Finding and counting given length cycles | pages = 354–364 | titre = Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands | année = 1994}}.
*{{Article
 | nom1 = Amano | prénom1 = Kazuyuki
 | nom2 = Maruoka | prénom2 = Akira
 | doi = 10.1137/S0097539701396959
 | numéro = 1
 | journal = [[SIAM Journal on Computing]]
 | mr = 2178806
 | pages = 201–216
 | titre = A superpolynomial lower bound for a circuit computing the clique function with at most {{math|(1/6)log log ''N''}} negation gates
 | volume = 35
 | année = 2005}}.
*{{Article |titre=Proof verification and the hardness of approximation problems |prénom1=Sanjeev |nom1=Arora |lien auteur1=Sanjeev Arora |prénom2=Carsten |nom2=Lund |lien auteur2=Carsten Lund |prénom3=Rajeev |nom3=Motwani |lien auteur3=Rajeev Motwani |prénom4=Madhu |nom4=Sudan |lien auteur4=Madhu Sudan |prénom5=Mario |nom5=Szegedy |lien auteur5=Mario Szegedy |journal=[[Journal of the ACM]] |volume=45 |numéro=3 |année=1998 |pages=501–555 |doi=10.1145/278298.278306 |s2cid=8561542 <!-- id={{ECCC|1998|98|008}}}}. -->| Originally presented at the 1992 [[Symposium on Foundations of Computer Science]], {{doi|10.1109/SFCS.1992.267823}}.}}
*{{Article |prénom1=S. |nom1=Arora |lien auteur1=Sanjeev Arora |prénom2=S. |nom2=Safra |lien auteur2=Shmuel Safra |titre=Probabilistic checking of proofs: A new characterization of NP |journal=[[Journal of the ACM]] |volume=45 |numéro=1 |année=1998 |pages=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}}.
*{{Article |nom1=Balas |prénom1=E. |nom2=Yu |prénom2=C. S. |titre=Finding a maximum clique in an arbitrary graph |journal=[[SIAM Journal on Computing]] |volume=15 |numéro=4 |année=1986 |pages=1054–1068 |doi=10.1137/0215075}}.
*{{Article
 | nom1 = Barrow | prénom1 = H.
 | nom2 = Burstall | prénom2 = R. | lien auteur2 = Rod Burstall
 | doi = 10.1016/0020-0190(76)90049-1
 | numéro = 4
 | journal = Information Processing Letters
 | pages = 83–84
 | titre = Subgraph isomorphism, matching relational structures and maximal cliques
 | volume = 4
 | année = 1976}}.
*{{Article |nom1=Battiti |prénom1=R. |nom2=Protasi |prénom2=M. |titre=Reactive local search for the maximum clique problem |journal=[[Algorithmica]] |volume=29 |numéro=4 |année=2001 |pages=610–637 |doi=10.1007/s004530010074|s2cid=1800512 }}.
*{{Article | nom1=Bollobás | prénom1=Béla | lien auteur1=Béla Bollobás | titre=Complete subgraphs are elusive | année=1976 | journal=[[Journal of Combinatorial Theory]] | series = Series B | issn=0095-8956 | volume=21 | numéro=1 | pages=1–7 | doi=10.1016/0095-8956(76)90021-6}}.
*{{Article |prénom1=R. |nom1=Boppana |prénom2=M. M. |nom2=Halldórsson |titre=Approximating maximum independent sets by excluding subgraphs |journal=[[BIT Numerical Mathematics]] |volume=32 |année=1992 |pages=180–196 |doi=10.1007/BF01994876 |numéro=2|s2cid=123335474 }}.
*{{Article | nom1=Bron | prénom1=C. | nom2=Kerbosch | prénom2=J. | titre=Algorithm 457: finding all cliques of an undirected graph | année=1973 | journal=[[Communications of the ACM]] | doi=10.1145/362342.362367 | volume=16 | numéro=9 | pages=575–577| s2cid=13886709 }}.
*{{Article |nom1=Carraghan |prénom1=R. |nom2=Pardalos |prénom2=P. M. |titre=An exact algorithm for the maximum clique problem |journal=Operations Research Letters |volume=9 |année=1990 |pages=375–382 |numéro=6 |doi=10.1016/0167-6377(90)90057-C}}.
*{{Article | nom1=Cazals | prénom1=F. | nom2=Karande | prénom2=C. | titre=A note on the problem of reporting maximal cliques | année=2008 | journal=[[Theoretical Computer Science]] | volume=407 | numéro=1 | pages=564–568 | doi=10.1016/j.tcs.2008.05.010 }}.
*{{Article |prénom1=Jianer | nom1=Chen |prénom2=Xiuzhen | nom2=Huang |prénom3=Iyad A. | nom3=Kanj |prénom4=Ge | nom4=Xia | titre=Strong computational lower bounds via parameterized complexity | journal=[[Journal of Computer and System Sciences]] | volume=72 | année=2006 | pages=1346–1367 | doi=10.1016/j.jcss.2006.04.007 | numéro=8}}
*{{Article |prénom1=N. |nom1=Chiba |prénom2=T. |nom2=Nishizeki | lien auteur2 = Takao Nishizeki |titre=Arboricity and subgraph listing algorithms |journal=[[SIAM Journal on Computing]] |volume=14 |numéro=1 |pages=210–223 |année=1985 |doi=10.1137/0214017}}.
*{{Article |nom1=Childs |prénom1=A. M. |nom2=Farhi |prénom2=E. |nom3=Goldstone |prénom3=J. |lien auteur3=Jeffrey Goldstone |nom4=Gutmann |prénom4=S. |titre=Finding cliques by quantum adiabatic evolution |journal=Quantum Information and Computation |volume=2 |numéro=3 |pages=181–191 |année=2002 |arxiv=quant-ph/0012104 |bibcode=2000quant.ph.12104C |doi=10.26421/QIC2.3 |s2cid=33643794 }}.
*{{Article |nom1=Childs |prénom1=A. M. |nom2=Eisenberg |prénom2=J. M. |titre=Quantum algorithms for subset finding |journal=Quantum Information and Computation |volume=5 |numéro=7 |pages=593–604 |année=2005 |arxiv=quant-ph/0311038|bibcode=2003quant.ph.11038C |doi=10.26421/QIC5.7 |s2cid=37556989 }}.
*{{Article | nom1 = Clark | prénom1 = Brent N. | nom2 = Colbourn | prénom2 = Charles J. | lien auteur2= Charles Colbourn | lien auteur3 = David S. Johnson | nom3 = Johnson | prénom3 = David S. | titre = Unit disk graphs | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]] | volume = 86 | numéro = 1–3 | année = 1990 | pages = 165–177 | doi = 10.1016/0012-365X(90)90358-O}}
*{{Ouvrage |prénom=S. A. |nom=Cook |lien auteur=Stephen Cook |année=1971 |titre=Proc. 3rd ACM Symposium on Theory of Computing |pages=151–158 |contribution-url=http://4mhz.de/cook.html |doi=10.1145/800157.805047 |contribution=The complexity of theorem-proving procedures|lien titre=Symposium on Theory of Computing |s2cid=7573663 }}.
*{{Article 
 | nom = Cook | prénom = Stephen A. | lien auteur = Stephen Cook
 | doi = 10.1016/S0019-9958(85)80041-3
 | numéro = 1–3
 | journal = [[Information and Control]]
 | mr = 837088
 | pages = 2–22
 | titre = A taxonomy of problems with fast parallel algorithms
 | volume = 64
 | année = 1985| accès doi = libre
 }}.
*{{Article |titre=Computational complexity of inferring phylogenies by compatibility |prénom1=William H. E. |nom1=Day |prénom2=David |nom2=Sankoff |journal=[[Systematic Zoology]] |volume=35 |numéro=2 |année=1986 |pages=224–229 |doi=10.2307/2413432 |jstor=2413432}}.
*{{Article |prénom1=R. G. |nom1=Downey |lien auteur2=Michael Fellows |prénom2=M. R. |nom2=Fellows |titre=Fixed-parameter tractability and completeness. II. On completeness for W[1] |journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] |volume=141 |numéro=1–2 |année=1995 |pages=109–131 |doi=10.1016/0304-3975(94)00097-3}}.
*{{Article |prénom1=F. |nom1=Eisenbrand |prénom2=F. |nom2=Grandoni |titre=On the complexity of fixed parameter clique and dominating set |journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] |volume=326 |numéro=1–3 |pages=57–67 |année=2004 |doi=10.1016/j.tcs.2004.05.009}}.
*{{Article |prénom1=David |nom1=Eppstein |lien auteur1=David Eppstein |prénom2=Maarten |nom2=Löffler |prénom3=Darren |nom3=Strash|titre= Listing all maximal cliques in large sparse real-world graphs in near-optimal time|année=2013|journal=Journal of Experimental Algorithmics|volume=18|numéro=3|page=3.1|doi=10.1145/2543629|arxiv=1103.0318|s2cid=47515491 }}.
*{{Article |prénom1=Paul |nom1=Erdős |lien auteur1=Paul Erdős |prénom2=George |nom2=Szekeres |lien auteur2=George Szekeres |titre=A combinatorial problem in geometry |journal=[[Compositio Mathematica]] |volume=2 |année=1935 |pages=463–470 |url=http://www.renyi.hu/~p_erdos/1935-01.pdf }}.
*{{Article |prénom1=S. |nom1=Even |lien auteur1=Shimon Even |prénom2=A. |nom2=Pnueli |lien auteur2=Amir Pnueli |prénom3=A. |nom3=Lempel |lien auteur3=Abraham Lempel |titre=Permutation graphs and transitive graphs |journal=[[Journal of the ACM]] |volume=19 |numéro=3 |pages=400–410 |année=1972 |doi=10.1145/321707.321710|s2cid=9501737 }}.
*{{Ouvrage|prénom=T. |nom=Fahle |titre=Proc. 10th European Symposium on Algorithms |series=Lecture Notes in Computer Science |éditeur=Springer-Verlag |volume=2461 |année=2002 |pages=47–86 |doi=10.1007/3-540-45749-6_44 |chapter=Simple and fast: Improving a branch-and-bound algorithm for maximum clique |isbn=978-3-540-44180-9|lien titre=European Symposium on Algorithms }}.
*{{Article |prénom=U. |nom=Feige |lien auteur=Uriel Feige |titre=Approximating maximum clique by removing subgraphs |journal=[[SIAM Journal on Discrete Mathematics]] |volume=18 |numéro=2 |pages=219–225 |année=2004 |doi=10.1137/S089548010240415X}}.
*{{Ouvrage |prénom1=U. |nom1=Feige |lien auteur1=Uriel Feige |prénom2=S. |nom2=Goldwasser |lien auteur2=Shafi Goldwasser |prénom3=L. |nom3=Lovász |lien auteur3=László Lovász |prénom4=S |nom4=Safra |lien auteur4=Shmuel Safra |prénom5=M. |nom5=Szegedy |lien auteur5=Mario Szegedy |titre=Proc. 32nd IEEE Symp. on Foundations of Computer Science |pages=2–12 |année=1991 |doi=10.1109/SFCS.1991.185341 |chapter=Approximating clique is almost NP-complete |isbn=0-8186-2445-0|lien titre=Symposium on Foundations of Computer Science |s2cid=46605913 }}.
*{{Article |prénom1=U. |nom1=Feige |lien auteur1=Uriel Feige |prénom2=R. |nom2=Krauthgamer |titre=Finding and certifying a large hidden clique in a semirandom graph |journal=Random Structures and Algorithms |volume=16 |numéro=2 |pages=195–208 |année=2000 |doi=10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A}}.
*{{Article 
 | nom1 = Frank | prénom1 = Ove
 | nom2 = Strauss | prénom2 = David
 | numéro = 395
 | journal = [[Journal of the American Statistical Association]]
 | mr = 860518
 | pages = 832–842
 | titre = Markov graphs
 | jstor = 2289017
 | volume = 81
 | année = 1986
 | doi=10.2307/2289017}}.
*{{Article |prénom1=M. R. |nom1=Garey |lien auteur1=Michael R. Garey |prénom2=D. S. |nom2=Johnson |lien auteur2=David S. Johnson |titre="Strong" NP-completeness results: motivation, examples and implications |journal=[[Journal of the ACM]] |volume=25 |pages=499–508 |année=1978 |doi=10.1145/322077.322090 |numéro=3|s2cid=18371269 }}.
* {{Ouvrage|langue=en|auteur1=Michael R. Garey|auteur2=David S. Johnson|titre=Computers and intractability|sous-titre=a guide to the theory of NP-completeness|volume=A1.2: GT19|lieu=New York|éditeur=W.H. Freeman|année=1979|pages totales=338|passage=194|isbn=0-7167-1045-5}}.
*{{Article
 | nom1 = Garey | prénom1 = M. R. | lien auteur1 = Michael R. Garey
 | nom2 = Johnson | prénom2 = D. S. | lien auteur2 = David S. Johnson
 | nom3 = Stockmeyer | prénom3 = L. | lien auteur3 = Larry Stockmeyer
 | doi = 10.1016/0304-3975(76)90059-1
 | numéro = 3
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | mr = 0411240
 | pages = 237–267
 | titre = Some simplified NP-complete graph problems
 | volume = 1
 | année = 1976}}.
*{{Article | nom = Gavril | prénom = F. | doi = 10.1002/net.3230030305 | numéro = 3 | journal = Networks | pages = 261–273 | titre = Algorithms for a maximum clique and a maximum independent set of a circle graph | volume = 3 | année = 1973}}.
*{{Article |prénom1=M. |nom1=Goldmann |prénom2=J. |nom2=Håstad |lien auteur2=Johan Håstad |titre=A simple lower bound for monotone clique using a communication game |journal=[[Information Processing Letters]] |volume=41 |numéro=4 |année=1992 |pages=221–226 |doi=10.1016/0020-0190(92)90184-W |citeseerx=10.1.1.185.3065 |url=http://www.csc.kth.se/%7Ejohanh/monotoneclique.pdf }}.
*{{Article | volume = 10 | numéro = 3 | pages = 119–127 | nom = Gröger | prénom = Hans Dietmar | titre = On the randomized complexity of monotone graph properties | journal = Acta Cybernetica | consulté le = 2009-10-02 | année = 1992 | url = http://www.inf.u-szeged.hu/actacybernetica/edb/vol10n3/pdf/Groger_1992_ActaCybernetica.pdf }}
*{{Article |prénom1=A. |nom1=Grosso |prénom2=M. |nom2=Locatelli |prénom3=F. |nom3=Della Croce |titre=Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem |journal=Journal of Heuristics |volume=10 |numéro=2 |année=2004 |pages=135–152 |doi=10.1023/B:HEUR.0000026264.51747.7f|s2cid=40764225 }}.
*{{Article |titre=Approximations of Weighted Independent Set and Hereditary Subset Problems |prénom=M. M. |nom=Halldórsson |journal=[[Journal of Graph Algorithms and Applications]] |volume=4 |numéro=1 |pages=1–16 |année=2000 |doi=10.7155/jgaa.00020|accès doi=libre }}.
*{{Ouvrage |nom1=Hamzaoglu |prénom1=I. |nom2=Patel |prénom2=J. H. |contribution=Test set compaction algorithms for combinational circuits |titre=Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design |année=1998 |pages=283–289 |doi=10.1145/288548.288615|s2cid=12258606 }}.
*{{Article |nom1=Harary |prénom1=F. |lien auteur1=Frank Harary |nom2=Ross |prénom2=I. C. |titre=A procedure for clique detection using the group matrix |journal=Sociometry |volume=20 |année=1957 |pages=205–215 |doi=10.2307/2785673 |numéro=3 |éditeur=American Sociological Association |mr=0110590 |jstor=2785673}}.
*{{Article|prénom=J. |nom=Håstad |lien auteur=Johan Håstad |titre=Clique is hard to approximate within {{math|''n''<sup>1 &minus; ''ε''</sup>}} |journal=[[Acta Mathematica]] |volume=182 |numéro=1 |pages=105–142 |année=1999 |doi=10.1007/BF02392825|accès doi=libre }}.
*{{Article |prénom1=R. |nom1=Impagliazzo |lien auteur1=Russell Impagliazzo |prénom2=R. |nom2=Paturi |prénom3=F. |nom3=Zane |titre=Which problems have strongly exponential complexity? |journal=[[Journal of Computer and System Sciences]] |volume=63 |numéro=4 |année=2001 |pages=512–530 |doi=10.1006/jcss.2001.1774}}.
*{{Article |prénom1=A. |nom1=Itai |prénom2=M. |nom2=Rodeh |titre=Finding a minimum circuit in a graph |journal=[[SIAM Journal on Computing]] |volume=7 |numéro=4 |pages=413–423 |année=1978 |doi=10.1137/0207033}}.
*{{Article |prénom=M. |nom=Jerrum |titre=Large cliques elude the Metropolis process |journal=Random Structures and Algorithms |volume=3 |pages=347–359 |année=1992 |doi=10.1002/rsa.3240030402 |numéro=4}}.
*{{Article | nom1=Jian | prénom1=T | titre=An {{math|O(2<sup>0.304''n''</sup>)}} algorithm for solving maximum independent set problem | éditeur=IEEE Computer Society | année=1986 | journal=[[IEEE Transactions on Computers]] | issn=0018-9340 | volume=35 | numéro=9 | pages=847–851 | doi=10.1109/TC.1986.1676847}}.
*{{Ouvrage |editor1-first=D. S. |editor1-last=Johnson |editor1-link=David S. Johnson |editor2-first=M. A. |editor2-last=Trick |editor2-link=Michael Trick |titre=Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993 |series=DIMACS Series in Discrete Mathematics and Theoretical Computer Science |volume=26 |éditeur=[[American Mathematical Society]] |url=http://dimacs.rutgers.edu/Volumes/Vol26.html |année=1996 |isbn=0-8218-6609-5 |auteur=<!-- this comment stops Citation bot adding incorrect info here--> }}.
*{{Article |prénom1=D. S. |nom1=Johnson |lien auteur1=David S. Johnson |prénom2=M. |nom2=Yannakakis |lien auteur2=Mihalis Yannakakis |titre=On generating all maximal independent sets |journal=[[Information Processing Letters]] |volume=27 |année=1988 |pages=119–123 |numéro=3 |doi=10.1016/0020-0190(88)90065-8}}.
*{{Ouvrage |nom=Karp |prénom=Richard M. |lien auteur=Richard M. Karp |url=http://www.cs.berkeley.edu/~luca/cs172/karp.pdf |contribution=Reducibility among combinatorial problems |titre=Complexity of Computer Computations |editor1-first=R. E. |editor1-last=Miller |editor2-first=J. W. |editor2-last=Thatcher |éditeur=[[Plenum Publishing Corporation|Plenum]] |lieu=New York |pages=85–103 |année=1972 }}.
*{{Ouvrage | nom=Karp |prénom=Richard M. |lien auteur=Richard M. Karp |contribution=Probabilistic analysis of some combinatorial search problems |titre=Algorithms and Complexity: New Directions and Recent Results |editor-first=J. F. |editor-last=Traub |éditeur=[[Academic Press]] |lieu=New York |année=1976 |pages=1–19}}.
*{{Article |prénom1=K. |nom1=Katayama |prénom2=A. |nom2=Hamamoto |prénom3=H. |nom3=Narihisa |titre=An effective local search for the maximum clique problem |journal=[[Information Processing Letters]] |volume=95 |numéro=5 |année=2005 |pages=503–511 |doi=10.1016/j.ipl.2005.05.010}}.
*{{Ouvrage |prénom=S. |nom=Khot |titre=Proc. 42nd IEEE Symp. Foundations of Computer Science |pages=600–609 |année=2001 |doi=10.1109/SFCS.2001.959936 |chapter=Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring |isbn=0-7695-1116-3|lien titre=Symposium on Foundations of Computer Science |s2cid=11987483 }}.
*{{Article |prénom1=T. |nom1=Kloks |prénom2=D. |nom2=Kratsch |prénom3=H. |nom3=Müller |titre=Finding and counting small induced subgraphs efficiently |journal=[[Information Processing Letters]] |volume=74 |numéro=3–4 |pages=115–121 |année=2000 |doi=10.1016/S0020-0190(00)00047-8}}.
*{{Article|prénom1=J. |nom1=Konc |prénom2=D. |nom2=Janežič |titre=An improved branch and bound algorithm for the maximum clique problem |journal=MATCH Communications in Mathematical and in Computer Chemistry |volume=58 |numéro=3 |pages=569–590 |année=2007 |url=http://insilab.org/articles/match2007.pdf }}. [http://insilab.org/maxclique Source code]
*{{Article |prénom1=F. S. |nom1=Kuhl |prénom2=G. M. |nom2=Crippen |prénom3=D. K. |nom3=Friesen |année=1983 |titre=A combinatorial algorithm for calculating ligand binding |journal=Journal of Computational Chemistry |doi=10.1002/jcc.540050105 |volume=5 |numéro=1 |pages=24–34}}.
*{{Article | nom1=Lagarias | prénom1=Jeffrey C. | lien auteur1=Jeffrey Lagarias | nom2=Shor |lien auteur2=Peter Shor| prénom2=Peter W. | titre=Keller's cube-tiling conjecture is false in high dimensions | doi=10.1090/S0273-0979-1992-00318-X | mr = 1155280 | année=1992 | journal=[[Bulletin of the American Mathematical Society]] | series = New Series | volume=27 | numéro=2 | pages=279–283| arxiv=math/9210222 | s2cid=6390600 }}.
*{{Article|nom1=Lipton |prénom1=R. J. |lien auteur1=Richard J. Lipton |nom2=Tarjan |prénom2=R. E. |lien auteur2=Robert Tarjan |titre=Applications of a planar separator theorem |journal=[[SIAM Journal on Computing]] |volume=9 |numéro=3 |pages=615–627 |année=1980 |doi=10.1137/0209046|s2cid=12961628 }}.
*{{Ouvrage
 | nom1 = Liu | prénom1 = Yu
 | nom2 = Lu | prénom2 = Jiaheng
 | nom3 = Yang | prénom3 = Hua
 | nom4 = Xiao | prénom4 = Xiaokui
 | nom5 = Wei | prénom5 = Zhewei
 | contribution = Towards maximum independent sets on massive graphs
 | année = 2015
 | doi = 10.14778/2831360.2831366
 | issue = 13
 | pages = 2122–2133
 | series = Proceedings of the VLDB Endowment
 | titre = Proceedings of the 41st International Conference on Very Large Data Bases (VLDB 2015)
 | volume = 8| hdl = 10138/157292
 | accès hdl = libre
 }}.
*{{Article | nom1 = Luce | prénom1 = R. Duncan | lien auteur1 = R. Duncan Luce | nom2 = Perry | prénom2 = Albert D. | titre = A method of matrix analysis of group structure | journal = Psychometrika | volume = 14 | numéro = 2 | année = 1949 | pages = 95–116 | doi = 10.1007/BF02289146 | pmid = 18152948| s2cid = 16186758 | hdl = 10.1007/BF02289146 | accès hdl = libre }}.
*{{Article | nom1=Mackey | prénom1=John | titre=A cube tiling of dimension eight with no facesharing | doi=10.1007/s00454-002-2801-9 | mr = 1920144 | année=2002 | journal=[[Discrete and Computational Geometry]] | volume=28 | numéro=2 | pages=275–279| accès doi=libre }}.
*{{Article | nom1 = Magniez | prénom1 = Frédéric | nom2 = Santha | prénom2 = Miklos | nom3 = Szegedy | prénom3 = Mario | lien auteur3 = Mario Szegedy | titre = Quantum algorithms for the triangle problem | année = 2007 | arxiv = quant-ph/0310134 | journal = [[SIAM Journal on Computing]] | volume = 37 | numéro = 2 | pages = 413–424 | doi = 10.1137/050643684| s2cid = 594494 }}.
*{{Ouvrage |prénom=K. |nom1=Makino |prénom2=T. |nom2=Uno |contribution=New algorithms for enumerating all maximal cliques |titre=Algorithm Theory: SWAT 2004 |series=Lecture Notes in Computer Science |éditeur=[[Springer-Verlag]] |volume=3111 |année=2004 |pages=260–272 |doi=10.1007/978-3-540-27810-8_23 |citeseerx=10.1.1.138.705 |url=http://research.nii.ac.jp/~uno/papers/04swat.pdf }}.
*{{Ouvrage
 | nom1 = Meka | prénom1 = Raghu
 | nom2 = Potechin | prénom2 = Aaron
 | nom3 = Wigderson | prénom3 = Avi | lien auteur3 = Avi Wigderson
 | arxiv = 1503.06447
 | contribution = Sum-of-squares lower bounds for planted clique
 | doi = 10.1145/2746539.2746600
 | isbn = 978-1-4503-3536-2
 | lieu = New York, NY, USA
 | pages = 87–96
 | éditeur = ACM
 | titre = Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC '15)
 | année = 2015| s2cid = 2754095
 }}.
*{{Article | nom1 = Moon | prénom1 = J. W. | lien auteur2 = Leo Moser | nom2 = Moser | prénom2 = L. | titre = On cliques in graphs | journal = [[Israel Journal of Mathematics]] | volume = 3 | année = 1965 | pages = 23–28 | mr = 0182577 | doi = 10.1007/BF02760024| s2cid = 9855414 }}.
*{{Article |lien auteur1=Jaroslav Nešetřil |prénom1=J. |nom1=Nešetřil |prénom2=S. |nom2=Poljak |titre=On the complexity of the subgraph problem |journal=Commentationes Mathematicae Universitatis Carolinae |volume=26 |numéro=2 |pages=415–419 |année=1985}}.
*{{Article |prénom=P. R. J. |nom=Östergård |titre=A fast algorithm for the maximum clique problem |journal=[[Discrete Applied Mathematics]] |volume=120 |numéro=1–3 |année=2002 |pages=197–207 |doi=10.1016/S0166-218X(01)00290-6}}.
*{{Article |nom1=Ouyang |prénom1=Q. |nom2=Kaplan |prénom2=P. D. |nom3=Liu |prénom3=S. |nom4=Libchaber |prénom4=A. |titre=DNA solution of the maximal clique problem |journal=[[Science (journal)|Science]] |volume=278 |numéro=5337 |pages=446–449 |pmid=9334300 |doi=10.1126/science.278.5337.446 |année=1997|bibcode=1997Sci...278..446O }}.
*{{Article
 | nom1 = Papadimitriou | prénom1 = Christos H. | lien auteur1 = Christos Papadimitriou
 | nom2 = Yannakakis | prénom2 = Mihalis | lien auteur2 = Mihalis Yannakakis
 | doi = 10.1016/0020-0190(81)90041-7
 | numéro = 4–5
 | journal = [[Information Processing Letters]]
 | mr = 651460
 | pages = 131–133
 | titre = The clique problem for planar graphs
 | volume = 13
 | année = 1981}}.
*{{Article |nom1=Pardalos |prénom1=P. M. |nom2=Rogers |prénom2=G. P. |titre=A branch and bound algorithm for the maximum clique problem |journal=Computers & Operations Research |année=1992 |volume=19 |numéro=5 |pages=363–375 |doi=10.1016/0305-0548(92)90067-F}}.
*{{Article |prénom=A. A. |nom=Razborov |lien auteur=Alexander Razborov |titre=Lower bounds for the monotone complexity of some Boolean functions |langue=ru |journal=[[Proceedings of the USSR Academy of Sciences]] |volume=281 |année=1985 |pages=798–801 |postscript=. English translation in ''Sov. Math. Dokl.'' '''31''' (1985): 354–357}}.
*{{Ouvrage |prénom=J.-C. |nom=Régin |contribution=Using constraint programming to solve the maximum clique problem |titre=Proc. 9th Int. Conf. Principles and Practice of Constraint Programming – CP 2003 |année=2003 |doi=10.1007/978-3-540-45193-8_43 |series=Lecture Notes in Computer Science |éditeur=[[Springer-Verlag]] |volume=2833 |pages=634–648}}.
*{{Article |prénom1=Nicholas |nom1=Rhodes |prénom2=Peter |nom2=Willett |prénom3=Alain |nom3=Calvet |prénom4=James B. |nom4=Dunbar |prénom5=Christine |nom5=Humblet |journal=Journal of Chemical Information and Computer Sciences |volume=43 |numéro=2 |pages=443–448 |année=2003 |doi=10.1021/ci025605o |pmid=12653507 |titre=CLIP: similarity searching of 3D databases using clique detection}}.
*{{Article |prénom=J. M. |nom=Robson |titre=Algorithms for maximum independent sets |journal=Journal of Algorithms |volume=7 |année=1986 |pages=425–440 |numéro=3 |doi=10.1016/0196-6774(86)90032-5}}.
*{{Ouvrage | nom1=Robson | prénom1=J. M. | titre=Finding a maximum independent set in time ''{{math|''O''(2<sup>''n''/4</sup>)}}'' | année=2001 | url=http://www.labri.fr/perso/robson/mis/techrep.html }}.
*{{Article |nom1=Rosgen |prénom1=B |nom2=Stewart |prénom2=L |année=2007 |titre=Complexity results on graphs with few cliques |journal=Discrete Mathematics and Theoretical Computer Science |volume=9 |numéro=1 |pages=127–136 |url=https://hal.inria.fr/hal-00966509 }}.
*{{Article |prénom1=Ram |nom1=Samudrala |prénom2=John |nom2=Moult |titre=A graph-theoretic algorithm for comparative modeling of protein structure |journal=Journal of Molecular Biology |volume=279 |numéro=1 |année=1998 |pages=287–302 |doi=10.1006/jmbi.1998.1689 |pmid=9636717}}.
*{{Article
 | nom1 = Sethuraman | prénom1 = Samyukta
 | nom2 = Butenko | prénom2 = Sergiy
 | doi = 10.1007/s10287-013-0197-z
 | numéro = 1
 | journal = Computational Management Science
 | mr = 3296231
 | pages = 197–218
 | titre = The maximum ratio clique problem
 | volume = 12
 | année = 2015| s2cid = 46153055
 }}.
* {{Article |prénom1=O. |nom1=Shmueli |titre=Nondeterminism and the clique problem |périodique=Information and Computation |volume=303 |numéro article =105260 
|date=2025
|doi=10.1016/j.ic.2024.105260}}
*{{Article |prénom1=Y. |nom1=Song |titre=On the independent set problem in random graphs |journal=International Journal of Computer Mathematics |volume=92 |numéro=11 |année=2015 |pages=2233–2242 |doi=10.1080/00207160.2014.976210 |s2cid=6713201 |url=https://zenodo.org/record/896067 }}.
*{{Article |prénom1=Victor |nom1=Spirin |prénom2=Leonid A. |nom2=Mirny |titre=Protein complexes and functional modules in molecular networks |journal=[[Proceedings of the National Academy of Sciences]] |volume=100 |numéro=21 |pages=12123–12128 |doi=10.1073/pnas.2032324100 |année=2003 |pmid=14517352 |pmc=218723|bibcode=2003PNAS..10012123S }}.
*{{Article |prénom1=R. E. |nom1=Tarjan |lien auteur1=Robert Tarjan |prénom2=A. E. |nom2=Trojanowski |titre=Finding a maximum independent set |journal=[[SIAM Journal on Computing]] |volume=6 |année=1977 |pages=537–546 |url=http://i.stanford.edu/pub/cstr/reports/cs/tr/76/550/CS-TR-76-550.pdf |doi=10.1137/0206038 |numéro=3 }}.
*{{Article |prénom1=E. |nom1=Tomita |prénom2=T. |nom2=Kameda |titre=An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments |journal=Journal of Global Optimization |volume=37 |numéro=1 |année=2007 |pages=95–111 |doi=10.1007/s10898-006-9039-7|s2cid=21436014 }}.
*{{Ouvrage |prénom1=E. |nom1=Tomita |prénom2=T. |nom2=Seki |titre=Discrete Mathematics and Theoretical Computer Science |series=Lecture Notes in Computer Science |éditeur=Springer-Verlag |volume=2731 |année=2003 |pages=[https://archive.org/details/discretemathemat0000dmtc/page/278 278–289] |doi=10.1007/3-540-45066-1_22 |chapter=An efficient branch-and-bound algorithm for finding a maximum clique |isbn=978-3-540-40505-4 |chapter-url=https://archive.org/details/discretemathemat0000dmtc/page/278 }}.
*{{Article |prénom1=E. |nom1=Tomita |prénom2=A. |nom2=Tanaka |prénom3=H. |nom3=Takahashi |titre=The worst-case time complexity for generating all maximal cliques and computational experiments |journal=[[Theoretical Computer Science]] |volume=363 |numéro=1 |pages=28–42 |année=2006 |doi=10.1016/j.tcs.2006.06.015}}.
*{{Article |prénom1=S. |nom1=Tsukiyama |prénom2=M. |nom2=Ide |prénom3=I. |nom3=Ariyoshi |prénom4=I. |nom4=Shirakawa |titre=A new algorithm for generating all the maximal independent sets |journal=[[SIAM Journal on Computing]] |volume=6 |année=1977 |pages=505–517 |doi=10.1137/0206036 |numéro=3}}.
*{{Ouvrage |nom=Valiant |prénom=L. G. |titre=Proc. 15th ACM Symposium on Theory of Computing |année=1983 |pages=110–117 |doi=10.1145/800061.808739 |chapter=Exponential lower bounds for restricted monotone circuits |isbn=0-89791-099-0|lien titre=Symposium on Theory of Computing |s2cid=6326587 }}.
*{{Ouvrage |prénom1=V. |nom1=Vassilevska|lien auteur1= Virginia Vassilevska Williams |prénom2=R. |nom2=Williams |lien auteur2=Ryan Williams (computer scientist) |titre=Proc. 41st ACM Symposium on Theory of Computing |année=2009 |pages=455–464 |doi=10.1145/1536414.1536477 |chapter=Finding, minimizing, and counting weighted subgraphs |isbn=978-1-60558-506-2|citeseerx=10.1.1.156.345 |lien titre=Symposium on Theory of Computing|s2cid=224579}}.
*{{Article |nom=Wegener |prénom=I. |titre=On the complexity of branching programs and decision trees for clique functions |journal=[[Journal of the ACM]] |volume=35 |numéro=2 |pages=461–472 |année=1988 |doi=10.1145/42282.46161|s2cid=11967153 }}.
*{{Article |prénom=R. |nom=Yuster |titre=Finding and counting cliques and independent sets in ''r''-uniform hypergraphs |journal=[[Information Processing Letters]] |volume=99 |numéro=4 |pages=130–134 |année=2006 |doi=10.1016/j.ipl.2006.04.005}}.
*{{Ouvrage |prénom=D. |nom=Zuckerman |titre=Proc. 38th ACM Symp. Theory of Computing |pages=681–690 |année=2006 |doi=10.1145/1132516.1132612 <!-- |id={{ECCC|2005|05|100}} -->|chapter=Linear degree extractors and the inapproximability of max clique and chromatic number |isbn=1-59593-134-1|lien titre=Symposium on Theory of Computing |s2cid=5713815 }}.
{{refend}}

{{Palette 21 problèmes NP-complets de Karp}}
{{Portail|informatique théorique}}

[[Catégorie:Problème NP-complet]]