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 Modèle:Mvar-clique est à la fois intraitable à paramètre fixé (il n'est pas dans la classe de problèmes FPT) et est Modèle:Lien. 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 Modèle:Citation 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 Modèle:Lien, 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 Modèle:Citation. 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 Modèle:Citation 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 cliqueModèle:Sfnp.

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 TimesModèle:Sfnp 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 cibleModèle:Sfnp et pour modéliser l'ancrage moléculaire et les sites de liaison des réactions chimiquesModèle:Sfnp. Ils peuvent également être utilisés pour trouver des structures similaires dans différentes moléculesModèle:Sfnp. 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éculesModèle:Sfnp. 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 produitModèle:Sfnp.

Dans la génération automatique de modèles de test, la recherche de cliques peut aider à limiter la taille d'un ensemble de testModèle:Sfnp. En bioinformatique, des algorithmes de recherche de clique ont été utilisés pour la génération d'arbres d'évolutions Modèle:Sfnp, la prédiction de structures protéiques Modèle:Sfnp, et pour trouver des groupes de protéines en interaction étroiteModèle:Sfnp. Lister les cliques d'un Modèle:Lien est une étape importante dans l'analyse de certains processus aléatoiresModèle:Sfnp. 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^[2].

Cliques maximales et cliques maximums

Soit Modèle:Math un graphe non orienté, avec Modèle:Mvar les sommets du graphe et Modèle:Mvar les arêtes. Une clique dans Modèle:Mvar est un sous-graphe Modèle:Math complet, ce qui signifie que tous les sommets dans Modèle:Mvar sont reliés entre eux. On distingue :

clique maximale : une clique de Modèle:Mvar à laquelle on ne peut rajouter aucun sommet de Modèle:Mvar, elle est maximale pour l'inclusion ;
clique maximum : une clique de Modèle:Mvar 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 maximaleModèle:Sfnp. 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 maximumModèle:Sfnp. 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 Modèle:Sfnp. 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 Modèle:Mvar que cette boucle examine, ajoutez Modèle:Mvar à la clique si Modèle:Mvar est adjacent à chaque sommet qui est déjà dans la clique, et rejetez Modèle:Mvar 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 Modèle:Sfnp.

Cliques de taille fixée

On peut tester si un graphe Modèle:Mvar 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 Modèle:Mvar 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 Modèle:Mvar doit être vérifiée. Ainsi, le problème peut être résolu en temps polynomial à condition que Modèle:Mvar soit une constante fixe. Cependant, lorsque Modèle:Mvar n'a pas de valeur fixe, et est une variable du problème, le temps est exponentielModèle:Sfnp.

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 Modèle:Mvar avec Modèle:Mvar arêtes, il peut y avoir au plus Modèle:Formule 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 Modèle:Mvar est lui-même une clique. Par conséquent, les algorithmes pour lister tous les triangles doivent prendre au moins Modèle:Formule temps dans le pire des cas (en utilisant la notation grand oméga), et des algorithmes sont connus qui correspondent à cette limite de tempsModèle:Sfnp. 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 Modèle:Mvar de la liste triée, à la recherche de triangles qui incluent Modèle:Mvar et n'incluent aucun sommet précédent dans le liste. Pour ce faire, l'algorithme marque tous les voisins de Modèle:Mvar, recherche à travers tous les arêtes incidentes à un voisin de Modèle:Mvar, produisant un triangle pour chaque arête qui a deux extrémités marquées, puis supprime les marques et supprime Modèle:Mvar du graphe. Comme le montrent les auteurs, le temps de cet algorithme est proportionnel à l'arboricité du graphe (notée Modèle:Formule ) multipliée par le nombre d'arêtes, qui est $O (m a (G))$ . L'arboricité étant au plus égale à $O (m^{\frac{1}{2}})$ , cet algorithme s'exécute au temps $O (m^{\frac{3}{2}})$ . Plus généralement, toutes les Modèle:Mvar -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 Modèle:Formule. 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^[3].

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 Modèle:Mvar -cliques pour des valeurs de Modèle:Mvar plus grandesModèle:Sfnp Modèle:,Modèle:Sfnp Modèle:,Modèle:Sfnp Modèle:,Modèle:Sfnp Modèle:,Modèle:Sfnp.

Lister toutes les cliques maximales

D'après un résultat de Moon & Moser (1965), chaque graphe de taille $n$ a au plus Modèle:Formule 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éesModèle:Sfnp. 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 alternativesModèle:Sfnp.

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 Modèle:Mvar de départ aux cliques maximales d'un graphe Modèle:Formule formé en supprimant un sommet arbitraire Modèle:Mvar de Modèle:Mvar :

Pour chaque clique maximale Modèle:Mvar de Modèle:Formule, soit Modèle:Mvar continue de former une clique maximale dans Modèle:Mvar, soit Modèle:Formule forme une clique maximale dans Modèle:Mvar. Par conséquent, Modèle:Mvar a au moins autant de cliques maximales que Modèle:Formule.
Chaque clique maximale dans Modèle:Mvar qui ne contient pas Modèle:Mvar est une clique maximale dans Modèle:Formule, et chaque clique maximale dans Modèle:Mvar qui contient Modèle:Mvar peut être formée à partir d'une clique maximale Modèle:Mvar dans Modèle:Formule en ajoutant Modèle:Mvar et en supprimant les non-voisins de Modèle:Mvar dans Modèle:Mvar.

En utilisant ces observations, on peut générer toutes les cliques maximales dans Modèle:Mvar par un algorithme récursif qui choisit Modèle:Mvar puis, pour chaque clique maximale Modèle:Mvar dans Modèle:Formule, produit à la fois Modèle:Mvar et la clique formée en ajoutant Modèle:Mvar à Modèle:Mvar et en supprimant les non-voisins de Modèle:Mvar. Cependant, certaines cliques de Modèle:Mvar peuvent être générées de cette manière à partir de plus d'une clique parente de Modèle:Formule, donc ils éliminent les doublons en conservant une clique dans Modèle:Mvar uniquement lorsque son parent dans Modèle:Formule est le maximum lexicographique parmi toutes les cliques parentes possibles. Sur la base de ce principe, ils montrent que toutes les cliques maximales dans Modèle:Mvar peuvent être générées en temps $O (m n)$ par clique, où Modèle:Mvar est le nombre d'arêtes dans Modèle:Mvar et Modèle:Mvar est le nombre de sommets. Chiba & Nishizeki (1985) l'améliorent à Modèle:Formule par clique, où Modèle:Mvar 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 Modèle:Lien bornée et les graphes planaires Modèle:Sfnp. 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^[3]Modèle:,^[4].

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.442 2^{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.259 9^{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.304 n}) = O (1.234 6^{n})$ , et Robson (1986) à $O (2^{0.276 n}) = O (1.210 8^{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 longueur du retour arrière. L'algorithme le plus rapide connu aujourd'hui est une version raffinée de cette méthode par Robson (2001) qui s'exécute dans le temps $O (2^{0.249 n}) = O (1.188 8^{n})$ Modèle:Sfnp.

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^[5], la recherche locale^[6], les algorithmes gloutons^[7], et la programmation par contraintes Modèle:Sfnp. 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 Modèle:Sfnp. Le problème de clique maximum a fait l'objet d'un défi de mise en œuvre parrainé par Modèle:Lien en 1992–1993Modèle:Sfnp, 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^[3]. En particulier, pour les graphes planaires, toute clique peut avoir au plus quatre sommets, selon le théorème de Kuratowski^[8].

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 Modèle:Sfnp. 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 parfaitsModèle:Sfnp. 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^[9]. Cet algorithme s'exécute en temps quadratiqueModèle:Sfnp. 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^[10].

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^[11]. 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 sommetsModèle:Sfnp.

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é Modèle:Formule, 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 (l o g^{2} (n))}$ . Il s'agit d'une limite temporelle quasi polynomiale Modèle:Sfnp. Bien que le nombre de cliques de ces graphes soit généralement très proche de Modèle:Formule, des algorithmes gloutons simples ainsi que des techniques d'approximation aléatoire plus sophistiquées ne trouvent que des cliques de taille Modèle:Formule, deux fois moins grandes. Le nombre de cliques maximales dans de tels graphes est avec une probabilité élevée exponentielle en Modèle:Formule, ce qui empêche les méthodes qui répertorient toutes les cliques maximales de s'exécuter en temps polynomialModèle:Sfnp. 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^[12]. Alors que les méthodes spectrales Modèle:Sfnp et la programmation semi-définie Modèle:Sfnp peuvent détecter les cliques cachées de taille $Ω (\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)Modèle:Sfnp.

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

Feige (2004) décrit un algorithme en temps polynomial qui trouve une clique de taille Modèle:Formule dans n'importe quel graphe contenant une clique de taille Modèle:Formule pour n'importe quelle constante $k$ . En utilisant cet algorithme quand la taille de la clique maximum est entre Modèle:Formule et Modèle:Formule, 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 Modèle:Formule. Même si le taux d'approximation de cet algorithme est faible, c'est le meilleur connu à ce jour^[14]. 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 Modèle:Citation. Modèle:Sfnp Ce problème a également été mentionné dans l'article de Stephen Cook présentant la théorie des problèmes NP-completsModèle:Sfnp. 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.

Modèle:Démonstration

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 Modèle:Mvar, significativement plus rapide qu'une recherche par force brute.Modèle:Sfnp 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. Modèle:Sfnp

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êtesModèle:Sfnp. Même si on autorise un petit nombre de portes non la complexité reste plus que polynomialeModèle:Sfnp. 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 cliqueModèle:Sfnp.

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 Modèle:Mvar et pour lesquels le problème devient plus difficile à mesure que Modèle:Mvar augmente, comme la recherche de Modèle:Mvar -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 Modèle:Mvar, et une fonction Modèle:Mvar, telle que l'algorithme s'exécute au temps $f (k) n^{O (1)}$ ^[15]. Autrement dit, il est traitable à paramètre fixé s'il peut être résolu en temps polynomial pour toute valeur fixe de Modèle:Mvar et de plus si l'exposant du polynôme ne dépend pas de Modèle:Mvar.

Pour trouver des Modèle:Mvar-cliques, l'algorithme de recherche par force brute a un temps d'exécution Modèle:Formule. Comme l'exposant de Modèle:Mvar dépend de Modèle:Mvar, 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 Modèle:Mvar. Ainsi, bien que le temps d'exécution des algorithmes connus pour le problème de clique soit polynomial pour tout Modèle:Mvar fixe, ces algorithmes ne suffisent pas pour la traitabilité à paramètre fixé. Downey & Fellows (1995)^[16] 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. Modèle:Sfnp

Chen et al. (2006)^[17] ont montré que trouver des k-cliques ne peut pas être fait en temps Modèle:Formule 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é.Modèle:Sfnp

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

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 1978Modèle:Sfnp 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 maximumModèle:Sfnp Modèle:,Modèle:Sfnp Modèle:Sfnp Modèle:,Modèle:Sfnp. Après de nombreuses améliorations, il est désormais connu que pour tout $ϵ > 0$ , il ne peut exister un algorithme en temps polynomial approximant la clique maximum avec un meilleur facteur qu'un $O (n^{1 - ϵ})$ à 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^[18].

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

Notes

Modèle:Références

Références