Problème de la clique

En informatique, le problème de la clique est un problème algorithmique qui consiste à trouver des cliques (sous-ensembles de sommets tous adjacents deux à deux, également appelés sous-graphes complets) dans un 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 NP-complet — c'est l'un des 21 problèmes NP-complets de Karp. Le problème de trouver une $k$ -clique est à la fois intraitable à paramètre fixé (il n'est pas dans la classe de problèmes FPT) et est difficile à approcher (en). Lister toutes les cliques maximums peut nécessiter un 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 temps polynomial ne soit connu pour ce problème, des algorithmes plus efficaces que la recherche exhaustive sont connus. Par exemple, l'algorithme de Bron-Kerbosch peut être utilisé pour lister toutes les cliques maximums, 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 la théorie de Ramsey du point de vue de la théorie des graphes par Erdős et Szekeres (1935). Mais le terme « 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 cliques sociales (en), des groupes de personnes qui se connaissent toutes. En 1949, Luce et 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 « cliques ». Le premier algorithme pour résoudre le problème de la clique est celui de Harary et Ross (1957)^[1], 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 « 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^[2].

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^[1]. Dans les années 1970, les chercheurs ont commencé à étudier ces algorithmes du point de vue de l'analyse du 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 le New York Times^[3] ont montré que (en supposant P ≠ NP) il n'est même pas possible d'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^[4] et pour modéliser l'ancrage moléculaire et les sites de liaison des réactions chimiques^[5]. Ils peuvent également être utilisés pour trouver des structures similaires dans différentes molécules^[6]. 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^[7]. 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^[8].

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^[9]. En bioinformatique, des algorithmes de recherche de clique ont été utilisés pour la génération d'arbres d'évolutions^[10], la prédiction de structures protéiques^[11], et pour trouver des groupes de protéines en interaction étroite^[12]. Lister les cliques d'un graphe de dépendances (en) est une étape importante dans l'analyse de certains processus aléatoires^[13]. En mathématiques, la conjecture de Keller sur le pavage de l'espace euclidien par des 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^[14].

Cliques maximales et cliques maximums

Soit $G =(V, E)$ un graphe non orienté, avec $V$ les sommets du graphe et $E$ les arêtes. Une clique dans $G$ est un sous-graphe $G' =(V', E')$ complet, ce qui signifie que tous les sommets dans $V'$ sont reliés entre eux. On distingue :

clique maximale : une clique de $G$ à laquelle on ne peut rajouter aucun sommet de $G$ , elle est maximale pour l'inclusion ;
clique maximum : une clique de $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^[13]. 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 complémentaires des graphes bien couverts, dans lesquels chaque ensemble indépendant maximal est maximum^[15]. 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 temps linéaire^[16]. 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 $v$ que cette boucle examine, ajoutez $v$ à la clique si $v$ est adjacent à chaque sommet qui est déjà dans la clique, et rejetez $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 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 lexicographique (celle trouvée par l'algorithme ci-dessus) s'est avéré complet pour 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^[17].

Cliques de taille fixée

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

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 triangle. Dans un graphe $G$ avec $m$ arêtes, il peut y avoir au plus $Θ(m 3/2)$ triangles (en utilisant la notation grand thêta pour indiquer que cette borne est serrée). Le pire des cas pour cette formule se produit lorsque $G$ est lui-même une clique. Par conséquent, les algorithmes pour lister tous les triangles doivent prendre au moins $Ω(m 3/2)$ temps dans le pire des cas (en utilisant la notation grand oméga), et des algorithmes sont connus qui correspondent à cette limite de temps^[19]. 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 $v$ de la liste triée, à la recherche de triangles qui incluent $v$ et n'incluent aucun sommet précédent dans le liste. Pour ce faire, l'algorithme marque tous les voisins de $v$ , recherche à travers tous les arêtes incidentes à un voisin de $v$ , produisant un triangle pour chaque arête qui a deux extrémités marquées, puis supprime les marques et supprime $v$ du graphe. Comme le montrent les auteurs, le temps de cet algorithme est proportionnel à l'arboricité du graphe (notée $a (G)$ ) multipliée par le nombre d'arêtes, qui est $O(m\ a(G))$ . L'arboricité étant au plus égale à $O(m\ a(G))$ , cet algorithme s'exécute au temps $O(m^{\frac {3}{2}})$ . Plus généralement, toutes les $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 $(k - 2)$ . Pour les graphes d'arboricité constante, tels que les graphes planaires (ou en général les graphes de toute famille de graphes mineurs fermés non triviale), cet algorithme prend un temps $O(m\ a(G))$ , ce qui est optimal car il est linéaire dans la taille de l'entrée^[20].

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 Coppersmith – Winograd peuvent être appliquées pour trouver des triangles dans le temps $O(n^{2.376})$ . Alon, Yuster & Zwick (1994) ont utilisé la multiplication matricielle rapide pour améliorer l'algorithme en $O(m^{\frac {3}{2}})$ pour trouver des triangles en $O(m^{1.41})$ . Ces algorithmes basés sur la multiplication matricielle rapide ont également été étendus aux problèmes de recherche de $k$ -cliques pour des valeurs de $k$ plus grandes^[21]^,^[22]^,^[23]^,^[24]^,^[25].

Lister toutes les cliques maximales

D'après un résultat de Moon & Moser (1965), chaque graphe de taille $n$ a au plus $3 n /3$ cliques maximales. Elles peuvent être listées par l'algorithme de Bron – Kerbosch, un algorithme de 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 $O(3^{n/3})$ , correspondant au nombre de cliques qui pourraient avoir besoin d'être listées^[26]. 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^[27].

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 $G$ de départ aux cliques maximales d'un graphe $G \ v$ formé en supprimant un sommet arbitraire $v$ de $G$ :

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

En utilisant ces observations, on peut générer toutes les cliques maximales dans $G$ par un algorithme récursif qui choisit $v$ puis, pour chaque clique maximale $K$ dans $G \ v$ , produit à la fois $K$ et la clique formée en ajoutant $v$ à $K$ et en supprimant les non-voisins de $v$ . Cependant, certaines cliques de $G$ peuvent être générées de cette manière à partir de plus d'une clique parente de $G \ v$ , donc ils éliminent les doublons en conservant une clique dans $G$ uniquement lorsque son parent dans $G \ 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 $G$ peuvent être générées en temps $O(mn)$ par clique, où $m$ est le nombre d'arêtes dans $G$ et $n$ est le nombre de sommets. Chiba & Nishizeki (1985) l'améliorent à $O(ma)$ par clique, où $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 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 graphes cordaux, les graphes complets, les graphes sans triangle, les graphes d'intervalles, les graphes de boxicité (en) bornée et les graphes planaires^[28]. En particulier, les graphes planaires ont $O(n)$ 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 graphe clairsemés (ayant un nombre d'arêtes au plus constant multiplié par le nombre de sommets) fermée sous l'opération de prise de sous-graphes^[20]^,^[29].

Rechercher une clique maximum

Il est possible de trouver une clique maximum, ou sa taille, d'un graphe arbitraire à n sommets dans le temps $O(3^{n/3})=O(1.4422^{n})$ 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 $O(2^{n/3})=O(1.2599^{n})$ . 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 à $O(2^{0.304n})=O(1.2346^{n})$ , et Robson (1986) à $O(2^{0.276n})=O(1.2108^{n})$ , 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 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 récursivité de 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 $O(2^{0.249n})=O(1.1888^{n})$ ^[30].

Il y a également eu des recherches approfondies sur les 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^[31], la recherche locale^[32], les algorithmes gloutons^[33], et la programmation par contraintes^[34]. Les méthodologies de calcul non standards qui ont été suggérées pour trouver des cliques comprennent le calcul ADN et le calcul quantique adiabatique^[35]. Le problème de clique maximum a fait l'objet d'un défi de mise en œuvre parrainé par DIMACS (en) en 1992–1993^[36], 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

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^[20]. En particulier, pour les graphes planaires, toute clique peut avoir au plus quatre sommets, selon le théorème de Kuratowski^[37].

Les graphes parfaits sont définis comme étant les graphes qui vérifie la propriété d'avoir leur nombre de clique égal à leur nombre chromatique, et dont chaque 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 programmation semi-définie^[38]. Cependant, cette méthode est complexe et non combinatoire, et des algorithmes de recherche de cliques spécialisés ont été développés pour de nombreuses sous-familles de graphes parfaits^[39]. Dans les graphes complémentaires des graphes bipartis, le théorème de Kőnig permet de résoudre le problème de la clique maximum en utilisant des techniques de couplage. Dans une autre famille de graphes parfaits, les graphes de permutation, une clique maximum est une 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 les graphes de comparabilité, une famille plus large de graphes parfaits qui inclut les graphes de permutation^[40]. Cet algorithme s'exécute en temps quadratique^[41]. Dans les graphes cordaux, les cliques maximales peuvent être trouvées en listant les sommets dans un ordre d'élimination, et en vérifiant les voisinages de clique de chaque sommet dans cet ordre^[42].

Dans certains cas, ces algorithmes peuvent également être étendus à d'autres familles de graphes non parfaits. Par exemple, dans un 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^[43]. De même, dans un 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^[44].

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é $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 $2^{O(log^{2}(n))}$ . Il s'agit d'une limite temporelle quasi polynomiale^[45]. Bien que le nombre de cliques de ces graphes soit généralement très proche de $2 log 2 n$ , des algorithmes gloutons simples ainsi que des techniques d'approximation aléatoire plus sophistiquées ne trouvent que des cliques de taille $log 2 n$ , deux fois moins grandes. Le nombre de cliques maximales dans de tels graphes est avec une probabilité élevée exponentielle en $log 2 n$ , ce qui empêche les méthodes qui répertorient toutes les cliques maximales de s'exécuter en temps polynomial^[46]. En raison de la difficulté de ce problème, plusieurs auteurs ont étudié le 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^[47]. Alors que les méthodes spectrales^[48] et la programmation semi-définie^[49] peuvent détecter les cliques cachées de taille $\Omega ({\sqrt {n}})$ , aucun algorithme en temps polynomial n'est actuellement connu pour détecter celles de taille $o({\sqrt {n}})$ (exprimées en utilisant la notation o)^[50].

Algorithmes d'approximation

Plusieurs auteurs ont envisagé des 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^[51].

Feige (2004) décrit un algorithme en temps polynomial qui trouve une clique de taille $Ω((log n /log log n) 2)$ dans n'importe quel graphe contenant une clique de taille $Ω(n /log k n)$ pour n'importe quelle constante $k$ . En utilisant cet algorithme quand la taille de la clique maximum est entre $n /log n$ et $n /log 3 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, Feige fournit un algorithme d'approximation qui trouve une clique de taille proche du maximum à un facteur $O(n (log log n) 2 /log 3 n)$ . Même si le taux d'approximation de cet algorithme est faible, c'est le meilleur connu à ce jour^[52]. 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

Le problème de la décision de clique est NP-complet. C'était l'un des 21 problèmes originaux de Richard Karp montré NP-complet dans son article de 1972 « Réductibilité parmi les problèmes combinatoires ». ^[53] Ce problème a également été mentionné dans l'article de Stephen Cook présentant la théorie des problèmes NP-complets^[54]. 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.

Réduction 3-SAT vers clique

Pour réduire le problème 3-SAT vers celui de la clique, à chaque formule 3-CNF, on associe un graphe non orienté dont le nombre de sommets est trois fois le nombre de 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 à $k$ clauses est satisfiable si et seulement si le graphe a une clique d'ordre $k$ .

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 $k$ , 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.

Certains problèmes NP-complets (tels que le problème du voyageur de commerce dans 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 $n$ , significativement plus rapide qu'une recherche par force brute.^[55] 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. ^[56]

Complexité de circuit

La complexité de résolution du problème de la clique a été utilisé pour trouver plusieurs bornes inférieures en complexité de circuit. L’existence d’une clique d’une taille donnée est une 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 ou 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^[57]. Même si on autorise un petit nombre de portes non la complexité reste plus que polynomiale^[58]. 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^[59].

Intraitabilité à paramètre fixé

La complexité paramétrée est l'étude théorique de la complexité de problèmes qui sont naturellement équipés d'un petit paramètre entier $k$ et pour lesquels le problème devient plus difficile à mesure que $k$ augmente, comme la recherche de $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 $n$ , et une fonction $f$ , telle que l'algorithme s'exécute au temps $f(k)n^{O(1)}$ ^[60]. Autrement dit, il est traitable à paramètre fixé s'il peut être résolu en temps polynomial pour toute valeur fixe de $k$ et de plus si l'exposant du polynôme ne dépend pas de $k$ .

Pour trouver des $k$ -cliques, l'algorithme de recherche par force brute a un temps d'exécution $O(n k k 2)$ . Comme l'exposant de $n$ dépend de $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 $k$ . Ainsi, bien que le temps d'exécution des algorithmes connus pour le problème de clique soit polynomial pour tout $k$ fixe, ces algorithmes ne suffisent pas pour la traitabilité à paramètre fixé. Downey & Fellows (1995)^[61] 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, 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-Levin pour la complexité paramétrée. ^[18]

Chen et al. (2006)^[62] ont montré que trouver des k-cliques ne peut pas être fait en temps $n o (k)$ 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é.^[63]

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 du graphe d'entrée^[29].

Dureté d'approximation

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^[64] ont observé que parce que le nombre de petites cliques est NP-difficile à calculer il ne peut y avoir 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 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^[3]^,^[65] ^[66]^,^[67]. Après de nombreuses améliorations, il est désormais connu que pour tout $\epsilon >0$ , il ne peut exister un algorithme en temps polynomial approximant la clique maximum avec un meilleur facteur qu'un $O\left(n^{1-\epsilon }\right)$ à moins que 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^[68].

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^[68].

Notes

↑ ^{a et b} (Bomze et al. 1999); (Gutin 2004).
↑ Wasserman et Faust (1994).
↑ ^{a et b} Kolata (1990).
↑ Rhodes et al. (2003).
↑ Kuhl, Crippen et Friesen (1983).
↑ National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995).
↑ Muegge et Rarey (2001).
↑ Barrow et Burstall (1976).
↑ Hamzaoglu et Patel (1998).
↑ Day et Sankoff (1986).
↑ Samudrala et Moult (1998).
↑ Spirin et Mirny (2003).
↑ ^{a et b} Frank et Strauss (1986).
↑ Le graphe que Keller utilisa pour (Lagarias et 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. (Mackey 2002) a simplifié la preuve pour trouver une clique de taille 256 dans un graphe de Keller à 65536 sommets.
↑ Plummer (1993).
↑ Skiena (2009).
↑ Cook (1985).
↑ ^{a et b} Downey et Fellows (1995).
↑ Itai et Rodeh (1978).
↑ ^{a b et c} (Chiba et Nishizeki 1985)
↑ Eisenbrand et Grandoni (2004).
↑ Kloks, Kratsch et Müller (2000).
↑ Nešetřil et Poljak (1985).
↑ Vassilevska et Williams (2009).
↑ Yuster (2006).
↑ Tomita, Tanaka et Takahashi (2006).
↑ Eppstein, Löffler et Strash (2013).
↑ Rosgen et Stewart (2007).
↑ ^{a et b} (Eppstein, Löffler et Strash 2013)
↑ Robson (2001).
↑ (Balas et Yu 1986); (Carraghan et Pardalos 1990); (Pardalos et Rogers 1992); (Östergård 2002); (Fahle 2002); (Tomita et Seki 2003); (Tomita et Kameda 2007); (Konc et Janežič 2007).
↑ (Battiti et Protasi 2001); (Katayama, Hamamoto et Narihisa 2005).
↑ (Abello, Pardalos et Resende 1999); (Grosso, Locatelli et Della Croce 2004).
↑ Régin (2003).
↑ Childs et al. (2002).
↑ Johnson et Trick (1996).
↑ (Papadimitriou et Yannakakis 1981); (Chiba et Nishizeki 1985).
↑ Grötschel, Lovász et Schrijver (1988).
↑ Golumbic (1980).
↑ (Golumbic 1980), p. 159.
↑ Even, Pnueli et Lempel (1972).
↑ (Blair et Peyton 1993), Lemme 4.5, p. 19.
↑ (Gavril 1973); (Golumbic 1980), p. 247.
↑ Clark, Colbourn et Johnson (1990).
↑ Song (2015).
↑ Jerrum (1992).
↑ (Arora et Barak 2009), Exemple 18.2, pp. 362–363.
↑ Alon, Krivelevich et Sudakov (1998).
↑ Feige et Krauthgamer (2000).
↑ Meka, Potechin et Wigderson (2015).
↑ (Boppana et Halldórsson 1992); (Feige 2004); (Halldórsson 2000).
↑ (Liu et al. 2015): « 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 « Ensemble indépendant maximum », qui est équivalent du point de vue de l'approximation
↑ Karp (1972).
↑ Cook (1971).
↑ Lipton et Tarjan (1980).
↑ Impagliazzo, Paturi et Zane (2001).
↑ Alon et Boppana (1987).
↑ Amano et Maruoka (2005).
↑ Goldmann et Håstad (1992).
↑ (Downey et Fellows 1999). Il y a une hypothèse technique supplémentaire qui demande que $f$ soit une computable function.
↑ (Downey et Fellows 1995)
↑ (Chen et al. 2006)
↑ Chen et al. (2006).
↑ Garey et Johnson (1978).
↑ Feige et al. (1991).
↑ Arora et Safra (1998).
↑ Arora et al. (1998).
↑ ^{a et b} La réduction est originellement due à (Feige et al. 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.

Références

Ouvrages de synthèse et ouvrages généraux

Sanjeev Arora et Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009 (ISBN 978-0-521-42426-4).
Jean R. S. Blair et Barry Peyton, Graph theory and sparse matrix computation, vol. 56, Springer, New York, coll. « IMA Vol. Math. Appl. », 1993, 1–29 p. (DOI 10.1007/978-1-4613-8369-7_1, MR 1320296, lire en ligne).
I. M. Bomze, M. Budinich, P. M. Pardalos et M. Pelillo, Handbook of Combinatorial Optimization, vol. 4, Kluwer Academic Publishers, 1999, 1–74 p. (CiteSeer^x 10.1.1.48.4074).
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press and McGraw-Hill, 2001 (ISBN 0-262-03293-7), p. 1003–1006.
R. G. Downey et M. R. Fellows, Parameterized complexity, Springer-Verlag, 1999 (ISBN 0-387-94883-X).
M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, coll. « Computer Science and Applied Mathematics », 1980 (ISBN 0-444-51530-5).
M. Grötschel, L. Lovász et A. Schrijver, Geometric Algorithms and Combinatorial Optimization, vol. 2, Springer-Verlag, coll. « Algorithms and Combinatorics », 1988 (ISBN 0-387-13624-X), p. 296–298.
G. Gutin, Handbook of graph theory, CRC Press, coll. « Discrete Mathematics & Its Applications », 2004 (ISBN 978-1-58488-090-5), p. 389–402.
Ingo Muegge et Matthias Rarey, Small molecule docking and scoring, vol. 17, 2001, 1–60 p. (ISBN 9780471398455, DOI 10.1002/0471224413.ch1).
National Research Council Committee on Mathematical Challenges from Computational Chemistry, Mathematical Challenges from Theoretical/Computational Chemistry, National Academies Press, 1995 (ISBN 978-0-309-05097-5, DOI 10.17226/4886, lire en ligne).
Marcello Pelillo, Encyclopedia of Optimization, Springer, 2009 (DOI 10.1007/978-0-387-74759-0_264), p. 1508–1520.
Michael D. Plummer, Well-covered graphs: a survey, vol. 16, 1993, 253–287 p. (DOI 10.1080/16073606.1993.9631737, MR 1254158, lire en ligne).
M. Sipser, Introduction to the Theory of Computation, International Thompson Publishing, 1996 (ISBN 0-534-94728-X).
Steven S. Skiena, The Algorithm Design Manual, Springer, 2009 (ISBN 978-1-84800-070-4).
Gabriel Valiente, Chapter 6: Clique, Independent Set, and Vertex Cover, Springer, 2002 (DOI 10.1007/978-3-662-04921-1_6), p. 299–350.
Stanley Wasserman et Katherine Faust, Social Network Analysis: Methods and Applications, vol. 8, Cambridge University Press, coll. « Structural Analysis in the Social Sciences », 1994 (ISBN 978-0-521-38707-1, lire en ligne), p. 276.

Presse populaire

Gina Kolata, In a Frenzy, Math Enters Age of Electronic Mail, 26 juin 1990 (lire en ligne).

Articles de recherche

J. Abello, P. M. Pardalos et M. G. C. Resende, External Memory Algorithms, vol. 50, American Mathematical Society, coll. « DIMACS Series on Discrete Mathematics and Theoretical Computer Science », 1999, 119–130 p. (ISBN 0-8218-1184-3).
N. Alon et R. Boppana, The monotone circuit complexity of boolean functions, vol. 7, 1987, 1–22 p. (DOI 10.1007/BF02579196, S2CID 17397273).
N. Alon, M. Krivelevich et B. Sudakov, Finding a large hidden clique in a random graph, vol. 13, 1998, 457–466 p. (DOI 10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO;2-W).
N. Alon, R. Yuster et U. Zwick, Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands, 1994, 354–364 p..
Kazuyuki Amano et Akira Maruoka, A superpolynomial lower bound for a circuit computing the clique function with at most $(1/6)log log N$ negation gates, vol. 35, 2005, 201–216 p. (DOI 10.1137/S0097539701396959, MR 2178806).
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan et Mario Szegedy, Proof verification and the hardness of approximation problems, vol. 45, 1998, 501–555 p. (DOI 10.1145/278298.278306, S2CID 8561542)
S. Arora et S. Safra, Probabilistic checking of proofs: A new characterization of NP, vol. 45, 1998, 70–122 p. (DOI 10.1145/273865.273901, S2CID 751563). Originally presented at the 1992 Symposium on Foundations of Computer Science, DOI 10.1109/SFCS.1992.267824.
E. Balas et C. S. Yu, Finding a maximum clique in an arbitrary graph, vol. 15, 1986, 1054–1068 p. (DOI 10.1137/0215075).
H. Barrow et R. Burstall, Subgraph isomorphism, matching relational structures and maximal cliques, vol. 4, 1976, 83–84 p. (DOI 10.1016/0020-0190(76)90049-1).
R. Battiti et M. Protasi, Reactive local search for the maximum clique problem, vol. 29, 2001, 610–637 p. (DOI 10.1007/s004530010074, S2CID 1800512).
Béla Bollobás, Complete subgraphs are elusive, vol. 21, coll. « Series B », 1976, 1–7 p. (ISSN 0095-8956, DOI 10.1016/0095-8956(76)90021-6).
R. Boppana et M. M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, vol. 32, 1992, 180–196 p. (DOI 10.1007/BF01994876, S2CID 123335474).
C. Bron et J. Kerbosch, Algorithm 457: finding all cliques of an undirected graph, vol. 16, 1973, 575–577 p. (DOI 10.1145/362342.362367, S2CID 13886709).
R. Carraghan et P. M. Pardalos, An exact algorithm for the maximum clique problem, vol. 9, 1990, 375–382 p. (DOI 10.1016/0167-6377(90)90057-C).
F. Cazals et C. Karande, A note on the problem of reporting maximal cliques, vol. 407, 2008, 564–568 p. (DOI 10.1016/j.tcs.2008.05.010).
Jianer Chen, Xiuzhen Huang, Iyad A. Kanj et Ge Xia, Strong computational lower bounds via parameterized complexity, vol. 72, 2006, 1346–1367 p. (DOI 10.1016/j.jcss.2006.04.007)
N. Chiba et T. Nishizeki, Arboricity and subgraph listing algorithms, vol. 14, 1985, 210–223 p. (DOI 10.1137/0214017).
A. M. Childs, E. Farhi, J. Goldstone et S. Gutmann, Finding cliques by quantum adiabatic evolution, vol. 2, 2002, 181–191 p. (DOI 10.26421/QIC2.3, Bibcode 2000quant.ph.12104C, arXiv quant-ph/0012104, S2CID 33643794).
A. M. Childs et J. M. Eisenberg, Quantum algorithms for subset finding, vol. 5, 2005, 593–604 p. (DOI 10.26421/QIC5.7, Bibcode 2003quant.ph.11038C, arXiv quant-ph/0311038, S2CID 37556989).
Brent N. Clark, Charles J. Colbourn et David S. Johnson, Unit disk graphs, vol. 86, 1990, 165–177 p. (DOI 10.1016/0012-365X(90)90358-O)
S. A. Cook, Proc. 3rd ACM Symposium on Theory of Computing, 1971, 151–158 p. (DOI 10.1145/800157.805047, S2CID 7573663).
Stephen A. Cook, A taxonomy of problems with fast parallel algorithms, vol. 64, 1985, 2–22 p. (DOI 10.1016/S0019-9958(85)80041-3 , MR 837088).
William H. E. Day et David Sankoff, Computational complexity of inferring phylogenies by compatibility, vol. 35, 1986, 224–229 p. (DOI 10.2307/2413432, JSTOR 2413432).
R. G. Downey et M. R. Fellows, Fixed-parameter tractability and completeness. II. On completeness for W[1], vol. 141, 1995, 109–131 p. (DOI 10.1016/0304-3975(94)00097-3).
F. Eisenbrand et F. Grandoni, On the complexity of fixed parameter clique and dominating set, vol. 326, 2004, 57–67 p. (DOI 10.1016/j.tcs.2004.05.009).
David Eppstein, Maarten Löffler et Darren Strash, Listing all maximal cliques in large sparse real-world graphs in near-optimal time, vol. 18, 2013 (DOI 10.1145/2543629, arXiv 1103.0318, S2CID 47515491), p. 3.1.
Paul Erdős et George Szekeres, A combinatorial problem in geometry, vol. 2, 1935, 463–470 p. (lire en ligne).
S. Even, A. Pnueli et A. Lempel, Permutation graphs and transitive graphs, vol. 19, 1972, 400–410 p. (DOI 10.1145/321707.321710, S2CID 9501737).
T. Fahle, Proc. 10th European Symposium on Algorithms, vol. 2461, Springer-Verlag, coll. « Lecture Notes in Computer Science », 2002, 47–86 p. (ISBN 978-3-540-44180-9, DOI 10.1007/3-540-45749-6_44), « Simple and fast: Improving a branch-and-bound algorithm for maximum clique ».
U. Feige, Approximating maximum clique by removing subgraphs, vol. 18, 2004, 219–225 p. (DOI 10.1137/S089548010240415X).
U. Feige, S. Goldwasser, L. Lovász, S Safra et M. Szegedy, Proc. 32nd IEEE Symp. on Foundations of Computer Science, 1991, 2–12 p. (ISBN 0-8186-2445-0, DOI 10.1109/SFCS.1991.185341, S2CID 46605913), « Approximating clique is almost NP-complete ».
U. Feige et R. Krauthgamer, Finding and certifying a large hidden clique in a semirandom graph, vol. 16, 2000, 195–208 p. (DOI 10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A).
Ove Frank et David Strauss, Markov graphs, vol. 81, 1986, 832–842 p. (DOI 10.2307/2289017, JSTOR 2289017, MR 860518).
M. R. Garey et D. S. Johnson, "Strong" NP-completeness results: motivation, examples and implications, vol. 25, 1978, 499–508 p. (DOI 10.1145/322077.322090, S2CID 18371269).
(en) Michael R. Garey et David S. Johnson, Computers and intractability : a guide to the theory of NP-completeness, vol. A1.2: GT19, New York, W.H. Freeman, 1979, 338 p. (ISBN 0-7167-1045-5), p. 194.
M. R. Garey, D. S. Johnson et L. Stockmeyer, Some simplified NP-complete graph problems, vol. 1, 1976, 237–267 p. (DOI 10.1016/0304-3975(76)90059-1, MR 0411240).
F. Gavril, Algorithms for a maximum clique and a maximum independent set of a circle graph, vol. 3, 1973, 261–273 p. (DOI 10.1002/net.3230030305).
M. Goldmann et J. Håstad, A simple lower bound for monotone clique using a communication game, vol. 41, 1992, 221–226 p. (DOI 10.1016/0020-0190(92)90184-W, CiteSeer^x 10.1.1.185.3065, lire en ligne).
Hans Dietmar Gröger, On the randomized complexity of monotone graph properties, vol. 10, 1992, 119–127 p. (lire en ligne)
A. Grosso, M. Locatelli et F. Della Croce, Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem, vol. 10, 2004, 135–152 p. (DOI 10.1023/B:HEUR.0000026264.51747.7f, S2CID 40764225).
M. M. Halldórsson, Approximations of Weighted Independent Set and Hereditary Subset Problems, vol. 4, 2000, 1–16 p. (DOI 10.7155/jgaa.00020 ).
I. Hamzaoglu et J. H. Patel, Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design, 1998, 283–289 p. (DOI 10.1145/288548.288615, S2CID 12258606).
F. Harary et I. C. Ross, A procedure for clique detection using the group matrix, vol. 20, American Sociological Association, 1957, 205–215 p. (DOI 10.2307/2785673, JSTOR 2785673, MR 0110590).
J. Håstad, Clique is hard to approximate within $n 1 - ε$ , vol. 182,‎ 1999, 105–142 p. (DOI 10.1007/BF02392825 ).
R. Impagliazzo, R. Paturi et F. Zane, Which problems have strongly exponential complexity?, vol. 63, 2001, 512–530 p. (DOI 10.1006/jcss.2001.1774).
A. Itai et M. Rodeh, Finding a minimum circuit in a graph, vol. 7, 1978, 413–423 p. (DOI 10.1137/0207033).
M. Jerrum, Large cliques elude the Metropolis process, vol. 3, 1992, 347–359 p. (DOI 10.1002/rsa.3240030402).
T Jian, An $O(2 0.304 n)$ algorithm for solving maximum independent set problem, vol. 35, IEEE Computer Society, 1986, 847–851 p. (ISSN 0018-9340, DOI 10.1109/TC.1986.1676847).
Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993, vol. 26, American Mathematical Society, coll. « DIMACS Series in Discrete Mathematics and Theoretical Computer Science », 1996 (ISBN 0-8218-6609-5, lire en ligne).
D. S. Johnson et M. Yannakakis, On generating all maximal independent sets, vol. 27, 1988, 119–123 p. (DOI 10.1016/0020-0190(88)90065-8).
Richard M. Karp, Complexity of Computer Computations, New York, Plenum, 1972, 85–103 p. (lire en ligne).
Richard M. Karp, Algorithms and Complexity: New Directions and Recent Results, New York, Academic Press, 1976, 1–19 p..
K. Katayama, A. Hamamoto et H. Narihisa, An effective local search for the maximum clique problem, vol. 95, 2005, 503–511 p. (DOI 10.1016/j.ipl.2005.05.010).
S. Khot, Proc. 42nd IEEE Symp. Foundations of Computer Science, 2001, 600–609 p. (ISBN 0-7695-1116-3, DOI 10.1109/SFCS.2001.959936, S2CID 11987483), « Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring ».
T. Kloks, D. Kratsch et H. Müller, Finding and counting small induced subgraphs efficiently, vol. 74, 2000, 115–121 p. (DOI 10.1016/S0020-0190(00)00047-8).
J. Konc et D. Janežič, An improved branch and bound algorithm for the maximum clique problem, vol. 58, 2007, 569–590 p. (lire en ligne). Source code
F. S. Kuhl, G. M. Crippen et D. K. Friesen, A combinatorial algorithm for calculating ligand binding, vol. 5, 1983, 24–34 p. (DOI 10.1002/jcc.540050105).
Jeffrey C. Lagarias et Peter W. Shor, Keller's cube-tiling conjecture is false in high dimensions, vol. 27, coll. « New Series », 1992, 279–283 p. (DOI 10.1090/S0273-0979-1992-00318-X, MR 1155280, arXiv math/9210222, S2CID 6390600).
R. J. Lipton et R. E. Tarjan, Applications of a planar separator theorem, vol. 9, 1980, 615–627 p. (DOI 10.1137/0209046, S2CID 12961628).
Yu Liu, Jiaheng Lu, Hua Yang, Xiaokui Xiao et Zhewei Wei, Proceedings of the 41st International Conference on Very Large Data Bases (VLDB 2015), vol. 8, coll. « Proceedings of the VLDB Endowment », 2015, 2122–2133 p. (DOI 10.14778/2831360.2831366, hdl 10138/157292 ).
R. Duncan Luce et Albert D. Perry, A method of matrix analysis of group structure, vol. 14, 1949, 95–116 p. (PMID 18152948, DOI 10.1007/BF02289146, hdl 10.1007/BF02289146 , S2CID 16186758).
John Mackey, A cube tiling of dimension eight with no facesharing, vol. 28, 2002, 275–279 p. (DOI 10.1007/s00454-002-2801-9 , MR 1920144).
Frédéric Magniez, Miklos Santha et Mario Szegedy, Quantum algorithms for the triangle problem, vol. 37, 2007, 413–424 p. (DOI 10.1137/050643684, arXiv quant-ph/0310134, S2CID 594494).
K. Makino et T. Uno, Algorithm Theory: SWAT 2004, vol. 3111, Springer-Verlag, coll. « Lecture Notes in Computer Science », 2004, 260–272 p. (DOI 10.1007/978-3-540-27810-8_23, CiteSeer^x 10.1.1.138.705, lire en ligne).
Raghu Meka, Aaron Potechin et Avi Wigderson, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC '15), New York, NY, USA, ACM, 2015, 87–96 p. (ISBN 978-1-4503-3536-2, DOI 10.1145/2746539.2746600, arXiv 1503.06447, S2CID 2754095).
J. W. Moon et L. Moser, On cliques in graphs, vol. 3, 1965, 23–28 p. (DOI 10.1007/BF02760024, MR 0182577, S2CID 9855414).
J. Nešetřil et S. Poljak, On the complexity of the subgraph problem, vol. 26, 1985, 415–419 p..
P. R. J. Östergård, A fast algorithm for the maximum clique problem, vol. 120, 2002, 197–207 p. (DOI 10.1016/S0166-218X(01)00290-6).
Q. Ouyang, P. D. Kaplan, S. Liu et A. Libchaber, DNA solution of the maximal clique problem, vol. 278, 1997, 446–449 p. (PMID 9334300, DOI 10.1126/science.278.5337.446, Bibcode 1997Sci...278..446O).
Christos H. Papadimitriou et Mihalis Yannakakis, The clique problem for planar graphs, vol. 13, 1981, 131–133 p. (DOI 10.1016/0020-0190(81)90041-7, MR 651460).
P. M. Pardalos et G. P. Rogers, A branch and bound algorithm for the maximum clique problem, vol. 19, 1992, 363–375 p. (DOI 10.1016/0305-0548(92)90067-F).
(ru) A. A. Razborov, Lower bounds for the monotone complexity of some Boolean functions, vol. 281, 1985, 798–801 p..
J.-C. Régin, Proc. 9th Int. Conf. Principles and Practice of Constraint Programming – CP 2003, vol. 2833, Springer-Verlag, coll. « Lecture Notes in Computer Science », 2003, 634–648 p. (DOI 10.1007/978-3-540-45193-8_43).
Nicholas Rhodes, Peter Willett, Alain Calvet, James B. Dunbar et Christine Humblet, CLIP: similarity searching of 3D databases using clique detection, vol. 43, 2003, 443–448 p. (PMID 12653507, DOI 10.1021/ci025605o).
J. M. Robson, Algorithms for maximum independent sets, vol. 7, 1986, 425–440 p. (DOI 10.1016/0196-6774(86)90032-5).
J. M. Robson, Finding a maximum independent set in time O(2n/4), 2001 (lire en ligne).
B Rosgen et L Stewart, Complexity results on graphs with few cliques, vol. 9, 2007, 127–136 p. (lire en ligne).
Ram Samudrala et John Moult, A graph-theoretic algorithm for comparative modeling of protein structure, vol. 279, 1998, 287–302 p. (PMID 9636717, DOI 10.1006/jmbi.1998.1689).
Samyukta Sethuraman et Sergiy Butenko, The maximum ratio clique problem, vol. 12, 2015, 197–218 p. (DOI 10.1007/s10287-013-0197-z, MR 3296231, S2CID 46153055).
Y. Song, On the independent set problem in random graphs, vol. 92, 2015, 2233–2242 p. (DOI 10.1080/00207160.2014.976210, S2CID 6713201, lire en ligne).
Victor Spirin et Leonid A. Mirny, Protein complexes and functional modules in molecular networks, vol. 100, 2003, 12123–12128 p. (PMID 14517352, PMCID 218723, DOI 10.1073/pnas.2032324100, Bibcode 2003PNAS..10012123S).
R. E. Tarjan et A. E. Trojanowski, Finding a maximum independent set, vol. 6, 1977, 537–546 p. (DOI 10.1137/0206038, lire en ligne).
E. Tomita et T. Kameda, An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments, vol. 37, 2007, 95–111 p. (DOI 10.1007/s10898-006-9039-7, S2CID 21436014).
E. Tomita et T. Seki, Discrete Mathematics and Theoretical Computer Science, vol. 2731, Springer-Verlag, coll. « Lecture Notes in Computer Science », 2003, 278–289 (ISBN 978-3-540-40505-4, DOI 10.1007/3-540-45066-1_22), « An efficient branch-and-bound algorithm for finding a maximum clique ».
E. Tomita, A. Tanaka et H. Takahashi, The worst-case time complexity for generating all maximal cliques and computational experiments, vol. 363, 2006, 28–42 p. (DOI 10.1016/j.tcs.2006.06.015).
S. Tsukiyama, M. Ide, I. Ariyoshi et I. Shirakawa, A new algorithm for generating all the maximal independent sets, vol. 6, 1977, 505–517 p. (DOI 10.1137/0206036).
L. G. Valiant, Proc. 15th ACM Symposium on Theory of Computing, 1983, 110–117 p. (ISBN 0-89791-099-0, DOI 10.1145/800061.808739, S2CID 6326587), « Exponential lower bounds for restricted monotone circuits ».
V. Vassilevska et R. Williams, Proc. 41st ACM Symposium on Theory of Computing, 2009, 455–464 p. (ISBN 978-1-60558-506-2, DOI 10.1145/1536414.1536477, S2CID 224579, CiteSeer^x 10.1.1.156.345), « Finding, minimizing, and counting weighted subgraphs ».
I. Wegener, On the complexity of branching programs and decision trees for clique functions, vol. 35, 1988, 461–472 p. (DOI 10.1145/42282.46161, S2CID 11967153).
R. Yuster, Finding and counting cliques and independent sets in r-uniform hypergraphs, vol. 99, 2006, 130–134 p. (DOI 10.1016/j.ipl.2006.04.005).
D. Zuckerman, Proc. 38th ACM Symp. Theory of Computing, 2006, 681–690 p. (ISBN 1-59593-134-1, DOI 10.1145/1132516.1132612, S2CID 5713815), « Linear degree extractors and the inapproximability of max clique and chromatic number ».

Portail de l'informatique théorique

[bbpp-1] {a et b} (Bomze et al. 1999); (Gutin 2004).

[WassermanFaust1994-2] Wasserman et Faust (1994).

[Kolata1990-3] {a et b} Kolata (1990).

[RhodesWillettCalvetDunbar2003-4] Rhodes et al. (2003).

[KuhlCrippenFriesen1983-5] Kuhl, Crippen et Friesen (1983).

[National_Research_Council_Committee_on_Mathematical_Challenges_from_Computational_Chemistry1995-6] National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995).

[MueggeRarey2001-7] Muegge et Rarey (2001).

[BarrowBurstall1976-8] Barrow et Burstall (1976).

[HamzaogluPatel1998-9] Hamzaoglu et Patel (1998).

[DaySankoff1986-10] Day et Sankoff (1986).

[SamudralaMoult1998-11] Samudrala et Moult (1998).

[SpirinMirny2003-12] Spirin et Mirny (2003).

[FrankStrauss1986-13] {a et b} Frank et Strauss (1986).

[14] Le graphe que Keller utilisa pour (Lagarias et 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. (Mackey 2002) a simplifié la preuve pour trouver une clique de taille 256 dans un graphe de Keller à 65536 sommets.

[Plummer1993-15] Plummer (1993).

[Skiena2009-16] Skiena (2009).

[Cook1985-17] Cook (1985).

[DowneyFellows1995-18] {a et b} Downey et Fellows (1995).

[ItaiRodeh1978-19] Itai et Rodeh (1978).

[CN85-20] {a b et c} (Chiba et Nishizeki 1985)

[EisenbrandGrandoni2004-21] Eisenbrand et Grandoni (2004).

[KloksKratschMüller2000-22] Kloks, Kratsch et Müller (2000).

[NešetřilPoljak1985-23] Nešetřil et Poljak (1985).

[VassilevskaWilliams2009-24] Vassilevska et Williams (2009).

[Yuster2006-25] Yuster (2006).

[TomitaTanakaTakahashi2006-26] Tomita, Tanaka et Takahashi (2006).

[EppsteinLöfflerStrash2013-27] Eppstein, Löffler et Strash (2013).

[RosgenStewart2007-28] Rosgen et Stewart (2007).

[ELS10-29] {a et b} (Eppstein, Löffler et Strash 2013)

[Robson2001-30] Robson (2001).

[31] (Balas et Yu 1986); (Carraghan et Pardalos 1990); (Pardalos et Rogers 1992); (Östergård 2002); (Fahle 2002); (Tomita et Seki 2003); (Tomita et Kameda 2007); (Konc et Janežič 2007).

[32] (Battiti et Protasi 2001); (Katayama, Hamamoto et Narihisa 2005).

[33] (Abello, Pardalos et Resende 1999); (Grosso, Locatelli et Della Croce 2004).

[Régin2003-34] Régin (2003).

[ChildsFarhiGoldstoneGutmann2002-35] Childs et al. (2002).

[JohnsonTrick1996-36] Johnson et Trick (1996).

[planar-37] (Papadimitriou et Yannakakis 1981); (Chiba et Nishizeki 1985).

[GrötschelLovászSchrijver1988-38] Grötschel, Lovász et Schrijver (1988).

[Golumbic1980-39] Golumbic (1980).

[40] (Golumbic 1980), p. 159.

[EvenPnueliLempel1972-41] Even, Pnueli et Lempel (1972).

[42] (Blair et Peyton 1993), Lemme 4.5, p. 19.

[43] (Gavril 1973); (Golumbic 1980), p. 247.

[ClarkColbournJohnson1990-44] Clark, Colbourn et Johnson (1990).

[Song2015-45] Song (2015).

[Jerrum1992-46] Jerrum (1992).

[47] (Arora et Barak 2009), Exemple 18.2, pp. 362–363.

[AlonKrivelevichSudakov1998-48] Alon, Krivelevich et Sudakov (1998).

[FeigeKrauthgamer2000-49] Feige et Krauthgamer (2000).

[MekaPotechinWigderson2015-50] Meka, Potechin et Wigderson (2015).

[51] (Boppana et Halldórsson 1992); (Feige 2004); (Halldórsson 2000).

[52] (Liu et al. 2015): « 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 « Ensemble indépendant maximum », qui est équivalent du point de vue de l'approximation

[Karp1972-53] Karp (1972).

[Cook1971-54] Cook (1971).

[LiptonTarjan1980-55] Lipton et Tarjan (1980).

[ImpagliazzoPaturiZane2001-56] Impagliazzo, Paturi et Zane (2001).

[AlonBoppana1987-57] Alon et Boppana (1987).

[AmanoMaruoka2005-58] Amano et Maruoka (2005).

[GoldmannHåstad1992-59] Goldmann et Håstad (1992).

[60] (Downey et Fellows 1999). Il y a une hypothèse technique supplémentaire qui demande que $f$ soit une computable function.

[61] (Downey et Fellows 1995)

[62] (Chen et al. 2006)

[ChenHuangKanjXia2006-63] Chen et al. (2006).

[GareyJohnson1978-64] Garey et Johnson (1978).

[FeigeGoldwasserLovászSafra1991-65] Feige et al. (1991).

[AroraSafra1998-66] Arora et Safra (1998).

[AroraLundMotwaniSudan1998-67] Arora et al. (1998).

[inapprox-redux-68] {a et b} La réduction est originellement due à (Feige et al. 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

[57]

[58]

[59]

[60]

[61]

[62]

[63]

[64]

[65]

[66]

[67]

[68]