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.

Recherche exhaustive d'une 4-clique dans ce graphe à 7 sommets en testant la complétude des C(7,4)= 35 sous-graphes à 4 sommets.

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), 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.

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. 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 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 et pour modéliser l'ancrage moléculaire et les sites de liaison des réactions chimiques. Ils peuvent également être utilisés pour trouver des structures similaires dans différentes molécules. 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. 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.

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. En bioinformatique, des algorithmes de recherche de clique ont été utilisés pour la génération d'arbres d'évolutions, la prédiction de structures protéiques, et pour trouver des groupes de protéines en interaction étroite. Lister les cliques d'un graphe de dépendances (en) est une étape importante dans l'analyse de certains processus aléatoires. 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.

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. 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. 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. 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.

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.

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. 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.

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.

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. 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.

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. 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.

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})$.

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, la recherche locale, les algorithmes gloutons, et la programmation par contraintes. 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. 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, 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

Dans ce graphe de permutation, les cliques maximums correspondent aux sous-suites décroissantes les plus longues, (4,3,1) et (4,3,2) dans la permutation ici définie.

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

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. 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. 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. Cet algorithme s'exécute en temps quadratique. 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.

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. 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.

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. Bien que le nombre de cliques de ces graphes soit généralement très proche de 2 log₂n, des algorithmes gloutons simples ainsi que des techniques d'approximation aléatoire plus sophistiquées ne trouvent que des cliques de taille log₂n, deux fois moins grandes. Le nombre de cliques maximales dans de tels graphes est avec une probabilité élevée exponentielle en log²n, ce qui empêche les méthodes qui répertorient toutes les cliques maximales de s'exécuter en temps polynomial. 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. Alors que les méthodes spectrales et la programmation semi-définie 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).

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.

Feige (2004) décrit un algorithme en temps polynomial qui trouve une clique de taille Ω((log n/log log n)²) dans n'importe quel graphe contenant une clique de taille Ω(n/log^kn) 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³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)²/log³n). Même si le taux d'approximation de cet algorithme est faible, c'est le meilleur connu à ce jour. 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

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 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 ». Ce problème a également été mentionné dans l'article de Stephen Cook présentant la théorie des problèmes NP-complets. 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. 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.

Complexité de circuit

Un circuit monotone pour détecter une k-clique dans un graphe à n-sommets pour k = 3 et n = 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 k-clique.

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. Même si on autorise un petit nombre de portes non la complexité reste plus que polynomiale. 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.

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)}$. 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^kk²). 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) 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.

Chen et al. (2006) 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é.

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.

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 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 . 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.

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.

Références