Problème de la clique - Wikiwand
For faster navigation, this Iframe is preloading the Wikiwand page for Problème de la clique.

Problème de la clique

Un article de Wikipédia, l'encyclopédie libre.

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.
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 est un problème algorithmique qui consiste à trouver une clique d'une certaine taille dans un graphe. Le problème de la clique maximale consiste à trouver la plus grande clique d'un graphe.

Énoncés

  • Le problème (de décision) de la clique prend en entrée un graphe G et un entier k et détermine si G contient une clique de taille k. Ce problème est NP-complet.
  • Le problème d'optimisation de la clique maximale consiste à exhiber, dans un graphe fini, l'une des cliques de taille maximale.
  • Par complémentarité, la recherche d'une clique dans un graphe revient aussi à rechercher un stable dans le graphe complémentaire.

Applications

Le problème de la clique se formule comme suit dans le contexte du monde réel. Dans un réseau social, où les sommets du graphe représentent des personnes, et les arêtes du graphe représentent une connaissance mutuelle, une clique représente un sous-ensemble de personnes qui se connaissent toutes, et des algorithmes pour trouver des cliques peuvent être utilisés pour découvrir ces groupes d'amis communs. En plus de ses applications dans les réseaux sociaux, le problème de la clique a aussi de nombreuses applications dans les domaines de la bio-informatique et de la chimie computationnelle.

La plupart des versions du problème de la clique sont dures. Le problème de décision de la clique est NP-complet (c'est l'un des 21 problèmes NP-complets de Karp). Le problème de trouver la clique maximale est à la fois de complexité paramétrée intraitable et difficile à approximer. Lister toutes les cliques maximales peut nécessiter un temps exponentiel car il existe des graphes avec un nombre exponentiel de cliques maximales. Par conséquent, une grande partie de la théorie sur le problème de la clique est consacrée à l'identification de familles particulières de graphes qui admettent des algorithmes plus efficaces, ou à établir la difficulté du calcul du problème général dans divers modèles de calcul.

Pour trouver une clique maximale, on peut systématiquement inspecter tous les sous-ensembles, mais ce type de recherche exhaustive est trop long pour être pratique pour des graphes comprenant plus de quelques dizaines de sommets. Bien qu'aucun algorithme en temps polynomial ne soit connu pour ce problème, des algorithmes plus efficaces que la recherche systématique sont connus. Par exemple, l'algorithme de Bron-Kerbosch (en) peut être utilisé pour lister toutes les cliques maximales en temps optimal dans le pire des cas, et il est également possible de les lister en temps polynomial par clique.

Démonstration de la NP-complétude

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

Algorithmes

Une méthode naïve de recherche de clique est la recherche exhaustive d'une k-clique à l'intérieur d'un graphe ; elle procède par examen de tous les sous-graphes de taille k et teste s'ils forment une clique. Toutefois, le nombre de sous-graphes de taille k dans un graphe à n sommets est grand, car il est égal à .

Un algorithme moins naïf consiste à former des cliques plus grandes par réunion de deux cliques jusqu'à ce qu'il n'y ait plus de réunion possible. On réunit deux cliques A et B quand tout sommet de la clique A est adjacent à chaque sommet de la clique B. On part des singletons ou cliques à 1 sommet. Cet algorithme a un coût linéaire (fonction linéaire du nombre de sommets du graphe), mais il peut ne pas trouver une clique de taille maximale parce que des sommets d'une telle clique ont pu être regroupés à une étape antérieure avec des sommets qui n'appartiennent pas à cette clique. Une mise en œuvre efficace s'appuie sur la structure de données « Union-Find ».

Certains cas particuliers peuvent être résolus à un coût sous-exponentiel. Pour k = 3, autrement dit pour la recherche de 3-cliques dans un graphe de taille n, il existe un algorithme de complexité O(n1.41)[1].

Histoire

Le problème de décision de la clique maximum fait partie des 21 problèmes NP-complets de Karp publiés en 1972 dans Reducibility Among Combinatorial Problems[2]. L'article précurseur de Cook[3] sur les problèmes NP-complets le mentionne aussi.

Notes et références

Bibliographie

{{bottomLinkPreText}} {{bottomLinkText}}
Problème de la clique
Listen to this article